As a consequence of the fact that I got in to Prolog not through what seems like the more typical academic route, but via Anne Ogborne’s great tutorial on using Prolog for web applications, I think I missed out on some of the fundamentals of the language. At this point I’ve written enough code in Prolog that I’m pretty comfortable with the basic syntax & semantics, but there are a few bits that took me a bit longer to actually understand.
If you’re like me & don’t have a background in the more theoretical aspects of Prolog but have just jumped in to using it to make things, or if you’re just getting started with the language, perhaps you’ll find this useful.
The first Prolog idiom that was kind of bewildering to me is the “difference list”. It’s a pretty interesting data structure that is unique to this sort of logic language.
The basic idea is that it’s a list where the tail of the list is an unbound variable. Why would you want this? The main use that I’ve had for them is having a list you can build from the end, instead of having to “cons” on to them from the front and then reverse at the end.
?- findall(X, between(1, 5, X), List, Tail0), writeln(List), Tail0 = [a, b, c|Tail1], write(List).
Since we have access to the tail of
List, we can actually append on to the end without having to use
append/3 or doing a double-reverse.
I was okay with this, but the thing that kind of puzzled me was how to create a new difference list? This was a little mind-bending, but I eventually figured out that an empty difference list is the same variable as both the list and the tail. For example:
double_list(, _DoubleList, ). double_list([X|Xs], DoubleList, DoubleTail0) :- DoubleTail0 = [X, X|DoubleTail1], double_list(Xs, DoubleList, DoubleTail1). ?- double_list([a, b, c], L, L), write(L).
This is something that I only realized thanks to a throw-away line in the documentation for forall/2:
The predicate forall/2 is implemented as \+ ( Cond, \+ Action), … The use of double negation implies that forall/2 does not change any variable bindings.
I don’t find much use for negation (
\+) in Prolog; it seems kind of awkward to me and I don’t think it plays well with declarative logic.
However, there’s a useful trick here: Because the negation implies backing out of whatever the negated goal was after it’s been proved, we can use double-negation to temporarily bind a variable without it affecting anything else.
In particular, I’ve found it useful when building up a difference list of character codes & wanting to print out what the values are part-way through.
~s format specifier prints out a list of character codes as a string, but it requires a “proper” list – i.e. one whose tail is a list, not a variable.
However, if one is accumulating a difference list, binding the tail to a list will mean that you can’t keep accumulating.
Using the double-negation lets you bind the tail to a proper list, print it, then undoing the variable bindings.
double_list(, _DoubleList, ). double_list([X|Xs], DoubleList, DoubleTail0) :- DoubleTail0 = [X, X|DoubleTail1], \+ \+ ( DoubleTail1 = , % without this, we'd get an error % when trying to pass the difference list to ~s format("DoubleList = ~s~n", [DoubleList]) ), % ...but here DoubleTail1 is still unbound format("DoubleTail1 = ~w~n", [DoubleTail1]), double_list(Xs, DoubleList, DoubleTail1). ?- double_list([0'a, 0'b, 0'c], L, L), write(L).
DoubleList = aa DoubleTail1 = _4726 DoubleList = aabb DoubleTail1 = _4754 DoubleList = aabbcc DoubleTail1 = _4782 [97,97,98,98,99,99]
Existentially Qualified Variables
This last one is the thing that took me the longest to get my head around.
It’s related to what I mentioned in a previous post, when trying to do things with unbound variables with
findall/3 and related predicates.
As discussed in the post, the problem can be seen with the below predicate, to generate all pairs of the elements of a list:
pairs(Xs, Pairs) :- findall(X-Y, (select(X, Xs, Other), member(Y, Other), % add an ordering constraint to avoid generating % both A-B and B-A X @< Y), Pairs).
This seems to work when the values in the list are ground values:
?- pairs([a, b, c, d], Pairs), write(Pairs).
However, if the values are variables, then this doesn’t work properly:
% This *should* give the same output as the above ?- pairs([A, B, C, D], Pairs), A = a, B = b, C = c, D = d, write(Pairs).
As I mentioned previously, I had an idea that this had something to do with qualifying unbound variables, so kind of guessing, I changed from
pairs(Xs, Pairs) :- bagof(X-Y, Other^(select(X, Xs, Other), member(Y, Other), X @< Y), Pairs).
This now works:
?- pairs([A, B, C, D], Pairs), A = a, B = b, C = c, D = d, write(Pairs).
So this works, but why?
From the documentation on
findall/3 is equivalent to bagof/3 with all free variables bound with the existential operator (^)
What does this mean?
bagof/3, variables in the goal that aren’t in the template are “shared” between all instantiations of the body.
If we want a variable in the goal to be “local” to each run through, it must be marked with the “existential operator”, as
Other is in the
bagof definition of
To hopefully clarify, let’s see what happens without the existential operator:
?- Xs = [a,b,c,d], bagof(X-Y, ( select(X, Xs, Other), member(Y, Other), X @< Y ), Pairs), format("Other = ~w, Pairs = ~w~n", [Other, Pairs]), fail. % loop over possible solutions
Other = [a,b,d], Pairs = [c-d] Other = [a,c,d], Pairs = [b-c,b-d] Other = [b,c,d], Pairs = [a-b,a-c,a-d]
What’s happening here is that on the first pass through the body,
Other is being bound, but then on subsequent times through, it’s trying to make the value of
Other stay the same.
This results in multiple solutions to the
When we define
pairs/2 with the existential qualification, then
Other is “fresh” each time through, so we just get our one solution of all the pairs.
What the quote from the
findall/3 documentation above means then is that it will automatically add the qualification for all the variables in the body that aren’t in template, which at first appears to be what we want here.
Looking at the code, it appears that
Other is the only variable in the body that’s not in the template and we want it existentially qualified, so why not using
The confusing bit is what are considered “free variables” in the body.
findall works is that it will qualify any variables that appear in the body dynamically, not lexically:
Even though it appears that
Other is the only variable in the body, if
Xs contains variables, then those too will be qualified!
This then means that all the variables in the list, since they aren’t in the template, are “fresh” for each time through the body, which destroys the relations we were trying to establish.
The takeaway from this is that if you’re doing anything involving passing variables around, you probably don’t want to use
findall/3 and instead use
It also seems to me that it would make more sense for
findall/3’s variable qualification to happen lexically, but I suppose that would be a pretty big breaking change.