Re: [Caml-list] Mutually recursive functions in different modules

[Andreas Rossberg <rossberg@mpi-sws.mpg.de>]

Julien Signoles wrote:
> I know (at least) 4 solutions to your problem: one use recursive modules
> as suggested by Jacques Garrigue, one use higher-order functions as
> suggested by Jean-Christophe Filliatre, one use functors and one use
> references on functions.

Having used most of these solutions in practice I thought that I may add 
my 2 cents.

> (* 1- using recursive modules *)
> module rec A : sig val f : int -> int end = struct
>   let f x = if x <= 0 then 0 else B.f (x - 2)
> end and B : sig val f : int -> int end = struct
>   let f x = if x = 1 then 1 else A.f (x - 2)
> end

That certainly is the natural solution, but unfortunately, does not 
currently allow separate compilation.

> (* 2- using higher-order functions *)
> module A' = struct let f g x = if x <= 0 then 0 else g (x - 2) end
> module B = struct let rec f x = if x = 1 then 1 else A'.f f (x - 2) end
> module A = struct let f = A'.f B.f end

In my experience, this solution does not scale at all. As soon as there 
are several mutual recursive functions involved that have to be called 
cross-module you have to parameterise all functions in A' over all those 
from B, and pass them through all local recusive calls in A'. That 
quickly gets out of hand, even if you use tuples. And don't even 
consider it for cases with more than 2 recursive modules.

> (* 3- using functors *)
> module FA(X:sig val f : int -> int end) = struct
>   let f x = if x <= 0 then 0 else X.f (x - 2)
> end
> module B = struct
>   let rec f x =
>     let module A = FA(struct let f = f end) in
>     if x = 1 then 1 else A.f (x - 2)
> end
> module A = FA(struct let f = B.f end)

Note that this solution is quite expensive, since the functor is applied 
repeatedly on each recursive invocation. Also, it would simply be 
incorrect if A had state.

The following variant probably is more appropriate:

(* 3a - using functors and recursive modules *)
module type B = sig val f : int -> int end

module FA(B : B) = struct
  let f x = if x <= 0 then 0 else B.f (x - 2)
end

module rec A : A = FA(B)
and B : B = struct
  let f x = if x = 1 then 1 else A.f (x - 2)
end

Note that you can separately compile FA and B. This is basically 
solution 2 lifted to the module level. You could also turn B into a 
functor as well to make it more symmetric and avoid having the actual 
definition of A being placed in B's compilation unit:

(* 3b - using functors and recursive modules symmetrically *)
module type A = sig val f : int -> int end
module type B = sig val f : int -> int end

module FA(B : B) = struct
  let f x = if x <= 0 then 0 else B.f (x - 2)
end

module FB(A : A) = struct
  let f x = if x = 1 then 1 else A.f (x - 2)
endnd

module rec A : A = FA(B)
and B : B = FB(A)

> (* 4- using references on functions *)
> module A' = struct let f = ref (fun _ -> assert false) end
> module B = struct let f x = if x = 1 then 1 else !A'.f (x - 2) end
> module A = struct
>   let () = A'.f := fun x -> if x <= 0 then 0 else B.f (x - 2)
>   let f = !A'.f
> end

This is what I mostly use in practice. It scales best, because it keeps 
the problem of tying the recursive knot local to the concerned modules 
and works directly with compilation units - i.e., no need for nesting 
the actual module definitions. Also, it does not get more complicated 
when more than 2 modules participate in the recursion. I usually stylise 
this approach by making the forward references to another module part of 
the signature as follows:

module A : sig
   module B : sig val f : (int -> int) ref end
   val f : int -> int
end = struct
   module B = struct let f = ref (fun _ -> assert false) end
   let f x = if x <= 0 then 0 else !B.f (x - 2)
end

module B : sig
   val f : int -> int
end = struct
   let f x = if x = 1 then 1 else A.f (x - 2)
   let () = A.B.f := f
end

The fact that this approach works best is somewhat unfortunate, because 
it relies on spurious use of state, and even makes that visible to the 
outside world.

In any case, all this gets much hairier when you want cross-module 
recursion across type definitions...

- Andreas