for review: Intro to accumulator.m

[Peter Ross]

Zoltan,

Here is the update introduction.  Do you find this more understandable?

Pete.

%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%
% Copyright (C) 1998 The University of Melbourne.
% This file may only be copied under the terms of the GNU General
% Public License - see the file COPYING in the Mercury distribution.
%-----------------------------------------------------------------------------%
%
% File:		accumulator.m
% Main authors: petdr
%
% Identify procedures which would become tail recursive if some of the
% output variables are accumulated and then transform them to the tail
% recursive form.
%
% The transformation works according to the schema shown below.
% In this schema, 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.
%
% The meaning of all the variables is
% 	X	the variables that control the recursion.
% 	Ys	the variables that will need to be accumulated.
% 	Os	the variables that will not be accumulated.
% 	Hs	the variables which are used to calculate the next
% 		answer from the previous answer.  They model the fact
% 		that each member of Ys needs an associated value which
% 		is used to caculate the next Ys.  We can't just use X
% 		because we want a different variable associated with 
% 		each member of Ys and there is no guarantee that the 
% 		size of X and Ys are the same.
%
% minimal/1 is true iff the set of vars, X, selects the base case.
% identity/1 is true iff the set of vars, Ys, are bound to the result of
% p at the base case.
% constant/1 is true iff the set of vars, Os, are bound to some
% constant.
%
% decompose/3 is true iff X can be decomposed into Xh and Xr, where Xh
% represents the element that will be used in the computation of the
% current recursive step and Xr is the elements that remain to be
% computed.
% process/2 is true iff Xh can be expanded to the set Hs.
% compose/3 is true if Ys is the answer constructed from the old answer, 
% Y0s, and the current data, Hs. 
%
% :- pred p(SomeTypes::IN, SomeTypes::OUT, SomeTypes::OUT) is SomeDeterminism.
% p(X, Ys, Os) -->
%     minimal(X),
%     identity(Ys),
%     constant(Os).
% p(X, Ys, Os) :-
%     decompose(X, Xh, Xr),
%     process(Xh, Hs),
%     p(X, Y0s, Os),
%     compose(Hs, Y0s, Ys).
%
% 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(Hs, As, A1s),
%	p'(Xr, A1s, Ys).
%
% Or more generally
%
% :- pred p(T::IN, U::OUT, V::OUT, X::IN, Y::OUT) is 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).
%
% As long as the compose section of the predicate obeys the
% following constraints.
%
% 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.
%
% A simple heuristic is used to try to ensure that the new version is
% more efficient then the old version.  We do this by ensuring that the
% variable that is calculated to be combined with the accumulator is
% only allowed to be in certain positions after rearrangment.  For
% example, the calculated variable should be in the first postion for
% append/3 because the accumulator is, in general, longer the calculated
% variable.
%
% XXX	Currently the transformation only knows the commutativity,
% identity elements and associativity of some standard predicates in the
% standard library.  When a more general way is determined to calculate
% or declare these properties of predicates this module will need to be
% changed to accomodate this.
%
% XXX	In the future this phase should also transform procedures for
% which only construction unifications remain after p' inside p',
% because the last call modulo constructor optimization (in lco.m) will
% continue the transformation into a tail recursive procedure.
%
%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%
----
 +----------------------------------------------------------------------+
 | Peter Ross      M Sci/Eng Melbourne Uni                              |
 | petdr at cs.mu.oz.au  WWW: www.cs.mu.oz.au/~petdr/ ph: +61 3 9344 9158  |
 +----------------------------------------------------------------------+