Subject: Re: [SWIPL] Getting Started with SWI

From: "Richard A. O'Keefe" <[email-masked]>
Date: Tue, 18 Sep 2001 12:19:26 +1200 (NZST)

?- [user].
	|: friends(X,Z):-
	|: friends(X,Y),
	|: friends(Y,Z).
	|: friends("steve","alicja").
	|: friends("alicja","tim").
	^D
	%user compiled 0.00 sec, 676 bytes
	
Point 1.  Why use strings (lists of characters) when you can use atoms?
Point 2.  The layout of the first clause makes it hard to read.

Rewrite:

    friends(X, Z) :-
	friends(X, Y),
	friends(Y, Z).
    friends(steve, alicja).
    friends(alicja, tim).

	?- friends("steve","alicja").
	ERROR: Out of local stack
	Exception: (31,742) friends([115, 116, 101, 118, 101], _G404) ?
	
	Did I step on some kind of known problem?
	
No, you wrote a program containing an infinite recursive loop.
When you ask

    ?- friends(steve, alicja).
the first clause MUST be the first to be tried; the instance that will
be used is
    friends(steve, alicja) :- friends(steve, Y), friends(Y, alicja).
So now we have the resolvent
    ?- friends(steve, Y), friends(Y, alicja).
Again, the first clause MUST be the first to be tried; the new
resolvent will be
    ?- friends(steve, Y2), friends(Y2, Y1), friends(Y1, alicjca).
and so it goes.

In grammars, this is called "left recursion".

Deductive databases such as Aditi can handle this by using a variety
of twisty control strategies.  For Prolog, with its simple (simplistic?)
control strategy (try clauses in the order written; process subgoals in
the order written), you will have to rewrite.

Perhaps the simplest way is

    friends(X, Y) :-
        friends_fact(X, Z),
        (   Y = Z
        ;   friends(Z, Y)
	).

    friends_fact(steve, alicja).
    friends_fact(alicja, tim).

Once I had loaded these three clauses into SWI Prolog, this worked:
    ?- friends(X, Y).

    X = steve
    Y = alicja ;

    X = steve
    Y = tim ;

    X = alicja
    Y = tim ;

    No

The "transitive closure" problem is discussed in most Prolog textbooks.