3 ms·

Most Common Lisps (certainly the compiled ones) do tail call optimization. Clojure doesn't because it's a Lisp in Java, and Java doesn't. Back when Clojure wa

Most Common Lisps (certainly the compiled ones) do tail call optimization. Clojure doesn't because it's a Lisp in Java, and Java doesn't. Back when Clojure was just starting to get some attention I watched a video [1] of Rich doing a demo for a user group. Tail call optimization was one of their first questions. He gave them an answer that sounded like he had given it multiple times before. [1] can't find it, sorry.

pjmlp 7y ago
Yes it is a common optimization, however it is not a requirement for Common Lisp standard compliance, like it happens with Scheme.
lvh 7y ago
> Clojure doesn't because it's a Lisp in Java, and Java doesn't. I keep hearing this and I have no idea where it comes from. x86_64 doesn't either, Clojure has recur, and prefers consistent var semantics to silently specialcasing some tail calls. There's no particularly good reason the compiler couldn't just do it.
- lispm 7y ago
  For every function call it should not grow the stack and jump into the function. The JVM does not support that. One would need to compile the code in complex ways - function calls would no longer map directly to JVM instructions.
  - lvh 7y ago
    You're explaining TCO. I understand how TCO works. I'm going to rephrase my own argument because it doesn't appear you interacted with it: what part of your argument doesn't work for x86_64? "One would need to compile the code in complex ways: function calls would no longer map directly to CALL/RET instructions." Sure! That's arguably what makes it an optimization. Who cares? CPUs can loop, and so can the JVM. I would maybe see your point if Clojure didn't already know how to do tail calls (and so would need to implement the allegedly complicated compilation step), but as I have pointed out several times: it already has `recur`, which lets you call a function without the JVM thinking there is a function call going on.
    - deleted 7y ago
      [deleted]
    - lispm 7y ago
      Tail recursion optimization would be when the compiler on its own would recognize tail recursion calls and generate special code for that. That one needs to manually annotate it in Clojure just means that the compiler is manually instructed to generate a loop-like construct instead of a function call. The advantage in Clojure is that these loops are explicitly marked, which IMHO improves readablity. Many Lisps don't bother to implement tail recursion optimization, because they support the more general tail call optimization - by adjusting/reusing the current stack frame and using a JMP instruction.
- kazinator 7y ago
  The JVM defines a particular model for program organization, which is largely inescapable from the point of view of someone targeting a language front-end to it. x86_64 instruction set gives the programmer complete control over the organization of memory: the stack, use of registers, calling conventions and so on. It has few safety features. x86_64 doesn't specifically support tail calls, but it makes tail calls possible by way of jump instructions being able to go anywhere in the address space. An instruction in the middle of one function can branch to an instruction in the middle of another function, and without doing anything with the registers or stack. The JVM byte code doesn't allow such a thing. The JVM supports iteration. Therefore local tail calling is possible, because it's a syntactic sugar for local control transfers. That's presumably why Clojure can have recur.
  - lvh 7y ago
    That sounds like a long-winded way of saying "x86_64 and the JVM are different but neither prevents TCO", which is precisely my point! Unless your point is "it's not TCO unless it's literally an instruction called 'jump' and iteration transforms don't count"?

pjmlp 7y ago

Yes it is a common optimization, however it is not a requirement for Common Lisp standard compliance, like it happens with Scheme.

lvh 7y ago

> Clojure doesn't because it's a Lisp in Java, and Java doesn't. I keep hearing this and I have no idea where it comes from. x86_64 doesn't either, Clojure has recur, and prefers consistent var semantics to silently specialcasing some tail calls. There's no particularly good reason the compiler couldn't just do it.

lispm 7y ago
For every function call it should not grow the stack and jump into the function. The JVM does not support that. One would need to compile the code in complex ways - function calls would no longer map directly to JVM instructions.
- lvh 7y ago
  You're explaining TCO. I understand how TCO works. I'm going to rephrase my own argument because it doesn't appear you interacted with it: what part of your argument doesn't work for x86_64? "One would need to compile the code in complex ways: function calls would no longer map directly to CALL/RET instructions." Sure! That's arguably what makes it an optimization. Who cares? CPUs can loop, and so can the JVM. I would maybe see your point if Clojure didn't already know how to do tail calls (and so would need to implement the allegedly complicated compilation step), but as I have pointed out several times: it already has `recur`, which lets you call a function without the JVM thinking there is a function call going on.
  - deleted 7y ago
    [deleted]
  - lispm 7y ago
    Tail recursion optimization would be when the compiler on its own would recognize tail recursion calls and generate special code for that. That one needs to manually annotate it in Clojure just means that the compiler is manually instructed to generate a loop-like construct instead of a function call. The advantage in Clojure is that these loops are explicitly marked, which IMHO improves readablity. Many Lisps don't bother to implement tail recursion optimization, because they support the more general tail call optimization - by adjusting/reusing the current stack frame and using a JMP instruction.
kazinator 7y ago
The JVM defines a particular model for program organization, which is largely inescapable from the point of view of someone targeting a language front-end to it. x86_64 instruction set gives the programmer complete control over the organization of memory: the stack, use of registers, calling conventions and so on. It has few safety features. x86_64 doesn't specifically support tail calls, but it makes tail calls possible by way of jump instructions being able to go anywhere in the address space. An instruction in the middle of one function can branch to an instruction in the middle of another function, and without doing anything with the registers or stack. The JVM byte code doesn't allow such a thing. The JVM supports iteration. Therefore local tail calling is possible, because it's a syntactic sugar for local control transfers. That's presumably why Clojure can have recur.
- lvh 7y ago
  That sounds like a long-winded way of saying "x86_64 and the JVM are different but neither prevents TCO", which is precisely my point! Unless your point is "it's not TCO unless it's literally an instruction called 'jump' and iteration transforms don't count"?