7 ms·
Tail Calls, Optimization, and ES6
- dgreensp 12y agoIt'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 agoin your second example you just described most async javascript, through it tends to be called "callback"
- findjashua 12y agoNope, 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 agocan'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 agoThe 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 agoThere'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 agoLoops 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 agoThere 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 agoThe 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 agoIt'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.
- yror10 12y agoIf you write ruby and want TCO put this at the top of your .rb file: RubyVM::InstructionSequence.compile_option = { :tailcall_optimization => true, :trace_instruction => false }
- eknkc 12y agoWhy is it optional? What is the benefit of having it disabled by default if there is a decent implementation?
- Tuna-Fish 12y agoA lot of people prefer having complete, explicit stacks for debugger use over having tail calls.
- hajile 12y agoloops don't leave a stack trace either...
- anonova 12y agoThey disabled it for error reporting/debugging reasons. Because you don't need to create a new stack frame, you eliminate that information in the backtrace.
- steveklabnik 12y agoI've seen at least one paper that shows a way to fix this... hm.
- damncabbage 12y agoAnd also apply this patch, if you're using MRI (the C implementation, and the most common Ruby runtime): https://gist.github.com/plexus/11201946 https://gist.github.com/plexus/11201946
- platz 12y agoHow will the affect the debugging of stack frames in javascript programs that utilize TCO?
- cwmma 12y agoin theory it could make them less informative, but I suspect in practice most engines that implement it will figure out a way to make stack frames usable with TCO
- vilhelm_s 12y agoScheme implementations have had to deal with this problem for a long time. (Of course, one can argue that languages with ordinary while loops have a similar problem, in that value of previous iterations of the loop get overwritten by later iterations). 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).
- skybrian 12y agoA tail call is basically goto with arguments. You can use it to build arbitrary extensible state machines. Like a goto, it's useful but potentially confusing. You shouldn't use it when a more structured loop construct will work.
- jacquesm 12y agoIn FP loops are typically frowned upon and then the tail call is presented as an elegant solution, because it can be optimized into a loop but still look like a function call with all the goodies a function call normally gives you, minus the new stack frame. 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.
- jules 12y agoIf you look at it from the perspective of continuations then tail calls are very natural. A function call is always a goto, the only difference is that calls in tail position do not need to add extra data to the continuation.
- skybrian 12y agoOf course! But that still doesn't mean you should use them most of the time. Continuations are great for writing compilers but confusing to use elsewhere. Just like you don't normally write assembly (but it's necessary sometimes), you shouldn't normally use these exceptionally flexible but unstructured abstractions in a program you want other people to read. Instead you want to use constructs that are familiar and easy to reason about. It's hard to beat a for loop.
- 12y ago
- TheLoneWolfling 12y ago...And then there's Python. (Although, amusingly enough, you can actually hack TCO into Python via decorator weirdness)
- SoftwareMaven 12y agoNot TCO. Tail recursion can be optimized, though. See this[1] discussion at LtU. I wish GvR would let TCO through. With TCO, Coffeescript or Clojurescript might become new favorites. 1. http://lambda-the-ultimate.org/node/1331 http://lambda-the-ultimate.org/node/1331
- mck- 12y agoTrampolining is a technique to achieve Tail-call Elimination in ES5 [1] 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.html http://raganwald.com/2013/03/28/trampolines-in-javascript.ht...
- kevingadd 12y agoAnother problem with trampolining in ES5 is that it produces GC pressure; not particularly ideal. TCO in future versions of JavaScript should be a big win, if only in that area.
- justincormack 12y agoApart from knowing if your environment supports TCO which could be an issue.
- esailija 12y agoChallenge accepted https://gist.github.com/petkaantonov/067c5f21395e7fe1f81d https://gist.github.com/petkaantonov/067c5f21395e7fe1f81d
- taylodl 12y agoI blogged about the advantages/disadvantages of trampolines in JavaScript a while back. See http://taylodl.wordpress.com/2013/06/07/functional-javascript-tail-call-optimization-and-trampolines/ http://taylodl.wordpress.com/2013/06/07/functional-javascrip.... I'm preparing to analyze TCO in ES6. I'll do a write up of my analysis.
- jbclements 12y agoThis is absolutely the best news I've had all day. I've been a fierce advocate of proper tail calling since 1999, and I'm incredibly happy to see it gaining traction outside of niche functional languages like Racket. Many, many, many thanks to dherman and jorendorff and all of the others who made this happen. Now, off to brag about this to my PL class!
- JBiserkov 12y agoSo ClojureScript will get TCO before Clojure? (JavaScript would get this before Java) Interesting times we live in.
- Solarsail 12y agoWell, Java does have TCO already, just depending on the JVM you're using. J9 supports it, just not HotSpot. http://stackmonthly.com/2010/9/tail-call-optimization http://stackmonthly.com/2010/9/tail-call-optimization