5 ms·
Is it prudent to utilize the functional style in a language that isn't tail call optimized? Doesn't that create a lot of garbage for the GC?
by bsimpson 14y ago
Is it prudent to utilize the functional style in a language that isn't tail call optimized? Doesn't that create a lot of garbage for the GC?
- johnpmayer 14y agoI think that because TCO is all but inevitable in future engines/standards, starting to use functional patterns now for the programming benefits is worthwhile.
- jcampbell1 14y agoBe my guest. Start using this implementation of each. Let me know if you run into any problems. function each(arr,fn,pos) { pos = pos || 0; fn(arr[pos++]) if(pos < arr.length) each(arr,fn,pos); } Seems like a recipe for a disaster.
- fogus 14y agoI prefer Underscore's implementation of `each`. It doesn't blow the stack. http://underscorejs.org/docs/underscore.html#section-13 http://underscorejs.org/docs/underscore.html#section-13
- k3n 14y agoThat would highly depend on if you're writing performance-sensitive code, and I doubt most JS would be greatly affected by these paradigms.
- MBlume 14y agolack of TCO doesn't mean it's a little slow, lack of TCO means that naive use of classic functional patterns blows the stack for big lists/structures/arguments.
- fogus 14y agoBy "classic functional patterns" you mean recursion. There are other ways to implement functions that are "classically functional" using techniques other than recursion, that do not blow the stack. I'll talk about each and their tradeoffs.
- MBlume 14y agoI did also say "naive use" =) Looking forward to the book.
- gngeal 14y agoIt's not just recursion, it's calls in general, I guess. (There are other ways of being space-inefficient in functional programs, see the odd versus even streams issue in Scheme.) Are you going to mention tail calls in ES6 in your book, BTW?
- fogus 14y agoSorry for the late response. I will not cover ES6 tail calls very much at all except to mention the possibility for inclusion.
- k3n 14y agoRight, but is this a concern for most JS? I realize that JS is becoming more popular for various tasks -- not always relating to the web -- but still, I kind of doubt that 99% of the JS out there is going to run up against these types of problems. Perhaps something like Uglify.js or similar might, but then again, if you're implementing a parser (or any other static code analyzer/tool) then you're probably going to avoid most libs to start with.
- Cushman 14y agoFunctional programming doesn't have to mean deep recursion-- it's not like you can't use functions and loops in the same code.
- gngeal 14y agoTail calls are not as much about "deep recursion" as they are about continuation-passing style, compositionality, and similar things. It's like with lazy evaluation. It allows you to write novel kinds of algorithms and data structures, and you can emulate it with helper objects or structures, but it's tedious, muddles the essence of the code, and the implementation without them (the helper structures) would be simpler if the language provided you with lazy expressions. In other words, repeat with me: loops don't compose. They're not first-class, they're not extensible, they're a syntactic construct.
- munificent 14y ago> In other words, repeat with me: loops don't compose. Iterators do, though. Most of the languages that don't do TCO instead lean on those instead: C++, C#, Python, and eventually JavaScript.
- pjmlp 14y agoFunctional Programming is much more than just recursion. There are lots of concepts that are still applicable even when using imperative loops.
- camus 14y agoWould it allow to avoid stackoverflows with a simple flood fill algorithm if Javascript had tail call optimization ? right now i need to build my own stack, and "unstack" it manually.
- cdumler 14y agoFunctional purity would be nice, but TCO not strictly necessary to be program very functionally. For instance, here TCO would be necessary to prevent the stack from being over-run: function fact(x) { return (function factIter(i, total){ if(i<=1){ return total; } return factIter(i-1, total*i); })(x,1); } However, if you're willing to allow mutation in non-accessible code or closures, there are options: function fact(x) { if(i<=1) { return 1; } return _.range(1,x+1).reduce( function(sum, x) { return sum*x; } ); }
- alexfarran 14y agoYou can use a trampoline like the one the author has written in this library https://github.com/fogus/lemonad/blob/master/lib/lemonad.js#L1089 https://github.com/fogus/lemonad/blob/master/lib/lemonad.js#... Basically you rewrite your recursive functions so that instead of calling another function they return a parameterless closure. Then you can iteratively call your first function, and the function it returns, and the function it returns etc until the return value is not a function.
- knowtheory 14y agoYes, in particular, asking people to think about the input and output to a particular piece of code is really important. Pulling apart the iteration over a collection of elements and behavior performed to each element is one of those insights that a functional style is good at communicating, and leads to better more testable code.
- fogus 14y agoKnowing the limitations of your runtime is important. My book is not a dogmatic application of functional programming in spite of JavaScript, but instead an exploration of the functional techniques that complement JavaScript. Tail calls make an appearance, but they are more broadly applicable than their use in the presence of TCO.
- kaoD 14y agoWho needs loops nowadays? Just map, reduce, filter and imperatively-loop when needed (around 0.1% of cases?).