4 ms·

I'm getting a bit tired of the "we don't have TCO because the JVM doesn't support it" argument. You know what doesn't have a tail-call construct either? Every h

I'm getting a bit tired of the "we don't have TCO because the JVM doesn't support it" argument. You know what doesn't have a tail-call construct either? Every hardware architecture in existence. You know what they have though? They have jumps. That is all a TCO is. It turns a recursive construct into a looping construct. And it's a really simple optimization - just update the local arguments to their new value and jump back to the start of the function instead of a call + return. No, Clojure doesn't have TCO because of a design decision. We can discuss the rationale behind that decision and the merits of it, but claiming it has anything to do with the JVM is dishonest.

lmm 10y ago
> You know what doesn't have a tail-call construct either? Every hardware architecture in existence. You know what they have though? They have jumps. Guess what the JVM doesn't have. Remember also that the JVM was originally designed for running untrusted bytecode, so it doesn't generally let code directly manipulate the call stack.
- poizan42 10y ago
  > Guess what the JVM doesn't have. https://docs.oracle.com/javase/specs/jvms/se7/html/jvms-6.html#jvms-6.5.goto https://docs.oracle.com/javase/specs/jvms/se7/html/jvms-6.ht... > so it doesn't generally let code directly manipulate the call stack. You are doing something wrong if you need to manipulate the call stack to do a tail call. You just have to update the local arguments and jump back to the start of the function. It is literally just turning the call into a loop.
  - jeremiep 10y ago
    That works for tail recursive functions, but not tail calls. TCO works for all tail calls, not just the recursive ones, so that jump would be to another function's body. The current stack frame may not have enough space for the new function's.
    - poizan42 10y ago
      It's true, but you probably don't want TCO for all tail calls since you lose information in stack traces. As long as you have control over all the code generated you can in principle compile multiple functions into a single one and just add some stubs for interop purposes. This of course complicates how you track function pointers (or equivalently) and may have some overhead. Still the cases where you can use recur today could be done automatically by the compiler without much trouble.
      - jeremiep 10y ago
        Good point! One worry I have about automatic TCO where recur/loop currently is used is with Lisp's dynamic nature. What happens to everyone who has a reference to the fn when you redefine its def? You're basically switching (defn f [] (recur [] (loop))) to (defn f [] (f)). What if I do (def g f) and then (def f +)? Will the original f now recur into + when I call (g)? If it still calls into the original f then that creates a mismatch between reloading normal and recur'd functions adding complexity to a language striving for simplicity. I'm probably overthinking it :)
        poizan42 10y ago
        If you want late binding at the call site it's probably unavoidable to have some extra complexity anyways, what if I changed f into something that wasn't callable? However Clojure binds at the definition time, e.g. > (defn f [] 42) #'sandbox9516/f > (f) 42 > (def g f) #'sandbox9516/g > (g) 42 > (def f 1337) #'sandbox9516/f > (g) 42 > (f) java.lang.ClassCastException: java.lang.Long cannot be cast to clojure.lang.IFn
        jeremiep 10y ago
        That's because defn binds f to the _value_ of the function, while (f) binds to the _variable_. > (defn f [] (f)) #'sandbox9672/f > (def g f) #'sandbox9672/g > (def f 42) #'sandbox9672/f > (g) java.lang.ClassCastException: java.lang.Long cannot be cast to clojure.lang.IFn
sethev 10y ago
It's not that dishonest. If the JVM supported TCO natively then it would be a no-brainer for Clojure. The alternative is to give up on seamless interop between Clojure and Java libraries.
- poizan42 10y ago
  > The alternative is to give up on seamless interop between Clojure and Java libraries. Why? The only issue I can see is that you can't tail call to java code, but that would only be a problem if you are trying to do mutual recursion involving both Clojure and Java code. For multiple Clojure functions with mutual recursion you could just compile all of them into a single function with a state argument to select which function to go to, and then add stub methods that just calls into the combined function with the correct value for the state argument for interop with java. The only artifact of that would be an extra method with a synthetic name in the stack trace.
  - sethev 10y ago
    Stubs == seams, IMO. Self calls are certainly not a problem, as you pointed out, but in that case recur is a pretty elegant way of supporting that while not making Clojure appear to support something it doesn't. EDIT: Also what you suggest would imply huge changes to the way code is evaluated in Clojure - for example, I can create functions in the REPL and they work the same way as reading functions out of a file. How would that work in your scenario? I think every function would actually have to have a stub not just the mutually recursive ones because you might not know until later which functions to combine.

