🚀 go-pugleaf

The two programs presented in the original "clause fusion" posting
are different and it does not make much sense to talk about one being
the optimisation of the other.  I propose to consider the revised
and optimized version of the program as the one for study:

	%  Optimised program.

        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 program suffers from clause fusion.  Given a personal
interpretation of the program's intended purpose I would
write it down like this (note that I'm not too fuzzy about
the groundedness of variables):

	%  Human-readable program.

	association( Stack,Key,Val,absent ) :-
		is_empty( Stack ), !.
	association( Stack,Key,Val,Result ) :-
		pop_stack( Key1,Val1,Stack,Stack1 ),
		assoc_test( Key,Key1,Val,Val1,Stack1,Result ).

	assoc_test( Key,Key,Val,Val,_,present ) :- !.
	assoc_test( Key,Key,_,_,_,conflict ) :- !.
	assoc_test( Key,_,Val,_,Stack,Result ) :-
		association( Stack,Key,Val,Result ).

If my interpretation of when the program should say "present" or
"conflict" is incorrect then the author can rewrite the clauses for
assoc_test/6 as necessary.

[[ If you feel that the "human-readable" version is not human-readable
   at all, or that the "optimized" version is more human-readable, then
   by all means flame. ]]

If we agree that these two programs are functionally equivalent,
we can ask two questions:

	a) Is the human-readable program really slower than
	   the optimized one?

	b) Given that the optimized program is faster, can
	   a Prolog compiler generate the optimized program
	   from the human-readable program?

I benchmarked both versions with Quintus Prolog, C-Prolog 1.5 and a
custom WAM based Prolog compiler.  The benchmarks were performed with
the following definitions (from original posting):

	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 ).

	is_empty(empty).

And the following goal:

	loop( 0 ).
	loop( N ) :-
		association( stack(a,1,stack(a,2,empty)),a,2,X ),
		NewN is N-1,
		loop( NewN ).

These are the results for: loop(1000). Times are in seconds after
subtracting the cost of the loop, by replacing assoc... by true.
All on a Sun-3/75 with 12Mb:

			"Optimized"	"Human-Readable"

Quintus Prolog 2.0:	2.5		2.5	(interpreted)
Quintus Prolog 2.0:	0.6		0.6	(compiled)
C-Prolog 1.5:		2.6		1.3
Custom WAM:		1.9		0.9

My conclusions are as follows:

1) The "human-readable" program is not slower than the "optimized" one
   for the Prolog implementations I tested this on.

2) Quintus Prolog seems to generate better code for the ; and -> constructs,
   than the two other Prolog's.  It would be interesting to hear
   about a Prolog for which the optimized version is significantly
   faster than the human-readable one.

3) Clause fusion sometimes results in slower programs, and is
   therefore not a generally useful technique for optimizing Prolog programs.