Path: utzoo!mnetor!uunet!mcvax!enea!ttds!draken!kth!sics!seif
From: seif@sics.se (Seif Haridi)
Newsgroups: comp.lang.prolog
Subject: Re: theorem prover of R. Overbeek (Destructive list predicates)
Message-ID: <1798@sics.se>
Date: 9 Mar 88 16:05:41 GMT
References: <710@cresswell.quintus.UUCP> <1048@hubcap.UUCP>
Reply-To: seif@sics.se (Seif Haridi)
Organization: Swedish Institute of Computer Science, Kista
Lines: 67


Regarding destructive assignment in Prolog, here is our experience at SICS
with this feature. SICStus Prolog (version 0.6 will be announced soon
for external use) has a backtrackable assignment called setarg/3:
	setarg(+ArgNo,+CompoundTerm,?NewArg)
which replaces destructively argument ArgNo in CompoundTerm with NewArg and
the assignment is undone on backtracking. There is also a lower level
nonbacktrackable assignment not available for the users.

We had this feature for a while to evaluate its need. My current view is
that setarg/3 is not needed as is but it has been used to implement in SICStus
Prolog other features that are important for efficiency.

1. setarg/3 has been used to implement a number of predicates for manipulating
logical arrays with constant access time for the latest array reference.

2. Also it has been used for implementing logical hash tables (with the
possibility of removing items from the hash table).

These features are needed in a project on natural language processing at SICS
where a grammar dictionary is created from reading an analysing a text in
natural language.  The features above can of course be used on other Prolog
conventional applications.

3. Another primitive that is now existing in SICStus 0.6 is an :
	if(+P,+Q,+R) which is: if P then Q else R
this is similar to (P -> Q ; R) construct except that it allows the
generation of all possible solutions for P. This construct was needed on
a work going on a complete theorem prover being built at SICS for
intuitionistic first order logic. This control primitive was implemented
efficiently first after using the lower primitive nonbacktrackable
destructive assignment.

Another area where we thought first that assignment is important is the
area of object oriented programming as in SmallTalk (mutable objects)
specially for the important class of discrete event simulation applications.
The way out was to do object oriented programming in SICStus in a way
that is similar to committed choice languages (CCLs). That is to introduce
a data-driven control element in the language above the normal goal driven
mechanism. This is done by introducing wait declarations in the language and
device a reasonably efficient suspension mechanism. This leads to a language
with the added expressive power of CCLs on sequential machines but it also
allows backtracking over streams.
A problem arose here is how to create multiple reference to a shared object.
This is done as in CCLs by creating a tree of binary merge operators to
the shared object. This can be done and isolated in a single predicate
called merge/2 for doing the so called multiway merge.
A problem here is that sending a message to a shared object would not take
a constant time. The message has to pass through a number of merge operators.
This is not acceptable in all known object oriented languages.

4. The multiway merge/2 is again implemented by  setarg/3 reduces the
message sending delay to constant time (see Shapiro).

5. Another object in the style CCLs that is useful in is an array object that
can be implemented using setarg/3.

The above two features had a considerable effect on the speed of a number
of discrete event simulation programs that we wrote.

In summary my current point of view is that the use of setarg/3 can be
isolated and hidden in a number of predicates that still can be implemented in
a Prolog system ( in case of object oriented feature you need a data driven
control element). The use of setarg is then to increase efficiency without
changing the semantics of your program

	Seif Haridi