Recursion, Tail Calls and Trampolines in JavaScript (2015)

http://www.datchley.name/recursion-tail-calls-and-trampolines/

by mweibel • 9 years ago

90 24 9 years ago

datchley.name

Tistron• 9 years ago

As ES6 is becoming more available, how do current browsers handle this now? Do they reuse the stack frame?

amichal• 9 years ago

https://www.chromestatus.com/feature/5516876633341952

soegaard• 9 years ago

Chrome 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?

baron8162• 9 years ago

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

krzkaczor• 9 years ago

I made a babel plugin to do TCO in JS https://github.com/krzkaczor/babel-plugin-tailcall-optimizat...

ryanpetrich• 9 years ago

Thanks for writing it! Reading the source was an easy intro to babel for me when I was writing a trampoline-based TCO plugin.

bad_user2• 9 years ago

In 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

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

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

chrisseaton2• 9 years ago

use a well grown data type

What does 'well grown' mean in the context of data types?

bad_user2• 9 years ago

Lawful.

Patient0• 9 years ago

This explanation with examples in Python is also pretty awesome IMHO: https://eli.thegreenplace.net/2017/on-recursion-continuation...

dahart2• 9 years ago

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

cryptonector4• 9 years ago

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

dahart2• 9 years ago

Yep, 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.

kazinator• 9 years ago

A loop which dispatches closures can implement cross module tail recursion (absent of continuations). Function A wants to call B. Instead of a direct call, it performs a dynamic return to the loop, passing it B and the arguments to be applied to B (wrapped up as a closure, or other object).

This shouldn't be called a trampoline; it's just a dispatch loop.

Trampolines are a technique for turning function pointers into closures. GCC uses trampolines for pointers to nested functions.

The trampoline mechanism constructs a piece of machine code on the stack (or possibly elsewhere). Next to that machine code at some fixed offset, there is the closure info: the real function plus context. The trampoline is referenced by the pointer to the code: a low level function pointer, compatible with C function pointers and the like. When that is called, it retrieves the closure info (via instruction-pointer-relative addressing) and calls the real target function.

cryptonector4• 9 years ago

Also, a trampoline is a very different thing in the contexts I'm used to. Typically it's a bit of executable object code generated on the fly to bridge something. The most obvious examples are: trampolines used in signal handling on Unix systems, the trampolines generated by GCC for local functions (closures of dynamic extent), and trampolines used in schedulers to switch tasks on CPU.

The loop-over-calling-the-current-continuation concept... kinda fits that description of "trampoline".

_greim_2• 9 years ago

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

wahern• 9 years ago

I thought "optimization" in tail call optimization refers to optimizing memory usage--eagerly discard or reuse the frame upon a tail call.

_greim_2• 9 years ago

There's also speed gains to be had from re-using frames instead of creating new ones in some languages, but this is a fair point.

bcherny• 9 years ago

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

Recursion, Tail Calls and Trampolines in JavaScript (2015)

Related Stories