[net.lang.prolog] eliminating duplicate solutions in Prolog

debray@sbcs.UUCP (Saumya Debray) (05/26/86)

There have been a number of responses in this group, saying basically that
duplicate solutions generated by a Prolog interpreter can be eliminated,
since Prolog is doing logic programming.  I'd like to put forth a
dissenting opinion (even if it means being burnt at the stake :-)

The problem is that even if we believe that "pure" Prolog somehow
approximates the nondeterministic behaviour of an ideal logic program
interpreter, *in reality* we *cannot* have such pure systems.  "Real"
Prolog does not, in general, do logic programming.

I'm not thinking of cuts (which can, in most cases, be done away with,
given sufficiently smart implementations) or assert/retract (which good
programmers don't seem to use too often): I'm thinking of the rather
mundane fact that any "real" system, to be useful, must interact with the
outside world, and hence necessarily have side effects like "read"
and "write".  So for the predicate

	p([]) :- write('success 1').
	p(X)  :- read(X).

the query :- p([]) should, in fact, succeed twice.  I notice that CProlog
v1.5 doesn't, and I see that as a bug.

In general, duplicate solutions for a predicate cannot be eliminated
unless it can be proved that the search tree for that predicate is free of
side effects.  This shouldn't be too hard (assuming we don't have goals like
"call(X)", in which case some heavy-duty flow analysis would be necessary),
but it's something to be aware of.

-- 
Saumya Debray
SUNY at Stony Brook

	uucp: {allegra, philabs, ogcvax} !sbcs!debray
	arpa: debray%suny-sb.csnet@csnet-relay.arpa
	CSNet: debray@sbcs.csnet

lhe@sicsten.UUCP (Lars-Henrik Eriksson) (05/31/86)

In article <126@sbcs.UUCP> debray@sbcs.UUCP writes:
>.... I'm thinking of the rather
>mundane fact that any "real" system, to be useful, must interact with the
>outside world, and hence necessarily have side effects like "read"
>and "write".  .....

I/o must do side effects, of course, but it is quite possible to hide this
from a logic program, so that it appears to be in a completely "logical"
environment.

Example: Input could be done in a logical fashion by having a special kind of
list with elements corresponding to successive objects read from the outside
world. That is, the list would initially be an uninstantiated variable.
Attempts to use the variable would cause an object to be read in and the
variable would be bound to a pair of the first element and another 
uninstantiated variable. Attempts to use the rest of the list would cause
the process to be repeated.

That is, to the program, the list would look like it had everything read in
on it from the start, but actually things would be read in only as they
were needed. 

Of course, special precautions would have to be taken to make sure this
worked when the program backtracked, but it is quite possible. (In fact, I
have implemented input working in this way).

Output could be done in a similar way, with objects being output as a list
was bound.

In both cases the program would think it was processing or creating a list,
while it was actually reading or writing.