18 ms·

Trampolines in JavaScript

157 points by austengary 13y ago

IgorPartola 13y ago
Very interesting and a nice hack. However, since you are already using a while loop, you might as well do this: function factorial(n) { for (var res = 1; n > 0; n--) { res *= n; } return res; } Simple, shorter, no overhead from function calls, etc.
- anaphor 13y ago
  Not really the point, the point is to gain explicit control over the call stack so you can have more flexibility. Also I would not really call it a hack, it's something you can do with many languages that support higher-order functions.
- raganwald 13y ago
  You know, this is the canonical programmer missing the forest by arguing the shape of the leaf on a tree. The point is to discuss the mechanism, and factorial happens to be a ridiculously simple example. Perhaps what the article needs is a disclaimer such as: We can easily rewrite this in iterative style, but there are other functions that aren’t so amenable to rewriting and using a simple example allows us to concentrate on the mechanism rather than the “domain.” ;-)
  - IgorPartola 13y ago
    Exactly. My point is that the factorial function is always used as an example when discussing tail call optimization and TCO is useless for it. I get how this is useful. I just would love to see an example of actually using it for something other than calculating factorials.
    - jfb 13y ago
      I understand this sentiment, but what simple zero-context function would you choose in place of factorial? You'd want something that's trivially and naturally recursive that doesn't also act on non-primitive types (to avoid having to do a bunch of blahblah introducing the particulars of a given data structure).
      - IgorPartola 13y ago
        How about merge sort or quicksort? Or maybe a binary search? Seems a little more real-worldy. I suppose factorial is a good starting point to illustrate how to construct the function, but an example or two of an actual use case would be so so great.
        jerf 13y ago
        "merge sort or quicksort? Or maybe a binary search?" OK, but couldn't you then still complain that each of those are "Simple, shorter, no overhead from function calls, etc." as while loops?
        IgorPartola 13y ago
        You might. The problem with doing a binary search in a while loop is that now you have to actually maintain your own stack, which to me seems like it should be left to the runtime. The point of using a recursion is that you can do the same thing as a loop but with less code. Mostly, the problem is that no developer in the last 10 years has ever had to write an efficient factorial function except in a job interview or for a blog post. That is slightly less the case with sorts and searches.
        mck- 13y ago
        Agreed -- I would love to see an example of a binary tree. As a matter of fact, I was struggling with Stack Overflow problems when constructing huge kd-trees recursively. I read this article a week ago, but failed to translate the pure recursive formulation of constructing a tree into a tail-recursive one -- since the recursion goes two ways instead of one Here's an example from Wikipedia: function kdtree (list of points pointList, int depth) { // Select axis based on depth so that axis cycles through all valid values var int axis := depth mod k; // Sort point list and choose median as pivot element select median by axis from pointList; // Create node and construct subtrees var tree_node node; node.location := median; node.leftChild := kdtree(points in pointList before median, depth+1); node.rightChild := kdtree(points in pointList after median, depth+1); return node; }
  - phpnode 13y ago
    I found your post interesting (just like all your other posts), but for me where this one falls short is the lack of real life examples. I mean I understand why this would be good for calculating factorials and other kinds of recursive math, but how often does the average javascript programmer need to do that anyway? How can I benefit from this to write better code in practise, and not just in theory? To me this is far less obvious than with, for example, your article on decorator functions [0]. [0] http://raganwald.com/2013/01/03/function_and_method_decorators.html http://raganwald.com/2013/01/03/function_and_method_decorato...
    - chriswarbo 13y ago
      Trampolining is one way to implement "tail call optimisation". This basically means that when the last instruction (the "tail") of a function is a call to another function (possibly the same one, recursively), then we can perform an optimisation: rather than "going down" into the function (adding a new stack frame) we can run it where we already are (in our current stack frame). This optimisation is possible because we know that we don't need our current stack frame anymore, since this is the last instruction. Ever find yourself writing a "main loop" full of unrelated code which only appears in the same place because you're forced to keep it all between the loop's braces? That's a prime candidate for mutual recursion, made safe using tail-call optimisation: var foo = function() { // }; var bar = function() { // }; var baz = function() { // }; var main = function() { while (true) { foo(); bar(); baz(); } }; main(); Can be replaced with: var foo = function() { // bar(); }; var bar = function() { // baz(); }; var baz = function() { // foo(); }; foo(); This is how I tend to write Javascript; although I generally handle tail-call optimisation by using setTimeout(foo, 0), which has the same effect.
      - IgorPartola 13y ago
        Not the same effect. setTimeout() will execute the callback after the main event loop has completed, potentially allowing the browser to reflow the page, etc. Doing that will slow things down considerably with lots of callbacks.
      - 13y ago
- samatman 13y ago
  Awesome! Could you show me how to write a parser combinator in this fashion?
misterdata 13y ago
This works even better with ES6 generators: https://github.com/pixelspark/dispatch.js https://github.com/pixelspark/dispatch.js
- teamonkey 13y ago
  Doesn't ES6 have tail calls anyway?
anonymoushn 13y ago
Creating a new function for every tail call seems a bit awful. It's a shame that the more performant alternatives are ridiculously ugly.
- badman_ting 13y ago
  Right, plus how is someone supposed to come in, look at the resulting code, and figure out how it works? Functions wrapped in functions wrapped in functions. (Remember, this is supposed to be the "ridiculously simple" case.) On the other hand, we do a lot of wrapping things in functions in JS-land, so this probably says more about the state of the art than anything.
  - justincormack 13y ago
    A trampolined state machine reads OK, where each state is the next transition function. But generally, you want tail recursion...
- darkstalker 13y ago
  I wonder why JS doesn't implement tail calls. Lot of effort has has been made optimizing JS engines, but not for this case.
imurray 13y ago
Did you know that “bookkeeping” is the only word in the English language containing three consecutive letter pairs? You’re welcome. Huh. Seems that's pretty much true. Occasionally people don't hyphenate sweettoothed. grep '$.$\1$.$\2$.$\3' word_list
- justincormack 13y ago
  And subbookkeeper has four...
- ArbitraryLimits 13y ago
  I always thought the Encyclopedia Brown case whose solution hinged on the villain's not knowing that was far-fetched. http://brownencyclopedia.tumblr.com/post/33647027942/the-case-of-the-hard-luck-boy http://brownencyclopedia.tumblr.com/post/33647027942/the-cas...
RyanMcGreal 13y ago
Sidenote: when you run the recursive function factorial(1000), Node.js returns "Infinity".
- dmm 13y ago
  Because javascript has only one numerical type: double float?
  - wging 13y ago
    > fact(1000) Infinity > fact(10000000) RangeError: Maximum call stack size exceeded
jheriko 13y ago
i've never been much of a fan of this 'fancy new terminology' and generally learn it as needed... however, there are two things i find scary here - and really both are the same thing - the idea that a stack frame is something that is not known about - that solving the endless stack frame problem requires tail-call elimination or any other specific optimisation that leaves the code in recursive form this reminds me of this section in the Michael Abrash programming black book - http://www.phatcode.net/res/224/files/html/ch59/59-04.html#Heading8 http://www.phatcode.net/res/224/files/html/ch59/59-04.html#H... i was shocked at that as well tbh. unrolling that particular recursion by understanding how functions work is something i just did once without any special thought many years before encountering this book... i assumed that programmers generally understand how to implement everything they use, or at least have a deep curiosity about that - but this is a flawed assumption. now, re writing recursive code to be iterative is something that i know from experience that programmers will shy away from until they get to grips with it. like many tasks it turns out that its both quick and easy and infact always possible, however before learning this they will worry it will be difficult or will take days. its such an easy task a dumb old computer can do it when it compiles your code after all... a human brain should have no problem (!) if you implement your own stack based iterative method the equivalent to tail-call optimisation falls out naturally without needing to change the inner loop whatsoever (you literally end up writing code like c=a a=b c=a and realise you can omit a) the result is nothing nearly as complicated or expensive as trampolining - although it is a bit unreadable by my standards - implementing trampolining as this article suggests is just as messy or worse.
nonchalance 13y ago
we need space O<em>n</em> for all those stack frames Why not use the normal O(n) notation?
crazygringo 13y ago
Genuine question, and this seems to be as good a place as any to ask it. I understand the concepts behind functional programming, and trying to implement them in JavaScript (recently read Functional JavaScript too). But from my experience, functional programming is mainly useful for parallelization/distribution of computation, because it's essentially mathematical -- functional code tends to be harder to write, understand, and debug, but you do it when you need to be able to split up computation. Kind of like assembly is harder than C++, but you do it when you need 100% optimized computation in a section of your program. But because there is obviously no multithreading in JavaScript, I've never found a compelling reason to use the FP paradigm in JavaScript. Can anyone enlighten me as to real-world situations where FP makes sense in JavaScript, either client- or server-side? Particularly in web-based projects, which is obviously what JS is for?
- sluukkonen 13y ago
  Small steps. Just using some simple functional constructs like `map` and `filter` will do wonders for your code. You don't have to start writing everything in a purely functional manner to benefit from it.
  - crazygringo 13y ago
    Oh, for sure -- I use map/filter/reduce/etc. whenever I can when they result in cleaner/shorter code. They're great. I'm asking more about things like tail-call recursion/trampolining, function decoration -- making the "architecture" of your program more functional, rather than just a few lines here or there.
    - cgag 13y ago
      Recursion isn't really hard once you get used to it, and often leads to shorter/cleaner code. Map/filter/reduce are themselves very clearly expressed using recursion.
  - mpyne 13y ago
    Indeed, I've started using many functional concepts in a Perl program I maintain. Functional code isn't just good for concurrency, it also helps when trying to reason about lists and associative containers at a higher level.
taylodl 13y ago
Trampolines are okay, but JavaScript still needs an actual TCO. In this blog post http://taylodl.wordpress.com/2013/06/07/functional-javascript-tail-call-optimization-and-trampolines/ http://taylodl.wordpress.com/2013/06/07/functional-javascrip... I look into the performance of trampolines compared to the normal recursive form. Trampolines perform worse. Moreover, TCO was invented to overcome the performance issues associated with recursive implementations, meaning trampolines perform much worse than TCO.
deleted 13y ago
[deleted]
erjiang 13y ago
Here is an example of trampolining in a Scheme interpreter I wrote in JavaScript: https://github.com/erjiang/foxscheme/blob/master/src/system/interpreter.js#L241 https://github.com/erjiang/foxscheme/blob/master/src/system/... This way, interesting Scheme programs can be written without using the small JavaScript stack. It uses an infinite loop that's broken out of by throwing an exception. There are also some other tricks that it uses to allow other things to happen on the page while it runs your program.
- tcdowney 13y ago
  Looks like Friedman taught you well. :)
