Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!usc!brutus.cs.uiuc.edu!apple!portal!portal!cup.portal.com!pgl
From: pgl@cup.portal.com (Peter G Ludemann)
Newsgroups: comp.lang.prolog
Subject: Re: Why is OCCURS-CHECK left out of Prolog?
Message-ID: <26775@cup.portal.com>
Date: 10 Feb 90 02:50:44 GMT
References: <9002081805.aa01763@PARIS.ICS.UCI.EDU>
Organization: The Portal System (TM)
Lines: 32

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