Fixed-point combinators in Javascript: Memoizing recursive functions

Is it possible to express a "recursive" function like factorial without using recursion or iteration? The answer--often surprising--is yes. The technique involved--expressing recursive functions as fixed-points--leads to a more fundamental understanding of recursion. And, as a practical application of this theory, recursive functions expressed as fixed points allow the use of a memoizing fixed-point combinator that can memoize even the internal call sites of a recursive function. This can, for example, turn the naive, exponential implementation of Fibonacci into the optimized, linear-time version for free.

In his research on the λ-calculus and combinatory logic, Haskell Curry discovered the "paradoxical" fixed-point combinator known as the Y combinator. The Y combinator takes a functional as input, and it returns the fixed point of that functional as its output. A fixed point of a function f is an input x that is equal to its output: x = f(x). A functional is a function that takes a function for its input. Therefore, the fixed point of a functional is going to be a function.

Using the concepts of functionals and fixed points, we can eliminate explicit recursion for a function through two steps:

Find a functional whose fixed point is the function we seek.
Find a way to find the fixed point of a functional without recursion.

A simple source transformation takes care of the first step. The Y combinator takes care of the second step.

Remarkably, any untyped language which permits lexically scoped anonymous functions (such as Javascript) can express the Y combinator without relying on recursion or side effects. Without understanding how the Y combinator works, you still can see it in action and verify for yourself that no recursion or iteration is used. The following example expresses the factorial function without using recursion:

// A "functional" is just a function that takes
// another function as input.  

// The Y combinator finds the fixed point
// of the "functional" passed in as an argument.

// Thus, the Y combinator satisfies the property:

//     Y(F) = F(Y(F))

// Note that Y does not reference itself:
  
var Y = function (F) {
 return (function (x) {
  return F(function (y) { return (x(x))(y);});
  })
        (function (x) {
  return F(function (y) { return (x(x))(y);});
  }) ;
} ;

// (In fact, all functions above are anonymous!)
 

// FactGen is the functional whose fixed point is
// factorial.
  
// That is, if you pass the factorial function to
// FactGen, you get back the factorial function.

// Since the Y combinator returns the fixed point
// of a functional, applying the Y combinator to
// FactGen returns the factorial function!

// Note that FactGen does not reference itself:
  
var FactGen = function (fact) {
 return (function(n) {
  return ((n == 0) ? 1 : (n*fact(n-1))) ;
 });
} ;

  
document.getElementById("result1").innerHTML
  = (Y(FactGen))(6) ;

[result1]

What's remarkable about the Y combinator is that it allows a simple transformation from a recursive function to a non-recursive function. If we have a recursive function f:

function f (arg) {
 ... f ...
}

This definition can be transformed into a non-recursive form:

var f = Y(function(g) { return (function (arg) {
 ... g ...
 }) ;}) ;

The Y combinator is a significant result in the theory of computation and the theory of programming languages, but practically speaking, it offers another way to think about nontrivial functions outside of the standard paradigms of recursion and iteration.

For instance, suppose we define a recursive function using the functional-fixed-point paradigm: can we then create a fixed-point combinator that automatically gives us better performance for the function? The answer is yes. We can create a memoizing fixed-point combinator: a Y-like combinator that caches the results of intermediate function calls.

For example, the naive way of defining Fibonacci using recursion makes two recursive calls, leading to exponential time complexity:

function fib(n) {
 if (n == 0) return 0 ;
 if (n == 1) return 1 ;
 return fib(n-1) + fib(n-2) ;
}

We could however, define Fibonacci using the Y combinator:

var fib = Y(function (g) { return (function (n) {
 if (n == 0) return 0 ;
 if (n == 1) return 1 ;
 return g(n-1) + g(n-2) ;
}) ; }) ;

This formulation still has exponential complexity, but we can change it to linear time just by changing the fixed-point combinator. The memoizing Y combinator, Ymem, keeps a cache of computed results, and returns the pre-computed result if available:


// Ymem takes a functional and an (optional)
// cache of answers.

// It returns the fixed point of the functional
// that caches intermediate results.
  
function Ymem(F, cache) {
 if (!cache)
  cache = {} ; // Create a new cache.
 return function(arg) {
  if (cache[arg])
   return cache[arg] ; // Answer in cache.
  var answer = (F(function(n){
   return (Ymem(F,cache))(n);
  }))(arg) ; // Compute the answer.
  cache[arg] = answer ; // Cache the answer.
  return answer ;
 } ;
}

var fib = Ymem(function (g) { return (function (n) {
 if (n == 0) return 0 ;
 if (n == 1) return 1 ;
 return g(n-1) + g(n-2) ;
}) ; }) ;

document.getElementById("result2").innerHTML =
 fib(100) ;

[result2]

There are a couple caveats with this particular Ymem:

Ymem only works on functions of one argument, but this could be remedied with Javascript's apply method and the use of a trie-like cache.
Ymem only works for indexable argument values like numbers and strings, but this can be circumvented by supplying a comparator on argument values, so that it can use a sorted tree for the cache.

The end result is that the 100th Fibonacci number is computed instantly, whereas the naive version (or the version using the ordinary Y combinator) would take well beyond the estimated lifetime of the universe.