bsaul 13y ago
Very interesting article. But then, frankly, if you're ever in the need for that kind of things, why don't you make yourself a favor and stop using javascript (especially on the server, where there are plenty other alternatives) ? I mean, if someone comes to me with some server code running a "trampoline" library so that he can perform tail-call optimization in javascript on node.js , he really better have some extremely good justification.
- tracker1 13y ago
  definitely true... If you're doing CPU intensive stuff in node, you should consider the following... worker script(s) (generic-pool helps too), with .fork(), refactoring the loop to use an async response with setImmediate, or converting to a binary module. Example: https://github.com/tracker1/node-js-scrypt/blob/master/lib/scrypt-async.js https://github.com/tracker1/node-js-scrypt/blob/master/lib/s...
mhewett 13y ago
You don't seem to be gaining much from this, at least in JavaScript. The Jatha small LISP library that hasn't been updated since 2007 returns factorial(32768) in 5 seconds on a middling machine. (Disclosure: I'm the author of Jatha)
numlocked 13y ago
Hopefully this will be a bit less painful if/when TCO makes its way into ECMAScipt 6 ("Harmony") as it is slated to do: http://wiki.ecmascript.org/doku.php?id=harmony:proper_tail_calls http://wiki.ecmascript.org/doku.php?id=harmony:proper_tail_c... Regardless, this was an excellent introduction to trampolining.
PotatoPotato 13y ago
jQuery script to fix that whole article: $("body").html($("body").html().replace(/rampol/g, "rambapol")); Happy Friday Everyone!

157 points by austengary 13y ago

Very interesting and a nice hack. However, since you are already using a while loop, you might as well do this: function factorial(n) { for (var res = 1; n > 0; n--) { res *= n; } return res; } Simple, shorter, no overhead from function calls, etc.

anaphor 13y ago
Not really the point, the point is to gain explicit control over the call stack so you can have more flexibility. Also I would not really call it a hack, it's something you can do with many languages that support higher-order functions.
raganwald 13y ago
You know, this is the canonical programmer missing the forest by arguing the shape of the leaf on a tree. The point is to discuss the mechanism, and factorial happens to be a ridiculously simple example. Perhaps what the article needs is a disclaimer such as: We can easily rewrite this in iterative style, but there are other functions that aren’t so amenable to rewriting and using a simple example allows us to concentrate on the mechanism rather than the “domain.” ;-)
- IgorPartola 13y ago
  Exactly. My point is that the factorial function is always used as an example when discussing tail call optimization and TCO is useless for it. I get how this is useful. I just would love to see an example of actually using it for something other than calculating factorials.
  - jfb 13y ago
    I understand this sentiment, but what simple zero-context function would you choose in place of factorial? You'd want something that's trivially and naturally recursive that doesn't also act on non-primitive types (to avoid having to do a bunch of blahblah introducing the particulars of a given data structure).
    - IgorPartola 13y ago
      How about merge sort or quicksort? Or maybe a binary search? Seems a little more real-worldy. I suppose factorial is a good starting point to illustrate how to construct the function, but an example or two of an actual use case would be so so great.
      - jerf 13y ago
        "merge sort or quicksort? Or maybe a binary search?" OK, but couldn't you then still complain that each of those are "Simple, shorter, no overhead from function calls, etc." as while loops?
        IgorPartola 13y ago
        You might. The problem with doing a binary search in a while loop is that now you have to actually maintain your own stack, which to me seems like it should be left to the runtime. The point of using a recursion is that you can do the same thing as a loop but with less code. Mostly, the problem is that no developer in the last 10 years has ever had to write an efficient factorial function except in a job interview or for a blog post. That is slightly less the case with sorts and searches.
      - mck- 13y ago
        Agreed -- I would love to see an example of a binary tree. As a matter of fact, I was struggling with Stack Overflow problems when constructing huge kd-trees recursively. I read this article a week ago, but failed to translate the pure recursive formulation of constructing a tree into a tail-recursive one -- since the recursion goes two ways instead of one Here's an example from Wikipedia: function kdtree (list of points pointList, int depth) { // Select axis based on depth so that axis cycles through all valid values var int axis := depth mod k; // Sort point list and choose median as pivot element select median by axis from pointList; // Create node and construct subtrees var tree_node node; node.location := median; node.leftChild := kdtree(points in pointList before median, depth+1); node.rightChild := kdtree(points in pointList after median, depth+1); return node; }
