🚀 go-pugleaf

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