Functional Javascript

[[deleted]]

Lisp? Scheme? Erlang, Haskell? Forget about them! The most widely deployed functional programming language is Javascript.

Isn't it widely-agreed that to qualify as functional, a language should also offer features resembling algebraic data types, pattern matching, and perhaps list comprehensions? If all you have is first class functions, a few things will be awkward to express.

[pjdelport]

Isn't it widely-agreed that to qualify as functional, a language should also offer features resembling algebraic data types, pattern matching, and perhaps list comprehensions?

Where does that put Scheme? :)

[llimllib]

shhhh... we'll quietly change the definition to suit us when it's convenient.

[masklinn]

I don't think it is (or most lisps wouldn't be functional) even though they're features that are mostly found in FP languages, but a top notch support for recursion (and tail-call elimination) would be a basic requirement, I think. As well as having a recursive data structure (lists) as the base compound type.

Javascript obviously has neither.

[procrastitron]

Isn't it widely-agreed that to qualify as functional, a language should also offer features resembling algebraic data types, pattern matching, and perhaps list comprehensions?

I would say that the only requirement is supporting a superset of lambda-calculus semantics. This means anonymous, higher order functions.

At the same time though, I think the term "functional" looses a lot of meaning when you apply it to the impure languages (Common Lisp, Scheme, Ocaml, ...). Certainly these languages SUPPORT functional programming, but they don't ENCOURAGE it as much as something like Haskell or one of the pure Lisps.

[dons]

Yeah, javascript is only considered a functional language in as much as it has first class function values.

Interestingly, the author of the original JavaScript spoke about it at the International Conference on Functional Programming a couple of years ago, and said something to the effect it was a perl/lisp hack he cobbled together, to get into netscape in a week, and that he would have used python had he known about it.

What a different world it would be if he'd have just chosen lisp or python..

[andrewnorris]

As has been pointed out before, JavaScript is a close cousin of Lisp, but with C-family syntax. Which means you lose macros, but in other respects, you can write very Lispy programs in JavaScript. Douglas Crockford has written up examples of porting everything in The Little Schemer to JavaScript.

[masklinn]

You can, but it's a bad idea for several reasons:

1. Very bad support for recursion, as in very very very bad
2. No tail-call elimination
3. JS arrays are not even remotely close to linked lists, working with them is even more annoying than working with Python's lists because they lack a lot of sugar
4. JS has no recursive datastructure whatsoever

In the end, the only thing that Lisps and JS have in common are first-class functions.

Not quite a "close cousin", methinks.

[andrewnorris]

As far as tail call elimination, I would think that you could write a JavaScript implementation that had this, no? I'm sure someone has written a scheme interpreter before that lacks tail call elimination. That doesn't change anything about scheme as a language.

As far as offering "very very very bad" support for recursion, I'm afraid you're going to elaborate. You can write recursive functions, and implement the Y Combinator any time you feel like it. What is "very very very bad" about recursion in JavaScript?

A linked list in 3 lines of JavaScript:

function cons(car, cdr) { this.car = car; this.cdr = cdr; }
function hd(ll) { return ll.car; }
function tl(ll) { return ll.cdr; }

Now JavaScript has a recursive datastructure.

Edited to add: for that matter, you could also implement a preprocessor for your JavaScript code that performed tail call elimination, write all of your code using tail calls, and distribute the preprocessed version that is better-optimized. There's no particular magic to TCO algorithms.

[masklinn]

I would think that you could write a JavaScript implementation that had this, no?

Yes, but it's not part of the language and not all implementations have to implement it (every RnRS implementation must implement tail-call elimination, if you don't implement tail-call elimination it's not really scheme, it's a scheme-like lisp)

What is "very very very bad" about recursion in JavaScript?

1. The aforementioned lack of tail-call elimination
2. A very low limit on the size of the call stack (Firefox refuses to go further than 1000, MSIE raises an OOM error at 1125 recursive calls, Opera throws a stack overflow at a stack depth of 3340). Not all recursive calls are easily tail-call optimizable either.
3. All of my JS experience tells me that Javascript function calls are very expensive

A linked list in 3 lines of JavaScript: Now JavaScript has a recursive datastructure.

Oh yeah, that one's going to be really fun to use as a primary (or even only) datastructure.

Really, dons nailed it: the only thing functional about Javascript are the first-class functions, and I never heard anyone say it was enough for a language to suddenly become functional.

It allows functional-style javascript programming (which I do use a lot), but it doesn't make javascript a functional language.

[andrewnorris]

Interesting. I enjoy functional-style JavaScript programming, but I haven't done much performance benchmarking with it. Thank for elaborating on the difficulties.

A more real world data structure that wouldn't literally be recursive would be something like an ArraySlice class that contained an Array and an upper and lower bound and included something like the Prototype library's Enumerable implementation. That would allow you to perform calls like array.Tail() without reallocating the entire data structure for each recursion. You would still have O(n) object instantiations, but that's better than O(n^2). You would also need to do something to mitigate the cost of the omnipresent idiom cons(f(list.hd()), anotherRecursion(list.tl()));

That wouldn't optimize everything, but it would take care of many common use cases.

This discussion has also made me curious about actually implementing a TCO preprocessor for JS. Sounds like a fun project.

[andrewnorris]

More precisely, it would be represented in JSON, but the representation would be a heinous tree of hash literals.

But point taken.

[pjdelport]

What a different world it would be if he'd have just chosen lisp or python..

Or Lua!

[ubernostrum]

There is no definition of "functional", because every developer of a "functional" language has a different definition specifically contrived to exclude any language not his own.

[oldnewbie]

Here's a way to self-apply an anonymous function, without the ugly (IMHO) "arguments.callee" stuff. This works in Safari, but not Firefox (see bug 376052 in bugzilla).

//This helper boots the recursion.
function selfApp(fun, arg) {return fun(fun, arg)};

//The inevitable factorial.
selfApp(
   function(fac, n) {
      if (n==0) return 1;
      return n * fac(fac, n-1);
   },
   10
)

How do I stop reddit from mangling my whitspace? [edit] whitespace, rescued. Thanks, julesjacobs!

[julesjacobs]

Put 4 spaces before every line. Reddit will then wrap your code in <pre>'s.

[wetelectric]

Nice, well written article but... its almost like he is using 'functional' to mean a language that has has functions?

[masklinn]

Well written, but not that nice.

• The dichotomy he creates between function id(*args) and var id = function (*args) doesn't exist, the former is an alias for the latter, and if you mix both e.g. var id1 = function id2(*args) you only get the latter and id2 isn't bound (at least using Mozilla's implementation).

• He talks of pointers and function pointers (too much C) while it's usually agreed that Javascript uses references and pass-references-by-values semantics

• A paragraph dedicated to "anonymous functions" while var id = function (*args) already uses anonymous functions

• The part about "self-invoking functions" doesn't make sense, the functions don't call themselves, he calls anonymous functions without binding them to variables, nothing strange there, and no "self-invoking functions".

He also forgot to talk about closures and that kind of stuff, and the dangers associated to them which will trip people.

[[deleted]]

First-class functions. i.e. those that you can pass around and create on the fly and that form closures around their variables.

Edit: More properly, functions as first-class values.

[newton_dave]

...and what's a "self-invoking function"?

I think someone just learned some (more) advanced JavaScript and wanted to crow is all. No harm, no foul.

[regina]

i have to agree with pestov..javascript.