From d1526a5f26872825688dbd957b8f9b296ff3cf71 Mon Sep 17 00:00:00 2001 From: Jim Pryor Date: Sat, 16 Oct 2010 14:05:49 -0400 Subject: [PATCH 1/1] alternate strategy for Y1,Y2 Signed-off-by: Jim Pryor --- hints/assignment_4_hint_3_alternate_1.mdwn | 23 +++++++++++++++++++++++ 1 file changed, 23 insertions(+) create mode 100644 hints/assignment_4_hint_3_alternate_1.mdwn diff --git a/hints/assignment_4_hint_3_alternate_1.mdwn b/hints/assignment_4_hint_3_alternate_1.mdwn new file mode 100644 index 00000000..12ddbd6b --- /dev/null +++ b/hints/assignment_4_hint_3_alternate_1.mdwn @@ -0,0 +1,23 @@ +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 + C + +is implemented using regular, non-mutual recursion, like this (`f'` is a variable not occurring free in `A`, `B`, or `C`): + + 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 + +or, expanded into the form we've been working with: + + let f' = Y (\f' g x. (\f. A) (f' g)) in + let g = Y (\g y. (\f. B) (f' g)) in + let f = f' g + -- 2.11.0