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

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) zero (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) zero (add-1 (int->church (- n 1))))) ;; Iterative process (define (int->church n) (define (iter i result) (if (= i n) result (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 https://en.wikipedia.org/wiki/Church_encoding#Church_numerals 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: https://qr.ae/psQjDk in "What is the difference between the first order and second order functions in Python?" although in wikipedia https://en.wikipedia.org/wiki/Higher-order_function 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)))))) 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)))))

author of the ex 2.6 solution ^^^