 Fixedpoints and Combinators
 Recursion
 Recursion as a Fixedpoint
 A More Practical Implementation
 More Than Divine
 Further Reading
 Notes and References
By now you’ve probably heard of the YCombinator and its cousin the ZCombinator but you may not have seen a derivation of it that made sense. There are tutorials and examples aplenty but they seem to skip steps or leave out some accompanying explanation leaving the reader with a sense of something missing. Let’s see if I can do better.
# Fixedpoints and Combinators
The fixedpoint of a function is the argument that you give to it so that it will return that same argument. A simple example:
λx. x * x
What value would be the fixedpoint of this function? 0
would work:
(λx. x * x) 0
→ (0) * (0)
→ 0
A function doesn’t have to have a single fixedpoint either. Let’s take the following:
λx. x
The absolute value (x
) will return the input when it’s nonnegative. Therefore every nonnegative number
is its fixedpoint.
The fixedpoints of functions aren’t restricted to numbers and strings of course. They can be other functions. A trivial example is the identity function:
λx. x
Every argument is a fixedpoint. If we restrict ourselves to only using functions as arguments, and only using the arguments specified we have “combinators”; simple enough. Now you know what a fixedpoint combinator is. In fact every combinator has a fixedpoint!^{1}
# Recursion
To iterate is human, to recurse divine L. Peter Deutsch
Here’s a function for calculating the factorial n!
:
let fact = n => {
let result = 1
while(n > 1) {
result *= n
n
}
return result
}
While the code is clear it’s imperative and procedural. It’s preferable to be declarative. We want to describe what we want to compute instead of the lowlevel^{2} details of how we compute it. Such code can be translated into recursive form:
let fact = n =>
n < 2 ? 1 : n * fact(n  1)
A significant improvement of clarity over the prior form. You can now more easily identify what the fixedpoint would be:
fact(1)
→ (1) < 2 ? 1 : (1) * fact((1)  1)
→ true ? 1 : (1) * fact((1)  1)
→ 1
Now, can we convert this into a combinator?
# Recursion as a Fixedpoint
Recall that a combinator is restricted to using its arguments and nothing outside of it. In other words, it has to be a closed expression.
The body of our fact
function references fact
but that’s not an argument. We can solve this problem through abstraction^{3}:
let fact = (self, n) =>
n < 2 ? 1 : n * self(n  1)
We obtained our closedexpression but now we’ve gotten ourselves into trouble. How do I call this function?
fact(?, 7)
A reasonable thought might be to just pass in fact
again:
fact(fact,7)
Which means that the recursive call would have to change to thread this extra parameter:
let fact = (self, n) =>
n < 2 ? 1 : n * self(self, n  1)
A quick test shows that this works:
fact(fact,7)
→ 5040
A bit inconvenient though and lowlevel^{2}. Let’s see if we can extract the essence of what’s going on and abstract this threading. We’ll begin with currying the function:
let fact = self =>
n => n < 2 ? 1 : n * self(self)(n  1)
If we call our curried function without the number parameter:
fact(fact)
→
n => n < 2 ? 1 : n * self(self)(n  1)
Notice the pattern? self(self)
in the body and fact(fact)
in the call.
Let’s give that form a name so we can obtain power over it^{4}:
let fact = self => {
let f = n => self(self)(n)
return n => n < 2 ? 1 : n * f(n  1)
}
A quick test and you see it still works:
fact(fact)(7)
→ 5040
The let
declaration feels a little dirty so let’s refactor that into a lambda as well:
let fact = self => {
return (f =>
n => n < 2 ? 1 : n * f(n  1)
)(
n => self(self)(n)
)
}
Then simplify:
let fact = self =>
(f =>
n => n < 2 ? 1 : n * f(n  1)
)(
n => self(self)(n)
)
If you’ve never seen a let
refactored into a lambda expression feel free to take a moment to compare the last two steps.
Basically the let variable f
becomes the parameter of an immediately invoked lambda expression and the body of the original
let becomes the argument.
Another quick test to show that it still works:
fact(fact)(7)
→ 5040
With all of this refactoring what did it get us? Notice that the innermost body of our new fact
has the same form
as the original before we turned it into a combinator. Let’s separate that innermost body into it’s own declaration:
let _fact = f => n =>
n < 2 ? 1 : n * f(n  1)
let fact = self =>
(
_fact
)(
n => self(self)(n)
)
Now let’s do something about that irritating fact(fact)(7)
call.
We’ll start by simply pushing the definition of fact
into an inner lambda and return the self application:
let _fact =
f => n => n < 2 ? 1 : n * f(n  1)
let fact = (() => {
let innerFact = self =>
(
_fact
)(
n => self(self)(n)
)
return innerFact(innerFact)
})()
Done!
fact(7)
→ 5040
Once again, let’s do some cleanup by refactoring that local let declaration into a lambda:
let _fact =
f => n => n < 2 ? 1 : n * f(n  1)
let fact = (() => {
return (
innerFact => innerFact(innerFact)
)(
self => (_fact)(n => self(self)(n))
)
})()
Then simplify:
let _fact =
f => n => n < 2 ? 1 : n * f(n  1)
let fact =
(innerFact => innerFact(innerFact))
(self => (_fact)(n => self(self)(n)))
The usage of innerFact
and self
look suspiciously similar. Let’s rename those variables to the same thing u
and see what that looks like. They’re in separate lexical scopes so we don’t have to worry about conflicts:
let _fact =
f => n => n < 2 ? 1 : n * f(n  1)
let fact =
(u => u(u))
(u => (_fact)(n => u(u)(n)))
fact
doesn’t exactly look like the factorial combinator anymore, moreso a setup for the actual factorial we care about: _fact
.
Let’s abstract and rename fact
to reflect this usage:
let _fact =
f => n => n < 2 ? 1 : n * f(n  1)
let setup = f =>
(u => u(u))
(u => f(n => u(u)(n)))
let fact = setup(_fact)
No need to be redundant with _fact
anymore so let’s inline it:
let setup = f =>
(u => u(u))
(u => f(n => u(u)(n)))
let fact = setup(
f => n => n < 2 ? 1 : n * f(n  1)
)
Now give f
a more meaningful name:
let setup = f =>
(u => u(u))
(u => f(n => u(u)(n)))
let fact = setup(
fact => n => n < 2 ? 1 : n * fact(n  1)
)
Looking at the body of setup
you see we have a second lambda being passed to the first lambda.
Let’s see if we can simplify this more by doing the application:
let setup = f =>
(u => f(n => u(u)(n)))
(u => f(n => u(u)(n)))
let fact = setup(
fact => n => n < 2 ? 1 : n * fact(n  1)
)
Well, how about that? We’ve just discovered the ZCombinator
which is the YCombinator in a callbyvalue language (like JavaScript). Let’s rename setup
to reflect our discovery:
let fix = f =>
(u => f(n => u(u)(n)))
(u => f(n => u(u)(n)))
let fact = fix(fact =>
n => n < 2 ? 1 : n * fact(n  1)
)
Final check:
fact(7)
→ 5040
Let’s try our fix
combinator on another definition to see if it works more generally:
let fix = f =>
(u => f(n => u(u)(n)))
(u => f(n => u(u)(n)))
let fib = fix(fib =>
n => n < 2 ? n : fib(n  1) + fib(n  2)
)
fib(12)
→ 144
Success!
# A More Practical Implementation
That definition of fix
though is a bit enigmatic to read at first glance though
even after going through the steps to derive it. You’d also be right to question
its efficiency. Can we improve our definition even more? The answer is yes but at
the expense of it no longer being a combinator and instead being a recursive
definition.
Here’s what we have:
let fix = f =>
(u => f(n => u(u)(n)))
(u => f(n => u(u)(n)))
Let’s begin with a betareduction of the self application to see if another pattern emerges:
let fix = f =>
f(n =>
(u => f(n => u(u)(n)))
(u => f(n => u(u)(n)))
(n)
)
Repeat:
let fix = f =>
f(n =>
f(n =>
(u => f(n => u(u)(n)))
(u => f(n => u(u)(n)))
(n)
)(n)
)
Once more:
let fix = f =>
f(n =>
f(n =>
f(n =>
(u => f(n => u(u)(n)))
(u => f(n => u(u)(n)))
(n)
)(n)
)(n)
)
Notice the pattern emerging? It looks suspiciously similar to the
very outer function, except that the outer fix
is missing the n
parameter. Let’s add that parameter and apply it to the top level f
call to match the nested ones:
let fix = f => n =>
f(n =>
f(n =>
f(n =>
(u => f(n => u(u)(n)))
(u => f(n => u(u)(n)))
(n)
)(n)
)(n)
)(n)
With this change let’s do a sanity check:
let fact = fix(fact =>
n => n < 2 ? 1 : n * fact(n  1)
)
fact(7)
→5040
So far so good. Now with our pattern clear, we’ll replace the
innermost selfapplication with fix(f)
let fix = f => n =>
f(n =>
f(n =>
f(fix(f))(n)
)(n)
)(n)
Repeat:
let fix = f => n =>
f(n =>
f(fix(f))(n)
)(n)
Once more:
let fix = f => n =>
f(fix(f))(n)
Final sanity check:
fact(7)
→5040
Compare our new definition with the original:
let fix = f =>
(u => f(n => u(u)(n)))
(u => f(n => u(u)(n)))
While the new one is no longer a combinator, from a practical point of view as a implementor the recursive form is probably preferable.
# More Than Divine
To recap, what we’ve accomplished so far is:
 Defined what a fixedpoint is
 Defined what a combinator is
 Introduced recursion
 Converted a recursive function into a fixedpont combinator and derived a generic way to define others.
So what? Is this just a party trick to just do recursion in disguise?
What we’ve discovered here is a third way to perform repetitive work. You know of looping, recursion, and now with fix
there is
rewriting. So to add to L. Peter Deutsch’s quote:
If recursion is divine then ‘fix’ is entelechy
Now go forth with your newfound knowledge and impress your fellow mortals.
# Further Reading
 Lambda Calculus
 To Mock a Mockingbird by Raymond Smullyan
 To Dissect a Mockingbird
 Fixedpoint combinators in lambda calculus
 Y in Practical Programs
 Oleg’s generic fix wrapper
# Notes and References

Belinfante J. G. F. (1987) S/K/ID: Combinators in Forth. § The Fixed Point Theorem. p. 565 ↩

“A programming language is low level when its programs require attention to the irrelevant.”  Alan Perlis ↩ ↩^{2}

If e is an expression and x is a variable, then
λx. e
is an abstraction. ↩ 
A double entendre. See True Name as well as Gerald Sussman’s use of the term in SICP. ↩
Comments