Re: Why no tail call optimization
On 3 August 2010 04:16, Dan Kersten dkers...@gmail.com wrote: Why can't the clojure bytecode compiler hand-perform this like functional languages do when compiling to native code? Because bytecode attempting to manipulate the stack and jump around (unrestricted goto-like) in other ways than through the usual JVM method call mechanisms would not pass verification (the first step of the bytecode loading process on the JVM). Is it to keep the clojure compiler fast (for dynamic runtime compilation), since performing tail call optimisation presumably requires a bunch of extra checks and more complex code generation? Perhaps this could be done on AOT compilation? TCO adds no complexity at all when the generated object code handles its own stack, subroutine calling conventions etc. A compiler targeting native code has the option of simply not storing a new return address on the stack when compiling a tail call (if the arguments to the current subrouting where passed in registers; if they were passed in a stack frame, it can simply be popped, with the return address saved and reused for the tail call). On the JVM it is impossible, because the generated object code (JVM bytecode) is not permitted to do this sort of thing. Interestingly, [Erjang][1] (a port of Erlang to the JVM) apparently performs TCO while claiming to stay reasonably fast. The gimmick involved is apparently a particularly smart implementation of trampolining. Read more about it [here][2]. I have a hunch that this is a no-go for Clojure (partly because Clojure tends to insist on staying close to the platform -- which has significant benefits -- and partly because I'm not sure if this kind of thing wouldn't disagree with Clojure's extremely dynamic nature... I haven't thought this through that well, though, so maybe this is nonsense). At any rate, it is interesting. Sincerely, Michał [1] git://github.com/krestenkrab/erjang [2] http://wiki.github.com/krestenkrab/erjang/how-erjang-compiles-tail-recursion -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why no tail call optimization
Can one not detect that a recursive call is a tail call and then transform the AST so that its iterative instead - ie, not use the stack besides for initial setup of local variables (which then get reused in each recursive tail-call). Isn't this how its done in native compiled languages with TCO? How is this different from generating bytecode for iterative loops in imperative languages, or from what recur does? Alternatively, why can't the tail call be detected and converted into recur? I'm guessing that the problem is detecting tal calls - but why; speed of dynamic compilation? Something else? Obviously I'm missing something fundamental here - can somebody explain to me what it is? Thanks! On 3 August 2010 05:54, Wilson MacGyver wmacgy...@gmail.com wrote: as Rich Hickey stated question: Is it fundamentally impossible to do TCO on JVM due to current JVM lack of primitives to do so? Would TCO ever be possible on the JVM without a new JVM design? rhickey: TCO is easy if you are an interpreter - see SISC Scheme. Using Java's call stack, the JVM would have to provide it. There are no fundamental technical difficulties, but potential issues for the security model, which uses the call stack to ensure privileges. On Mon, Aug 2, 2010 at 10:16 PM, Dan Kersten dkers...@gmail.com wrote: Why can't the clojure bytecode compiler hand-perform this like functional languages do when compiling to native code? Is it to keep the clojure compiler fast (for dynamic runtime compilation), since performing tail call optimisation presumably requires a bunch of extra checks and more complex code generation? Perhaps this could be done on AOT compilation? On Aug 3, 2:58 am, Frederick Polgardy f...@polgardy.com wrote: It means that the JVM doesn't look at method calls and figure out that they're in tail call position and optimize them. You can hand-write code that performs a goto in a tight loop (like recur does), but means you can't assume that method calls in general will be tail call optimized. -Fred -- Science answers questions; philosophy questions answers. On Aug 2, 2010, at 4:09 PM, Dale wrote: The JVM has an unconditional goto opcode and the ability to re-bind function parameters, so why no tail-call optimization? Thanks. Dale -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.comclojure%2bunsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.comclojure%2bunsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en -- Omnem crede diem tibi diluxisse supremum. -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.comclojure%2bunsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en -- Daniel Kersten. Leveraging dynamic paradigms since the synergies of 1985. -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why no tail call optimization
On Aug 3, 2:19 am, Daniel Kersten dkers...@gmail.com wrote: Can one not detect that a recursive call is a tail call and then transform the AST so that its iterative instead - ie, not use the stack besides for initial setup of local variables (which then get reused in each recursive tail-call). Isn't this how its done in native compiled languages with TCO? How is this different from generating bytecode for iterative loops in imperative languages, or from what recur does? Alternatively, why can't the tail call be detected and converted into recur? I'm guessing that the problem is detecting tal calls - but why; speed of dynamic compilation? Something else? Obviously I'm missing something fundamental here - can somebody explain to me what it is? When speaking about general TCO, we are not just talking about recursive self-calls, but also tail calls to other functions. Full TCO in the latter case is not possible on the JVM at present whilst preserving Java calling conventions (i.e without interpreting or inserting a trampoline etc). While making self tail-calls into jumps would be easy (after all, that's what recur does), doing so implicitly would create the wrong expectations for those coming from, e.g. Scheme, which has full TCO. So, instead we have an explicit recur construct. Essentially it boils down to the difference between a mere optimization and a semantic promise. Until I can make it a promise, I'd rather not have partial TCO. Some people even prefer 'recur' to the redundant restatement of the function name. In addition, recur can enforce tail-call position. Rich -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why no tail call optimization
Interestingly, [Erjang][1] (a port of Erlang to the JVM) apparently performs TCO while claiming to stay reasonably fast. The gimmick I have never done extensive benchmarking of clojure, but given the frequent mentions of use of '-server' in order to achieve specific performance goals, I get the impression clojure (i.e. Rich) definitely wants to take advantage of all the optimizations the JIT can offer now and in the future. Trampoline-based TCO would, as far as I can tell, always defeat the JIT's notion of a call site - unless the JIT is made to understand the trampoline (but then are we getting close to full TCO support anyway? I dunno, I'm definitely not an expert on this topic...). So, I would expect that those cases which are aggressively optimized by JIT:ing, such as eliminating method lookups by inline caching in light loops, would suffer potentially very extreme performance impacts which aren't fixed by just avoiding allocation as is mentioned in the erjang wiki page. Or is this over-stating the problem? -- / Peter Schuller -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why no tail call optimization
When speaking about general TCO, we are not just talking about recursive self-calls, but also tail calls to other functions. Full TCO in the latter case is not possible on the JVM at present whilst preserving Java calling conventions (i.e without interpreting or inserting a trampoline etc). Understood. Thanks! -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why no tail call optimization
Thanks for the replies, that certainly clarified things! On 3 August 2010 13:39, Rich Hickey richhic...@gmail.com wrote: On Aug 3, 2:19 am, Daniel Kersten dkers...@gmail.com wrote: Can one not detect that a recursive call is a tail call and then transform the AST so that its iterative instead - ie, not use the stack besides for initial setup of local variables (which then get reused in each recursive tail-call). Isn't this how its done in native compiled languages with TCO? How is this different from generating bytecode for iterative loops in imperative languages, or from what recur does? Alternatively, why can't the tail call be detected and converted into recur? I'm guessing that the problem is detecting tal calls - but why; speed of dynamic compilation? Something else? Obviously I'm missing something fundamental here - can somebody explain to me what it is? When speaking about general TCO, we are not just talking about recursive self-calls, but also tail calls to other functions. Full TCO in the latter case is not possible on the JVM at present whilst preserving Java calling conventions (i.e without interpreting or inserting a trampoline etc). Ah, this where my confusion was then. Self-calls aren't the problem at all, since they can be compiled how recur is, but tail-calls to other functions cannot be due to the JVM's calling conventions. I understand now, thanks for the explanation. While making self tail-calls into jumps would be easy (after all, that's what recur does), doing so implicitly would create the wrong expectations for those coming from, e.g. Scheme, which has full TCO. So, instead we have an explicit recur construct. Essentially it boils down to the difference between a mere optimization and a semantic promise. Until I can make it a promise, I'd rather not have partial TCO. To me, it is really only an optimization and I'm very much in the group who likes the explicit recur statement, since it conveys intent. Therefore I'd be happy with the partial optimization, though, honestly, not having it doesn't bother me at all. Some people even prefer 'recur' to the redundant restatement of the function name. In addition, recur can enforce tail-call position. Rich -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.comclojure%2bunsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en -- Daniel Kersten. -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why no tail call optimization
Some people even prefer 'recur' to the redundant restatement of the function name. In addition, recur can enforce tail-call position. Rich Because recur only takes you back to the innermost loop, sometimes I miss the ability to jump back to some outer loop (or the overall function call). Hypothetically, could Clojure support a way to name a specific loop, and use a version of recur that lets you jump back to a given named outer loop (like Scheme's named let), or is this outside the scope of what Java's goto permits? -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why no tail call optimization
It means that the JVM doesn't look at method calls and figure out that they're in tail call position and optimize them. You can hand-write code that performs a goto in a tight loop (like recur does), but means you can't assume that method calls in general will be tail call optimized. -Fred -- Science answers questions; philosophy questions answers. On Aug 2, 2010, at 4:09 PM, Dale wrote: The JVM has an unconditional goto opcode and the ability to re-bind function parameters, so why no tail-call optimization? Thanks. Dale -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why no tail call optimization
the jvm goto's only can jump around inside method bodies, so it is a very restricted goto On Mon, Aug 2, 2010 at 2:09 PM, Dale dpar...@ptd.net wrote: The JVM has an unconditional goto opcode and the ability to re-bind function parameters, so why no tail-call optimization? Thanks. Dale -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en -- And what is good, Phaedrus, And what is not good— Need we ask anyone to tell us these things? -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why no tail call optimization
Why can't the clojure bytecode compiler hand-perform this like functional languages do when compiling to native code? Is it to keep the clojure compiler fast (for dynamic runtime compilation), since performing tail call optimisation presumably requires a bunch of extra checks and more complex code generation? Perhaps this could be done on AOT compilation? On Aug 3, 2:58 am, Frederick Polgardy f...@polgardy.com wrote: It means that the JVM doesn't look at method calls and figure out that they're in tail call position and optimize them. You can hand-write code that performs a goto in a tight loop (like recur does), but means you can't assume that method calls in general will be tail call optimized. -Fred -- Science answers questions; philosophy questions answers. On Aug 2, 2010, at 4:09 PM, Dale wrote: The JVM has an unconditional goto opcode and the ability to re-bind function parameters, so why no tail-call optimization? Thanks. Dale -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why no tail call optimization
as Rich Hickey stated question: Is it fundamentally impossible to do TCO on JVM due to current JVM lack of primitives to do so? Would TCO ever be possible on the JVM without a new JVM design? rhickey: TCO is easy if you are an interpreter - see SISC Scheme. Using Java's call stack, the JVM would have to provide it. There are no fundamental technical difficulties, but potential issues for the security model, which uses the call stack to ensure privileges. On Mon, Aug 2, 2010 at 10:16 PM, Dan Kersten dkers...@gmail.com wrote: Why can't the clojure bytecode compiler hand-perform this like functional languages do when compiling to native code? Is it to keep the clojure compiler fast (for dynamic runtime compilation), since performing tail call optimisation presumably requires a bunch of extra checks and more complex code generation? Perhaps this could be done on AOT compilation? On Aug 3, 2:58 am, Frederick Polgardy f...@polgardy.com wrote: It means that the JVM doesn't look at method calls and figure out that they're in tail call position and optimize them. You can hand-write code that performs a goto in a tight loop (like recur does), but means you can't assume that method calls in general will be tail call optimized. -Fred -- Science answers questions; philosophy questions answers. On Aug 2, 2010, at 4:09 PM, Dale wrote: The JVM has an unconditional goto opcode and the ability to re-bind function parameters, so why no tail-call optimization? Thanks. Dale -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en -- Omnem crede diem tibi diluxisse supremum. -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
