Mutually recursive functions in different modules

Mutually recursive functions in different modules

[Arthur Chan]

[-- Attachment #1: Type: text/plain, Size: 435 bytes --]

Hey all,

Is it possible to have mutually recursive functions in separate modules?

For example, is it possible for function x in module A to call function y in
module B and vice versa?

The reason why I'm asking is because I've written a good bit of my code with
functors, and now I need to make some of the code mutually recursive, and
thus, the mutually recursive functions have to be in separate modules.

Best Regards
Arthur Chan

[-- Attachment #2: Type: text/html, Size: 471 bytes --]

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

[Jacques Garrigue]

From: "Arthur Chan" <baguasquirrel@gmail.com>
> Is it possible to have mutually recursive functions in separate modules?
> 
> For example, is it possible for function x in module A to call function y in
> module B and vice versa?
> 
> The reason why I'm asking is because I've written a good bit of my code with
> functors, and now I need to make some of the code mutually recursive, and
> thus, the mutually recursive functions have to be in separate modules.

Recursive modules are available. See the "language extensions" section
of the reference manual.
(Note that this is about exactly what you asked, i.e. recursive
modules, not recursion between compilation units.)

Jacques Garrigue

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

[Jean-Christophe Filliatre]

Arthur Chan writes:
 > Hey all,
 > 
 > Is it possible to have mutually recursive functions in separate modules?
 > 
 > For example, is it possible for function x in module A to call function y in
 > module B and vice versa?

Not directly,  but at least you  can make A.x  a higher-order function
taking y as parameter and then define y in B as

	let rec y ... = ... (A.x y) ...

Hope this helps,
-- 
Jean-Christophe

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

[Yitzhak Mandelbaum]

[-- Attachment #1: Type: text/plain, Size: 1331 bytes --]

Beware, though, that recursive modules cannot contain functors. Nor  
can functors be recursive.


On Sep 18, 2007, at 3:53 AM, Jacques Garrigue wrote:

> From: "Arthur Chan" <baguasquirrel@gmail.com>
>> Is it possible to have mutually recursive functions in separate  
>> modules?
>>
>> For example, is it possible for function x in module A to call  
>> function y in
>> module B and vice versa?
>>
>> The reason why I'm asking is because I've written a good bit of my  
>> code with
>> functors, and now I need to make some of the code mutually  
>> recursive, and
>> thus, the mutually recursive functions have to be in separate  
>> modules.
>
> Recursive modules are available. See the "language extensions" section
> of the reference manual.
> (Note that this is about exactly what you asked, i.e. recursive
> modules, not recursion between compilation units.)
>
> Jacques Garrigue
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs

--------------------------------------------------
Yitzhak Mandelbaum
AT&T Labs - Research

http://www.research.att.com/~yitzhak



[-- Attachment #2: Type: text/html, Size: 6130 bytes --]

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

[Julien Signoles]

Hello,

> Is it possible to have mutually recursive functions in separate modules?

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.

For example, if you want something (stupid) like

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

you can write:

(* 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

(* 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

(* 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)

(* 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

In my opinion, solution 1 is the more natural when A and B are in the 
same file.

Hope this helps,
Julien
-- 
mailto:Julien.Signoles@lri.fr ; http://www.lri.fr/~signoles
"In theory, practice and theory are the same,
but in practice they are different" (Larry McVoy)

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

[Andreas Rossberg]

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