left_of exercise from The Art Of Prolog

Question

In the book we are asked to define the predicates left_of, right_of, above, and below using the following layout.

% bike               camera
% pencil  hourglass  butterfly  fish

left_of(pencil, hourglass).
left_of(hourglass, butterfly).
left_of(butterfly, fish).

above(bike, pencil).
above(camera, butterfly).

right_of(Obj1, Obj2) :-
    left_of(Obj2, Obj1).

below(Obj1, Obj2) :-
    above(Obj2, Obj1).

This seems to find correct solutions.

Later in the book we are asked to add a recursive rule for left_of. The only solution I could find is to use a different functor name: left_of2. So I've basically reimplemented the ancestor relationship.

left_of2(Obj1, Obj2) :-
    left_of(Obj1, Obj2).
left_of2(Obj1, Obj2) :-
    left_of(Obj1, X),
    left_of2(X, Obj2).

In my attempts to reuse left_of, I can get all the correct solution but on the final redo, a stack overflow occurs. I'm guessing that's because I don't have a correct base case defined. Can this be coded using left_of for facts and a recursive procedure?

Really? It seems to be working correctly to me. Might want to quit your Prolog session and load the code again just to make sure. — Daniel Lyons
Daniel, my question was can left_of be used for facts and a recursive rule (without having to use left_of2). I might be interpreting the book exercise wrong. — stirfoo
In that case the answer is no. There are lots of occasions with Prolog when you must have separate predicates where you wouldn't need them in other languages (loops with initialization or finalization steps come to mind as well). This is just one of them. You can always conceal the "internal" predicate with a different name (directly_left_of/2 comes to mind) and expose left_of2 as left_of for your users. — Daniel Lyons
@DanielLyons: if you post as an answer, I'll upvote it. It's the correct way to do this in Prolog. — Fred Foo

Daniel Lyons Daniel Lyons · Accepted Answer · 2013-05-01T20:28:52

As mentioned in the comments, it is an unfortunate fact that in Prolog you must have separately named predicates to do this. If you don't, you'll wind up with something that looks like this:

left_of(X,Z) :- left_of(X,Y), left_of(Y,Z).

which gives you unbounded recursion twice. There's nothing wrong in principle with facts and predicates sharing the same name--in fact, it's pretty common for a base case rule to look like a fact. It's just that handling a transitive closure situation like this results in stack overflows unless one of the two steps is finite, and there's no other way to ensure that in Prolog than by naming them separately.

This is far from the only case in Prolog where you are compelled to break work down into separate predicates. Other commonly-occurring cases include computational loops with initializers or finalizers.

Conventionally one would wind up naming the predicate differently from the fact. For instance, directly_left_of for the facts and left_of for the predicate. Using the module system or Logtalk you can easily hide the "direct" version and encourage your users to use the transitive version. You can also make the intention more explicit without disallowing it by using an uncomfortable name for the hidden one, like left_of_.

In other languages, a function is a more opaque, larger sort of abstraction and there are facilities for hiding considerable work behind one. Prolog's predicates, by comparison, are "simpler," which used to bother me. Nowadays I'm glad that they're simpler because there's enough other stuff going on that I'm glad I don't also have to figure out variable-arity predicates or keyword arguments (though you can easily simulate both with lists, if you need to).

left_of exercise from The Art Of Prolog

1 Answers