Hacker News Reader

Comment by bsimpson | Hacker News Reader

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?

View on HN

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

You can use a trampoline like the one the author has written in this library 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.

or rather than creating an iterator yourself, use setTimeout(..., 0) to put the next call on the event loop.

I talk about that too. :-)

Functional programming doesn't have to mean deep recursion-- it's not like you can't use functions and loops in the same code.

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

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

Functional 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; }
      );
  }

Functional Programming is much more than just recursion.

There are lots of concepts that are still applicable even when using imperative loops.

That would highly depend on if you're writing performance-sensitive code, and I doubt most JS would be greatly affected by these paradigms.

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

By "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.

I did also say "naive use" =) Looking forward to the book.

It'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?

Sorry for the late response. I will not cover ES6 tail calls very much at all except to mention the possibility for inclusion.

Right, 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.

Yes, 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.

Who needs loops nowadays? Just map, reduce, filter and imperatively-loop when needed (around 0.1% of cases?).

I think that because TCO is all but inevitable in future engines/standards, starting to use functional patterns now for the programming benefits is worthwhile.

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

I prefer Underscore's implementation of `each`. It doesn't blow the stack. http://underscorejs.org/docs/underscore.html#section-13

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

Reply on news.ycombinator.com