4 ms·

It's important to explain why (or when) TCO is important. You could read a dozen articles like this that explain what a tail call is in simple terms and still

It's important to explain why (or when) TCO is important. You could read a dozen articles like this that explain what a tail call is in simple terms and still not know. The core demographic that cares about TCO is implementers of languages like Scheme, because if you have TCO: * Loops can be written as recursive functions. In Scheme, you don't write loops, you write functions that re-invoke themselves at the end. This is efficient with TCO and impractical without (because the stack grows with every iteration). * You can implement continuations. Imagine if every function took an argument "next", and instead of returning it called "next()". Without TCO, the stack would grow and grow, while with TCO, the old stack frame is torn down when you call "next()".

cwmma 12y ago
in your second example you just described most async javascript, through it tends to be called "callback"
- findjashua 12y ago
  Nope, they're completely different. In OP's second example, each caller function stays on the stack until its next() returns, thus the stack keeps growing in size. In async functions, the caller is thrown off the stack once it hands off the callback to the event loop. This is why a callback can't return values or throw exceptions.
  - cwmma 12y ago
    * shouldn't throw exceptions
    - mattdw 12y ago
      can't throw exceptions that the caller can catch. If an exception falls in the forest, and there's no one there to catch it…
  - russell_h 12y ago
    The problem is that this forces programmers to tightly couple interfaces and implementations. Take for example a cache interface that wraps multiple implementations. The cache might be in-process or it might be a centralized memcached, etc. In order to support both of these, the "get" method must take a key and a callback. But the most reasonable in-process implementation actually grows the stack before calling the callback, while the other implementations reset it. If you iterate a large list of keys, you'll blow the stack with the in-process implementation. So you end up doing things like "setImmediate()" on every get to reset the stack. The "async" library has a neat trick to detect if the callback is called without deferring to the event loop, in which case it does the deferral itself. But in general, programmers are forced to think about these kinds of problems constantly, or hit weird bugs. For example, I once had a periodic task that iterated every account in the database. It began crashing when our database client began returning larger batches, causing iteration not to defer to the event loop.
surrealize 12y ago
There's a nice example from Shriram Krishnamurthi of implementing automata using functions, where the functions represent states and state transitions are just function calls. It's an elegant way of creating automata IMHO, but the efficiency of the approach depends on TCO: http://cs.brown.edu/~sk/Publications/Papers/Published/sk-automata-macros/paper.pdf http://cs.brown.edu/~sk/Publications/Papers/Published/sk-aut...
mantrax5 12y ago
Loops can be written as recursive functions, so that the compiler can use TCO to turn them back into loops... If your language religiously omits loops, it's understandable why you'd need to emulate loops this way, but the alternative solution is: have loops in the language. This leaves us with continuations, which is a great hack, but again, a hack, for languages which don't implement fibers/coroutines/generators natively (see Python generators, see C# await/async, etc.). This is not the path we have to go down to. Layering hacks upon hacks, so we can implement other hacks on top of it. If we need loops, have a language with loops. If we need coroutines, the language should implement coroutines.
- RHSeeger 12y ago
  There are a number of algorithms that, while able to be expressed as loops, are more succinctly expressed recursively. Obviously, the reverse is also true, but having both options in the language means there are more cases where the code is a cleaner expression of the algorithm being implemented.
  - mantrax5 12y ago
    The problem with this is that not every recursion qualifies for a TCO optimization, and when it doesn't, you're in big doodoo if your recursion goes deep. This means a programmer has to tell apart two types of recursion based on how a compiler optimizes them. It's possible to learn, but this qualifies as a "leaky abstraction". It's far better to use loops when you want to loop, and recursion when you want to recurse, and if the compiler happens to use TCO, so be it. But don't rely on TCO. Instead, we see here whole algorithms which depend on TCO to work without filling up the stack. It's a path towards more obscure code, not more succinct code.
    - rapala 12y ago
      It's dead simple to tell apart a tail call. Does it look like return call(a, r, g, s) It is also very simple to test if the compiler does TCO. Just write def f(a): return f(a + 1) f(0) and wait for a stack overflow.

cwmma 12y ago

in your second example you just described most async javascript, through it tends to be called "callback"

findjashua 12y ago
Nope, they're completely different. In OP's second example, each caller function stays on the stack until its next() returns, thus the stack keeps growing in size. In async functions, the caller is thrown off the stack once it hands off the callback to the event loop. This is why a callback can't return values or throw exceptions.
- cwmma 12y ago
  * shouldn't throw exceptions
  - mattdw 12y ago
    can't throw exceptions that the caller can catch. If an exception falls in the forest, and there's no one there to catch it…
- russell_h 12y ago
  The problem is that this forces programmers to tightly couple interfaces and implementations. Take for example a cache interface that wraps multiple implementations. The cache might be in-process or it might be a centralized memcached, etc. In order to support both of these, the "get" method must take a key and a callback. But the most reasonable in-process implementation actually grows the stack before calling the callback, while the other implementations reset it. If you iterate a large list of keys, you'll blow the stack with the in-process implementation. So you end up doing things like "setImmediate()" on every get to reset the stack. The "async" library has a neat trick to detect if the callback is called without deferring to the event loop, in which case it does the deferral itself. But in general, programmers are forced to think about these kinds of problems constantly, or hit weird bugs. For example, I once had a periodic task that iterated every account in the database. It began crashing when our database client began returning larger batches, causing iteration not to defer to the event loop.

surrealize 12y ago

There's a nice example from Shriram Krishnamurthi of implementing automata using functions, where the functions represent states and state transitions are just function calls. It's an elegant way of creating automata IMHO, but the efficiency of the approach depends on TCO: http://cs.brown.edu/~sk/Publications/Papers/Published/sk-automata-macros/paper.pdf http://cs.brown.edu/~sk/Publications/Papers/Published/sk-aut...

mantrax5 12y ago

Loops can be written as recursive functions, so that the compiler can use TCO to turn them back into loops... If your language religiously omits loops, it's understandable why you'd need to emulate loops this way, but the alternative solution is: have loops in the language. This leaves us with continuations, which is a great hack, but again, a hack, for languages which don't implement fibers/coroutines/generators natively (see Python generators, see C# await/async, etc.). This is not the path we have to go down to. Layering hacks upon hacks, so we can implement other hacks on top of it. If we need loops, have a language with loops. If we need coroutines, the language should implement coroutines.

RHSeeger 12y ago
There are a number of algorithms that, while able to be expressed as loops, are more succinctly expressed recursively. Obviously, the reverse is also true, but having both options in the language means there are more cases where the code is a cleaner expression of the algorithm being implemented.
- mantrax5 12y ago
  The problem with this is that not every recursion qualifies for a TCO optimization, and when it doesn't, you're in big doodoo if your recursion goes deep. This means a programmer has to tell apart two types of recursion based on how a compiler optimizes them. It's possible to learn, but this qualifies as a "leaky abstraction". It's far better to use loops when you want to loop, and recursion when you want to recurse, and if the compiler happens to use TCO, so be it. But don't rely on TCO. Instead, we see here whole algorithms which depend on TCO to work without filling up the stack. It's a path towards more obscure code, not more succinct code.
  - rapala 12y ago
    It's dead simple to tell apart a tail call. Does it look like return call(a, r, g, s) It is also very simple to test if the compiler does TCO. Just write def f(a): return f(a + 1) f(0) and wait for a stack overflow.