4 ms·
> Why don't languages give tail calls their own syntax rather than making it an optimization? Clojure does exactly that: (defn gcd [x y] (if (zero?
by dghf 9y ago
> Why don't languages give tail calls their own syntax rather than making it an optimization?
Clojure does exactly that:
(defn gcd [x y]
(if (zero? y)
x
(recur y (quot x y)))
You can also recur with TCO to an explicitly labelled point within the function (effectively creating an inner, anonymous function):
(defn factorial [n]
(loop [n n, fac 1]
(if (zero? n)
fac
(recur (dec n) (* fac n)))))
As I understand it, this syntax was developed because of limitations of the JVM w/r/t TCO.
- catnaroek 9y ago> As I understand it, this syntax was developed because of limitations of the JVM w/r/t TCO. This doesn't make sense. Tail calls don't need any virtual machine support whatsoever: they're translated into jumps by the compiler. The real problem is a lack of willingness to translate functions into anything other than JVM methods, because “compatibility“, but that is a political issue, not a technical one.
- _pmf_ 9y agoI don't think it's that easy. Clojure code calls into Java libraries, and these are regular Java functions so you cannot reuse the same stack frame for these. Pure Clojure code, on which you could perform arbitrary transformations, is quite rare (does not exist at the moment, since the core datastructures are written in Java).
- catnaroek 9y ago> Clojure code calls into Java libraries, and these are regular Java functions so you cannot reuse the same stack frame for these. Somehow, programs written in <insert language that provides correctly implemented tail calls> can call routines written in C (of all languages!) without any problems. So I stand by what I previously said: the problem is political, not technical.
- pjmlp 9y agoThey do so, by having a FFI marshaling layer that creates a stack frame the way C expects it, which is in full control of the language runtime, something that languages that pretend to be Java cannot do on the JVM. Eventually one could do some tricks with invokedynamic, but I doubt the performance impact would be worthwhile.
- mannykannot 9y agoIf I understand your point correctly, it is not a problem. If your TCO-ed recursive function calls Java functions, they will expand the stack temporarily, but it will all be popped back to your stack frame by the time they return. It is no different than if you made the same calls from an equivalent non-recursive function.
- denisw 9y agoYou don't need VM support for tail self-calls (which is exactly what Clojure supports with `recur`), but you sure do for optimizing tail calls to other functions. There is no way in the JVM to say "replace my stack frame with a new one for that other method and execute that", especially not one that gives you a useful stacktrace for debugging.
- catnaroek 9y ago> There is no way in the JVM to say "replace my stack frame with a new one for that other method and execute that" Nor does there need to be one, because translating function calls to jumps is the (AOT) compiler's business, not the VM's.
- pjmlp 9y agoThe CLR has byte codes for tail calls, properly named .tail..