<< 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. Poor 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 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"

I think you are right. As says, we can use induction to prove the book implementation is same as the definition after "encapsulates its argument". Then `(a add-1)` means same as "add-1 a times". The rest is trivial.

wikipedia definition can also easily explain why we should use `(a f) ((b f) x)` for `add`.


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

second-order function reference: in "What is the difference between the first order and second order functions in Python?" although in wikipedia it is called Higher-order function.


An easier explanation to understand:

 (define zero 
     (lambda (f) (lambda (x) x))) 
 (define one 
     (lambda (f) (lambda (x) (f x)))) 
 (define two 
     (lambda (f) (lambda (x) (f (f x))))) 
 It can be easily proved that (n f) is (lambda (x) (f (f .. (f x) .. ))) where f is repeated n times, by induction. 
 ((add n m) f) = ((n+m) f) 
               = (lambda (x) (f^(n+m) x)) 
               = (lambda (x) ((lambda (x) (f^n x)) (f^m x))) 
               = (lambda (x) ((lambda (x) (f^n x)) ((lambda (x) (f^m x)) x))) 
               = (lambda (x) ((n f) ((m f) x))) 
 (define (add n m) 
     (lambda (f) (lambda (x) ((n f) ((m f) x))))) 


Maybe a duplicate, but still...

 (define zero 
     (lambda (f) (lambda (x) x))) 
 (define one 
     (lambda (f) (lambda (x) (f x)))) 
 (define two 
     (lambda (f) (lambda (x) (f (f x))))) 
 ;; with the above, we can get 
 (define n 
     (lambda (f) (lambda (x) (f (f (f (f ... (f x)))))))) 
 ;;                          ------n times----- 
 ;; examine `add-1' 
 (define (add-1 n) 
   (lambda (f) 
     (lambda (x) 
       (f ((n f) x))))) 
 ;; consider `((n f) x)' in `add-1' 
 ((n f) x) 
   = (((lambda (f) 
         (lambda (x) 
         (f (f (f (f ... (f x))))))) 
       f) x) 
   = ((lambda (x) 
        (f (f (f (f ... (f x)))))) 
   = (f (f (f (f ... (f x))))) 
 ;; that is, f is applied n-times to x. 
 ;; thus, in `add-1', one is added by prepending 
 ;; ((n f) x) with an additional f 
 (f ((n f) x)) 
 ;; now, assume the result of applying f n-times 
 ;; to x is n-result 
 (define n-result ((n f) x)) 
 ;; if we want to apply f another m-times to n-result 
 ;; we would write 
 ((m f) n-result) 
 ;; which is 
 ((m f) ((n f) x)) 
 ;; put the result back into `add-1', we get 
 (define (add-m-n m n) 
   (lambda (f) 
     (lambda (x) 
       ((m f) ((n f) x)))))