Kawa: Compiling Scheme to Java
1.19 Tail-calls
Scheme requires that tail-calls be implemented without
causing stack growth. This is difficult to do
portably in Java (or for that matter in C), since implementing
it efficiently requires low-level access to the hardware stack.
There are tricks one can use (a function returns a pointer to the
next function to be called, rather than calling it directly), but
these are rather expensive, especially in Java (which does not
have function pointers).
Compiler optimizations can re-write many tail-calls into
gotos. The most important case is self-tail-calls
or tail recursion. Kawa rewrites these
when it can prove that is safe. It is rather
conservative: it must be able to prove that the procedure
binding cannot be re-assigned to some other value. Thus
only letrec tail-recursion is supported, not
tail-recursion of global procedures. This restriction may
be excessively paranoid, but it is required by the language,
and it is sufficient to optimize the standard do
and named-let forms. A future version will provide a way
to specify that Kawa can be less conservative (using either a
module system or compiler switches).
While full tail-call elimination will probably never be supported
by Kawa (except perhaps on modified Java interpreters),
some forms of mutual tail-recursion can be eliminated with
more sophisticated compiler analysis, though there are no concrete
plans for that yet.
