🚀 go-pugleaf

In article <1992Dec30.094352.4243@cucs5.cs.cuhk.hk> bmtong@cs.cuhk.hk (Tong Bo-Ming) writes:

> In the field of Logic Programming, we have a kind of optimization
> technique called the Last Call Optimization.  The idea is simple.

> 	p(a,b,c)
> 	{	x(a);
> 		y(b);
> 		z(c);
> 	}

> In the above procedure, we may discard the current stack frame (or reg
> window in Sparc) before calling z.  We then replace the call z
> instruction by a jump instruction.

> 	p(a)
> 	{	x(a);
> 	}

> In the above kind of procedure where there is only one call, no stack
> frame is necessary.  It can be optimized as if it were a leaf procedure.

> It is a sad thing to notice that such a nice optimization is not
> implemented in languages other than Prolog and on RISC architectures.

IBM's compilers for the RS/6000 do this, when possible.  There are a few
things one must watch out for.  The linkage conventions of the RS/6000
dictate that a procedure that must save and restore registers does so
using a save area in the caller's stack frame.  That means that, in your
second example, one cannot always regard p() as a leaf procedure unless
x() is a leaf procedure.  The differences between the conventional linkage
semantics of C and FORTRAN (multiple procedures in a FORTRAN 77 file are
regarded as if they came from multiple files, i.e., some may be replaced
at link time) mean, in practice, that this optimization can be done in
C but not in FORTRAN.

And, of course, this optimization eliminates tail recursion as an instance
of the more general phenomenon.
--
                                   Dan Prener (prener@watson.ibm.com)