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?
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.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".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:but this does:
This functionality is implemented here, as part of Clojure's implementation for
let
, and seems to push/pop local bindings within a Javawhile
loop to achieve the TCO effect.Kawa Scheme
Kawa - a JVM Scheme - achieves TCO, mentioning the following on its "Features" page:
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?