baxter@zola.ICS.UCI.EDU (Ira Baxter) (02/09/90)
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
rar@KRONOS.ADS.COM (Bob Riemenschneider) (02/10/90)
=> From: baxter@zola.ICS.UCI.EDU (Ira Baxter)
=>
=> ... 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.)
-- rarpgl@cup.portal.com (Peter G Ludemann) (02/10/90)
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: X = f(@(1)) . where the "@" indicates a pointer up the tree. (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]) . - peter ludemann pgl@cup.portal.com
jha@lfcs.ed.ac.uk (Jamie Andrews) (02/12/90)
In article <9002092357.AA04805@kronos.ads.com> rar@KRONOS.ADS.COM (Bob Riemenschneider) writes: >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! >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. jha@lfcs.ed.ac.uk Copyright (c) 1990 by Jamie Andrews; for redistribution only on unmoderated USENET newsgroups.