1 665c255d 2023-08-04 jrmu ;; Exercise 2.6.  In case representing pairs as procedures wasn't mind-boggling enough, consider that, in a language that can manipulate procedures, we can get by without numbers (at least insofar as nonnegative integers are concerned) by implementing 0 and the operation of adding 1 as
 2 665c255d 2023-08-04 jrmu 
 3 665c255d 2023-08-04 jrmu (define zero (lambda (f) (lambda (x) x)))
 4 665c255d 2023-08-04 jrmu 
 5 665c255d 2023-08-04 jrmu (define (add-1 n)
 6 665c255d 2023-08-04 jrmu   (lambda (f) (lambda (x) (f ((n f) x)))))
 7 665c255d 2023-08-04 jrmu 
 8 665c255d 2023-08-04 jrmu ;; This representation is known as Church numerals, after its inventor, Alonzo Church, the logician who invented the calculus.
 9 665c255d 2023-08-04 jrmu 
10 665c255d 2023-08-04 jrmu ;; Define one and two directly (not in terms of zero and add-1). (Hint: Use substitution to evaluate (add-1 zero)). Give a direct definition of the addition procedure + (not in terms of repeated application of add-1). 
11 665c255d 2023-08-04 jrmu 
12 665c255d 2023-08-04 jrmu (define one (add-1 zero))
13 665c255d 2023-08-04 jrmu 
14 665c255d 2023-08-04 jrmu (lambda (f) (lambda (x) (f (((lambda (f) (lambda (x) x)) f) x))))
15 665c255d 2023-08-04 jrmu ;;(lambda (f) (lambda (x) (f ((n f) x))))
16 665c255d 2023-08-04 jrmu (lambda (f) (lambda (x) (f (((lambda (f) f)) x))))
17 665c255d 2023-08-04 jrmu (lambda (f) (lambda (x) (f ((lambda (f) f) x))))
18 665c255d 2023-08-04 jrmu (lambda (f) (lambda (x) (f x)))
19 665c255d 2023-08-04 jrmu (lambda (f) (lambda (x) (f x)))
20 665c255d 2023-08-04 jrmu 
21 665c255d 2023-08-04 jrmu (define one (lambda (f) (lambda (x) (f x))))
22 665c255d 2023-08-04 jrmu (define two (add-1 one))
23 665c255d 2023-08-04 jrmu 
24 665c255d 2023-08-04 jrmu (lambda (f) (lambda (x) (f (((lambda (f) (lambda (x) (f x))) f) x))))
25 665c255d 2023-08-04 jrmu (lambda (f) (lambda (x) (f ((lambda (x) (f x)) x))))
26 665c255d 2023-08-04 jrmu (lambda (f) (lambda (x) (f (f x))))
27 665c255d 2023-08-04 jrmu 
28 665c255d 2023-08-04 jrmu (define two (lambda (f) (lambda (x) (f (f x)))))
29 665c255d 2023-08-04 jrmu 
30 665c255d 2023-08-04 jrmu ;; Give a direct definition of the addition procedure + (not in terms of repeated application of add-1). 
31 665c255d 2023-08-04 jrmu 
32 665c255d 2023-08-04 jrmu (define (+ a b)
33 665c255d 2023-08-04 jrmu   (lambda (f) (lambda (x) ((a f) ((b f) x)))))