Loop optimisation and predicate specialisation and stuff.

[Ralph Becket]

A couple of queries regarding optimisation in Mercury 0.7.3:

1 . Say I have a tail recursive predicate which calculates some
    locally constant value in its body, e.g.

	:- pred foo(int, int, list(int), int).
	:- mode foo(in,  in,  in,        out) is det.

	foo(_, [], C, C).

    	foo(A, [B | Bs], C0, C) :-
		X = f(A),		% f/1 is a det function.
		C1 = g(X, B, C0),
		foo(A, Bs, C1, C).

    Will the compiler move the calculation of X outside the loop body?
    If not, the programmer has to do this by hand, probably by
    introducing a new predicate.

2 . Some algorithms do require one to pass around a fair amount of
    state (e.g. a dozen variables).  If several predicates are
    required to implement the algorithm then this can get rather
    messy.  The answer is usually to box 'em up in a functor and use
    various projection and updating functions:

	:- func a(some_state) = type_a.
	:- mode a(in) is det.
	a(some_state(A,_,...)) = A.

	[and so on]

	:- pred set_a(some_state, type_a, some_state).
	:- mode set_a(di,         in,     uo) is det.
	set_a(some_state(_,B,...,Z), A, some_state(A,B,...,Z)).

	[and so on, then...]

	bar(..., State0, State) :-
		baz(a(State0)),
		set_b(State0, Something, State1),
		quux(..., State1, State).

    With suitable use of inlining this can be made quite efficient (or
    it will be when di/ui/uo modes are fully implemented [what's the
    status of this?]).

    It seems to me that predicate calls *may* be cheaper this way
    since all or most state is passed via a single argument.  On the
    other hand, every access to some part of state is via indirection.

    Can the compiler/will the compiler be able to spot the common
    structured argument type and specialise predicates so that the
    some_state wrapper is done away with and the various state members
    are passed directly as arguments?  And if so, will the compiler
    reorder the order of arguments to try to minimise the number of
    rearrangements of the stack frame for tail call optimisation?

3 . Beg beg beg, can we have nested unique modes soon?  Pretty please!

Normally I wouldn't be too worried about stuff this low level, but I'm
in the middle of an efficiency argument with somebody.  It seems to me
that if these optimisations aren't already there, it's only a matter
of time before they appear.

For that matter, are there any plans to provide a stripped-down
compiler back end to support experiments in source-to-source program
transformation?  The expand_terms sample program doesn't really cut it
since it doesn't provide access to the full program, just the parse of
a single file.  This is important if you want to transform higher
order code or need access to typing information (as in 2 above).

I'm sure the Mercury development team have more than enough on their
plates as it is, so please take these as requests for information and
not demands of any kind!

Cheers,

Ralph

-- 
Ralph Becket  |  rwab1 at cam.sri.com  |  http://www.cam.sri.com/people/becket.html