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=c62d620dae1229d786624117d008724a876d0b38;hb=f212354152a53c6a3ab018c7874570c600f463b9;hpb=7c8829dbea0cfaa2fedfb7d6fdd46d1558e9e68a diff --git a/hints/assignment_4_hint_3_alternate_1.mdwn b/hints/assignment_4_hint_3_alternate_1.mdwn index c62d620d..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 (`u` 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 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 + 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: +