Jiahua Chen

Church Numerals in Ruby

A quick and dirty introduction to numbers in λ calculus, with a twist of Ruby.

Necessary Preface

So, what syntactic sugar?

Here’s some of the syntax that I use (and think is cool!). This is also all you need to know to understand this.

Anyways, why does this matter?

So, how do we do it?

We’ll represent numbers as a ‘function’. In lambda calculus, everything is a lambda (!).

We’ll follow this rule:

The Church numeral N is a function that takes in a function f as input, and produces a function that applies that function f, N times.

For example…

0 is represented as

zero = ->(f) { ->(x) {x} }

“The function that takes a function, and applies it 0 times. So it returns the identity function.”

1 is represented as

one = ->(f) { f }

“The function that just applies f once.”

And we can continue this…

two = ->(f) { f >> f }
three = ->(f) { f >> f >> f }

and so on.

(Note that we use the composition operator here! Recall that (f >> f)[x] is the same as f[f[x]] so we can use f >> f to represent the function that will apply f twice.)

But these are all #<Proc>s!

We can convert Church numerals into honest-to-goodness numbers. What does it mean for a function to be applied N times? We can apply the successor function N times to 0.

num_of_church = ->(n) { n[->(x){x.succ}][0] }

Church numerals (don’t) succ

We can now also define successors - we make a function that applies f just one more time (composing n f’s with one more).

succ = ->(n) { ->(f) { n[f] >> f } }

More numbers!

We can now get more numbers:

four = succ[three]
five = succ[four]

and so on.

Adding numbers

Adding numbers is functional composition (apply n times first, then apply m times more):

add = ->(n,m) { ->(f) { n[f] >> m[f] } }

try

num_of_church[add[five,two]]

In closing

We might want to do some more powerful things, like multiplication or taking powers. I’ll leave you to ponder the following:

mult = ->(n,m) { n >> m }
num_of_church[mult[three,five]]

(what is multiplying? we can do the act of [applying f n times] m times for a total of mn applications.)

how about…

pow = ->(n,m) { m[n] }
num_of_church[pow[three,four]]

(also try taking a zero’eth power!)

What about predecessor functions? Subtraction?


These are my notes, slightly edited, for a lightning talk presented at RubyConf Mini 2022.

To see more, take a look at Tom Stuart’s Programming with Nothing (thanks to many who recommended this to me) and his book Understanding Computation.

#ruby #lambda-calculus #functional-programming