This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

Mutually recursive functions in different modules
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 2007-09-19 (11:39) From: Andreas Rossberg Subject: Re: [Caml-list] Mutually recursive functions in different modules
```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

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

```