8 ms·

I guess I don't understand what the big deal is with tail call optimization. Could someone give an example where it really shines and clojure's loop/recur just

I guess I don't understand what the big deal is with tail call optimization. Could someone give an example where it really shines and clojure's loop/recur just doesn't? If you are looking to put time into a programming language that is interesting in and of itself, I'd suggest Haskell.

jnordwick 10y ago
Looping is fine for imperative languages. It should be the norm for performance sensitive things since that is how the CPU works. It is just easier than trying to make a smart compiler turn your recursion into looping constructions. However, for functional languages you really want TCO to work properly so you can write your algorithms in a properly functional way. And you don't just want self-calls to work, but full mutual recursion (A calls B that calls A etc) to be properly optimized too.
- optforfon 10y ago
  the CPU is just doing a jump to an instruction at the end of each iteration. When you do tail call recursion you are doing just that. The assembly jumps to a tag and in recursion you jump to a function name, which is also effectively a tag. So it's not really about mapping better to the CPU instructions or anything like that The added benefit is that with tail call recursion you can have mutually recursive function (function A calls function B at the end and function B calls function A at the end), which isn't possible with a simple iterative loop, so the functional style is actually more powerful than an iterative approach and still maps directly to "the way the CPU works"
  - jnordwick 10y ago
    You are forgetting about the function prologue, epilogue, and the maintenance of the various pointers. It certainly isn't as simple as a jump as you imply. To do proper TCO most implementation resort to function trampolines and other self-modifying trickery to get similar to loop-like performance. Within the confines of the JVM, without doing extensive source analysis, I doubt there is even a way to do it.
    - optforfon 10y ago
      this is outside my field of expertise. Can you give an example of a tail call that needs "trickery"? I'm not 100% on this, but when you have a tail call I don't think you have to remember the state of the stack frame. "function prologue, epilogue, and the maintenance of the various pointers" aren't god given rules - they're things dictated by something like the C ABI so you can resume the caller. So if you're thinking in terms of C ABI then yes, it's a compiler optimization, but in principle I think it's a zero cost abstraction (though I'd argue that the iterative loop is the actual abstraction) In tail call recursion you're ensured the caller will never resume! When you enter a tail-recursive function you save (as you normally would) a return pointer for the program counter and allocate registers/memory for your function arguments. At the end of the function you've done all the computation that that frame will ever do, so you are free to overwrite the argument variables when calling the next iteration/recursive-step. The return pointer doesn't need to be touched at all. Where is the complexity you're talking about?
      - senex 10y ago
        When TCO is "lexically scoped" like loop/recur, the compiler can handle it. When HoF are involved, you may have a case where a procedure calls a procedure-parameter, which calls another, and another... Something about the runtime has to recognize this or else the compiler has to accept more constrains. See, for example, how Gambit-C implements tail calls by compiling modules to single C functions and how there is a trade off for procedure calls across module boundaries versus Chicken Scheme's approach to essentially garbage-collecting the call stack.
        optforfon 10y ago
        Okay, but at that point you're talking about things that are way beyond the capabilities of an iterative loop. I think my point still stands - that implementing a tail recursion in place of a loop is not something you will have to pay for. Both structures will map to the same instructions.
        10y ago
  - deleted 10y ago
    [deleted]
- DigitalJack 10y ago
  I will have to look for mutual recursion support (or lack thereof) in clojure. Clojure's loop/recur is a work-around for some issue with the JVM and lack of fine grained control over the stack. That said, It's not a simple loop, the keyword "loop" is effectively an anonymous function that gets called by the "recur" keyword, with parameters. An example: (loop [iter 1 acc 0] (if (> iter 10) (println acc) (recur (inc iter) (+ acc iter)))) I don't know if that is any different than other lisps or not. In case it's less less than clear, the bracketed portion after the "loop" keyword is an initial binding form (setting iter to 1, and acc to 0), and thereafter iter and acc are just considered parameters. For self recursion, that seems like a fair compromise. No help at all for mutual recursion though.
  - dmichulke 10y ago
    I never had to use it but I recall there was a 'trampoline' fn for mutual recursion
    - smnplk 10y ago
      Exactly. I once read a great article [1] written by Martin Trojer I think, it was about recursion in Clojure. EDIT: [1] https://martintrojer.github.io/clojure/2011/11/20/tail-calls-in-f-clojure-and-scala https://martintrojer.github.io/clojure/2011/11/20/tail-calls...
