Hacker News Reader

Comment by dgreensp | Hacker News Reader

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()".

View on HN

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-aut...

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

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.

* shouldn't throw exceptions

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…

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.

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.

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.

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.

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.

That gives an indication, but not if it sometimes does TCO but not always (like gcc for C).

The point here is the guarantee -- as specified by the language standard. There is no guarantee for TCO in C. The ES6 standard only guarantees the TCO for certain constructs which rapala's example showed (informally).

Reply on news.ycombinator.com