[mercury-users] Loop optimisation and predicate specialisation and stuff.

[Andrew Bromage]

G'day all.

Ralph Becket wrote:

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

As Tyson noted, the answer is "not yet".  In principle, it's just
a SMOP, however there is a semantic "gotcha".

Suppose:

	f(A) = 100/A.

And we query:

	?- foo(0, [], 42, X).

Without the optimisation, this call succeeds with X bound to 42.
With the optimisation, there is a division by zero.

In this case, we could simply note that f/1 will be called if the
second argument is a non-empty list and only perform the optimisation
then.  Now consider this related function:

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

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

We'd like to hoist the call to f/1 out of the loop here, too, but
now whether or not this optimisation is valid depends on the values
in the list (or at least the _first_ value in the list).

The problem occurs when the code to be hoisted out of the loop can
call error/1, raise an exception (same as error/1) or infinitely loop.

What you have to do is either:

	- Prove that the hoisted code doesn't do any of these things
	  (see our recent paper on termination analysis), or

	- Defer the optimisation until you're irrevocably committed
	  to executing the common code.  This has the potential for
	  code explosion.  (Anyone know how bad it gets in practice
	  if at all?)  In the case of the original foo/4 above,
	  the transformed code might look something like this:

		foo(_, [], C, C).
		foo(A, [B | Bs], C0, C) :-
			X = f(A),
			C1 = g(X, B, C0),
			foo_2(X, A, Bs, C1, C).

		foo_2(_, _, [], C, C).
		foo_2(X, A, [B | Bs], C0, C) :-
			C1 = g(X, B, C0),
			foo_2(X, A, Bs, C1, C).

	  (For the purposes of illustration, I left unused argument
	  eliminiation turned off.)

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

Please note that ML/Haskell-style record syntax is on the "to do" list,
but not very close to the top for lots of reasons.  Perhaps the two
most important of them are:

	- It's not a very interesting problem to solve, so getting
	  people (and/or funding) is difficult.

	- It requires the sort of syntax hacking which we're reluctant
	  to do while we still rely on Prolog for debugging.

>     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?]).

That would be me.

The new mode checker is getting there slowly.  For those who care, in the
tests I ran today it passed all the regression tests and failed to compile
only one module in the compiler.  It won't be ready for release for a
little while yet, though.

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

This is in the new mode checker too.

Cheers,
Andrew Bromage