some framing text
[lambda.git] / topics / week3_church_arithmetic.mdwn
1 We're continuing to assume Church's encodings of the numbers:
2
3 `0` &equiv; `\f z. z`, which is (convertible with) <code>\f z. f<sup>0</sup> z</code>    
4 `1` &equiv; `\f z. f z`, which is (syntactically identical to) <code>\f z. f<sup>1</sup> z</code>  
5 `2` &equiv; `\f z. f (f z)`, which is <code>\f z. f<sup>2</sup> z</code>  
6 `3` &equiv; `\f z. f (f (f z))`, which is <code>\f z. f<sup>3</sup> z</code>
7
8 One of your homework problems for last week was to define `succ` for this encoding. Here is how we do it:
9
10     \n. \f z. f (n f z)
11
12 Now how shall we define more advanced arithmetic functions, such as addition?
13
14 Let's recall the structural similarity between this encoding of the numbers and our right-fold encoding of lists. If we feed the number `3` the `succ` function and `0` as its arguments, we get:
15
16     3 succ 0 ~~>
17     succ (succ (succ 0))
18
19 and that will reduce to `\f z. f (f (f z))`, the same number with which we began. This parallels the fact that if we feed the `cons` function and `[]` as arguments to our encoded list `[a, b, c]`, we get:
20
21     [a, b, c] cons [] ~~>
22     cons a (cons b (cons c []))
23
24 and that will reduce to `\f z. f a (f b (f c z))`, the same list with which we began. You may recall that if you supply `cons` plus a *non*-empty list as arguments to a right-fold operation, the result is
25
26     [a, b, c] cons [d, e] ~~>
27     cons a (cons b (cons c [d, e]))
28
29 which will reduce to `[a, b, c] && [d, e]`, that is `[a, b, c, d, e]` or `\f z. f a (f b (f c (f d (f e z))))`. What if we did the analogous thing to our Church number? That is, what do we get if instead of `3 succ 0` we evaluate `3 succ 2`?
30
31     3 succ 2 ~~>
32     succ (succ (succ 2))
33
34 which we abbreviate as <code>succ<sup>3</sup> 2</code>. That will reduce to our encoding for `5`.
35
36 In general, this can be our strategy for performing the addition `add 2 3`. We can define **add** as:
37
38     \l r. r succ l
39
40 That lambda term cannot be further reduced, but
41 we can prove inductively that when that abstract is applied to any Church-encoded numbers `l` and `r`, the result will always be convertible with
42 `\f z. r f (l f z)`. So we can alternatively define **add** as:
43
44     \l r. \f z. r f (l f z)
45
46 This corresponds to the natural extension of our "exponential" metalanguage abbreviation:
47
48 <code>f<sup>l<b>+</b>r</sup> z &equiv; f<sup>r</sup> (f<sup>l</sup> z)</code>
49
50 (If you wonder why the `l`s and `r`s are in the specific orders they are here, the answer is that with `add` their order doesn't matter, but the pattern begun here coheres better with the orders needed for some other arithmetic functions to be described below.)
51
52 If we knew how to encode `pred`, then we could define subtraction in a similar way: `sub l r` would just be <code>pred<sup>r</sup> l</code>, or `r pred l`. We'd have to decide what `pred 0` should reduce to. Perhaps some special error formula, or a free variable `err`, or perhaps just to `0` --- in the same spirit that it can be natural to make `tail []` just be `[]`. A more pressing issue is that we don't know yet how to define `pred`. And in fact, with Church's encoding of the numbers, this is not trivial. We discuss the issue and give you some guidance about how to do it in this week's homework. (With some other encodings of the numbers, it is more straightforward to define `pred`; but then those other encodings have other compensating disadvantages.)
53
54 What about multiplication? Well, in general, `mul l r` should be the result of applying the (curried, partially applied) function `(add l)` to `0`, and then applying `(add l)` again to the result, and again, ... `r` times. In other words, it should be <code>(add l)<sup>r</sup> 0</code>. But given how we encode `r`, that will just be `r (add l) 0`. And so we can define **mul** as:
55
56     \l r. r (add l) 0
57
58 As with `add`,
59 we can prove inductively that when that abstract is applied to any Church-encoded numbers `l` and `r`, the result will always be convertible with
60 `\f z. r (l f) z`. So we can alternatively define **mul** as:
61
62     \l r. \f z. r (l f) z
63
64 This corresponds to the natural extension of our "exponential" metalanguage abbreviation:
65
66 <code>f<sup>l<b>*</b>r</sup> z &equiv; (f<sup>l</sup>)<sup>r</sup> z</code>
67
68
69 Interestingly, `mul l r` defined in that second way eta-reduces to `\f. r (l f)`, which we also know as the *composition* <code>r &cir; l</code> of `r` with `l`.
70
71 If we continue in this direction, we end up defining `l^r` (where `2^5` is `32`) either as `r (mul l) one` or as the *application* `r l` of `r` to `l`.
72
73 Not all of the arithmetic encodings are so neat and elegant, however. As we mentioned, `pred` takes some ingenuity. We'll also have you define `zero?` and <code>&leq;</code> for homework.
74
75 Here is an example of [some programmers having fun with Church numbers](http://www.schemers.org/Miscellaneous/imagine.txt). A tiny glossary: FORTRAN is a very old imperatival language that Scheme hoped to replace; SML is a sister language to OCaml; Chez is one Scheme implementation (like Racket and Chicken); and you will learn about "Y" next week. You should be able to figure out what the refrain means.