4 ms·
Recursion, Tail Calls and Trampolines in JavaScript (2015)
- Tistron 9y agoAs ES6 is becoming more available, how do current browsers handle this now? Do they reuse the stack frame?
- amichal 9y agohttps://www.chromestatus.com/feature/5516876633341952 https://www.chromestatus.com/feature/5516876633341952
- soegaard 9y agoChrome has removed support for tail recursion (it was briefly enabled). Does anybody know if there are plans to reenable it? Or are they still lobbying for an explicit keyword approach?
- baron816 9y agoNo. Last I heard, they were trying to remove proper tail calls from the spec completely. Safari, I believe, is the only browser where it is currently implemented.
- goatlover 9y agoWhy? I recall when ES6 first came out, Crockford gave a talk on the good and bad of it. He hated that classes were brought into the language, but was super bullish on tail calls, saying it was the most important new feature.
- baron816 9y agoYou’re going to have to ask the Chrome and Firefox teams about that. I’m guessing there’s performance issues—perhaps every function invocation needs to check if it’s a proper tail call?
- krzkaczor 9y agoI made a babel plugin to do TCO in JS https://github.com/krzkaczor/babel-plugin-tailcall-optimization https://github.com/krzkaczor/babel-plugin-tailcall-optimizat...
- ryanpetrich 9y agoThanks for writing it! Reading the source was an easy intro to babel for me when I was writing a trampoline-based TCO plugin.
- bad_user 9y agoIn case you need a trampoline, it's more comfortable to use a well grown data type. Here's mine ... Eval, a data-type for handling synchronous evaluation: https://funfix.org/api/effect/classes/eval.html https://funfix.org/api/effect/classes/eval.html IO, a data-type for suspending side effects, including asynchronous ones, an FP/lawful replacement for Promise; ported from Haskell, but better: https://funfix.org/api/effect/classes/io.html https://funfix.org/api/effect/classes/io.html Also note that Promise's implementation leaks memory in "then" chains, so be cautious when using Promises to work around JavaScript's call-stack — https://alexn.org/blog/2017/10/11/javascript-promise-leaks-memory.html https://alexn.org/blog/2017/10/11/javascript-promise-leaks-m...
- chrisseaton 9y ago> use a well grown data type What does 'well grown' mean in the context of data types?
- bad_user 9y agoLawful.
- chrisseaton 9y agoI've heard of lawful but never 'well grown' - where does the term come from?
- Patient0 9y agoThis explanation with examples in Python is also pretty awesome IMHO: https://eli.thegreenplace.net/2017/on-recursion-continuations-and-trampolines/ https://eli.thegreenplace.net/2017/on-recursion-continuation...
- dahart 9y agoThis is the first time I completely understand what thunks and trampolines are. For some reason I always thought a thunk was some mysterious kind of closure that wasn't quite a closure. But a bind() that sends all the expected arguments is a thunk. It's very simple, I'm not sure why it hadn't quite crystallized before. It is worth pointing out that large recursions can often be easily turned into iterative code by pre-allocating your own pseudo-stack from the heap, as long as you have a reasonable maximum upper bound size. The pseudo-stack is just an array that holds only the recursion state you need. Plus, this works even if you have branching recursion and need backtracking. Recursive flood fill is a good example, this can be done by allocating another image as the stack, and then doing the recursion via iteration and storing the backtracking coordinates in the (image) stack. Both safe and fast.
- cryptonector 9y agoA trampoline is a loop that iteratively invokes thunk-returning functions. That's a description of a very common technique for implementing, e.g., Schemes. It is described in, for example, LISP in Small Pieces. But we don't usually call that a "thunk" so much as a "continuation". It's just a function (closure, generally, but the state it closes over can be passed in explicitly, which is what is done when compiling to C, naturally) that does one step of a computation and returns a continuation to do the next step. The main point of this is that you can start allocating your true function activation frames on a heap and mostly lose the stack. This then allows one to do crazy things like return multiple times through the same path (search for call/cc). Having different terms for the same concepts is a fact of life in this industry.
- dahart 9y agoYep, overloaded language is common, and I've heard about continuations as well. First time I heard about thunks (a looong time ago) was in my 2nd year CS class that was taught in Scheme. I implemented one, and still never quite grokked what it was. The term continuation was being used as well, and I didn't know if it was the same thing or different. I hadn't heard of trampolines until fairly recently. The next mysterious term I don't know but is probably overloaded and probably simple is monad.
- _greim_ 9y agoNit regarding proper tail calls versus tail call optimization: As I understand, JS maybe will be getting the former but not necessarily the latter. I.e., you'd avoid blowing the call stack, but not necessarily get a dramatic speed boost just for moving something to tail position.
- bcherny 9y agoFor the record, many implementors are against STC and PTC for a few reasons: - It may be significantly slower than regular recursive calls (though this claim seems to be false both in practice and theory) - It may break debug tools - It may break browser telemetry (especially on IE) Additionally, they would have to decide on an explicit syntax for STC (return.tail or something like that). Personally, I would love to see STC anf PTC land so I can write proper functional code in JS. It would also make functional programming in JS easier to teach (less gotchas). See TC39 discussion: https://github.com/rwaldron/tc39-notes/blob/master/es7/2016-05/may-24.md#syntactic-tail-calls-bt https://github.com/rwaldron/tc39-notes/blob/master/es7/2016-...