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

[Peter Ross]

On 18-Jun-1999, Lee Naish <lee at cs.mu.OZ.AU> wrote:
> 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.

These cases have comments at the top of the files which explain what the
test case is.

I put comments above each individual predicate only if there was more
then one in the module.

> 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).
> 
I will look into this.

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

> >+	% 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).
> 
Good idea.

> >+	{ 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.
> 
It should make no difference since the head of the
predicate never changes, just the body.

> 
> Finally(?), how about some cases with functions (or combinations of
> functions and predicates).
> 
Yes I should do that.  To keep things simple my test cases were all
valid prolog code as well.

Thanks for the comments,
Pete.
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------