Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!linus!philabs!sbcs!debray
From: debray@sbcs.UUCP (Saumya Debray)
Newsgroups: net.lang.prolog
Subject: eliminating duplicate solutions in Prolog
Message-ID: <126@sbcs.UUCP>
Date: Mon, 26-May-86 11:50:40 EDT
Article-I.D.: sbcs.126
Posted: Mon May 26 11:50:40 1986
Date-Received: Wed, 28-May-86 00:13:54 EDT
Distribution: net
Organization: Computer Science Dept, SUNY@Stony Brook
Lines: 36

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