X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=week4.mdwn;h=fb843462cfda3053bfe8c95651ae56fc72375d85;hp=78e2d37e8a4363b6ebe10e46baa2e0205148ab08;hb=e9750f1e80f6bb2ffe5193ea0c1e7abcf4482b61;hpb=21d0ff6296bd67c8828a6968b9e909078aa3aa67 diff --git a/week4.mdwn b/week4.mdwn index 78e2d37e..fb843462 100644 --- a/week4.mdwn +++ b/week4.mdwn @@ -51,9 +51,9 @@ successor. Let's just check that `X = succ X`:
let succ = \n s z. s (n s z) in
let X = (\x. succ (x x)) (\x. succ (x x)) in
succ X
-≡ succ ( (\x. succ (x x)) (\x. succ (x x)) )
+≡ succ ( (\x. succ (x x)) (\x. succ (x x)) )
~~> succ (succ ( (\x. succ (x x)) (\x. succ (x x)) ))
-≡ succ (succ X)
+≡ succ (succ X)
You should see the close similarity with `Y Y` here.
@@ -66,12 +66,12 @@ numeral:
[same definitions]
succ X
-≡ (\n s z. s (n s z)) X
-~~> \s z. s (X s z)
+≡ (\n s z. s (n s z)) X
+~~> \s z. s (X s z)
<~~> succ (\s z. s (X s z)) ; using fixed-point reasoning
-≡ (\n s z. s (n s z)) (\s z. s (X s z))
-~~> \s z. s ((\s z. s (X s z)) s z)
-~~> \s z. s (s (X s z))
+≡ (\n s z. s (n s z)) (\s z. s (X s z))
+~~> \s z. s ((\s z. s (X s z)) s z)
+~~> \s z. s (s (X s z))
So `succ X` looks like a numeral: it takes two arguments, `s` and `z`,
@@ -109,17 +109,17 @@ endless reduction:
let prefact = \f n. iszero n 1 (mul n (f (pred n))) in
let fact = Y prefact in
fact 2
-≡ [(\f. (\x. f (x x)) (\x. f (x x))) prefact] 2
+≡ [(\f. (\x. f (x x)) (\x. f (x x))) prefact] 2
~~> [(\x. prefact (x x)) (\x. prefact (x x))] 2
~~> [prefact ((\x. prefact (x x)) (\x. prefact (x x)))] 2
~~> [prefact (prefact ((\x. prefact (x x)) (\x. prefact (x x))))] 2
-≡ [ (\f n. iszero n 1 (mul n (f (pred n)))) (prefact ((\x. prefact (x x)) (\x. prefact (x x))))] 2
+≡ [ (\f n. iszero n 1 (mul n (f (pred n)))) (prefact ((\x. prefact (x x)) (\x. prefact (x x))))] 2
~~> [\n. iszero n 1 (mul n ([prefact ((\x. prefact (x x)) (\x. prefact (x x)))] (pred n)))] 2
~~> iszero 2 1 (mul 2 ([prefact ((\x. prefact (x x)) (\x. prefact (x x)))] (pred 2)))
~~> mul 2 ([prefact ((\x. prefact (x x)) (\x. prefact (x x)))] 1)
...
~~> mul 2 (mul 1 ([prefact ((\x. prefact (x x)) (\x. prefact (x x)))] 0))
-≡ mul 2 (mul 1 (iszero 0 1 ([prefact ((\x. prefact (x x)) (\x. prefact (x x)))] (pred 0))))
+≡ mul 2 (mul 1 (iszero 0 1 (mul 1 ([prefact ((\x. prefact (x x)) (\x. prefact (x x)))] (pred 0)))))
~~> mul 2 (mul 1 1)
~~> mul 2 1
~~> 2