Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!samsung!uakari.primate.wisc.edu!ames!zodiac!KRONOS.ADS.COM!rar
From: rar@KRONOS.ADS.COM (Bob Riemenschneider)
Newsgroups: comp.lang.prolog
Subject: Why is OCCURS-CHECK left out of Prolog? (And request for a reference)
Message-ID: <9002092357.AA04805@kronos.ads.com>
Date: 9 Feb 90 23:57:02 GMT
Sender: daemon@zodiac.ADS.COM
Lines: 45

=>   From: baxter@zola.ICS.UCI.EDU (Ira Baxter)
=>
=>   ...  First question: why doesn't Prolog produce the wrong
=>   answer (or loop indefinitely) sometimes?  If it does produce the wrong
=>   answer, what do real Prolog programmers do to circumvent it?

Most Prologs produce the wrong answer ("yes") to the query

                             :- query.

given the program

                          query :- p(X,X).
                             p(X, f(X)).

and go into an infinite loop given the program

                          query :- p(X,X).
                        p(X, f(X)) :- p(X,X).

As for what real programmers do about it, they try not to write programs
that give wrong answers or go into infinite loops due to the missing
occurs-check.

=>   Second question: ... why isn't a linear time algorithm used?

Linear time isn't good enough.  (In fact, I seem to remember an argument that
omitting the occurs-check actually improves Prolog's design, because,
generally speaking, primitive operation in programming languages should
all be O(1) to make intuitive performance estimation easier.  Can't 
recall where.  Anyone out there have any ideas?)

If you're really worried about the lack of an occurs-check, analysis that
adds one when possibly needed is cheaper than the additional overhead of 
having one all the time.  (See Plaisted's article in the _Proceedings of 
the 1984 International Symposium on Logic Programming_.)

An alternative is to change the semantics of Prolog so that the circular
bindings represent legal infinite terms, effectively making the wrong
answers right by changing the definition of "right".  (Actually, this 
move works better if you forget about the relation between Prolog and
logic programming, and think of Prolog clauses as tree rewrite rules,
a la Prolog II.)

							-- rar