lmm 10y ago

> You know what doesn't have a tail-call construct either? Every hardware architecture in existence. You know what they have though? They have jumps. Guess what the JVM doesn't have. Remember also that the JVM was originally designed for running untrusted bytecode, so it doesn't generally let code directly manipulate the call stack.

poizan42 10y ago
> Guess what the JVM doesn't have. https://docs.oracle.com/javase/specs/jvms/se7/html/jvms-6.html#jvms-6.5.goto https://docs.oracle.com/javase/specs/jvms/se7/html/jvms-6.ht... > so it doesn't generally let code directly manipulate the call stack. You are doing something wrong if you need to manipulate the call stack to do a tail call. You just have to update the local arguments and jump back to the start of the function. It is literally just turning the call into a loop.
- jeremiep 10y ago
  That works for tail recursive functions, but not tail calls. TCO works for all tail calls, not just the recursive ones, so that jump would be to another function's body. The current stack frame may not have enough space for the new function's.
  - poizan42 10y ago
    It's true, but you probably don't want TCO for all tail calls since you lose information in stack traces. As long as you have control over all the code generated you can in principle compile multiple functions into a single one and just add some stubs for interop purposes. This of course complicates how you track function pointers (or equivalently) and may have some overhead. Still the cases where you can use recur today could be done automatically by the compiler without much trouble.
    - jeremiep 10y ago
      Good point! One worry I have about automatic TCO where recur/loop currently is used is with Lisp's dynamic nature. What happens to everyone who has a reference to the fn when you redefine its def? You're basically switching (defn f [] (recur [] (loop))) to (defn f [] (f)). What if I do (def g f) and then (def f +)? Will the original f now recur into + when I call (g)? If it still calls into the original f then that creates a mismatch between reloading normal and recur'd functions adding complexity to a language striving for simplicity. I'm probably overthinking it :)
      - poizan42 10y ago
        If you want late binding at the call site it's probably unavoidable to have some extra complexity anyways, what if I changed f into something that wasn't callable? However Clojure binds at the definition time, e.g. > (defn f [] 42) #'sandbox9516/f > (f) 42 > (def g f) #'sandbox9516/g > (g) 42 > (def f 1337) #'sandbox9516/f > (g) 42 > (f) java.lang.ClassCastException: java.lang.Long cannot be cast to clojure.lang.IFn
        jeremiep 10y ago
        That's because defn binds f to the _value_ of the function, while (f) binds to the _variable_. > (defn f [] (f)) #'sandbox9672/f > (def g f) #'sandbox9672/g > (def f 42) #'sandbox9672/f > (g) java.lang.ClassCastException: java.lang.Long cannot be cast to clojure.lang.IFn

sethev 10y ago

It's not that dishonest. If the JVM supported TCO natively then it would be a no-brainer for Clojure. The alternative is to give up on seamless interop between Clojure and Java libraries.

poizan42 10y ago
> The alternative is to give up on seamless interop between Clojure and Java libraries. Why? The only issue I can see is that you can't tail call to java code, but that would only be a problem if you are trying to do mutual recursion involving both Clojure and Java code. For multiple Clojure functions with mutual recursion you could just compile all of them into a single function with a state argument to select which function to go to, and then add stub methods that just calls into the combined function with the correct value for the state argument for interop with java. The only artifact of that would be an extra method with a synthetic name in the stack trace.
- sethev 10y ago
  Stubs == seams, IMO. Self calls are certainly not a problem, as you pointed out, but in that case recur is a pretty elegant way of supporting that while not making Clojure appear to support something it doesn't. EDIT: Also what you suggest would imply huge changes to the way code is evaluated in Clojure - for example, I can create functions in the REPL and they work the same way as reading functions out of a file. How would that work in your scenario? I think every function would actually have to have a stub not just the mutually recursive ones because you might not know until later which functions to combine.