- phpnode 13y ago
  I found your post interesting (just like all your other posts), but for me where this one falls short is the lack of real life examples. I mean I understand why this would be good for calculating factorials and other kinds of recursive math, but how often does the average javascript programmer need to do that anyway? How can I benefit from this to write better code in practise, and not just in theory? To me this is far less obvious than with, for example, your article on decorator functions [0]. [0] http://raganwald.com/2013/01/03/function_and_method_decorators.html http://raganwald.com/2013/01/03/function_and_method_decorato...
  - chriswarbo 13y ago
    Trampolining is one way to implement "tail call optimisation". This basically means that when the last instruction (the "tail") of a function is a call to another function (possibly the same one, recursively), then we can perform an optimisation: rather than "going down" into the function (adding a new stack frame) we can run it where we already are (in our current stack frame). This optimisation is possible because we know that we don't need our current stack frame anymore, since this is the last instruction. Ever find yourself writing a "main loop" full of unrelated code which only appears in the same place because you're forced to keep it all between the loop's braces? That's a prime candidate for mutual recursion, made safe using tail-call optimisation: var foo = function() { // }; var bar = function() { // }; var baz = function() { // }; var main = function() { while (true) { foo(); bar(); baz(); } }; main(); Can be replaced with: var foo = function() { // bar(); }; var bar = function() { // baz(); }; var baz = function() { // foo(); }; foo(); This is how I tend to write Javascript; although I generally handle tail-call optimisation by using setTimeout(foo, 0), which has the same effect.
    - IgorPartola 13y ago
      Not the same effect. setTimeout() will execute the callback after the main event loop has completed, potentially allowing the browser to reflow the page, etc. Doing that will slow things down considerably with lots of callbacks.
    - 13y ago
samatman 13y ago
Awesome! Could you show me how to write a parser combinator in this fashion?

misterdata 13y ago

This works even better with ES6 generators: https://github.com/pixelspark/dispatch.js https://github.com/pixelspark/dispatch.js

teamonkey 13y ago
Doesn't ES6 have tail calls anyway?

anonymoushn 13y ago

Creating a new function for every tail call seems a bit awful. It's a shame that the more performant alternatives are ridiculously ugly.

badman_ting 13y ago
Right, plus how is someone supposed to come in, look at the resulting code, and figure out how it works? Functions wrapped in functions wrapped in functions. (Remember, this is supposed to be the "ridiculously simple" case.) On the other hand, we do a lot of wrapping things in functions in JS-land, so this probably says more about the state of the art than anything.
- justincormack 13y ago
  A trampolined state machine reads OK, where each state is the next transition function. But generally, you want tail recursion...
darkstalker 13y ago
I wonder why JS doesn't implement tail calls. Lot of effort has has been made optimizing JS engines, but not for this case.

imurray 13y ago

Did you know that “bookkeeping” is the only word in the English language containing three consecutive letter pairs? You’re welcome. Huh. Seems that's pretty much true. Occasionally people don't hyphenate sweettoothed. grep '$.$\1$.$\2$.$\3' word_list

justincormack 13y ago
And subbookkeeper has four...
ArbitraryLimits 13y ago
I always thought the Encyclopedia Brown case whose solution hinged on the villain's not knowing that was far-fetched. http://brownencyclopedia.tumblr.com/post/33647027942/the-case-of-the-hard-luck-boy http://brownencyclopedia.tumblr.com/post/33647027942/the-cas...

RyanMcGreal 13y ago

Sidenote: when you run the recursive function factorial(1000), Node.js returns "Infinity".

dmm 13y ago
Because javascript has only one numerical type: double float?
- wging 13y ago
  > fact(1000) Infinity > fact(10000000) RangeError: Maximum call stack size exceeded

jheriko 13y ago

i've never been much of a fan of this 'fancy new terminology' and generally learn it as needed... however, there are two things i find scary here - and really both are the same thing - the idea that a stack frame is something that is not known about - that solving the endless stack frame problem requires tail-call elimination or any other specific optimisation that leaves the code in recursive form this reminds me of this section in the Michael Abrash programming black book - http://www.phatcode.net/res/224/files/html/ch59/59-04.html#Heading8 http://www.phatcode.net/res/224/files/html/ch59/59-04.html#H... i was shocked at that as well tbh. unrolling that particular recursion by understanding how functions work is something i just did once without any special thought many years before encountering this book... i assumed that programmers generally understand how to implement everything they use, or at least have a deep curiosity about that - but this is a flawed assumption. now, re writing recursive code to be iterative is something that i know from experience that programmers will shy away from until they get to grips with it. like many tasks it turns out that its both quick and easy and infact always possible, however before learning this they will worry it will be difficult or will take days. its such an easy task a dumb old computer can do it when it compiles your code after all... a human brain should have no problem (!) if you implement your own stack based iterative method the equivalent to tail-call optimisation falls out naturally without needing to change the inner loop whatsoever (you literally end up writing code like c=a a=b c=a and realise you can omit a) the result is nothing nearly as complicated or expensive as trampolining - although it is a bit unreadable by my standards - implementing trampolining as this article suggests is just as messy or worse.

nonchalance 13y ago

we need space O<em>n</em> for all those stack frames Why not use the normal O(n) notation?

crazygringo 13y ago

Genuine question, and this seems to be as good a place as any to ask it. I understand the concepts behind functional programming, and trying to implement them in JavaScript (recently read Functional JavaScript too). But from my experience, functional programming is mainly useful for parallelization/distribution of computation, because it's essentially mathematical -- functional code tends to be harder to write, understand, and debug, but you do it when you need to be able to split up computation. Kind of like assembly is harder than C++, but you do it when you need 100% optimized computation in a section of your program. But because there is obviously no multithreading in JavaScript, I've never found a compelling reason to use the FP paradigm in JavaScript. Can anyone enlighten me as to real-world situations where FP makes sense in JavaScript, either client- or server-side? Particularly in web-based projects, which is obviously what JS is for?

sluukkonen 13y ago
Small steps. Just using some simple functional constructs like `map` and `filter` will do wonders for your code. You don't have to start writing everything in a purely functional manner to benefit from it.
- crazygringo 13y ago
  Oh, for sure -- I use map/filter/reduce/etc. whenever I can when they result in cleaner/shorter code. They're great. I'm asking more about things like tail-call recursion/trampolining, function decoration -- making the "architecture" of your program more functional, rather than just a few lines here or there.
  - cgag 13y ago
    Recursion isn't really hard once you get used to it, and often leads to shorter/cleaner code. Map/filter/reduce are themselves very clearly expressed using recursion.
- mpyne 13y ago
  Indeed, I've started using many functional concepts in a Perl program I maintain. Functional code isn't just good for concurrency, it also helps when trying to reason about lists and associative containers at a higher level.

taylodl 13y ago

Trampolines are okay, but JavaScript still needs an actual TCO. In this blog post http://taylodl.wordpress.com/2013/06/07/functional-javascript-tail-call-optimization-and-trampolines/ http://taylodl.wordpress.com/2013/06/07/functional-javascrip... I look into the performance of trampolines compared to the normal recursive form. Trampolines perform worse. Moreover, TCO was invented to overcome the performance issues associated with recursive implementations, meaning trampolines perform much worse than TCO.

deleted 13y ago

[deleted]

erjiang 13y ago

Here is an example of trampolining in a Scheme interpreter I wrote in JavaScript: https://github.com/erjiang/foxscheme/blob/master/src/system/interpreter.js#L241 https://github.com/erjiang/foxscheme/blob/master/src/system/... This way, interesting Scheme programs can be written without using the small JavaScript stack. It uses an infinite loop that's broken out of by throwing an exception. There are also some other tricks that it uses to allow other things to happen on the page while it runs your program.

tcdowney 13y ago
Looks like Friedman taught you well. :)

