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

 Page 1 of 1 [ 2 post ]

Relevant Pages