Entries About Feed

Prolog Fundamentals Catchup

Three Things I Wish I’d Known

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.

Difference Lists

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.

Many of the built-in predicates that “return” lists also have variants that yield difference lists; for example, findall/3 and findall/4. Using difference lists is pretty straight-forward:

?- findall(X, between(1, 5, X), List, Tail0),
   writeln(List),
   Tail0 = [a, b, c|Tail1],
   write(List).
[1,2,3,4,5|_4456]
[1,2,3,4,5,a,b,c|_4572]

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).
[a,a,b,b,c,c]

Double-Negation

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. The ~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.

For example:

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).
[a-b,a-c,a-d,b-c,b-d,c-d]

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).
[_5262-_5264,_5250-_5252,_5238-_5240,_5226-_5228,_5214-_5216,_5202-_5204]

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 findall/3 to bagof/3:

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).
[a-b,a-c,a-d,b-c,b-d,c-d]

So this works, but why?

From the documentation on findall/3:

findall/3 is equivalent to bagof/3 with all free variables bound with the existential operator (^)

What does this mean?

In 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 pairs/2 above.

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 bagof.

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 findall?

The confusing bit is what are considered “free variables” in the body. The way 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 bagof/3.

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.