<< Previous exercise (2.5) | Index | Next exercise (2.7) >>

The first tough question.

If zero is given as:

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

And add-1 is:

 (define (add-1 n) 
   (lambda (f) (lambda (x) (f ((n f) x))))) 

one is the result of (add-1 zero)

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

zero is a function of one arg, that returns a function of one arg that returns the argument (identity function), so ((zero f) x) is just x. So, one reduces to:

 (lambda (f) (lambda (x) (f x))) 

two is the result of (add-1 one)

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

substituting, and changing the lambda args for sanity:

  => (lambda (f) (lambda (x) (f (((lambda (a) (lambda (b) (a b))) f) x))))
  => (lambda (f) (lambda (x) (f ((lambda (b) (f b)) x))))
  => (lambda (f) (lambda (x) (f (f x))))

So, one and two are:

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

Applying add-1 again for kicks gives

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

So, the function f (or whatever) gets applied again and again to the innermost x.

To define add generally, the result will just be the function applied n times, where n is the (numerical) sum. add needs to take 2 args, a and b, both of which are 2-level nested lambdas (as above). So, the method signature is:

 (define (add a b) ...) 

and add needs to return a 2-level nested lambda, as a and b will be:

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

Essentially, we need to apply a's multiple calls to its f (its outer lambda arg) to b's multiple calls to its f and its x. Crappy explanation. We need the function calls to be like this:

 (fa (fa (fa (fa ... (fa xa))))...) 

and xa will be the call to b:

 xa = (fb (fb (fb ... (fb x))) ...) 

We pass f and x to b like this:

 ((b f) x) 

so, we have

 (fa (fa (fa (fa ... (fa ((b f) x)))))) 

but we need the function used by a in its outer lambda function to be the same as that used by b, or nothing will make any sense - using different functions would be like mixing octal and decimal numbers in a math problem. So, we pass f as the first lambda arg to a:

 (a f) 

and then a's inner lambda - a's x - will be ((b f) x)

So, the whole thing is:

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

Thanks to Ken Dyck for the hint.

Note: this explanation is friggin brutal. If you are more articulate than I, let 'er rip.


author of the ex 2.6 solution ^^^


If you wonder how to use these functions here are few examples..

1 ]=> ((one square) 2)

;Value: 4

1 ]=> ((two square) 2)

;Value: 16

1 ]=> (((add two one) square) 2)

;Value: 256

1 ]=> 


I found it helpful when experimenting to have a way to convert between integers and church numerals (e.g. to set up problems and also to confirm a solution). I used the following:

 (define zero (lambda (f) (lambda (x) x))) 
 (define (add-1 n) 
   (lambda (f) (lambda (x) (f ((n f) x))))) 
 (define (int-to-church n) 
   (define (iter a result) 
     (if (> a n) 
       (add-1 (iter (+ a 1) result)) 
   (iter 1 zero)) 
 (define (church-to-int cn) 
   ((cn (lambda (n) (+ n 1))) 0)) 


Hey jsdalton, thank you for the idea of procedures to convert between integers and church numerals. However, your int-to-church procedure doesn't need to define a helper procedure. The int-to-church procedure can be more succinctly written as:

 ;; Recursive process 
 (define (int->church n) 
   (if (= n 0) 
       (add-1 (int->church (- n 1))))) 
 ;; Iterative process 
 (define (int->church n) 
   (define (iter i result) 
     (if (= i n) 
         (iter (+ i 1) (add-1 result)))) 
   (iter 0 zero)) 


I think I have a much simpler and easier to understand solution, but I'm not convinced it's entirely correct

 (define (add a b) 
   ((a add-1) b)) 

Basically, you want to add-1 a times to b so you call a with add-1 and then call the resulting function with b to get a new function

Note: you should notice that this question says "not in terms of repeated application of add-1"


Here's yet another way of looking at it. A Church numeral is a second-order function: the numeral n is the function that turns f into "f composed with itself n times". Therefore we can define:

 (define one (lambda (f) f)) 
 (define two (lambda (f) (compose f f))) 

where compose is the function from ex1.42:

 (define (compose f g) (lambda (x) (f (g x)))) 

My short-cut for the "int->church" procedure is:

 (define (print-church n) 
   (display ((n inc) 0)) (newline)) 

Then we can do:

 (define (church-add m n) (lambda (f) (compose (m f) (n f)))) 
 (print-church (church-add one two)) 

Another interesting thing: multiplying Church numerals is actually easier than adding them!

 (define (church-mult m n) (compose m n)) 
 (define three (add-1 two)) 
 (print-church (church-mult two three))