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

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:  20070919 (11:39) 
From:  Andreas Rossberg <rossberg@m...> 
Subject:  Re: [Camllist] 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 higherorder functions as > suggested by JeanChristophe 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 higherorder 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 crossmodule 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 crossmodule recursion across type definitions...  Andreas