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.