Tail Calls, Optimization, and ES6
duartes.org
duartes.org
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()".
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.
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.
http://cs.brown.edu/~sk/Publications/Papers/Published/sk-aut...
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.
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.
return call(a, r, g, s)
def f(a):
return f(a + 1)
f(0)
However, I found this to only work in a linearly recursive algorithm (eg factorial) and not in a bi-directional recursive algorithm (eg tree construction)
I'm thinking TCO in ES6 might solve this problem? Anyone tried?
[1] http://raganwald.com/2013/03/28/trampolines-in-javascript.ht...
I'm preparing to analyze TCO in ES6. I'll do a write up of my analysis.
RubyVM::InstructionSequence.compile_option = {
:tailcall_optimization => true,
:trace_instruction => false
}Now, off to brag about this to my PL class!
Like a goto, it's useful but potentially confusing. You shouldn't use it when a more structured loop construct will work.
I'm really not convinced of this, it looks like a function call but it is a loop. If it is a loop under the hood then I'd like to see that loop, in my mind I always see this 'stackoverflow' neon sign hover over every tail call (of course it doesn't but years of debugging stuff have ingrained all kinds of interesting detection habits).
Making it look like a loop would introduce all kinds of syntactical complexity, and suddenly you'd be re-using your local variables. So that's not a solution either. But it feels a bit like a kludge.
Instead you want to use constructs that are familiar and easy to reason about. It's hard to beat a for loop.
There's nothing wrong with using the more powerful tools when you need them (such as when implementing the more restricted tools). It's just that needing them frequently is a sign that you're doing weird things and should take a second look at your design to make sure there isn't a better way to do things.
Every function call is "goto with arguments". Sometimes there's even an argument that tells the code block where to jump back to when it's done.
>Like a goto, it's useful but potentially confusing.
How is it confusing? You don't even have to be aware of TCO to take advantage of it. Many recursive algorithms are tail-call-optimizable out of the box.
>You shouldn't use it when a more structured loop construct will work.
Ironically, there are many programmers who consider loops to be too low-level and unstructured compared to recursive algorithms.
http://www.lua.org/pil/6.3.html
It's a nice example because it's simple, it doesn't confuse/intermix the concept with recursion, and it's an effective solution because it allows you to achieve the goal of moving to rooms (i.e. s state machine) elegantly. And in a language without proper tail recursion, it is easy to envision how you could accidentally blow up the call stack.
In the lowest level, yes, but you could say the same about regular function calls, return statements, and even loops and conditionals, break and continue, etc.
The main selling point of using recursion for looping, IMO, is immutability. As jacquesm said, you don't need mutable local variables to track the state of the loop.
And in the real world functional programming you rarely use recursion to replace a loop, you mostly use abstractions like map/reduce/etc along with lambdas, etc.
Also, avoiding mutation of local variables is a poor reason to prefer recursion. Mutable local variables are harmless so long as they don't escape (as in a closure). If the inputs and outputs are immutable then it's still a pure function. You can use them if it makes the program simpler and/or faster and the program as a whole is just as pure.
It's really too bad that functional languages avoid mutable local variables; it would make the divide between imperative and functional languages easier to jump.
Erm, that's not really true is it? Isn't the main way which TCO is (usually? always?) done by introducing a counter/accumulator?
It does alleviate the kind of thing you see in c (or other similar languages):
while(int i = 0; i++; i < 10)
{
i--; // whoops
blah();
}
So not having TCO is generally a way to avoid local state variables (but an ever expanding, eventually overflowing stack), implementing TCO tends to re-introduce a counter to avoid growing the stack (and then you have clever ways to emulate stack frames based on how far you got in the loop... sort of giving you the best (and/or worst) of both worlds).
Anyway, if all you want is a safe loop construct, recursion isn't the only option.
(All that said, I like the elegance of "lets pretend the call stack is infinite"-recursion -- and like the idea of TCO. Just don't oversell it.)
> Erm, that's not really true is it? Isn't the main way which TCO is done by introducing a counter/accumulator?
Yes, but accumulators aren't mutable. You're just passing something like acc*n or acc+1 to the tail call... acc is still the same.
Also, accumulators are not analogous to loop counters, they're more like the "sum" variable in this example (also mutable):
var list = [0,1,2,3];
var sum = 0;
for (var i = 0; i < list.length; i++)
sum += list[i];
I agree! The point of having TCO in a language isn't replacing every for/while loop with recursion. TCO is just an optimization. The right way (at least IMO and IME) is using better abstractions, like you mentioned. Recursion is just a way of easily building those abstractions, as are loops.
Btw, I probably write way more recursive functions in C than I do in Haskell, because in Haskell I have folds and catamorphisms.
I mean, the idiomatic way of summing those numbers as I did above in functional style is probably this:
[0,1,2,3].reduce(function(a,b){return a+b;}, 0);
sum [0,1,2,3]
This is anecdotal, but some reasons, goto labels are not as well named as function names. With a goto it is more difficult to guess what data the destination code is expected to touch.
Tail calls are an improvement on both the counts. I often do not have to break context from reading a piece of code to start reading the piece of code that the program counter jumps to (unless it is a very local jump). The arguments passed by a tail call and the name of the function that has been tail called often makes (i) breaking code reading context less necessary and (ii) make larger semantic jumps remain within realms of easy human reasoning. With gotos, the jumps better be within 20 lines of text.
You can alleviate it by hanging on to stack frames for a while. Scheme48 heap-allocates stack frames, and then relies on garbage collection to reclaim space from tail-calls, so this happens automatically. And MIT Scheme uses a ring-buffer to keep around the last 10-or-so frames. (Actually it is even nicer than that: it uses ringbuffer-of-ringbuffers to keep 10-or-so frames from each of the last 10-or-so non-tail recursive calls. So when debugging you can pop up the call stack, and then at each level examine the last couple interations of the loops done at that level).
(Although, amusingly enough, you can actually hack TCO into Python via decorator weirdness)
I wish GvR would let TCO through. With TCO, Coffeescript or Clojurescript might become new favorites.