Why is OCCURS-CHECK left out of Prolog? 
Author Message
 Why is OCCURS-CHECK left out of Prolog?

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,

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

Tue, 28 Jul 1992 10:10:21 GMT  
 Why is OCCURS-CHECK left out of Prolog?
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:

(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]) .

Wed, 29 Jul 1992 10:50:44 GMT  
 [ 2 post ] 

 Relevant Pages 

1. Is there a prolog with occurs check unification?

2. Unification with Occur-Check in Quintus-Prolog

3. Occurs Checking in Prolog

4. Why is OCCURS-CHECK left out of Prolog? (And request for a reference)

5. Prolog and occur checks.

6. Validity checking when no keyboard entry occurred

7. Occurs-check reduction: unification

8. occurs-check in SWI?

9. Q:Write my own occurs check?

10. static occurs check

11. Occur-check considered harmful?

12. Occurs check


Powered by phpBB® Forum Software