author Jim Pryor Sat, 16 Oct 2010 20:41:43 +0000 (16:41 -0400) committer Jim Pryor Sat, 16 Oct 2010 20:41:43 +0000 (16:41 -0400)
Signed-off-by: Jim Pryor <profjim@jimpryor.net>

index 99a4202..b0c0673 100644 (file)
@@ -11,23 +11,43 @@ Alternate strategy for Y1, Y2

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
+               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 x. (\f. A) (u g)) in
-               let g = Y (  \g y. (\f. B) (u g)) in
-               let f =                     u g in
+               let u =    Y (\u g x. (\f. A) (u g))  in
+               let g =    Y (  \g y. (\f. B) (u g))  in
+               let f =                        u g    in
C

+       We abstract the 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 u = Y (\u g h x.      (\f. A) (u g h)) in
-               let w = Y (  \w h x. (\g. (\f. B) (u g h)) (w h)) in
-               let h = Y (    \h x. (\g. (\f. C) (u g h)) (w h)) in
+               let v = Y (\v g h x.      (\f. A) (v g h)) in
+               let w = Y (  \w h x. (\g. (\f. B) (v g h)) (w h)) in
+               let h = Y (    \h x. (\g. (\f. C) (v g h)) (w h)) in
let g =                                     w h in
-               let f =                            u g h in
+               let f =                            v g h in
D
+
+       Or in Y1of3, Y2of3, Y3of3 form:
+
+               let Yv    = \ff.       Y (\v g h.      ff (    v g h) g h)               in
+               let Yw    = \ff gg.    Y (  \w h. (\g. gg (Yv ff g h) g h) (       w h))  in
+               let Y3of3 = \ff gg hh. Y (    \h. (\g. hh (Yv ff g h) g h) (Yw ff gg h))  in
+               let Y2of3 = \ff gg hh.                                      Yw ff gg (Y3of3 ff gg hh)  in
+               let Y1of3 = \ff gg hh.                     Yv ff (Y2of3 ff gg hh) (Y3of3 ff gg hh)  in
+               D
+