Functional Programming in JavaScript is Garbage
awardwinningfjords.com
awardwinningfjords.com
1) Strong Preference for Immutable Data: Javascript's object model isn't particularly confusing: If it's not a primitive, it's a reference. That's all there is to it. Knowing this, when architecting a functional framework in JS, one should know in the various instances they need to mutate data, or copy it.
2) Recursion & Tail Call Elimination: How would one solve this problem in any other language with a stack? Memory concerns don't just exist in the browser.
3) Functional Composition: It seems like OP's main concern here is garbage collection. There are ways to manage the garbage you generate here, and, frankly, engines like V8 do an exceedingly good job at cleaning up on their own.
I don't blame people for not liking Javascript, and misdirected angst like this is at least good for keeping people on their toes about the many idiosyncracies of the language, but it won't go away just because you don't like it.
2)http://en.wikipedia.org/wiki/Tail_call ("Tail calls are significant because they can be implemented without adding a new stack frame to the call stack.")
3) I don't know enough about implementing partial in other languages to comment on if it's more garbage than should be necessary.
Be honest now, did you actually read the article ;-) because it answers that exact question.
---
> Languages with Tail Call Elimination will recognize this situation and basically rewrite the function into a while loop. Since this is a low-level function, we should do the same, but sometimes it's hard to know when you're recurring dangerously.
---
> but it won't go away just because you don't like it.
I didn't like it and it go away. Out came Dart. I like Dart. All worked out well so far.
Except that javascript hasn't gone away, but has in fact exploded exponentially in adoption to become a compile point for various languages, and almost no one and nothing actually uses Dart yet, at least not in the browser.
Unless it's compiled to javascript, of course.
The issue with immutable data is not that Javascript's model is confusing, it's that there is no way to write "this array is immutable." Without that guarantee, you can't allow multiple data structures to reference the same copy of data because the data might get modified unexpectedly.
There is a similar issue with tail calls. The compiler could replace calls in tail position with jumps, but it's important that this be part of the language spec. Without a guarantee in the language spec, code that runs fine on one system may blow up with a stack overflow on another.
It's impressive that JS works as well as it does when written in a style different from what it was designed for. Many languages make other styles so difficult that it's not even worth trying (looking at you, Java).
FWIW, |Object.freeze| does it but unfortunately it disables some optimizations.
> There is a similar issue with tail calls. The compiler could replace calls in tail position with jumps, but it's important that this be part of the language spec. Without a guarantee in the language spec, code that runs fine on one system may blow up with a stack overflow on another.
Tail calls are part of ES6.
Regarding the garbage point brought up by the OP, with regards to point-free programming: generational gc makes it so that short lived objects are super cheap; I suspect it isn't a bottleneck in 99% of use cases and in the remaining cases you can refactor your code appropriately.
Agreed, of course, that if JS were designed to be functional from the ground up it would make coding in the paradigm a lot easier. Pretty much a tautology.
Since Javascript does not have data structures that facilitate immutability, this is a major pain point. Even if you're not writing code in an FP style, you should still be avoiding mutability as much as possible.
2) Tail call elimination is supported in plenty of languages, and is pretty much essential for proper FP. Mind you it's still useful in imperative code as well, and most C/C++ compilers will do the optimization when provably safe.
3) V8 garbage collection is terrible. Creating lots of small object copies has a massive overhead (Compared with, say, the JVM, which has virtually no overhead)
Care to elaborate on this, what kind of GC overhead are you seeing when creating small object copies?
No, everything is ALWAYS a reference.
This is, in fact, enshrined in the ECMAScript standard. Everything is a reference, and gets passed to GetValue() when required.
Now, some of the JIT's do a phenomenal job of backing this out, but it's always a hazard.
There is a reason that the newer versions of ECMAScript are trying to specify constant type variables and immutability in globals.
- Immutable data arguments
Nobody is stopping you from just working as if JS is immutable.
- Recursive functions and the stack
Tail call elimination would be nice. But for most common things, instead of writing the recursive call yourself, you'd use other common functions in the FP toolbox like map, reduce. You only need to find a good implementaiton of these base functions and 90% of your headaches are gone.
But the stack is still an issue in other languages (See foldr debate in Scala).
- Partial application and composition
How do you think this is implemented in other FP languages? At one point you do have to store pointers to the functions you are composing to build the composed function , so you'll have at least one new object.
>but if you are doing a lot of Point-free Programming, then your loops have the possibility of generating a ton of garbage.
You shouldn't be doing something like for(..){ compose(f,g)(elt); } obviously, but this is just a specific case of "cache values". If you store the function beforehand, the amount of garbage created is linear to the size of your code, not of your data. (Never mind that you shouldn't be looping in FP).
If you try hard enough and don't mind a more obscure syntax, you can actually reduce this function creation overhead too.
var composeObj = Object.create(null);
composeObj.prototype.invoke = function(x){
return this.g(this.f(x));
}
compose = function(f,g){
var rV=Object.create(composeObj);
rV.f = f; rV.g=g;
return rV;
}
h = compose(function(elt){return 2*elt;},function(elt){return elt+3;});
h.invoke(10);
You cant just work "as if" things are immutable when they aren't. You have to be super careful about not mutating objects, for example copying an array with .slice() before messing with it. That is not ideal because 1) it is manual, and 2) copy on write is inefficient compared to the structure sharing that immutable data structures use.
If you want the benefits of persistent data structures in Javascript, you have to use something like Mori. And that is ok, but not as nice as it is in functional languages, because you loose the specialized literal syntax to create the data structures and work with them. For example, to create a vector in mori you have to:
var vec = mori.vector(1,2,3);
var result = mori.map(inc, mori.vector(1,2,3,4,5))I think there was some outfit "loop/recur" that was doing heavily composition-style javascript. They often write the types for function in comments in haskell notation above the actual function definitions.
a) Going to be bounded by a small number or user controlled
b) Something you would have to use recursion for in any language, like a recursive descent parser.
So like you said call stacks growing is usually not a big issue if you know what you're doing.
function trampoline(fn /*, args */) {
var result = fn.apply(fn, _.rest(arguments));
while (typeof result === 'function') {
result = result();
}
return result;
}
You build algorithms around assumed immutability, and then it's trivial to accidentally introduce mutation into them - sometimes entirely by accident, since third party JS libraries can introduce mutation into non-mutating operations. For example, I once pulled in a third-party JS 'printStackTrace' library for debugging purposes, then weeks later had to spend half a day troubleshooting to figure out that printStackTrace was mutating arbitrary arrays from the stack, thus permanently corrupting random globals.
If you're maintaining a large codebase with multiple people, the risk of accidentally introducing mutability is very, very real.
Faking tail calls in JS requires using constructs that introduce unnecessary GC pressure and prevent most JIT optimizations, compared to tail calls in a real functional environment where they deliver great performance without GC pressure.
Partial application and composition in JS performs like garbage, as mentioned above with faking tail calls. 'True' FP runtimes can do better here, as do some static runtimes (.NET, for example, has the ability to do a subset of composition and partial application without any GC or call overhead whatsoever.)
Your composeObj example is another good one. You've created this special variant of JS callables that isn't actually a function (because JS functions are rigid and hard to build composable primitives out of), and it contains patterns that subdue JIT optimization (Object.create, for one). Again, attempts to pretend that JS is a good functional language just produce ugly, underperforming, hard-to-maintain code.
sigh Javascript just is. It only hates you because you hate it. Accept it for what it is and you & your code will be happier :-)
Remember, abstraction loves you and doesn't need to be purely functional inside. It will still work. Breathe, Ahhhh.
As far as the data structures not being there, well, keep in mind that JavaScript is based on imperative languages; hence its focus on arrays and hash tables (both of which are almost always implemented mutably). Also, mutability is baked into the DOM, and short of doing everything in a monad, that looks to be the way it's going to be, so again, it makes sense that JS was written as it was. When immutability is needed, use a library -- or just don't use JavaScript.
Blaming JavaScript's awful standard library on imperative languages is lazy. Almost every imperative language I've used has a standard library vastly superior to JS's, in breadth, depth and quality.
I wish the article had been framed that way from the outset instead kind of admitting it only at the end. Instead we got an attention grabbing title that misleads the reader about the content/intent of the author.
yet you're not forced to learn most of them.
Now there is a solution from most issues the OP raises,but frankly Javascript is working against the developpers. That's why people say "embrace javascript", because it's a language that wont embrace the way you want to code. Javascript is a lucky mistake.And if not because politics we wouldnt be stuck with it. ES6 brings are few interesting things to the table though,and some scary ones like proxies,and god, people will abuse proxies and make code just "magic"...
https://www.destroyallsoftware.com/talks/the-birth-and-death...
Alos, does anyone else get annoyed that operators aren't functions? I would love to write `_.reduce([1, 2, 3, 4], +, 0);` but instead I have to implement a sum function first. There's all sorts of little issues like this that make JavaScript a pain to work with.
Er, what?
> foo = [1, 2, 3]
[1, 2, 3]
> foo.map(function(i) { return i + 1; })
[2, 3, 4]
> foo
[1, 2, 3]Implementing map:
function map(f, ary) {
var ret = [];
for(var i = 0; i < ary.length; i+= 1) {
ret.push(f(ary[i]));
}
return ret;
}
https://github.com/clojure/clojure/blob/master/src/clj/cloju...
function map(f, ary) {
return [].map.call(ary, f);
}Functional programming in a language without pervasive immutability does require you to do some thinking about how you want to approach state, but this is just as true in many traditional functional languages like Scheme.
As for partial() and compose(), JavaScript already includes partial() in the form of Function.prototype.bind. And the compose() function shown there does not require the slice hack AFAIK, because it never does anything to arguments except take its length and access numeric indexes — but even if it did, I mean, that function has to do allocation in Scheme too.
HAMTs aren't unique to Clojure.
unordered-containers in Haskell has them, as well as Scala, Rubinius, and C++. There's a concurrent and lock-free version too.
Haskell's efficient and immutable containers library is based on papers from 1993 and 1973. Persistent Search Trees have existed as a topic of research since at least 1986.
So no, JS isn't excused here.
And, like, for any topic, you can usually point to some earlier research and say "Hey, look, there was this one paper so it's an old thing." But Haskell 98 wasn't even in existence when JavaScript came about. These were not mainstream ideas, even to the small degree they're mainstream now. The point is that JavaScript has similar limitations to many languages that were traditionally seen as supporting the functional style well around that time, such as most of the mainstream Lisps and OCaml. The ideas the OP is faulting it for not adopting were not well-explored despite having some old papers about them. (And from looking at history, I suspect trying to add those to the rush-job that was JavaScript would have resulted in eldritch horrors the human mind cannot fathom, so it was probably an OK choice not to get all experimental.)
Okasaki and Bagwell did a lot to expand and firm up knowledge on persistent data structures, but there have been persistent search trees (usable for hash-maps) for ages. Lists too.
Function.prototype.bind creates unnecessary GC pressure and performs like garbage. It's not realistic to use in any scenario where you care about performance.
I thought I'd come prepared with some templates this time.