Making Sense of Lambda Calculus 6: Recurring Problems
By Artyom Bologov
Timeline of Making Sense of Lambda Calculus
We know how to work with primitive data, like numbers and booleans. We also know how to handle aggregate data, like lists and monads. What’s missing is a way to act on them. Algorithms. The most obvious (to a Lisper like me, at least) class of algorithms is recursion. Let’s go over the ways recursion works in Lambda Calculus. And how to use it without destroying your computer.
Note that this post is shaped like an interactive notebook. All the code snippets in the post can be ran, modified, and re-ran. Some cells might depend on cells before them. Like this one, used in all the other cells. Run it!
function output (val) {
document.currentScript.closest("figure").querySelector("pre").innerHTML
+= "\n// " + val
}
output("Hello!")
In case you have an aversion to JavaScript and maybe disabled it, worry not. JS is not required for reading, and all the code snippets are still there. Just without the evaluation feature.
First of all we need some data to recur over. Like numbers! Remember numbers as compositions, right? We can assemble functions from numbers. And get numbers from these function applying them to the right data.
function tonum (fn) {
return fn((x) => x + 1)(0)
}
function fromnum (num) {
return (f) => (x) => {
let res = x
for (let i = 0; i < num; i++)
res = f(res)
return res
}
}
var iszero = (n) => {
return n (_ => false) (true)
}
var dec = (n) => {
return (f) => (x) => {
return n ((g) => (h) => h(g(f))) (u => x) (u => u)
}
}
var mul = (multiplicand) => (multiplier) => {
return (f) => (x) => multiplicand(multiplier(f))(x)
}
output(tonum(fromnum(5)))
Now that we talk of numbers…
Numbers Are Iterations Already #
The most basic loop type is iteration for a number of steps. Which is… exactly what LC numbers do: they are repeated compositions of the same function to a value. In case we need to, say, build a list of N same strings, we can just apply a number:
let n = fromnum(10)
let a_repeated_n_times = n(vals => ['a', ...vals])([])
output(a_repeated_n_times)
Given how many CS algorithms use for-loops with i counter,
we could stop here.
But that’s no fun and doesn’t cover what we’re here for: recursion
Omega: Smallest Recursive Combinator #
So the essential idea of recursion in LC is that: feed the function into itself. Recursive combinators are, then, just functions applying their argument to themselves. Right, Omega?
function omega (f) {
return f(f)
}
output(typeof omega)
You can see these types of functions in the wild, using Omega carelessly:
// (λb.bb) is Omega
λa.a((λb.bb)(λbcde.d(bb)(λf.fce)))(λbc.c)
Problems with Omega combinator:
- It requires the recursive function call to awkwardly apply to itself:
bb. Compare that to Y/Z combinators where you just call the wrapped recursive function directly. - It’s a normal order combinator, meaning it’l blow up the stack if you try running it.
- It’s too simple to be fun to digest.
On to the more horrible things then?
Y Combinator #
Ah, dreaded Y combinator! No, not that startup thing (though I’m not particularly excited about it either.) Y combinator is the next simplest functional combinator after Omega enabling recursion in Lambda Calculus.
I’m saying simple.
But not easy.
To be honest, I don’t fully understand how it works even now.
Because I see this definition below.
And I just don’t get it: where does the function argument go?
Where does factorial’s n argument fit?
function Y(f) {
return ((x) => f(x(x))) ((x) => f(x(x)))
}
output(typeof Y)
So let’s expand it step by step:
- Y(f)
- Y combinator is used on a function we need to make recursive
- ((x) => f(x(x))) ((x) => f(x(x)))
- After use, it expands into this application
- f(((x) => f(x(x)))(((x) => f(x(x)))))
- Which then feeds “into itself.” Yeah, I know, lots of parentheses. Did I tell you I’m a Lisp programmer?
- f(recur(recur))
- Now let’s abbreviate this
- f(recur(recur))(n)
- And add an argument.
And we have a necessary shape for e.g. factorial.
It took me a long time to understand that f is a two-argument function.
It consumes the recur part and asks for more.
And it only computes after it gets N.
Here’s a good talk explaining fixed point from zero to Y/Z combinators. Because I won’t be able to explain it well enough anyway. But run the code below to see the glorious Y combinator in action!
var _fac_y = (r) => (n) => {
if (iszero(n))
return fromnum(1)
else
return mul(n)(r(dec(n)))
}
output(Y(_fac_y)(fromnum(5)))
Except… “InternalError: too much recursion” (on Firefox.) Which means that Y combinator, calling itself infinitely, has blown up the stack. Normal vs. Applicative all over again. We need Y combinator, but the one that’ll run properly in applicative systems (like JavaScript.) Enter…
Z Combinator #
Z (what an unfortunate name) combinator is Y with benefits.
It’s friendly to applicative systems, while being almost as simple as Y.
The trick is to wrap every recursive call into an additional lambda.
This lambda will only be unwrapped when r argument is called.
And only after that will Z reproduce itself, for one more step of recursion.
function Z(f) {
return ((x) => f((y) => x(x)(y))) ((x) => f((y) => x(x)(y)))
}
// Yes, it’s exactly the same as _fac_y!
// Z combinator is a drop-in replacement for Y
var _fac_z = (r) => (n) => {
if (iszero(n))
return fromnum(1)
else
return mul(n)(r(dec(n)))
}
output(tonum(Z(_fac_z)(fromnum(5))))
Cheating, cheating!
The code works now.
But one thing you might’ve noticed is that I’m not doing full Lambda Calculus.
I’m using JavaScript’s own if and booleans instead of LC ones.
This is purely for brevity’s sake.
I know how to handle conditionals in applicative systems.
And I know how booleans work too.
But I shouldn’t be too stringent, and neither should you.
Look, interactive cells!
fromnum(30)((x) => output("Sorry!"))(0)
But how far can one go with a single function argument? It’s always possible to store args in an aggregate structure, like tuple or triple. But that’s a really inconvenient arrangement. We need more args!
Z2 Combinator and Multi-Argument Combinators #
I also owe some to this Github repository of Călin Cruceru. They’ve done a really great job of explaining Y combinator and its siblings. With code samples and potential problems. It’s also where I stole the idea of Z2 combinator to solve the multi-arg problem:
function Z2 (f) {
let inner = ((x) => f ((y) => (z) => x(x)(y)(z)))
return inner(inner)
}
// Yeah, this is cheating, but do you really want to see
// THE REAL MOD FUNCTION???
function mod (x, y) {
return fromnum(tonum(x) % tonum(y))
}
// Euclidean Greatest Common Denominator
var _gcd_z2 = (r) => (x) => (y) => {
if (iszero(y))
return x
else
return r(y)(mod(x, y))
}
output(tonum(Z2(_gcd_z2)(fromnum(10))(fromnum(5))))
The idea generalizes well to more arguments: just add yet another level of lambdas! (It’s always solved like this in Lambda Calculus, isn’t it?) So we have a working applicative-friendly way to do recursion on multiple arguments in Lambda Calculus. I consider it a success.
THE REAL MOD FUNCTION
Modulo function is indivisible (🥁) from division function. So here’s horrible lambda-juggling division. (Cold sweat goes down my spine at the thought of reproducing it in JS.) And here’s modest modulo. It’s not that scary. But the whole amount of infrastructure needed for it is stupefying.
- subtraction:
- predecessor
- multiplication
- division:
- T combinator
- K combinator
- I combinator/identity
Reproducing it here would take a lot of time and page space. I’m not ready for that. I’ll leave full lambda implementation to the bold among the readers.
This post is less structured and more interactive than the previous ones. That’s because I don’t fully understand how Omega/Y/Z/Z2 work. And I don’t really care, as long as they help me building recursive algorithms. I promise, the next piece will be slightly more involved. (Maybe because I’ll get over the excitement of having interactive JavaScript cells in my posts?)
output("Bye, reader!")