On Dec 9, 2013, at 7:29 AM, Michal Maruska mmaruska@gmail.com wrote:

Hello, I'm curious about how the ... function calls translated to jumps ... explained in the 90min document/video is implemented for scheme libraries compiled separately, and thus the possible jumps are between different (Elf) object files.

I.e. at the C level, how is TCO (constant space for special recursion..) achieved for 2 scheme functions which were compiled into 2 separate object files?

Thanks

Is your question specific to the 90 min Scheme to C compiler, or are you asking a more general question about Scheme to C compilation?

TCO is basically the garbage collection of useless stack frames, with the definition that a stack frame is useless at a certain point in time if the only useful value at that moment is the return address. A C stack frame can be reclaimed in one of two ways:

1) returning from the C function (using a "return") 2) using a longjump to return to some ancestral stack frame

Option #2 is used by the Cheney-on-the-MTA approach (google it), and specifically the Chicken Scheme implementation.

Option #1 is used in the "trampoline" approach, and specifically in Gambit (and the 90 min Scheme to C compiler). Basically, there is a driver function called "trampoline" that does

next = main; // main is the entry point of the program while (1) next = next();

And a function returns the next function to jump to. For example function A could tail call function B using "return B;".

Note that a tail call at the Scheme level becomes a function return (to "trampoline") and a function call (from "trampoline" to the destination function), so performance is an issue. An optimization, which is implemented in Gambit, is to have a two level trampoline. So in addition to the "trampoline" function, there is a similar mechanism inside of the destination function with does

while (1) switch (pc) { case 0: ...; case 1: ...; case 2: ...; }

And tail calls become assignments to pc, i.e. "pc=2;" will jump to the code of case 2. When a jump is (possibly) non-local to the C function, a return to the "trampoline" function is performed.

When gcc is detected the "while (1) switch (pc) ..." is replaced by indirect jumps using label values. But this can be seen as just an optimization of the switch statement.

Marc