Trampolines in JavaScript

http://raganwald.com/2013/03/28/trampolines-in-javascript.html?utm_content=bufferdab4c&utm_source=buffer&utm_medium=twitter&utm_campaign=Buffer

by austengary • 13 years ago

157 72 13 years ago

raganwald.com

IgorPartola5• 13 years 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• 13 years 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.

raganwald2• 13 years 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.”

;-)

IgorPartola5• 13 years 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.

phpnode• 13 years 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_decorato...

samatman• 13 years ago

Awesome!

Could you show me how to write a parser combinator in this fashion?

misterdata• 13 years ago

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

teamonkey• 13 years ago

Doesn't ES6 have tail calls anyway?

anonymoushn• 13 years 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• 13 years 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.

justincormack2• 13 years ago

A trampolined state machine reads OK, where each state is the next transition function.

But generally, you want tail recursion...

darkstalker• 13 years 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• 13 years 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

justincormack2• 13 years ago

And subbookkeeper has four...

ArbitraryLimits• 13 years 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-cas...

RyanMcGreal• 13 years ago

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

dmm• 13 years ago

Because javascript has only one numerical type: double float?

wging• 13 years ago

fact(1000) Infinity fact(10000000) RangeError: Maximum call stack size exceeded

jheriko• 13 years 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#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• 13 years ago

    we need space O<em>n</em> for all those stack frames

Why not use the normal O(n) notation?

crazygringo3• 13 years 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• 13 years 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.

crazygringo3• 13 years 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.

mpyne• 13 years 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.

theseoafs3• 13 years ago

That's a poor characterization of why functional code is "useful". People write functional code in languages that have no support for multithreading all the time. (Further, functional programming isn't often used for cases where optimization is super important -- imperative code can often yield faster solutions.)

Functional programming makes code simpler in a lot of situations. Statelessness is one of the big draws of the functional paradigm. If I'm debugging in a functional language and I find a variable has the wrong value, I can rule out stateful problems -- for example, I know I didn't accidentally reset the variable, and I know there's no code off in another function (or worse, another source file) that's messing with the state of the objects I'm managing. If you're debugging in a functional language, you can basically be certain that you got your algorithm wrong, which is helpful.

lmkg• 13 years ago

because it's essentially mathematical -- functional code tends to be harder to write, understand, and debug

Many proponents of functional programming (including myself) believe exactly the opposite--that functional programs are easier to read and write, and tend towards being more modular which makes it simpler to test and debug.

This is mostly a product of experience and familiarity. My background is in mathematics, and I came to programming later. Many people come to functional program without as explicit of a math background as mine, but it's still mostly a matter of getting used to it.

mattmanser3• 13 years ago

But they're obviously not.

We've now has 5-10 years of this new batch of FP languages and none of them have 'stuck', they've still not caught on.

It's not cause we're all dummies, it's because, generally speaking, for most problems FP sucks ass.

And that's the obviousness of it. If it were better, it really would have serious traction by now.

Instead people are integrating the best bits of FP into OOP languages. And at that at least they've been a wild success, it's made OOP languages a lot easier to program in. And will make Java easier to program in. Poor old Java programmers. Java 8 will be like a revelation...

jamesbritt• 13 years ago

functional code tends to be harder to write, understand, and debug,

I've heard just the opposite. It's likely harder to write if you've being doing procedural code for a long time but the elimination of state, the referential integrity, makes things easier to reason about and easier to debug in the long run. The ability to compose larger methods from numerous small, state-free methods s a big win as well.

I've never found a compelling reason to use the FP paradigm in JavaScript.

My motivation to write more FP-oriented code is to reduce the number of WTF moments.

crazygringo3• 13 years ago

Do you (or anyone) have any links to web-centric JavaScript programs written this way?

My confusion comes from the fact that I feel like most of the web-based stuff I deal with has to do with state -- the state of the DOM, the state of the database, the state of a connection, etc.

All the FP I read about always uses simple algorithmic examples (like factorials, Fibonnaci, etc.), and I've never been able to find a good example of a real-life webapp, say, that is written in a functional manner, that is a good example of how a program can be easier to write/maintain/debug/etc. Pointers?

c0mpute• 13 years ago

As somebody who has written a lot of Java code before (read imperative) and now have had the opportunity to write more JS (which makes it a bit easier to write Functional) and also Scala, I think the process to "think" functionally takes time.

Sure, its easier to apply it to the mathematics domain and harder to something that many of us might think in OO. I guess it comes with taking small steps (as someone already said in a comment). Also, making conscious effort to keep questioning how functional our code is helps.

I saw this talk on functionatalks.org by Paul Chiusano (author of Functional programming in Scala) http://functionaltalks.org/2013/06/20/paul-chiusano-how-to-w...

If you see he repeatedly asks how can we make it more functional. I think that is kind of thinking we need to practice. Its hard after too much of imperative thinking I guess. One more thing I have heard is read SICP and forget OO for a bit :).

taylodl• 13 years ago

Trampolines are okay, but JavaScript still needs an actual TCO. In this blog post 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.

erjiang• 13 years ago

Here is an example of trampolining in a Scheme interpreter I wrote in JavaScript: 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• 13 years ago

Looks like Friedman taught you well. :)

bsaul• 13 years 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• 13 years 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/s...

mhewett• 13 years 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• 13 years 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_c...

Regardless, this was an excellent introduction to trampolining.

PotatoPotato• 13 years ago

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

Happy Friday Everyone!

Trampolines in JavaScript

Related Stories