[m-dev.] Re: for review: Accumulator introduction

[Peter Schachte]

Hi Pete,

I didn't actually read the diff, just Fergus' comments.  But this lead
me to a few comments of my own.

> > % 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),

Shouldn't that be Xr?

> > %     { compose(Hs, Y0s, Ys) }.

And shouldn't you allow Os to be passed to process and compose?

Also, Ys doesn't have to be an identity in the first clause.  For
example:

	sum3([], 3).
	sum3([X|Xs], S) :-
		sum3(Xs, S0),
		S = S0 + X.


====>	sum3(Xs, S) :- sum3'(Xs, 3, S).

	sum3([], S, S).
	sum3([X|Xs], S0, S) :-
		S1 = S0 + X,
		sum3(Xs, S1, S).


Also, in the first clause, X doesn't have to be minimal:

	min([X|Xs], M) :-
		(   Xs = [] ->
			M = X
		;	min(Xs, M0),
			min2(M0, X, M)
		).

====>	min([X|Xs], M) :-
		min'(Xs, X, M).

	min'(Xs, M0, M) :-
		(   Xs = [] ->
			M = M0
		;	Xs = [X|Xs1],
			min2(M0, X, M1)
			min'(Xs1, M1, M)
		).

but I think that one is probably a bit harder.

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

As the min example shows, you don't actually need a left identity,
because you can always peel off the first value and use it as the
initial accumulator.  Ie, if you're going to be computing

	x1 @ x2 @ x3 ...

where @ is any binary operation, then if there is a left identity id, you
can compute

	accumulate(Collection, id, Result)

but if there isn't a left identity, you can still compute

	decompose(Collection, X1, C1),
	accumulate(C1, X1, Result)

> > % 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/then/than/
s/thats/that/
s/to be/be/


-- 
Peter Schachte                | When I give food to the poor, they call me a
mailto:pets at cs.mu.OZ.AU       | saint. When I ask why the poor have no food,
http://www.cs.mu.oz.au/~pets/ | they call me a communist.
PGP: finger pets at 128.250.37.3 |     -- Dom Helder Camara