Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!csd4.milw.wisc.edu!lll-winken!uunet!ncrlnk!ncr-sd!hp-sdd!hplabs!hpfcdc!hpldola!patch
From: patch@hpldola.HP.COM (Pat Chkoreff)
Newsgroups: comp.lang.prolog
Subject: Higher Order Extensions
Message-ID: <11500013@hpldola.HP.COM>
Date: 12 Apr 89 01:58:59 GMT
Organization: HP Elec. Design Div. -ColoSpgs
Lines: 51

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?

They surely are not necessary for the purpose of computation, since pure
Prolog is equivalent to the most powerful known model of computation.  I
suspect that much of the so-called `need' for these extensions arises
when structured data is encoded as a relational structure _in the
program_, rather than as data structures passed as predicate arguments.

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.  If instead the stream were encoded as the data
structure ['3','+','7'], then it would be trivial to calculate its
length using pure Prolog.

This may explain why _The_Art_of_Prolog_ (section 17.2) suggests that
you `need' both extensions for the breadth-first search of possibly
cyclic graphs.  In their example, they encode the graph into the program
as the edge/2 relation.  If the graph were instead represented as a data
structure, then I maintain that the extensions would be unnecessary.

I am not claiming that these data structure problems are easy:  in fact,
I find it quite difficult to represent objects that have a complex,
cross-referenced structure.  I'm doing it anyway, using some techniques
that do NOT involve circular structures and rely heavily on the natural
numbers.  It works, but that doesn't imply that I know what the hell I'm
doing.

I would appreciate some good references and lively discussion on this
subject.  I haven't seen much in the five Prolog books that I own.


Regards,
Patrick Chkoreff            "AC:  It's not just an axiom; it's the LAW!"