X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=hints%2Fassignment_4_hint_3_alternate_1.mdwn;h=f75bad0efce8079169eac9a41b99cbd76c95e31f;hp=12ddbd6bd9a59bf1d4cb53dee2b15f103cf594ff;hb=5bda5b5a2df9af3e0b46179854b370819f14ced8;hpb=d1526a5f26872825688dbd957b8f9b296ff3cf71;ds=sidebyside
diff --git a/hints/assignment_4_hint_3_alternate_1.mdwn b/hints/assignment_4_hint_3_alternate_1.mdwn
index 12ddbd6b..f75bad0e 100644
--- a/hints/assignment_4_hint_3_alternate_1.mdwn
+++ b/hints/assignment_4_hint_3_alternate_1.mdwn
@@ -2,22 +2,57 @@ Alternate strategy for Y1, Y2
* This is (in effect) the strategy used by OCaml. The mutually recursive:
- let rec
- f x = A ; A may refer to f or g
- and
- g y = B ; B may refer to f or g
- in
+ let rec
+ f x = A ; A may refer to f or g
+ and
+ g y = B ; B may refer to f or g
+ in
+ C
+
+ is implemented using regular, non-mutual recursion, like this (`u` is a variable not occurring free in `A`, `B`, or `C`):
+
+ let rec u g x = (let f = u g in A) in
+ let rec g y = (let f = u g in B) in
+ let f = u g in
+ C
+
+ or, expanded into the form we've been working with:
+
+ let u = Y (\u g. (\f x. A) (u g)) in
+ let g = Y ( \g. (\f y. B) (u g)) in
+ let f = u g in
C
-is implemented using regular, non-mutual recursion, like this (`f'` is a variable not occurring free in `A`, `B`, or `C`):
+ We could abstract Y1 and Y2 combinators from this as follows:
+
+ let Yu = \ff. Y (\u g. ff ( u g ) g) in
+ let Y2 = \ff gg. Y ( \g. gg (Yu ff g ) g) in
+ let Y1 = \ff gg. (Yu ff) (Y2 ff gg) in
+ let f = Y1 (\f g. A) (\f g. B) in
+ let g = Y2 (\f g. A) (\f g. B) in
+ C
+
+
+* Here's the same strategy extended to three mutually-recursive functions. `f`, `g` and `h`:
- let rec f' g x = (let f = f' g in A)
- in let rec g y = (let f = f' g in B)
- in let f = f' g in C
+ let v = Y (\v g h. (\f x. A) (v g h)) in
+ let w = Y ( \w h. (\g. (\f y. B) (v g h)) (w h)) in
+ let h = Y ( \h. (\g. (\f z. C) (v g h)) (w h)) in
+ let g = w h in
+ let f = v g h in
+ D
-or, expanded into the form we've been working with:
+