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)  in
  15                 let rec    g y = (let f = u g in B)  in
  16                 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. (\f x. A) (u g))  in
  22                 let g =    Y (  \g. (\f y. B) (u g))  in
  23                 let f =                        u g    in
  24                 C
  25
  26         We could abstract Y1 and Y2 combinators from this as follows:
  27
  28                 let Yu = \ff.    Y (\u g. ff ( u      g        ) g)  in
  29                 let Y2 = \ff gg. Y (  \g. gg (Yu ff   g        ) g)  in
  30                 let Y1 = \ff gg.             (Yu ff) (Y2 ff gg)      in
  31                 let f  = Y1 (\f g. A) (\f g. B)  in
  32                 let g  = Y2 (\f g. A) (\f g. B)  in
  33                 C
  34
  35
  36 *       Here's the same strategy extended to three mutually-recursive functions. `f`, `g` and `h`:
  37
  38                 let v = Y (\v g h.      (\f x. A) (v g h)) in
  39                 let w = Y (  \w h. (\g. (\f y. B) (v g h)) (w h)) in
  40                 let h = Y (    \h. (\g. (\f z. C) (v g h)) (w h)) in
  41                 let g =                                     w h in
  42                 let f =                            v g h in
  43                 D
  44
  45         <!--
  46         Or in Y1of3, Y2of3, Y3of3 form:
  47
  48                 let Yv    = \ff.       Y (\v g h.      ff ( v    g h) g h)                in
  49                 let Yw    = \ff gg.    Y (  \w h. (\g. gg (Yv ff g h) g h) ( w       h))  in
  50                 let Y3of3 = \ff gg hh. Y (    \h. (\g. hh (Yv ff g h) g h) (Yw ff gg h))  in
  51                 let Y2of3 = \ff gg hh.                                      Yw ff gg (Y3of3 ff gg hh)  in
  52                 let Y1of3 = \ff gg hh.                     Yv ff (Y2of3 ff gg hh) (Y3of3 ff gg hh)     in
  53                 let f = Y1of3 (\f g h. A) (\f g h. B) (\f g h. C)  in
  54                 let g = Y2of3 (\f g h. A) (\f g h. B) (\f g h. C)  in
  55                 let h = Y3of3 (\f g h. A) (\f g h. B) (\f g h. C)  in
  56                 D
  57         -->
  58