hints/assignment_4_hint_3_alternate_1.mdwn

   1 Alternate strategy for Y1, Y2
   2
   3 *       This is (in effect) the strategy used by OCaml. The mutually recursive:
   4
   5                 let rec
   6                         f x = A  ; A may refer to f or g
   7                 and
   8                         g y = B  ; B may refer to f or g
   9                 in
  10                         C
  11
  12         is implemented using regular, non-mutual recursion, like this (`u` is a variable not occurring free in `A`, `B`, or `C`):
  13
  14                 let rec  u g x = (let f = u g in A)
  15                 in let rec g y = (let f = u g in B)
  16                 in let                f = u g in
  17                 C
  18
  19         or, expanded into the form we've been working with:
  20
  21                 let u = Y (\u g x. (\f. A) (u g)) in
  22                 let g = Y (  \g y. (\f. B) (u g)) in
  23                 let f =                     u g in
  24                 C
  25
  26 *       Here's the same strategy extended to three mutually-recursive functions. `f`, `g` and `h`:
  27
  28                 let u = Y (\u g h x.      (\f. A) (u g h)) in
  29                 let w = Y (  \w h x. (\g. (\f. B) (u g h)) (w h)) in
  30                 let h = Y (    \h x. (\g. (\f. C) (u g h)) (w h)) in
  31                 let g =                                     w h in
  32                 let f =                            u g h in
  33                 D