[gclist] Name that hypothesis

[Fergus Henderson]

Nick Barnes, you wrote:
> 
> > We (the Mercury compiler implementors) are currently working on
> > "LCMCA" (last call modulo constructor application) optimization.
> 
> Interesting. So you receive results by reference?

Well, the implementation is not yet complete, but yes, that's the idea.

> In pseudo-ML:
> 
> 	fun foo 0 = [] | foo n = n :: (foo (n-1))
> 
> 	=>
> 
> 	fun foo' (p,0) = (p := [])
> 	  | foo' (p,n) = (p := new_cons();
> 	                  car(p) := n;
> 			  foo' (&cdr(p), n-1))
> 
> 	?

Yep.

The reason this optimization is particularly important for us is that
an important section of our competition -- Prolog implementations --
get this for free, because "return by reference" is a common-place use
of Prolog's logic variables.

	foo(N, L) :-
		( N = 0 -> L = []
		; L = [N | L1], N1 is N + 1, foo(N1, L1)
		).

Mercury's mode analysis will actually reorder this code so that it becomes

	:- mode foo(in, out).
	foo(N, L) :-
		( N = 0 -> L = []
		; N1 = N + 1, foo(N1, L1), L = [N | L1]
		).

The advantage of this reordering is that we can return output results
in registers, which is usually a win, but if by so doing we lose tail
recursion optimization, then it would be better to use pass by reference.

-- 
Fergus Henderson <fjh@cs.mu.oz.au>   |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>   |  of excellence is a lethal habit"
PGP: finger fjh@128.250.37.3         |     -- the last words of T. S. Garp.