ufo 10y ago
loop/recur is good for replacing structured loops but tail recursion is more general, since it can replace arbitrary gotos. One example is given by Guy Steele in "Why Object-Oriented Languages need Tail Calls". Basically, tail recursion lets you keep O(1) stack space even in the face of opaque method dispatching in OO code. https://eighty-twenty.org/2011/10/01/oo-tail-calls https://eighty-twenty.org/2011/10/01/oo-tail-calls Another required reading are the "Lambda the Ultimate" papers, if you haven't read them yet. The "GOTO" one is particularly relevant here. http://library.readscheme.org/page1.html http://library.readscheme.org/page1.html
- DigitalJack 10y ago
  Thanks! These must be where the website/blog got its name. I actually thought that was what you were referring to at first.
shiro 10y ago
It's a big deal since it's not really about optimization, but more about the overall coding style and thought process. With TCO, you start seeing functions as composable code blocks rather than something that is called and then return from. State machines are just mutually tail-calling functions---it's not that state machines are written so, but that in your mental model two are the same. And usually a program is humongous multi-layered state machine. Suppose you want to abstract the part of the loop. You just write a generic version that tail-calls user-passed function. Users can extend the loop freely, even interlacing two independent loops by mutually calling them (which can't be done with callback model without consuming stack frames). It's really a matter of style, but for those who get used to think in this way, not having guaranteed TCO is like writing code with one hand tied up in the back.
senex 10y ago
An interesting thing about general tail recursion is that it's composable. Closure's loop/recur is a special case implementation of a common pattern. That's Ok, but it can't extend. Any higher order function in scheme can be parameterized with methods that should be tail recursive. No special language support needed. That's why for-each is a procedure instead of a special form in scheme. This allows libraries (like SFRI-1) or DSLs to be created that expect callers can conform by contract instead of by using special forms. Callers, in turn, can create abstractions over the libraries and DSLs that are equally general, instead of being strongly influenced by what they're built on. Clojure does a really nice job of creating reusable abstractions. From what I understand, tail-call optimization isn't possible in the JVM, so we have iterators and lazy evaluation first-class instead; which has other nice advantages for creating abstractions.
- macmac 10y ago
  Clojure has both recur and trampoline which handle tail calls (in general not just with loop) and trampoline for corecursion: recur: (defn factorial ([n] (factorial n 1)) ([n acc] (if (= n 0) acc (recur (dec n) (* acc n))))) trampoline: (declare is-even?) (defn is-odd? [n] (if (zero? n) false #(is-even? (dec n)))) (defn is-even? [n] (if (zero? n) true #(is-odd? (dec n)))) (trampoline (is-odd? 10000))
  - senex 10y ago
    Yep, and the same can be implemented in any language that supports functions-as-objects (for example, javascript). It's a practical solution/workaround, but isn't quite composable/generalizable as first-class support for TCO (unless the community is willing to follow some convention like "TCO-like behavior is a 'good thing' and so libraries should try to support and interface compatible with `trampoline`". This is a little bit like `function` / yield in newer versions of Javascript. It's not TCO, but it is a strong community convention (with the assist of special syntax to enforce the semantic). Clojure is a great example of how practical/tasteful decisions by language author can create re-usable abstractions that are really powerful (even while at the same time working around limitations of the underlying technology). Some might also argue that TCO is "bad" because it's less debuggable (e.g. when an exception is thrown, the stack trace is gone). We can see the same phenomena with non-blocking IO, for example. So maybe it's a Good Thing to have "less general" semantics in a language (e.g. function, trampoline, and loop/recur may be good-enough while at the same time preserving debuggability). There are always tradeoffs. What's nice about general TCO is that the composibility of unrelated libraries/DSLs is more probable whereas with conventions like trampoline, DSL/library authors need to understand the advantages and design the DSL/library in a compatible way in advance. As Clojure shows with lazy sequences, this can absolutely work given enough community awareness of the convention.
technomancy 10y ago
> Could someone give an example where it really shines and clojure's loop/recur just doesn't? In practice you don't replace TCO with loop/recur; you replace it with lazy sequences. They both solve the "how to work on unbounded data while consuming bounded memory" problem even though at first glance loop/recur seems more similar. Most people who complain about not having TCO have not fully wrapped their heads around lazy sequences.

jnordwick 10y ago

Looping is fine for imperative languages. It should be the norm for performance sensitive things since that is how the CPU works. It is just easier than trying to make a smart compiler turn your recursion into looping constructions. However, for functional languages you really want TCO to work properly so you can write your algorithms in a properly functional way. And you don't just want self-calls to work, but full mutual recursion (A calls B that calls A etc) to be properly optimized too.

optforfon 10y ago
the CPU is just doing a jump to an instruction at the end of each iteration. When you do tail call recursion you are doing just that. The assembly jumps to a tag and in recursion you jump to a function name, which is also effectively a tag. So it's not really about mapping better to the CPU instructions or anything like that The added benefit is that with tail call recursion you can have mutually recursive function (function A calls function B at the end and function B calls function A at the end), which isn't possible with a simple iterative loop, so the functional style is actually more powerful than an iterative approach and still maps directly to "the way the CPU works"
- jnordwick 10y ago
  You are forgetting about the function prologue, epilogue, and the maintenance of the various pointers. It certainly isn't as simple as a jump as you imply. To do proper TCO most implementation resort to function trampolines and other self-modifying trickery to get similar to loop-like performance. Within the confines of the JVM, without doing extensive source analysis, I doubt there is even a way to do it.
  - optforfon 10y ago
    this is outside my field of expertise. Can you give an example of a tail call that needs "trickery"? I'm not 100% on this, but when you have a tail call I don't think you have to remember the state of the stack frame. "function prologue, epilogue, and the maintenance of the various pointers" aren't god given rules - they're things dictated by something like the C ABI so you can resume the caller. So if you're thinking in terms of C ABI then yes, it's a compiler optimization, but in principle I think it's a zero cost abstraction (though I'd argue that the iterative loop is the actual abstraction) In tail call recursion you're ensured the caller will never resume! When you enter a tail-recursive function you save (as you normally would) a return pointer for the program counter and allocate registers/memory for your function arguments. At the end of the function you've done all the computation that that frame will ever do, so you are free to overwrite the argument variables when calling the next iteration/recursive-step. The return pointer doesn't need to be touched at all. Where is the complexity you're talking about?
    - senex 10y ago
      When TCO is "lexically scoped" like loop/recur, the compiler can handle it. When HoF are involved, you may have a case where a procedure calls a procedure-parameter, which calls another, and another... Something about the runtime has to recognize this or else the compiler has to accept more constrains. See, for example, how Gambit-C implements tail calls by compiling modules to single C functions and how there is a trade off for procedure calls across module boundaries versus Chicken Scheme's approach to essentially garbage-collecting the call stack.
      - optforfon 10y ago
        Okay, but at that point you're talking about things that are way beyond the capabilities of an iterative loop. I think my point still stands - that implementing a tail recursion in place of a loop is not something you will have to pay for. Both structures will map to the same instructions.
        10y ago
- deleted 10y ago
  [deleted]
DigitalJack 10y ago
I will have to look for mutual recursion support (or lack thereof) in clojure. Clojure's loop/recur is a work-around for some issue with the JVM and lack of fine grained control over the stack. That said, It's not a simple loop, the keyword "loop" is effectively an anonymous function that gets called by the "recur" keyword, with parameters. An example: (loop [iter 1 acc 0] (if (> iter 10) (println acc) (recur (inc iter) (+ acc iter)))) I don't know if that is any different than other lisps or not. In case it's less less than clear, the bracketed portion after the "loop" keyword is an initial binding form (setting iter to 1, and acc to 0), and thereafter iter and acc are just considered parameters. For self recursion, that seems like a fair compromise. No help at all for mutual recursion though.
- dmichulke 10y ago
  I never had to use it but I recall there was a 'trampoline' fn for mutual recursion
  - smnplk 10y ago
    Exactly. I once read a great article [1] written by Martin Trojer I think, it was about recursion in Clojure. EDIT: [1] https://martintrojer.github.io/clojure/2011/11/20/tail-calls-in-f-clojure-and-scala https://martintrojer.github.io/clojure/2011/11/20/tail-calls...

ufo 10y ago

loop/recur is good for replacing structured loops but tail recursion is more general, since it can replace arbitrary gotos. One example is given by Guy Steele in "Why Object-Oriented Languages need Tail Calls". Basically, tail recursion lets you keep O(1) stack space even in the face of opaque method dispatching in OO code. https://eighty-twenty.org/2011/10/01/oo-tail-calls https://eighty-twenty.org/2011/10/01/oo-tail-calls Another required reading are the "Lambda the Ultimate" papers, if you haven't read them yet. The "GOTO" one is particularly relevant here. http://library.readscheme.org/page1.html http://library.readscheme.org/page1.html

DigitalJack 10y ago
Thanks! These must be where the website/blog got its name. I actually thought that was what you were referring to at first.

shiro 10y ago

It's a big deal since it's not really about optimization, but more about the overall coding style and thought process. With TCO, you start seeing functions as composable code blocks rather than something that is called and then return from. State machines are just mutually tail-calling functions---it's not that state machines are written so, but that in your mental model two are the same. And usually a program is humongous multi-layered state machine. Suppose you want to abstract the part of the loop. You just write a generic version that tail-calls user-passed function. Users can extend the loop freely, even interlacing two independent loops by mutually calling them (which can't be done with callback model without consuming stack frames). It's really a matter of style, but for those who get used to think in this way, not having guaranteed TCO is like writing code with one hand tied up in the back.

senex 10y ago

An interesting thing about general tail recursion is that it's composable. Closure's loop/recur is a special case implementation of a common pattern. That's Ok, but it can't extend. Any higher order function in scheme can be parameterized with methods that should be tail recursive. No special language support needed. That's why for-each is a procedure instead of a special form in scheme. This allows libraries (like SFRI-1) or DSLs to be created that expect callers can conform by contract instead of by using special forms. Callers, in turn, can create abstractions over the libraries and DSLs that are equally general, instead of being strongly influenced by what they're built on. Clojure does a really nice job of creating reusable abstractions. From what I understand, tail-call optimization isn't possible in the JVM, so we have iterators and lazy evaluation first-class instead; which has other nice advantages for creating abstractions.

macmac 10y ago
Clojure has both recur and trampoline which handle tail calls (in general not just with loop) and trampoline for corecursion: recur: (defn factorial ([n] (factorial n 1)) ([n acc] (if (= n 0) acc (recur (dec n) (* acc n))))) trampoline: (declare is-even?) (defn is-odd? [n] (if (zero? n) false #(is-even? (dec n)))) (defn is-even? [n] (if (zero? n) true #(is-odd? (dec n)))) (trampoline (is-odd? 10000))
- senex 10y ago
  Yep, and the same can be implemented in any language that supports functions-as-objects (for example, javascript). It's a practical solution/workaround, but isn't quite composable/generalizable as first-class support for TCO (unless the community is willing to follow some convention like "TCO-like behavior is a 'good thing' and so libraries should try to support and interface compatible with `trampoline`". This is a little bit like `function` / yield in newer versions of Javascript. It's not TCO, but it is a strong community convention (with the assist of special syntax to enforce the semantic). Clojure is a great example of how practical/tasteful decisions by language author can create re-usable abstractions that are really powerful (even while at the same time working around limitations of the underlying technology). Some might also argue that TCO is "bad" because it's less debuggable (e.g. when an exception is thrown, the stack trace is gone). We can see the same phenomena with non-blocking IO, for example. So maybe it's a Good Thing to have "less general" semantics in a language (e.g. function, trampoline, and loop/recur may be good-enough while at the same time preserving debuggability). There are always tradeoffs. What's nice about general TCO is that the composibility of unrelated libraries/DSLs is more probable whereas with conventions like trampoline, DSL/library authors need to understand the advantages and design the DSL/library in a compatible way in advance. As Clojure shows with lazy sequences, this can absolutely work given enough community awareness of the convention.

technomancy 10y ago

> Could someone give an example where it really shines and clojure's loop/recur just doesn't? In practice you don't replace TCO with loop/recur; you replace it with lazy sequences. They both solve the "how to work on unbounded data while consuming bounded memory" problem even though at first glance loop/recur seems more similar. Most people who complain about not having TCO have not fully wrapped their heads around lazy sequences.