Path: utzoo!utgpu!jarvis.csri.toronto.edu!clyde.concordia.ca!mcgill-vision!bloom-beacon!mintaka!yale!think!samsung!brutus.cs.uiuc.edu!jarthur!uci-ics!gateway
From: baxter@zola.ICS.UCI.EDU (Ira Baxter)
Newsgroups: comp.lang.prolog
Subject: Why is OCCURS-CHECK left out of Prolog?
Message-ID: <9002081805.aa01763@PARIS.ICS.UCI.EDU>
Date: 9 Feb 90 02:10:21 GMT
Lines: 26


Excuse my ignorance... I am not much of a Prolog-ite.

If I understand it right, an OCCURS-CHECK is intended to prevent
the attempt to unify a variable with a tree containing that same variable
(i.e. claiming that  ?x unifies with G(...,?x,...) ).

Rumor has it that most Prologs don't do occurs-checks because they are
"expensive".  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?

Second question: Apparantly doing linear time (and space) unification
has been known since 1976 (Paterson&Wegman, Journal of Computer and
System Sciences, "Linear Unification").  ... so why isn't a linear
time algorithm used, avoiding the purported cost, thus getting rid of
any diseases related to absence of OCCURS-CHECK ?  Or is the constant
factor just plain too big?

Please reply directly to me; I don't read the Prolog newsgroup much.

Befuddledly yours,


IDB
(714) 856-6693  ICS Dept/ UC Irvine, Irvine CA 92717