🚀 go-pugleaf

In article <SWK.92Aug10220513@seymour.mlb.semi.harris.com> swk@seymour.mlb.semi.harris.com (Song W. Koh) writes:
>[...]  I am having trouble describing transitive and
>symetric relations without stack overflows.  Things like:
>
>distance(X,Y,D) :- distance(Y,X,D).
>
>and
>
>distance(X,Z,D) :- distance(X,Y,D1), distance(Y,Z,D2), D is D1 + D2.
>
As some other posters have noted, if you see Prolog as a *programming
language* with a particular operational semantics, the looping is
not surprising. Compare for instance the C function

int distance(x, y)
Point *x, *y;
{
   return distance(y, x);
}

It will surely loop and very possibly run out of stack (unless the
C compiler is clever enough do do some sort of last-call optimization).

Problems of the kind you describe, which involve computing closures of
relations, are best processed with a bottom-up or memoizing execution method
rather than the top-down execution method built into Prolog. These
methods avoid looping by goals already attempted and conclusions already
reached to avoid retrying them. These methods can be simulated in Prolog by
using assert judiciously. My book

@book(Pereira+Shieber:Prolog,
	Author={Fernando C. N. Pereira and Stuart M. Shieber},
	Key={Pereira and Shieber},
	Title={Prolog and Natural-Language Analysis},
	Publisher={Center for the Study of Language and Information},
	Number={10},
	Address={Stanford, California},
	Series={CSLI Lecture Notes},
	Year={1985},
	Note={Distributed by Chicago University Press}
)

discusses some of those methods, althout it might be nice to have
a tutorial introduction to them in a more general stetting (Is there
one?)

Alternatively, for particular relations you can keep track of points/nodes
already visited with an extra argument in the relevant predicates of
your program (some other posting also referred to this technique).

Fernando Pereira
2D-447, AT&T Bell Laboratories
600 Mountain Ave, PO Box 636
Murray Hill, NJ 07974-0636
pereira@research.att.com