Lambda Calculus, Pt. 3

Last time, we looked at representing natural numbers with Church numerals. In this post, we'll expand to representations of integers and rational numbers, and then look at recursion which will help us define division.

Integers

A simple representation of an integer is a pair (a, b), which has the value (b-a) where a, b are natural numbers. Every integer has a reduced form where either a or b are 0, but it'll often be easier to perform operations on integers in unreduced form before reducing them separately.

We can promote a natural number into an integer easily:

(int a) = (pair 0 a)

and we can negate an integer easily as well:

(neg i) = (swap i)

where (swap p) = (pair (snd p) (fst p)).

We can also define some useful predicates:

• (zero?z i) = (i =)
• (pos? i) = (i ≤)

The 'z' suffix indicates that it operates on integers. Remember that a pair p = (a, b) is simply (λx -> (x a b)), so (p f) = (f a b).

And the basic operations:

• (succz i) = (pair (fst i) (succ (snd i)))
  (predz is similar)
• (addz a b) = (pair
    (add (fst a) (fst b))
    (add (snd a) (snd b)))
  (subz is similar)

There are a few ways to reduce an integer. One is to find its magnitude and sign:

(magn i) = (((pos? i) (swap i) i) sub)

In essence:

• if i is positive (so a ≤ b), swap (a, b) into (b, a), then apply sub to get b-a.
• otherwise, we do the same but without swapping.

Note that magn returns a natural number. Therefore:

(reducez i) = (((pos? i) id neg) (int (mag i)))

Another way to reduce an integer is to call succz/predz on it repeatedly based on its sign:

(reducez i) = ((pos? i)
        ((fst i) succz i)
        ((snd i) predz i))

With the magnitude, we can define multiplication:

(multz a b) = (((xor (pos? a) (pos? b)) neg id)
    (int (mult (mag a) (mag b))))

• Since (xor a b) returns true iff a and b are different, we can use it to determine whether the product should be positive or negative.
• Then we simply multiply the magnitudes together.

Recursion

In the introduction, I mentioned that recursion can't be implemented in the typical way since lambda calculus doesn't have named functions. Thus, there's no way for a function to refer to itself.

Instead, we use something called a Y-combinator, which is a function that produces a recursive effect when it's applied to another function. The definition of the typical Y-combinator is:

Y = (λy -> ((λx -> (y (x x))) (λx -> (y (x x)))))

which is honestly impenetrable. I just pretend it's magic. In particular, if we apply Y to a function f, we get:

(Y f) = ((λx -> (f (x x))) (λx -> (f (x x))))
    = (f ((λx -> (f (x x))) (λx -> (f (x x)))))

which looks suspiciously similar to the previous step. In fact, this expression is just (f (Y f))! So we can see that (Y f) has the effect of "duplicating" the function f which can be applied to an earlier result, which is basically recursion.

If you're having trouble following along, it may help to try it yourself. Substitute (λx -> (f (x x))) into every instance of x in the first function, and you should end up with the 2nd line. Then convince yourself that this is just (f (Y f)).

We can illustrate how this works with an example, such as the factorial function (on natural numbers). We first define the helper function R:

R = (λr, n -> ((zero? n) 1 (mult n (r (pred n))))

We can think of this as the "body" of the recursive function, with:

• r as "itself"
• n (or any additional variables) as parameters.

Inside, we need a base case for the recursion to stop (which is when n = 0) and we use r where we want to call the function again. Then we can define:

(fact n) = (Y R)

Here's a demonstration:

(fact 3) = ((Y R) 3)
    = ((R (Y R)) 3)
    = (R (Y R) 3)
    = ((zero? 3) 1 (mult 3 ((Y R) (pred 3)))
    = (mult 3 ((Y R) 2)
    = (mult 3 (R (Y R) 2)
    = (mult 3 ((zero? 2) 1 (mult 2 ((Y R) (pred 2)))
    = (mult 3 (mult 2 ((Y R) 1)))
    ...
    = (mult 3 (mult 2 (mult 1 1))))
    = 6

You can see how the Y-combinator allows the function to keep unwrapping itself and taking (Y R) as the recursive argument over and over again until the base case is reached.

Now we can finally define division!

divR = (λr,a,b ->
    ((zero? a) 0 (succ (r (- a b) b))))

(div a b) = ((Y divR) a b)

Essentially, this subtracts b from a until a is 0, and counts the number of times this can be done.

We can extend this to integers exactly like how multiplication is defined:

(divz a b) = (((xor (pos? a) (pos? b)) neg id)
    (int (div (mag a) (mag b))))

Whew! I'll leave it as an exercise on how to extend this system to rational numbers (hint: use more pairs). You won't need any new tools. Try to also write a function that reduces a rational number to lowest terms.

Now that we've got a pretty good numeric system and recursion, we'll look at lists next!