Trampolines in JavaScript(raganwald.com)
raganwald.com
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
15 comments
> 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.
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.
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...
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...
> And that's the obviousness of it. If it were better, it really would have serious traction by now.
You're getting picked on here, and I'm going to do my best to add to the pile. From http://www.johndcook.com/blog/2008/03/25/innovation-ii/ --
""" In 1601, an English sea captain did a controlled experiment to test whether lemon juice could prevent scurvy. He had four ships, three control and one experimental. The experimental group got three teaspoons of lemon juice a day while the control group received none. No one in the experimental group developed scurvy while 110 out of 278 in the control group died of scurvy. Nevertheless, citrus juice was not fully adopted to prevent scurvy until 1865. """
So lemon juice cut the mortality of scurvy in sailors by forty percentage points (!), from 40% to 0% (!!). And a mere 260 years after this was demonstrated, it achieved "traction". Do you think you might be jumping the gun a little here? History would suggest that even if programming in FP style prevented 100% of bugs from occuring, the best you could say about its eventual adoption would be "it's a crapshoot".
You're getting picked on here, and I'm going to do my best to add to the pile. From http://www.johndcook.com/blog/2008/03/25/innovation-ii/ --
""" In 1601, an English sea captain did a controlled experiment to test whether lemon juice could prevent scurvy. He had four ships, three control and one experimental. The experimental group got three teaspoons of lemon juice a day while the control group received none. No one in the experimental group developed scurvy while 110 out of 278 in the control group died of scurvy. Nevertheless, citrus juice was not fully adopted to prevent scurvy until 1865. """
So lemon juice cut the mortality of scurvy in sailors by forty percentage points (!), from 40% to 0% (!!). And a mere 260 years after this was demonstrated, it achieved "traction". Do you think you might be jumping the gun a little here? History would suggest that even if programming in FP style prevented 100% of bugs from occuring, the best you could say about its eventual adoption would be "it's a crapshoot".
But they're obviously not.
I'm going to challenge you right there. First, note that using aspects of functional programming doesn't immediately necessitate you do nothing but functional programming and use nothing but "functional" languages.
Consider a piece of poorly refactored C++ spaghetti you've been tasked with understanding. The same variables mean different things at different times... code assuming vectors have the appropriate length, then later normalizing them in place, and then later yet changing their direction... state being repeatedly accumulated and adjusted in different branches... how do you start cleaning this code up to understand it?
One of the first things in my hat is to start using a more functional style. I sprinkle around the const keyword on local variables like a madman, helping catch all code with side effects to local temporaries. Variables are split in twain, with vectors and their normalized versions being forced to have different labels. But therein lies the advantage: I no longer have to track "x means y except after z when it means y2", but can drastically simplify to "x means y" -- something I can usually encode in the variable name, easing pressure on my feeble memory. Moreover, since the constants stick around, I can paint a better picture of "before and after" much more quickly than through the pinhole of stepping (usually in one direction only) through more procedural code, simply by slapping a breakpoint at the end.
While I'm still not using nor desiring to use functional languages as my bread and butter, integrating functional styles into otherwise procedural code quite frequently helps save my time and sanity outright, even on those occasions when it feels stilted and unnatural compared to the procedural versions.
I'm going to challenge you right there. First, note that using aspects of functional programming doesn't immediately necessitate you do nothing but functional programming and use nothing but "functional" languages.
Consider a piece of poorly refactored C++ spaghetti you've been tasked with understanding. The same variables mean different things at different times... code assuming vectors have the appropriate length, then later normalizing them in place, and then later yet changing their direction... state being repeatedly accumulated and adjusted in different branches... how do you start cleaning this code up to understand it?
One of the first things in my hat is to start using a more functional style. I sprinkle around the const keyword on local variables like a madman, helping catch all code with side effects to local temporaries. Variables are split in twain, with vectors and their normalized versions being forced to have different labels. But therein lies the advantage: I no longer have to track "x means y except after z when it means y2", but can drastically simplify to "x means y" -- something I can usually encode in the variable name, easing pressure on my feeble memory. Moreover, since the constants stick around, I can paint a better picture of "before and after" much more quickly than through the pinhole of stepping (usually in one direction only) through more procedural code, simply by slapping a breakpoint at the end.
While I'm still not using nor desiring to use functional languages as my bread and butter, integrating functional styles into otherwise procedural code quite frequently helps save my time and sanity outright, even on those occasions when it feels stilted and unnatural compared to the procedural versions.
I'm not entirely sure why this is getting downvoted so much other than possibly tone that offends the FP community (I'm sympathetic since the evergreen Perl is dying! stuff causes a twitch in me for down voting as well).
The biggest reason I have dismissed functional programming languages is that they appear to believe that all problems are pure (which in some cases are entirely appropriate to assume) but then have to exempt themselves from their own paradigms to deal with reality. What I mean is essentially what Kant declares with the categorical imperative, "wish it universal." FP paradigms always seem to have to exempt themselves from this in order to work with a lot of real-world problems.
Of course, I may just be old and not entirely grokking the real abstract ideas of functional programming.
The biggest reason I have dismissed functional programming languages is that they appear to believe that all problems are pure (which in some cases are entirely appropriate to assume) but then have to exempt themselves from their own paradigms to deal with reality. What I mean is essentially what Kant declares with the categorical imperative, "wish it universal." FP paradigms always seem to have to exempt themselves from this in order to work with a lot of real-world problems.
Of course, I may just be old and not entirely grokking the real abstract ideas of functional programming.
> But they're obviously not.
They are obviously not for a substantial subset of the people who started programming with other-than-functional languages, which includes most current programmers. That's not the same as whether or not they are easier to read and write and debug and reason about in general.
> It's not cause we're all dummies, it's because, generally speaking, for most problems FP sucks ass.
Examples?
They are obviously not for a substantial subset of the people who started programming with other-than-functional languages, which includes most current programmers. That's not the same as whether or not they are easier to read and write and debug and reason about in general.
> It's not cause we're all dummies, it's because, generally speaking, for most problems FP sucks ass.
Examples?
Lisp used to be the lingua franca of universities. So, please, let's cite examples...
But seriously, state is inherent in most enterprise apps, which is to say, 95% of apps in existence.
But seriously, state is inherent in most enterprise apps, which is to say, 95% of apps in existence.
> But seriously, state is inherent in most enterprise apps, which is to say, 95% of apps in existence.
That doesn't justify the claim that for most problems FP is poor; functional languages deal with mutable state, indeed, a big point of FP is that using it provides a way to cleanly divide pieces of code that deal with mutable state so that the presence of mutable state only complicates reasoning about those pieces of code that it inherently must complicate, rather than making the whole code base hard to reason about.
That doesn't justify the claim that for most problems FP is poor; functional languages deal with mutable state, indeed, a big point of FP is that using it provides a way to cleanly divide pieces of code that deal with mutable state so that the presence of mutable state only complicates reasoning about those pieces of code that it inherently must complicate, rather than making the whole code base hard to reason about.
The lack of state in FP is a major myth. There's plenty of state, it just looks different than you're used to and, thanks to that, is far easier to reason about. It means that everyone who's first making the transition from imperative/OO to FP complains about it, but anyone who sticks around long enough to learn much anything besides "Hello World" learns quickly that there's really no problem.
State is inherent but loops where recursion helps are sadly in scarce supply in enterprise apps (at least the ones that I've seen). Many (most?) apps are pushing data around, many times strings, often from a database. Lots of if statements, fewer whiles. Recursion can help with the kinds of problems that one encounters dealing with these types of programs, but it's not necessary and I would say probably doesn't even make things easier.
And the overwhelming majority of those apps probably experienced a particularly nasty and expensive bug that was due to state (i.e. one that would have been very difficult or even impossible to replicate in a primarily functional environment).
Except scala has achieved traction and clojure is hot on its tail
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.
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.
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?
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?
Here's an example that I'll put in here. Let's say you have an array of strings, and you want to create a UL element with each string in an LI. You can do this with a for loop just fine and everyone's happy:
var ul = document.createElement("ul");
for(var i = 0; i < strings.length; ++i) {
var text = document.createTextNode(strings[i]);
var li = document.createElement("li");
li.appendChild(text);
ul.appendChild(li);
}
var ul = document.createElement("ul");
strings.map(function (string) {
return document.createTextNode(string);
}).map(function (text) {
var li = document.createElement("li");
li.appendChild(text);
return li;
}).each(function (li) {
ul.appendChild(li);
});
function toTextNode(string) {
return document.createTextNode(string);
}
function wrap(tag, child) {
var wrapper = document.createElement(tag);
wrapper.appendChild(child);
return wrapper;
}
function append(parent, child) {
parent.appendChild(child);
}
// Helper function to provide partial-application.
// This is usually built into functional languages.
function wrapIn(tag) {
return function (child) {
return wrap(tag, child);
};
}
function appendTo(parent) {
return function (child) {
return append(parent, child);
}
}
var ul = document.createElement("ul");
strings.map(toTextNode).map(wrapIn("li")).each(appendTo(ul));
Hmm. In your perfect world, the code to solve that problem would look like this one-liner:
Also note that my solution doesn't really follow your pattern of composing several operations. The template loops over the array only once instead of three times. Maybe that's because it feels more natural to some people to nest several operations inside one loop, rather than pull out each operation as its own loop. I share that point of view as well, it feels weird to write a chunk of code differently depending on whether it's inside a loop or outside a loop. YMMV.
Of course the functional approach also supports putting all operations inside one loop. You could build up the composite operation by using a lambda (which would look similar to your initial imperative example), or using some function composition operators (which I wouldn't enjoy reading afterward).
strings.map(toTextNode).map(wrapIn("li")).each(appendTo(ul));
<template name="mytemplate"
args="strings: array[string]"
<ul>
<li foreach="string in strings"
content="string">
</li>
</ul>
</template>
mytemplate.fill(strings);
Also note that my solution doesn't really follow your pattern of composing several operations. The template loops over the array only once instead of three times. Maybe that's because it feels more natural to some people to nest several operations inside one loop, rather than pull out each operation as its own loop. I share that point of view as well, it feels weird to write a chunk of code differently depending on whether it's inside a loop or outside a loop. YMMV.
Of course the functional approach also supports putting all operations inside one loop. You could build up the composite operation by using a lambda (which would look similar to your initial imperative example), or using some function composition operators (which I wouldn't enjoy reading afterward).
Understood, and templating is a good solution also. I specifically wrote what I did based on the original question, which I interpreted as "what does functional programming in a UI look like?" And I wanted to show the progression from a loop to inline lambdas to reusable and generic functions.
Thank you for your thoughtful and informative comment. This is what I read HN for.
I generally don't like double posting in a thread but...
7 lines to 30 lines, with a never-ending call stack of despair if anything ever does go wrong.
That imo, is really shit code.
7 lines to 30 lines, with a never-ending call stack of despair if anything ever does go wrong.
That imo, is really shit code.
But the 5 helper functions are all very reusable, making the code specific to this particular usage shrink from 7 lines to 2. With a handful more usages like this, they can have a huge decrease in code size.
And later on, seeing "map ... map ... each", it is immediately obvious that we are iterating over the entire array, producing new values, and then doing something with each of them. With the explicit for-loop, the unique logic is mixed in with boilerplate iteration code.
Of course, by now,
That's a huge benefit of functional programming IMO: replacing a bunch of repetitive, error-prone patterns with a higher-order function call.
On a side note, it's really unfriendly to call a comprehensive, helpful example "shit code." If you can relate your opinion in a slightly more respectful way, people will be more apt to listen to you.
And later on, seeing "map ... map ... each", it is immediately obvious that we are iterating over the entire array, producing new values, and then doing something with each of them. With the explicit for-loop, the unique logic is mixed in with boilerplate iteration code.
Of course, by now,
for (var i = 0; i < strings.length; i++) {
/* something with i */
}
That's a huge benefit of functional programming IMO: replacing a bunch of repetitive, error-prone patterns with a higher-order function call.
On a side note, it's really unfriendly to call a comprehensive, helpful example "shit code." If you can relate your opinion in a slightly more respectful way, people will be more apt to listen to you.
... not to mention that off-by-one errors and other confounding bugs are really common when you loop through the elements of an array manually. That's all but impossible with map, filter, and reduce.
This is such a silly criticism, and is even sillier by the fact that I already answered it:
> And now you have a bunch of general-purpose, easily-tested functions that you can apply in similar situations all over the place.
EDIT: Not to mention that at least 10 of those lines could be removed with built-in currying and/or partial application, which any self-respecting functional language supports directly. JavaScript is not counted among these.
> And now you have a bunch of general-purpose, easily-tested functions that you can apply in similar situations all over the place.
EDIT: Not to mention that at least 10 of those lines could be removed with built-in currying and/or partial application, which any self-respecting functional language supports directly. JavaScript is not counted among these.
Sorry, I don't have any links to share off hand. But I do have some comments:
Of course we all have to deal with state, otherwise our programs are essentially useless.
As a casual FP practitioner, I try to make web-based design decisions that minimize the number of places where I handle state. The majority of the functions that I write just take values and return some referentially transparent transformation of their inputs.
So for me it's really more about black-boxing and forgetting (once it's thoroughly tested) about 90% of my code, thus hopefully limiting the scope of my state related wtf moments to the other 10%.
There was a time in my life where I thought that this sort of design was obvious and everybody was doing it. I've since learned, through lots of painful maintenance and debugging, that this is not at all the case :/
Of course we all have to deal with state, otherwise our programs are essentially useless.
As a casual FP practitioner, I try to make web-based design decisions that minimize the number of places where I handle state. The majority of the functions that I write just take values and return some referentially transparent transformation of their inputs.
So for me it's really more about black-boxing and forgetting (once it's thoroughly tested) about 90% of my code, thus hopefully limiting the scope of my state related wtf moments to the other 10%.
There was a time in my life where I thought that this sort of design was obvious and everybody was doing it. I've since learned, through lots of painful maintenance and debugging, that this is not at all the case :/
> minimize the number of places where I handle state
The idea isn't to minimize places where you handle state. If you want to manage state, use a State monad. Here are some examples in Scala - http://stackoverflow.com/questions/7734756/scalaz-state-mona...
The idea isn't to minimize places where you handle state. If you want to manage state, use a State monad. Here are some examples in Scala - http://stackoverflow.com/questions/7734756/scalaz-state-mona...
> use a State monad
Sure, I agree that that's the proper, academic, and purely functional way to handle state. Whether or not that introduces its own set of problems I'll leave as a thought exercise for the reader.
The key phrase in my comment was "casual FP practitioner." I'd only hoped to show OP a way to painlessly introduce some principles from the FP world , ones with, IMO, real and immediately obvious benefits, without cramming "monads and combinators and category theory oh my!" down his or her throat.
I tend to prefer simple, dumb, readable code to academic elegance, and I've found that treating data as immutable (whether it actually is or not under the covers) and preferring data transformation to state manipulation are two ways to get closer to that goal.
Sure, I agree that that's the proper, academic, and purely functional way to handle state. Whether or not that introduces its own set of problems I'll leave as a thought exercise for the reader.
The key phrase in my comment was "casual FP practitioner." I'd only hoped to show OP a way to painlessly introduce some principles from the FP world , ones with, IMO, real and immediately obvious benefits, without cramming "monads and combinators and category theory oh my!" down his or her throat.
I tend to prefer simple, dumb, readable code to academic elegance, and I've found that treating data as immutable (whether it actually is or not under the covers) and preferring data transformation to state manipulation are two ways to get closer to that goal.
The vast majority of your code probably isn't manipulating state, or doesn't need to be. You can have well defined boundaries where you're dealing with state. Read from the database, pass those values through a bunch of pure functions, then eventually rewrite to the database. You only have side effects when you intially read from and eventually write to the DB. Same goes for manipulating the DOM, and almost anything else.
This book helped me answer the same question: https://leanpub.com/fp-oo
This talk is pretty good as well, but I already had a decent grasp on FP before watching, so it might not be as good before having such an understanding, http://vimeo.com/34522837
This talk is pretty good as well, but I already had a decent grasp on FP before watching, so it might not be as good before having such an understanding, http://vimeo.com/34522837
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.
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.
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 :).
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 :).
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.
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.
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.
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.
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.
Functional code isn't just good for concurrency, it also helps when trying to reason about lists and associative containers at a higher level.
For anyone interested in applying functional concepts to Perl, I highly recommend Mark Jason Dominus's Higher Order Perl[1], the full text of which is now available online for free.
It starts by teaching a reader moderately familiar with Perl functional concepts, and then it deep dives into these concepts and iteratively applies them to example programs to make them better.
[1]http://hop.perl.plover.com/
It starts by teaching a reader moderately familiar with Perl functional concepts, and then it deep dives into these concepts and iteratively applies them to example programs to make them better.
[1]http://hop.perl.plover.com/
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.
Huh. Seems that's pretty much true. Occasionally people don't hyphenate sweettoothed.
grep '\(.\)\1\(.\)\2\(.\)\3' word_listI 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...
http://brownencyclopedia.tumblr.com/post/33647027942/the-cas...
And subbookkeeper has four...
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.
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.
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...
Example: https://github.com/tracker1/node-js-scrypt/blob/master/lib/s...
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.
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.
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.
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.
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.
Looks like Friedman taught you well. :)
Creating a new function for every tail call seems a bit awful. It's a shame that the more performant alternatives are ridiculously ugly.
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.
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.
A trampolined state machine reads OK, where each state is the next transition function.
But generally, you want tail recursion...
But generally, you want tail recursion...
I wonder why JS doesn't implement tail calls. Lot of effort has has been made optimizing JS engines, but not for this case.
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.
Regardless, this was an excellent introduction to trampolining.
[deleted]
Sidenote: when you run the recursive function factorial(1000), Node.js returns "Infinity".
This works even better with ES6 generators: https://github.com/pixelspark/dispatch.js
Doesn't ES6 have tail calls anyway?
we need space O<em>n</em> for all those stack frames
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)
jQuery script to fix that whole article:
$("body").html($("body").html().replace(/rampol/g, "rambapol"));
Happy Friday Everyone!
Happy Friday Everyone!
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;
}
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.”
;-)
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.”
;-)
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...
[0] http://raganwald.com/2013/01/03/function_and_method_decorato...
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:
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();
var foo = function() {
//
bar();
};
var bar = function() {
//
baz();
};
var baz = function() {
//
foo();
};
foo();
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.
You handle TCO by making it asynchronous? WTF.
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.
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).
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.
"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?
OK, but couldn't you then still complain that each of those are "Simple, shorter, no overhead from function calls, etc." as while loops?
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.
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.
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:
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;
}Did you see the follow-up post "High-Level Trampolining?"
http://raganwald.com/2013/03/29/high-level-trampolining.html
http://raganwald.com/2013/03/29/high-level-trampolining.html
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.
Awesome!
Could you show me how to write a parser combinator in this fashion?
Could you show me how to write a parser combinator in this fashion?
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?