🚀 go-pugleaf

Why is occurs check left out of Prolog?  Simple: the
fancy "linear time" unification algorithms are actually
slower than the non-occurs-check algorithm.

Some Prologs can handle "infinite trees", for example
Prolog-III and IBM-Prolog.  For the goal:
	?- X = f(X) .
they print out something like:
	X = f(@(1)) .
where the "@" indicates a pointer up the tree.
(Some other Prologs print out X = f(f(f(f(f( ...
and eventually get a stack overflow.)

IBM-Prolog provides an "is_inf" predicates which checks
which allows you to add the occurs check if you want.
(I think that Prolog-III has something similar.)

Is it useful?  That depends.  I've seen a program which
encodes a grammar in an infinite tree and then walks the
tree to do a parse (a meta-interpreter on a data structure,
instead of using clause/2).  The encoding is quite natural:

	?- Sentence = (NounPhrase , VerbPhrase) ,
	   NounPhrase = ( Noun |
			  Adj  | NounPhrase) ,
		...
	   Noun = ( man | woman | child | ...) ,
	   Adj  = ( big | small | ...) ,
		...
	   parse(Sentence, [the,big,man,saw,the,small,child]) .
		
- peter ludemann	pgl@cup.portal.com