[m-dev.] choice point deforestation

[Fergus Henderson]

Consider the following code:

	:- mode benchmark(in, out) is det.
	benchmark(Data, Out) :-
		(
			mymember(X, Data), test(X)
		->
			Out = "found"
		;
			Out = "not found"
		).

	:- mode mymember(out, in) is nondet.
	mymember(X, [X|_]).
	mymember(X, [_|Xs]) :- mymember(X, Xs).

	:- mode test(in) is semidet.
	test(X) :- X = 15.

Currently we generate code for that which is quite inefficient,
relative to what it could be.  The call to `mymember' creates
a choice point, which then gets pruned away.

By applying a deforestation-like "conjunctive partial deduction"
transformation to the conjunction `mymember(X, Data), test(X)',
we can push the pruning further in, to the point where we avoid
creating the choice points at all.

	:- mode benchmark2(in, out) is det.
	benchmark2(Data, Out) :-
		(
			mymember_and_test(Data)
		->
			Out = "found"
		;
			Out = "not found"
		).
	:- mode mymember_and_test(in) is semidet.
	mymember_and_test([X|_]) :- test(X).
	mymember_and_test([_|Xs]) :- mymember_and_test(Xs).

This speeds things up dramatically -- by a factor of 7,
according to a test I did on my Linux box (hg).

To generalize, if you have a goal of the following form

	% model_semi conjunction
	(
		% model_non call
		<generate>(<Args>),

		% model_semi goal
		<Test>
	)

	(here the notation <var> denotes a meta-variable; also note
	that the conjunction must be cc_nondet or have no output
	variables in order for it to be model_semi)

and the body of `generate' is a disjunction, 

	<generate>(<Args>) :- ( <Case1> ; <Case2> ; ... ; <CaseN> ).

then it will probably be advantageous to apply a deforestation-like
transformation to change this goal into

	<generate_and_test>(<NonLocals>)

where <NonLocals> are the non-local variables of the original goal and
<generate_and_test> is a new procedure with a model_semi determinism
defined by

	generate_and_test(<NonLocals>) :-
		( <Case1>, <Test>
		; <Case2>, <Test>
		; ...
		; <CaseN>, <Test>
		).

To get a big speed up it is crucial to replace recursive calls to
<generate> in the <Case>s with recursive calls to <generate_and_test>.

Anyway, it seems to me that this optimization is quite similar to the
existing deforestation optimization.  Simon, how hard do you think it
would be to extend deforestation to handle cases like this?
	
-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>  |  of excellence is a lethal habit"
PGP: finger fjh at 128.250.37.3        |     -- the last words of T. S. Garp.
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------