tejohnso.github.com

SICP - 2.6 Church Numerals

A little bit about the church numerals exercise from Structure and Interpretation of Computer Programs. I've been trekking through the book with some occasional difficulty but this section was the most difficult so far. Credit goes to Bill the Lizard for the counting metaphor and much credit goes to Wikipedia for the detailed entry regarding Lambda calculus.

The exercise starts off with a definition for a strange representation of the number one.

(define one (lambda (f) (lambda (x) (f x))))

Turns out this is referred to as a Church numeral named after Alonzo Church who first formulated the Lambda calculus. This representation of one takes an action function and returns a function that executes the action on the next parameter once. To test it out, let's set up an action function for it to work on. We'll call it add-one.

(define (add-one x) (+ 1 x))

Now we can see use the Church numeral one combined with this add-one action and we should get one plus whatever target we pass to the resulting function.

((one add-one) 5) ;;6   The one numeral gets the action function add-one and applies it to 5 once.

We can think of this as being similar to counting. Imagine a bag with an inifinite number of oranges. If we want to start counting oranges we could apply a (take-orange) function to the bag. If we did that once we would have one orange taken from the bag. That's one way to look at the above defined function for one. If we wanted two, or three oranges we would apply the take-orange function two, or three times. Now we could do that by repeatedly applying the one function, but it's more convenient to use other numerals, like two for twice applying the take-orange function or three for thrice applying the take-orange function.

(define two (lambda (f) (lambda (x) (f (f x)))))
(define three (lambda (f) (lambda (x) (f (f (f x))))))

For a representation of zero, we would apply the action function 0 times, and just get back the unchanged target (our infinite orange bag remains untouched).

(define zero (lambda (f) (lambda (x) x)))

So zero will take a function and apply it 0 times to the target just giving the target back untouched.

((zero add-one) 5) ;; 5   Add-one never gets called

Now what about a plus function, can we create such a function that will operate on these number functions? If we think about a + b as the result of applying the action function b times to the target, and then applying the action function another a times, we can come up with a plus function that takes parameters a and b as follows:

(define (plus a b) (lambda (f) (lambda (x) ((a f) ((b f) x)))))

So we have a function that takes an action function f and returns a function that will take a target parameter x. It will then start applying the numbers using target function f. First we call the b number with action function f against x and use that result as the target parameter for a call of the a number with target function f. It helps to go through a few tests to see what's going on. For example:

((one add-one) 5) ;;6
((two add-one) 5) ;;7
((one add-one) 7) ;;8
(((plus one two) add-one) 5) ;;8

Let's look at that last line in more detail.

First (plus one two) gives us:

(plus one two)
(lambda (f) (lambda (x) ((one f) ((two f) x))))

(lambda (x) ((one add-one) ((two add-one) x)))

Now we pass our target of five as parameter x into the function that was returned.

((one add-one) ((two add-one) 5))
((one add-one) 7)
8

After that we reduce down similar to the earlier examples executing one numeral function after the other. Okay, so we have a plus function that only operates on two numeral functions. What about a more general plus function?

(define (multi-plus . c) ;;we'll take any number of parameters
  (lambda (f)
    (lambda (x)
      (define (recur num-list)
        (if (null? num-list)
          ((zero f) x)  ;;The last number to be added is zero
          (((car num-list) f) (recur (cdr num-list)))))
      (recur c))))

This version of plus continally applies the next number to the target. The target is the result of the previous number's application to the target. The last number to be applied is the zero number and ends the recursive addition process.

I've written this out and worded it in a way that I hope I will understand if I come back to it eight months from now. Hopefully it might be of use to somebody else as well.