[m-dev.] Re: diff: test cases for accumulator introduction.

[Lee Naish]

Peter Ross <petdr at cs.mu.OZ.AU> writes:

>+p([], L, L).
>+p([H|T], _, L) :-
>+	p(T, H, L0),
>+	L is L0 + 1.

This example (and some other similar simple ones) is lacking comments.
Also at least one example with multiplication (and any other known
associative operations) would be nice.

I suggest an example or two illustrating rounding/overflow potential
problems also.  Eg, summing [1, maxint, -maxint] and (something like)
[0.000000001, 0.000000001, 0.000000001,..., 1.0].  For the integer example
I think its fair enough to say the "correct" answer is 1 (rather than
overflow - assumes mod arithmetic).  The floating point case is more
tricky, figuring out what the precision should be and what the correct
answer is.  One possibility would be to include a commented out test
case which could be used/adapted once the desired semantics is sorted
out.  It might also be possible to use the floating point case to test
if accumulators really are being introduced (so correct introduction of
accumulators is not invisible wrt computed answers).



>+	% We have two calls to append with dynamic variables in them
                               ^^^^^^
>+	% that don't require rearrangement.  Hence we CAN introduce
>+	% accumulator recursion.
>+	%
>+:- pred pc(list(int)::in, int::out) is det.
>+
>+pc([], 0).
>+pc(X, Y) :-
>+	X = [H | T],
>+	pc(T, Y0),
>+	Tmp is Y0 + (2*H),
>+	Y is Tmp + H.

Looks like you copied but forgot to change the comment.

>+	% We CANNOT introduce accumulators because the chain of calls
>+	% are to different predicates.
>+	%
>+:- pred pd(list(int)::in, int::out) is det.
>+
>+pd([], 0).
>+pd(X, Y) :-
>+	X = [H | T],
>+	pd(T, Y0),
>+	Tmp is 2*Y0,
>+	Y is Tmp + H.

Clarify the two preds are times and plus (rather than is/2 and is/2)?

>+	% Highoder functions cannot use accumulator recursion because we
>+	% don't know anything about the assocativity of P.

The typo is a bit on the nose:-)

Also, depending on the relative order of accumulator introduction and
inlining + specialisation of higher order calls, this may be incorrect.
I suggest a test case where highorder__foldr is called with a pred which
is definitely known to be associative (ie, not your minus/3) so that if
things are appropriately specialised before accumulator introduction
then an accumulator will be introduced (I don't know what order things
are currently done in the compiler but whatever it is it might change
and potentially break things).

>+	{ highorder__foldr(minus, [1,10,100], 0, ListA) },
>+	io__write(ListA),
>+	io__nl.
>+	
>+:- pred minus(int::in, int::in, int::out) is det.
>+ 
>+minus(A, B, C) :-
>+	C is A - B.



>+	% This is an interleaved version of reverse and length.
>+	% Tests if we can introduce more then one accumulator.

Nice one.  How about another where a potential acc pred calls another
potential acc pred?  Does this test anything useful?  Maybe not.


Finally(?), how about some cases with functions (or combinations of
functions and predicates).

Nice work.

	lee

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