🚀 go-pugleaf

Recently someone asked me a question about the capabilities of the
Quintus Prolog compiler.  There was a fairly obvious optimisation,
and he wondered whether the compiler did it or whether he would be
rewarded with a speedup if he rewrote the code himself.  My answer
was that the compiler *doesn't* do this optimisation.  I think it
may be of interest to this newsgroup to see what the question was
and why an incremental Prolog compiler *can't* do the optimisation.
I hope we'll get some discussion about what conditions *would*
permit the optimisation, and how a compiler can check them.

The original code was

	association(Stack, Key, Val, absent) :-
		is_empty(Stack),
		!.
	association(Stack, Key, Val, Result) :-
		pop_stack(Key1, Val1, Stack, Stack1),
		Key1 \== Key,
		!,
		association(Stack1, Key, Val, Result).
	association(Stack, Key, Val, present) :-
		pop_stack(Key1, Val1, Stack, Stack1),
		Key1 == Key,
		Val1 = Val,
		!.
	association(Stack, Key, Val, conflict).


The revised code was

	assocation(Stack, Key, Val, absent) :-
		is_empty(Stack),
		!.
	association(Stack, Key, Val, Result) :-
		pop_stack(Key1, Val1, Stack, Stack1),
		(   Key1 \== Key ->
		    association(Stack1, Key, Val, Result)
		;   Val1 = Val ->
		    Result = present
		;   Result = conflict
		).

The question was whether the Quintus Prolog compiler was smart enough
to perform this optimisation.  The answer is that it isn't.

Why not?

The answer is simple:  the two versions of the code are not equivalent.
Amongst other things, the query assocation(S,K,V,conflict) will always
succeed for the first version (the predicate is not steadfast).

Let's avoid questions of soundness by supposing that Stack, Key, and
Val are always ground, and that pop_stack/4 always returns ground
values for Key1, Val1, and Stack1, and let's avoiding questions of
steadfastness by supposing that association/4 is always called with
its last argument a variable.  Let's assume that is_empty is trivial:
	is_empty(empty).
The two versions *still* aren't equivalent.

Suppose pop_stack/4 is defined thus:
	pop_stack(K, V, stack(K,V,S), S) :-
		write('pop_stack/4 called'), nl.
and suppose that we call
	| ?- association(stack(a,1,empty), a, 2, Result).

Then the first version will print "pop_stack/4 called" twice, while the
second version will print it only once.

Suppose that the compiler has processed the definition of pop_stack/4
and knows that it is free of side effects.  [In the absence of call/1,
this is trivially easy to determine.]  The two versions *still* aren't
equivalent.

Suppose pop_stack/4 is defined thus:
	pop_stack(K, V, stack(K,V,S), S).
	pop_stack(K, V, stack(J,U,S1), stack(J,U,S2)) :-
		pop_stack(K, V, S1, S2).

Then the query
	| ?- association(stack(a,1,stack(a,2,empty)), a, 2, X).
will report X=present if the first version is called, but
will report X=conflict if the second version is called.

In this particular case, I think it suffices to know that pop_stack/4
is both side-effect-free and determinate.  In general, even that isn't
enough; the main predicate may still have the same solutions after
this optimisation, but they may not be found in the same order.  It
seems that we need a weaker notion of equivalence than is usual in
programming languges: in order to perform optimisations like this
automatically a compiler needs to be licensed to treat predicates
according to their declarative reading rather than according to the
strict behaviour of a Prolog interpreter.  (This is not unlike
allowing a Fortran compiler to pretend that X+Y+Z = Y+Z+X in
Fortran, it _isn't_ but it _ought_ to be (:-).)