If you like the article below, you might also enjoy:
- My recommended reading for programming languages.
- What every CS major should know.
- JavaScript: The Good Parts. Exactly that.
- JavaScript: The Definitive Guide. The reference on JavaScript.
Recursion as fixed points
Students of algebra are already familiar with recursion and fixed points.
They just don't realize it.
Consider an equation like "x = x^{2} - 2." (Programmers might recognize this as a recursive definition, in which x is being defined in terms of itself.)
If asked to solve for the value of x, a student might re-arrange the equation to use the quadratic formula. However, there is another way to express, and even find, the value(s) of x: fixed points.
A fixed point of a function f is an input that is equal to its output; that is x is a fixed point of the function f if x = f(x). Some functions have no fixed points; some have many. The notation Fix(f) denotes the set of fixed points of a function f.
Define the function f such that f(v) = v^{2} - 2. Then, observe that the original equation may now be re-written as "x = f(x)." In other words, the solutions to the equation are the fixed points of the function f! That is, Fix(f) = {-1,2}--a fact we can verify by seeing that
These are exactly the solutions to x = x^{2} - 2 given by Wolfram Alpha.
The insight that powers the upcoming technique is the observation that any time we have a recursive definition of the form "x = f(x)," the meaning of x is going to be defined in terms of fixed points.
The trick is to find a way to obtain fixed points when the equation has the form "f = F(f)," in which the value of f is not a number, but a function.
The Y combinator is that trick.
The Y combinator in theory
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 (unique) fixed point of that functional as its output. 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 recursive function we seek.
- Find the fixed point of a functional without recursion.
Deriving the Y combinator
The λ-calculus, the language in which the Y combinator is typically expressed, is a programming language which contains only anonymous functions, function applications and variable references. (Remarkably, this language is Turing-complete.) The notation λv.e stands for the function that maps the input v to the output e. JavaScript supports anonymous functions:
λv.e == function (v) { return e ; }
To derive the Y combinator, start with the core property we seek. Namely, if we give the Y combinator a functional F, then Y(F) needs to be a fixed point:
We could actually transliterate this definition into JavaScript as:
function Y(F) { return F(Y(F)) ; }
Of course, if we tried to use it, it would never work because the function Y immediately calls itself, leading to infinite recursion.
Using a little λ-calculus, however, we can wrap the call to Y in a λ-term:
Now, when we invoke the function Y, it immediately calls the function F, and passes it λ x.(Y(F))(x), which is equivalent to the fixed point.
Or, in JavaScript:
function Y(F) { return F(function (x) { return (Y(F))(x) ; } ) ; }
This function will actually find the fixed point of a functional, and we could use it to eliminate recursion. Of course, as defined, the function Y calls itself recursively, so we haven't really eliminated recursion yet. We've just moved it all into the function Y.
Using another construct called the U combinator, we can eliminate the recursive call inside the Y combinator, which, with a couple more transformations gets us to:
Note that the right-hand-side makes no reference to Y.
The Y combinator in JavaScript
Any untyped language which permits lexically scoped anonymous functions, such as JavaScript, can express the Y combinator without relying on recursion, iteration or side effects. Even 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:
Take a close look at the definition of Y. It uses only three kinds of expression: anonymous functions, variable reference and function application. Each anonymous function has the form function (argument) { return expression ; }. The Y combinator is a closed expression--it makes no explicit reference to an outside variable or to itself. Clearly, there is no recursion, iteration or mutation.
The Y combinator allows a concise
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 ... }) ;}) ;
It is inspiring to see what you can achieve in just a few extra characters.
Exploiting the Y combinator
The Y combinator is a significant result in the theory of computation and the theory of programming languages. It offers another way to think about nontrivial functions in terms of fixed points, rather than 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:
There are a couple caveats with this particular Ymem
:
Ymem
only works on functions of one argument, but this could be remedied with Javascript'sapply
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.
External resources
- Benjamin Pierce's Types and Programming Languages is a great resource for the lambda calculus and programming language theory.
- Doug Crockford's site is a great reference on advanced JavaScript.
- A cool paper by Daniel Brown and William Cook on monads, mixins, inheritence and, yes, fixed points.