Path: utzoo!attcan!uunet!mcsun!ukc!edcastle!lfcs!jha
From: jha@lfcs.ed.ac.uk (Jamie Andrews)
Newsgroups: comp.lang.prolog
Subject: Re: Why is OCCURS-CHECK left out of Prolog? (And request for a reference)
Message-ID: <2226@castle.ed.ac.uk>
Date: 12 Feb 90 12:07:24 GMT
References: <9002092357.AA04805@kronos.ads.com>
Reply-To: jha@lfcs.ed.ac.uk (Jamie Andrews)
Organization: Laboratory for the Foundations of Computer Science, Edinburgh U
Lines: 31

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.