Path: utzoo!attcan!uunet!mcvax!ukc!icdoc!cdsm
From: cdsm@doc.ic.ac.uk (Chris Moss)
Newsgroups: comp.lang.prolog
Subject: Re: Higher Order Extensions
Message-ID: <783@gould.doc.ic.ac.uk>
Date: 26 Apr 89 10:00:27 GMT
References: <11500013@hpldola.HP.COM>
Reply-To: cdsm@doc.ic.ac.uk (Chris Moss)
Organization: Dept. of Computing, Imperial College, London, UK.
Lines: 50

In article <11500013@hpldola.HP.COM> patch@hpldola.HP.COM (Pat Chkoreff) writes:
>There are certain extensions to pure Prolog which are commonly regarded
>as necessary for `real world' programming, namely:
>
>    o  set expressions (findall, etc.)
>    o  negation as failure
>
>Are these extensions really necessary, and why?
>
The standard reference for this is:
  D.H.D. Warren: Higher order extensions to Prolog: are they needed?
   Machine Intelligence 10, 1982, pp441-454. (This is a book to all intents
   and purposes).

2 points: 
  1. The predicate to find the set of all solutions can easily be written 
in pure Prolog with negation. (It's the list of which there are no
other solutions). The only problem is that it is O(N^2). 
"setof" (defined in Warren's paper) also needs metalogical predicates such
as var, though these _can_ be defined in Prolog with cut.
  2. findall cannot be defined in Prolog without assert/retract or equivalent
as far as I know (I've never seen a proof). The problem here is precisely
showing that there are multiple solutions.

>They surely are not necessary for the purpose of computation, since pure
>Prolog is equivalent to the most powerful known model of computation. 

Negation is needed if you want to program strictly at "first-order" level.
Ok if you raise everything up to the term level you can do everything
(e.g. write Turing machine programs).

>For example, a stream of symbols ['3','+','7'] may be encoded as a
>relational structure as follows:
>
>    % input(P,S,Ps).
>    %
>    % The symbol at position P >= 0 in the input stream is S, and Ps is
>    % the successor of P.
>
>    input(0,'3',1).
>    input(1,'+',2).
>    input(2,'7',3).
>
>However, if the stream is encoded this way, it is impossible in pure
>Prolog to calculate the `length' of the stream. You would need at least
>one of the extensions.  

Yes, negation is sufficient, using the trick above.

Chris Moss.