# Church Numerals in Ruby

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

## Necessary Preface

• I have zero Ruby experience prior to this.
• All my Ruby knowledge comes from putting this together.
• However, Ruby has some very nice syntactic sugar with lambdas that I’ll take full advantage of.
• Try out some of the code blocks in `irb`!

### 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.

• Ruby has lambdas/procs like `f = lambda { |x| x + 1 }`. There’s also shorthand for lambdas that’s equivalent `f = ->(x) { x + 1 }`.
• Lambdas are called by `f.call(2)` (which produces `3`, in this case). They can also be called like `f.(2)` or even just `f[2]`. I’ll use the last one.
• Lambdas are composable. If we had some `f[g[x]]`, this is the same as `(f << g)[x]` or `(g >> f)[x]` (that is, shoveling composes procs). This can be chained for more than 2 procs too. I’ll be using this to compose functions together.

## Anyways, why does this matter?

• It’s cool.
• We know a lot of representations of numbers:
• Writing the digit `4`,
• holding up 4 fingers,
• or even `IV` in Roman numerals!
• four tick marks like ‘IIII’ on the wall, etc.
• this is one more!

## So, how do we do it?

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

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 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.)

``````pow = ->(n,m) { m[n] }