for review: Accumulator introduction

[Fergus Henderson]

On 25-Aug-1998, Peter David ROSS <petdr at cs.mu.OZ.AU> wrote:
> 
> Add the optimization to automatically introduce accumulators.
> 
> compiler/accumulator.m:
>     Does the optimization.
> 
> compiler/inst_match.m:
>     Add a utility predicate which determines whether or not an inst
>     contains a 'any' inst.
> 
> compiler/mercury_compile.m:
>     Call the accumulator module.
> 
> compiler/mode_util.m:
>     Make the prediate insts_to_mode public.
> 
> compiler/options.m:
>     Add the option to run the optimization.

You need to modify doc/user_guide.texi to document the new option.

> Index: mode_util.m
> ===================================================================
> RCS file: /home/staff/zs/imp/mercury/compiler/mode_util.m,v
> retrieving revision 1.111
> diff -u -r1.111 mode_util.m
> --- mode_util.m	1998/07/08 20:56:54	1.111
> +++ mode_util.m	1998/08/25 01:34:18
> @@ -94,6 +94,12 @@
>  :- pred inst_lists_to_mode_list(list(inst), list(inst), list(mode)).
>  :- mode inst_lists_to_mode_list(in, in, out) is det.
>  
> +	% insts_to_mode(InitialInst, FinalInst, Mode):
> +	%	Given the initial and final insts, return the mode which maps 
> +	%	from the initial inst to the final inst.
> +:- pred insts_to_mode(inst, inst, mode).
> +:- mode insts_to_mode(in, in, out) is det.

s/the mode/a mode/

Also you should document the purpose of this predicate --
why not just use `Mode = (InitialInst -> FinalInst)'?

options.m:
> +		"\t--introduce-accumulators\n",
> +		"\t\tEnable the introduction of accumulators.\n",

The documentation here doesn't really explain things.
A more detailed explanation, e.g. something vaguely similar to the
following comment from accumulator.m

	% Identify procedures which would become tail recursive if some of the
	% output variables are accumulated and then transform them to the tail
	% recursive form.

would be better.

accumulator.m:
> % Identify procedures which would become tail recursive if some of the
> % output variables are accumulated and then transform them to the tail
> % recursive form.
> %
> % Every variable mentioned is a set of variables.
> % Mode IN is one where the instantiatedness of the variable stays the
> % same, while mode OUT is one where a variable becomes more
> % instantiated.

I suggest that you add

	% The transformation works according to the schema shown below.
	% In this schema, ...

before "every variable mentioned ...".

> % :- pred p(T::IN, U::OUT, V::OUT, X::IN, Y::OUT) is SomeMode.

s/SomeMode/SomeDeterminism/

> % p(X, Ys, Os) -->
> %     minimal(X),
> %     { identity(Ys) },
> %     { constant(Os) },
> %     threaded.
> % p(X, Ys, Os) -->
> %     decompose(X, Xh, Xr),
> %     process(Xh, Hs),
> %     p(X, Y0s, Os),
> %     { compose(Hs, Y0s, Ys) }.
> % 
> % can be transformed into
> % 
> % p(X, Ys, Os) -->
> %     { identity(As) },
> %     { constant(Os) },
> %     p'(X, As, Ys, Os).
> % 
> % p'(X, As, Ys, Os) -->
> %     minimal(X),
> %     { Ys = As },
> %     threaded.
> % p'(X, As, Ys, Os) -->
> %     decompose(X, Xh, Xr),
> %     process(Xh, Hs)
> %     { compose(As, Hs, A1s) },
> %     p'(X, A1s, Ys, Os).
> %
> % Then as long as the compose section of the predicate obeys the
> % following constraints.

Delete the word "Then".

I think it would probably be a bit clearer if you actually expand out
the DCG notation, using some explicit state variables (say S0, S1, ..., S).

> % Either
> % 	compose(A, B, C) <=> compose(B, A, C)
> % or
> % 	compose(A, B, AB), compose(AB, C, ABC) <=>
> % 		compose(B, C, BC), compose(A, BC, ABC)
> %	identity(A), compose(A, B, C) <=> identity(A), compose(B, A, C)
> %
> % The above conditions states that the compose goal must either be
> % commutative OR if it isn't commutative, then it must be associative
> % with the base case initialising the accumulator to being the identity
> % element for the compose function.
> %
> % p(X,Ys) :-
> % 	identity(As),
> % 	p'(X, As, Ys).
> %
> % p'(X, As, Ys) :-
> % 	minimal(X),
> % 	Ys = As.
> % p'(X, As, Ys) :-
> % 	decompose(X, Xh, Xr),
> % 	process(Xh, Hs),
> % 	compose(Xh, As, A1s),
> %	p'(Xr, A1s, Ys).

This simpler schema is missing the untransformed version.

I think it might be good to keep the simpler schema, and
to first give the simpler schema (both untransformed
and transformed versions) and then show the more general one.

> % A simple heuristic is used to ensure that the new version is more
> % efficient then the old version.  The heursitic is that if a call
> % requires thats its arguments to be rearranged then we must also state
> % the set of postitions where static variables must be after the
> % rearranging.  For example for append/3 the first argument must be
> % static after rearrangement.

s/heursitic/heuristic/

How does this heuristic ensure that the new version is more efficient?
What's a static variable?

> %
> % XXX	In the future this phase should also transform procedures for which
> %	only construction unifications remain after p' inside p'.  As
> %	the last call modulo constructor optimization (in lco.m) will
> %	continue the transformation into a tail recursive procedure.

s/. As/, because/

[... to be continued.]

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