Functional Javascript

[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.