Wednesday, July 29, 2015

Avoiding left recursion

A reminder of why I had (and still have) some qualms about Prolog, elegant though it is. We're told that Prolog programs are to be read declaratively, as specifications - don't think about the execution model! So pretty much my first SWI-Prolog program is this simple statement of likes below. To make it more interesting, I (counterfactually) state that 'likes' is transitive. So this is the program you get.

Program (wrong)

likes(puss-puss, voles).
likes(adrian, football).
likes(adrian, puss-puss).
likes(alex, jokes).
likes(alex, adrian).

likes(X, Z) :- likes(X, Y), likes(Y, Z).   %  transitivity of 'likes'

And this is what you see when you run the program with the query likes(alex,Y) where the intention is to list all the things Alex likes.


?- likes(alex, X).
X = jokes ;
X = adrian ;
ERROR: Out of local stack

What has happened is that the two facts:

likes(alex, jokes).
likes(alex, adrian).

were matched, then the 'transitivity' clause was invoked, which unfortunately matched itself repeatedly in an infinite loop, until the interpreter ran out of stack space. No problem with the program declaratively, but operationally it loops.

Here's the correct program with the results.

Program (correct)

likes1(puss-puss, voles).
likes1(adrian, football).
likes1(adrian, puss-puss).
likes1(alex, jokes).
likes1(alex, adrian).

likes(X,Y) :- likes1(X,Y).
likes(X, Z) :- likes1(X, Y), likes(Y, Z).   % to stop left recursion, likes1 is first.

Result when executed

?- likes(alex,X).
X = jokes ;
X = adrian ;
X = football ;
X = puss-puss ;
X = voles ;

Even this simple program has a small capacity to surprise: how did it figure out that Alex likes voles?


Note: this post is executable by pasting into your favourite interpreter such as here (click on 'create a new program' once you closed the annoying 'Limited Edition!' window).

When copying from here don't forget the top slash-asterisk and the bottom asterisk-slash sign below, plus the full stop after the query likes(alex, X). For extra credit, try likes(Y, voles).  to illustrate Prolog running backwards.