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


=>
=>   ...  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



Wed, 29 Jul 1992 07:57:02 GMT  
 Why is OCCURS-CHECK left out of Prolog? (And request for a reference)

Quote:

>Linear time isn't good enough.

     Another problem is that the representation of terms needed
for the linear algorithms makes them need something like twice
as much memory.  If you have stack size problems already, then
you probably don't need this extra burden.  The occurs-check
problem doesn't come up frequently enough (for most people) to
warrant a correct interpreter!

Quote:
>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.)

     I'm not sure what you mean by "the relation between Prolog
and logic programming" -- it sounds like you think these are
separate concepts.  In any case, Prolog II is certainly logical:
it has a well-defined and axiomatizable underlying logic.  The
only difference is that the version of equality that it uses is
not the simple identity of most Prologs.  Colmerauer gives the
operational semantics of Prolog II in terms of tree rewrite
rules, but this is just a generalization of the usual
resolution-based operational semantics.

--Jamie.

Copyright (c) 1990 by Jamie Andrews;
for redistribution only on unmoderated USENET newsgroups.



Fri, 31 Jul 1992 20:07:24 GMT  
 
 [ 2 post ] 

 Relevant Pages 

1. Why is OCCURS-CHECK left out of Prolog?

2. Is there a prolog with occurs check unification?

3. Unification with Occur-Check in Quintus-Prolog

4. Occurs Checking in Prolog

5. Prolog and occur checks.

6. Validity checking when no keyboard entry occurred

7. Error 7 occurred at Open VI Reference with Application Builder

8. Occurs-check reduction: unification

9. occurs-check in SWI?

10. Q:Write my own occurs check?

11. static occurs check

12. Occur-check considered harmful?

 

 
Powered by phpBB® Forum Software