Differences

This shows you the differences between two versions of the page.

@@ Line 1: / Line 1: @@
+====== 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
+<code scheme>
+(define zero (lambda (f) (lambda (x) x)))
+(define (add-1 n)
+  (lambda (f) (lambda (x) (f ((n f) x)))))
+</code>
+This representation is known as Church numerals, after its inventor, Alonzo
+Church, the logician who invented the calculus.
+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).
+====== Solutions ======
+Starting from substitution of (add-1 zero), with variables renamed to
+avoid confusion:
+<code>
+(lambda (f) (lambda (x) (f (((lambda (g) (lambda (y) y)) f) x))))
+(lambda (f) (lambda (x) (f ((lambda (y) y) x))))
+(lambda (f) (lambda (x) (f x)))
+</code>
+Therefore:
+<code scheme>
+(define one (lambda (f) (lambda (x) (f x))))
+(define two (lambda (f) (lambda (x) (f (f x)))))
+(define (+ m n)
+  (lambda (f) (lambda (x) ((m f) ((n f) x)))))
+</code>
+It is interesting to compare this with [[Exercise 1.43]].