bsaul 13y ago

Very interesting article. But then, frankly, if you're ever in the need for that kind of things, why don't you make yourself a favor and stop using javascript (especially on the server, where there are plenty other alternatives) ? I mean, if someone comes to me with some server code running a "trampoline" library so that he can perform tail-call optimization in javascript on node.js , he really better have some extremely good justification.

tracker1 13y ago
definitely true... If you're doing CPU intensive stuff in node, you should consider the following... worker script(s) (generic-pool helps too), with .fork(), refactoring the loop to use an async response with setImmediate, or converting to a binary module. Example: https://github.com/tracker1/node-js-scrypt/blob/master/lib/scrypt-async.js https://github.com/tracker1/node-js-scrypt/blob/master/lib/s...

mhewett 13y ago

You don't seem to be gaining much from this, at least in JavaScript. The Jatha small LISP library that hasn't been updated since 2007 returns factorial(32768) in 5 seconds on a middling machine. (Disclosure: I'm the author of Jatha)

numlocked 13y ago

Hopefully this will be a bit less painful if/when TCO makes its way into ECMAScipt 6 ("Harmony") as it is slated to do: http://wiki.ecmascript.org/doku.php?id=harmony:proper_tail_calls http://wiki.ecmascript.org/doku.php?id=harmony:proper_tail_c... Regardless, this was an excellent introduction to trampolining.

PotatoPotato 13y ago

jQuery script to fix that whole article: $("body").html($("body").html().replace(/rampol/g, "rambapol")); Happy Friday Everyone!