Tail-call Optimization

[fosskers]

I hope to open a discussion about TCO.

Background

This is inspired by my work on Transducers. The current implementation assumes that labels performs TCO for recursive calls.

• Example 1
• Example 2

This was done as a compromise to full, function-based tail recursion, as not all of the main Lisp implementations support that. Unfortunately, ABCL doesn't do TCO within labels either, so I was forced to declare it merely "partially supported".

Couldn't you just use the loopmacro internally? Or some other custom macro to simulate TCO?

Potentially, but that doesn't address the issue at hand regarding TCO within ABCL, in general. Someone had this thought and came up with this custom rlabels macro, but I don't intend to utilise it.

Prior Art

Clojure

Clojure does not support function-based TCO either. However, its loop / recur pair do accomplish it in effect. For example, this does not blow the stack:

(loop [n 1000000]
  (if (= n 0)
    "Done!"
    (recur (- n 1))))

but this does:

(defn loopy [n]
  (if (= n 0)
    "Done!"
    (loopy (- n 1))))

(loopy 1000000)

This functionality is implemented here, as part of Clojure's implementation for let, and seems to push/pop local bindings within a Java while loop to achieve the TCO effect.

Kawa Scheme

Kawa - a JVM Scheme - achieves TCO, mentioning the following on its "Features" page:

Kawa now does general tail-call elimination, but only if you use the flag --full-tailcalls. (Currently, the eval function itself is not fully tail-recursive, in violation of R5RS.) The --full-tailcalls flag is not on by default, partly because it is noticably slower (though I have not measured how much), and partly I think it is more useful for Kawa to be compatible with standard Java calling conventions and tools. Code compiled with --full-tailcalls can call code compiled without it and vice versa.

Even without --full-tailcalls, if the compiler can prove that the procedure being called is the current function, then the tail call will be replaced by a jump. This includes most “obvious” cases of calls to the current function named using define or letrec, and many cases of mutual tail-recursion (including state-machines using letrec).

Scala

While not a Lisp, it is a functional programming language, and is able to detect tail-calls, optimizing them into loops at compile time.

Discussion

While TCO is not mandated by the CL spec, some form of it is available within the major implementations. Considering that ABCL's other JVM brethren have achieved it, is implementing this (by altering labels or otherwise) something that this project would have interest in?