Path: utzoo!mnetor!uunet!mcvax!enea!ttds!draken!kth!sics!alf
From: alf@sics.se (Thomas Sj|land)
Newsgroups: comp.lang.prolog
Subject: Re: Destructive predicates (random musings - part-I).
Message-ID: <1797@sics.se>
Date: 9 Mar 88 15:51:43 GMT
References: <7289@agate.BERKELEY.EDU> <716@sandino.quintus.UUCP>
Reply-To: alf@sics.se (Thomas Sj|land)
Organization: Swedish Institute of Computer Science, Kista
Lines: 95
Keywords: Destructive predicates, LISP vs PROLOG Philosophy

Reacting against introducing more "non-logical" features into Prolog is
natural and justified. The very reason Prolog is something different than
backtracking LISP is just that a subset of the language can be given a
logical reading where program execution is construction of a proof using
some simple proof rules. 

When practical people turned to making this proof procedure into a usable
programming language, i.e. inventing Logic Programming, they quickly
discovered the need for some kind of control over the theorem prover, which
does not immediately destroy this nice feature. The logical reading of a
program also gives no clue to whether a predicate is used as producer or
consumer of a variable. This may vary with different queries, and seriously
affects the execution efficiency of a logic program.

'Setarg' is considered "non-logical" by most "logic programmers", since its
logical reading would be something like this: " replace any given assumption
you are currently using for this variable with this new one for the rest of
this branch, but use the old one when you explore the rest of the tree".
This informal understanding of the primitive has a clearly non-monotonous
character, and this is what is understood as "non-logical".

It might be argued that destructive assignment is needed for efficiency.
My intuition is that examples CAN be formulated that perform better with
'setarg' than any "pure" reformulation of the problem. It is also possible to
write assembly programs, which are more efficient than Prolog programs.
(This is perhaps a more sensible idea, if performance is the only purpose of 
the programming enterprise.)

The non-naive proponent of non-logic logic programming features goes ahead 
and tries to formulate a methodology or (better still) a compilation scheme
with which pure programs can be transformed to more efficient ones, which
perhaps use non-logical features. 

Such methods are already used by logic programmers.

Let me list some, which I come to think of:

- Bagof, Setof, Findall and all other more or less intuitive variants
- metaprogramming 
- Programming with difference structures like d-lists
- various uses of cut (red an green, if-then-else etc.)
- read-only annotations like wait, delay, dif, freeze


D-lists are normally (e.g. in grammar rules) considered a perfectly logical
extension, or rather, programming technique. Indeed, their use demand no 
particular control primitive to be introduced into the language, and using
them is therefore often considered to be totally harmless.
Some subtleties occur when you try to use them as ordinary lists in a program,
though. Try to define a predicate dlength/2 that determines the length of
a d-list and the predicate dappend/3 that appends two d-lists into a third one.
Try to use them together and you see what I mean: 
...dlength(D1,L1), dlength(D2,L2), dappend(D1,D2,D3)...

There is to our knowledge no way in which it is possible to formulate a 
predicate dlength/2 without using non-logical primitives like '==', that 
doesn't instantiate the lists, thereby destroying the possibility to use
the d-list in the same way as a normal list, in this example. 
This has its explanation in the fact that d-lists have no meaning as such
in the standard logic semantics, but are INTENSIONAL in nature, i.e. their
meaning is CODED into the program, not a part of the program semantics.
More bluntly put: A D-list is not an object in the Herbrand domain.

Using careful heuristics, which has been well investigated by the logic 
programming community programming with difference-structures is nevertheless
a very powerful technique and is part of the standard material of any Prolog
curriculum. 

What is perhaps needed is a methodology for the use of destructive assignment
in Prolog. I doubt, however, whether such an endeavour will be succesful, and 
it will probably yield very rigourous demands on how programs must be written
in order to preserve some form of "logical" reading.

It all boils down to the standard problems with the semantics of assignment:
How should it be understood as anything else than an operational description
of what the system does with its internal structures on a given place in the
execution, i.e. be given a "logical" or "declarative" meaning ?

PS. Note that setarg can be fully defined using primitives already in the
    language, namely 'var'/1 and '!'/0. The version of setarg which keeps
    the value assigned also when backtracking (sometimes called $setarg)
    seems to demand something else, however. There is a project at our lab 
    concerning a theorem prover implemented in SICStus Prolog, which except
    from lots of cuts, vars and '=='s seems to need also $setarg to reach
    efficient implementation. For such an implementation, with non-naive
    programmers to do the job, the designers/implementors see no problems
    generated by using non-logic features.
DS.


Thomas Sj|land
Logic Programming Systems Laboratory
SICS, PO Box 1263, S-164 28 KISTA, SWEDEN
Tel: +46 8 752 15 42	Ttx: 812 61 54 SICS S	Fax: +46 8 751 72 30
Internet: alf@sics.se or {mcvax,munnari,ukc,unido}!enea!sics.se!alf