Recursion, Tail Calls and Trampolines in JavaScript (2015)
datchley.name
datchley.name
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...
What does 'well grown' mean in the context of data types?
- 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-...
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.
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.
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.
The next mysterious term I don't know but is probably overloaded and probably simple is monad.
In a language like C a continuation is... the return address to the caller, and, ipliedly, the caller's frame pointer.
That is, the closure {<return address>, <frame pointer>} is a function of one argument (the value being returned). (When this finally clicked for me, a long time ago, I was astounded by the beauty and obviousness of this idea. Exclamation points abounded in my head.)
call-with-current-continuation (aka, call/cc) in Scheme is basically a reification of the caller's return closure as the "current continuation". To "reify" is a fancy term that means to "make visible an implied value" (the implied value is the return address and frame that is then made available as a first-class value).
So it's all very simple, really.
And if you structure the whole thing as a loop over calling the "current continuation" which then returns the "next current continuation", then you can move all activation frames onto the heap.
But putting each activation frame on the heap is a bit... expensive, as the work the GC has to do greatly increases, as does the amount of garbage (especially if you never call call/cc!). So the next idea is to have "delineated continuations", which... is basically like having a stack for each series of frames delineated by calls to call/cc... which is a lot like... co-routines... which people tend to implement with call/cc...
Now, monads... are a lot like such a loop over calling the current continuation. Normally, in a language like Haskell the order of evaluation of expressions is undefined for optimization reasons, and also in order to force you to have pure functions (or vice versa). Having only pure functions means that the order of evaluation can be left undefined, which increases available opportunities to parallelize, defer computation, etc... But when doing I/O, you kinda need to force some order. Well, a monad is the construct that lets you do that. In a monadic context you can think of the current continuation as not just a simple closure that returns the next current continuation, but as a closure that closes over the current state of the monad, which for the IO monad is actually the state of the world. But it's really still a plain closure at the end of the day -- one that notionally closes over more of the state of the world than a typical closure does.
The loop-over-calling-the-current-continuation concept... kinda fits that description of "trampoline".