* 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
+ 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`):
-is implemented using regular, non-mutual recursion, like this (`f'` 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
- 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:
-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
+ C
- 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
+* 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 g = w h in
+ let f = u g h in
+ D