Re: How do full cail talls work in Kawa?

[Per Bothner <per at bothner dot com>]

On Mon 12 Sep 2011 01:26:33 AM PDT, Denis Washington wrote:
> I am trying to understand how --full-tailcalls is implemented in Kawa
> (in order to see how it can be used for full continuation support),
> but have some problems finding my way trough the code. The only thing
> I gathered so far is that it seems to use a slightly different calling
> convention with an additional "CallContext" argument.

It is a bit under-documented.  There is a little bit of explanation
in the very last section of:
http://www.gnu.org/software/kawa/internals/procedures.html

This may be helpful:
http://en.wikipedia.org/wiki/Tail_call
Specifically:
Many implementations achieve this by using a device known as a 
trampoline, a piece of code that repeatedly calls functions. All 
functions are entered via the trampoline. When a function has to call 
another, instead of calling it directly it returns the address of the 
function to be called, the arguments to be used, and so on, to the 
trampoline. This ensures that the C stack does not grow and iteration 
can continue indefinitely.

Specifically for Kawa:
(0) There is a single (per-thread) CallContext object, which can be 
thought of
as being like the hardware registers of traditional CPU.
(1) During a call, Argument expressions are evaluated, and the argument 
values left
in the CallContext object.  See ApplyExp#compile.
(2) The match method of the procedure is called.  This checks for 
compatibility,
may do conversions, and may handle "generic" (in the Lisp sense) functions.
(I.e. if match fails we try the next method of the generic function.)
(3) If the call is a non-tail call we call the procedure's 
apply(CallContext) method.
Otherwise we stash the procedure in the CallContext and return.
(4) After returning, the CallContext#runUNtilDone method checks if there
is a pending procedure, and if so calls apply(CallContext) on it.

JSR 292 and invokedynamic could potentially make this more efficient.
(Well, it could potentially be more efficient regardless - the 
argument-passing
though CallContext is not well optimized.)
--
	--Per Bothner
per@bothner.com   http://per.bothner.com/