sicp-ex-2.6

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:

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:

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:

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:

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

author of the ex 2.6 solution ^^^

shyam

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 ]=>

jsdalton

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

anonymous

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

anonymous

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"

LisScheSic

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

alexh

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

LisScheSic

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.

seok

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