Disfunctional RSS

Where misquotes, misinformation, and misspellings occur daily.

Archive

Sep
30th
Sun
permalink

Tail call optimization on it’s way… Who gives a frak?!

I’m going to talk about capturing different recursive patterns in higher order functions and how we are better off with them over explicit recursion anyways. But first, let’s quickly go over what recursion is in javascript and why we might care about it.

Recursion in javascript

What is recursion? Well, it’s just calling a function from within itself. It is usually used as a replacement for loops in functional languages.

Let’s define a recursive version of Array#reverse. We need a couple of helper functions: head and tail.

head = function(xs) {
  return xs[0];
};

tail = function(xs) {
  return xs.slice(1, xs.length);
};
head will grab the first item in an array and tail will return everything but the first item. Now then, reverse!

reverse = function(xs) {
  if(xs.length == 0) return xs;
  return reverse(tail(xs)).concat(head(xs));
}

reverse([1,2,3,4]) // [4,3,2,1]
First, we create a base case that returns the empty array if the length is 0. This prevents us from looping forever. Then, we just concat the first item with the result of calling this function recursively on the tail, essentially sticking it on the end of the new array we’re building.

When I first was acquainted with recursion, I kept trying to visualize the stack and each step in the process. Now, I find it much easier to just mentally replace the recursive call with what would be the result. In this case, that would be return [4,3,2].concat(1);

Okay, on with the show

reverse doesn’t have to be defined recursively. We can use a good old fashion loop.

reverse = function(xs) {
  var result = [];
  
  for(x in xs) {
    result = [xs[x]].concat(result);
  }
  return result;
}
There are some benefits of recursion. It’s elegant, it reads well, it’s not creating messy variables to keep state or reassigning/destroying them. But in javascript, it is not very practical. For one, the syntax is a bit clunky. If you contrast this with an erlang or haskell example, it highlights how unnatural recursion is in javascript. Here’s haskell:

reverse [] = []
reverse (x:xs) = reverse xs ++ [x]
The (x:xs) part uses built in pattern matching to extract the head from the tail of the array. Also we can define the function twice - once for the base case.

A second reason recursion isn’t very practical in javascript is the compiler is not optimized to keep track of all the recursive calls. They say tail call optimization is coming, which is a compiler trick to release memory during each iteration, but I say don’t worry, we can do better than both of these…

A better way


reverse = reduce(function(acc, x){ return [x].concat(acc); }, []);
Check that out! We don’t have to specify any iteration at all. We can just leave it to the reduce function to figure that out. I’ve used partial application here and only gave reduce two of it’s three arguments.

What’s more, since I’m familiar with the function, I know just by reading the word reduce that we’re capturing a specific recursion pattern where the base case is an empty list and for each iteration we apply a function to an accumulator and the element from the list. Here it is explicitly:

reduce = function(f, acc, xs) {
  if(xs.length == 0) return acc;
  return reduce(f, f(acc, head(xs)), tail(xs));
}
Now, reduce isn’t actually implemented using this recursion pattern above for performance reasons, but that makes no difference to us. We captured the pattern in a named abstraction (reduce) and now we’re unshackled from the chains of iteration…or something like that.

The pattern we just witnessed was a catamorphism - your basic fold.* In fact, most languages call reduce foldl for fold left.

Our beloved map is just a specific implementation of this recursion pattern. So is filter. That means we can implement each of these methods in terms of reduce.

But wait, there’s more

There isn’t just one type of recursion pattern out there. There are a number of them and each have their own qualities. For instance, if, in addition to the accumulator and current element, you want access to the rest of the array during each iteration use a paramorphism.

paraReduce = function(f, acc, xs) {
  if(xs.length == 0) return acc;
  return paraReduce(f, f(acc, head(xs), xs), tail(xs));
}
This is just like the catamorphism, except that we pass the extra xs into the supplied function.

On top of instant recognition of the named pattern, DRY code, and easy swapping of recursion strategies, we’ve opened the door to different implementations of our underlying loop. That means we can optimize under the hood.

There’s a law (via functors) that states the following:

compose(map(f), map(g)) == map(compose(f, g))
So instead of looping through the whole array and running g, then doing the whole thing again and running f, we can just make 1 loop and run compose(f, g) for the same result.

// not fused
compose(map("*2"), map("+1"))

// fused
map(compose("*2", "+1"))
}
We can also use our abstractions to run in parallel or add any other optimizations you can imagine. If we had two explicit loops going on there, it’d be very difficult to make this kind of change. The point is when you program declaratively you leave room for different implementation.

A vulgar display of explicit iteration

So in conclusion, I say frak the tail-call optimization! We’re reaping the all benefits of abstraction, labeling our patterns for easy understanding, writing smaller, more concise code…why did we want all this messy recursion back in our applications again anyways?

*Hopefully, I’ll do a post on anamorphisms (or unfolds) soon. Until then, check out this paper
blog comments powered by Disqus