[comp.lang.prolog] Copying

gerdeman@clio.las.uiuc.edu (10/19/88)

Sterling and Shapiro give the following procedure for copying:

copy(X,Y):- assert('$foo'(X)),retract('$foo'(Y)).

I have found the following to be much faster:

copy(X,Y):- findall(Z, Z = X,[Y]).

This only works with findall not setof or bagof. Can anyone
explain why this works? In general, I have discovered, destructive
variable bindings embedded within findall have no global effect.
Again this is not the case with setof and bagof. Very peculiar
isn't it?
                          --- Dale Gerdemann

ok@quintus.uucp (Richard A. O'Keefe) (10/20/88)

In article <16400001@clio> gerdeman@clio.las.uiuc.edu writes:

>Sterling and Shapiro give the following procedure for copying:
>copy(X,Y):- assert('$foo'(X)),retract('$foo'(Y)).

There are two problems with that:  retract/1 is prepared to backtrack.
In DEC-10 Prolog and C Prolog, a choice-point will be left behind even
if there is just the one clause for $foo.  That's not a mistake, that's
the way it _has_ to work.  Quintus Prolog 2.0 and later use a slightly
different definition of assert and retract ("a running predicate does
not notice any changes to its clauses") which means that a choice
point will not be left behind in this case.  With other Prolog systems,
check the manual (and use whatever resource measurement tools are offered
to find out what is really happening).  But that's not the only problem.

	| ?- copy(a, b).

fails, leaving the clause '$foo'(a) in the data base.  The next call,
	| ?- copy(c, X).
will pick up that clause, binding X = a, and leave '$foo'(c) in the
data base.  And so it goes...

If you're going to do this, you have to write

	copy_term(Original, Copy) :-
		asserta('$foo'(Original)),
		retract('$foo'(Working)),
		!,
		Copy = Working.

(And people wonder why I recommend _not_ changing the data base unless
you absolutely have to.)

>I have found the following to be much faster:

>copy(X,Y):- findall(Z, Z = X,[Y]).

>This only works with findall not setof or bagof. Can anyone
>explain why this works?

It works because findall(Template, Generator, List) does

	mark a stack
	(   call(Generator)
	    make a copy of the current instance of Template
	    and push it on the stack
	    fail
	;   true
	),
	Answer := []
	while there is something above the mark do
	    Answer := [pop the top copy off the stack | Answer]
	pop the mark
	List = Answer

An even simpler form of the call which will accomplish this effect is

	copy_term(Original, Copy) :-
		findall(Original, true, [Copy]).

This may be faster than the assert+retract versions in some systems, or it
may be slower.  (The implementation shown in Clocksin & Mellish, for
example, would solve this query by performing TWO asserts and TWO
retracts, so it would be slower than the Sterling & Shapiro suggestion.)

If your Prolog system hasn't got findall/3 (it is a library predicate
in DEC-10 Prolog and Quintus Prolog, for example, not built in), you can do

	copy_term(Original, Copy) :-
		bagof(Original, true, [Copy]).

Or in Quintus Prolog you could call the built-in predicate copy_term/2.

>In general, I have discovered, destructive
>variable bindings embedded within findall have no global effect.
>Again this is not the case with setof and bagof. Very peculiar
>isn't it?

(a) What's a "destructive variable binding"?
(b) If you mean that setof/3 and bagof/3 enumerate bindings for the
    free variables (the variables in the Generator which are not
    explicitly quantified and do not appear in the Template) and that
    findall/3 doesn't, that hardly counts as peculiar.  That's what
    they are FOR.