OCaml recursive modules across compilation units

3
votes

I'm trying to split the following recursive modules into separate compilation units. Specifically, I'd like B to be in its own b.ml, to be able to reuse it with other A's.

module type AT = sig
  type b
  type t = Foo of b | Bar
  val f : t -> b list
end

module type BT = sig
  type a
  type t = { aaa: a list; bo: t option }
  val g : t -> t list
end

module rec A : (AT with type b = B.t) = struct
  type b = B.t
  type t = Foo of b | Bar
  let f = function Foo b -> [ b ] | Bar -> []
end
and B : (BT with type a = A.t) = struct
  type a = A.t
  type t = { aaa: a list; bo: t option }
  let g b =
    let ss = List.flatten (List.map A.f b.aaa) in
    match b.bo with
    | Some b' -> b' :: ss
    | None -> ss
end

let a = A.Bar;;
let b = B.({ aaa = [a]; bo = None });;
let c = A.Foo b;;
let d = B.({ aaa = [a;c]; bo = Some b });;

I can't figure out how to split it across units.

The following sentence from Xavier Leroy's paper on the topic gives me hope that it's possible to encode using OCaml's module syntax: "the proposal does not support recursion between compilation units. The latter can however be encoded using separately-compiled functors, whose fix-point is taken later using the module rec construct".

I've played around with module rec but can't seem to find a way to make it type-check. The use of A's function f inside B's function g seems to cause the trouble.

(For the context, in the original code A.t is an instruction type, and B.t is a basic block type. Branch instructions reference blocks, and blocks contain lists of instructions. I'd like to reuse the basic block type and associated functions with different instruction sets.)

2
recursionmoduleocamlfunctor
If my answer below doesn't solve the problem you are having with splitting up this file, please post your best attempt so far at separate compilation, and the type error you are getting on A.f in B.g. - antron
Also, focusing on the end of your question, there are some other ways to approach this problem – for example, storing basic block indices or keys into a data structure, instead of typed basic block references, in your instructions. - antron
Thank you antron, while trying to come up with a best attempt, I apparently stumbled upon a solution, at least for this test case. Hopefully it will translate to my actual code. - Anon Anon
Good, best of luck :) - antron

2 Answers

3
votes

I think the paper is referring to something like this:

(* a.ml *)

module F (X : sig val x : 'a -> 'a end) =
struct
  let y s = X.x s
end

(* b.ml *)

module F (Y : sig val y : 'a -> 'a end) =
struct
  (* Can use Y.y s instead to get infinite loop. *)
  let x s = Y.y |> ignore; s
end

(* c.ml *)

module rec A' : sig val y : 'a -> 'a end = A.F (B')
       and B' : sig val x : 'a -> 'a end = B.F (A')

let () =
  A'.y "hello" |> print_endline;
  B'.x "world" |> print_endline

Running this (ocamlc a.ml b.ml c.ml && ./a.out) prints

hello
world

Obviously, the definitions of A and B I used are nonsense, but you should be able to substitute your own definitions into this pattern, as well as use named signatures instead of writing them out literally like I did.

1
votes

The following seems to work, although it is rather ugly.

(* asig.mli *)

module type AT = sig
  type b
  type b' (* b = b' will be enforced externally *)
  type t
  val f : t -> b' list
end

(* bsig.mli *)

module type BT = sig
  type a
  type b' (* t = b' will be enforced externally *)
  type t = { aaa: a list; bo: b' option }
  val g : t -> b' list
end

(* b.ml *)

open Asig

module MakeB(A : AT) = struct
  type a = A.t
  type t = { aaa: a list; bo: A.b' option }
  type b' = A.b'
  let g b =
    let ss = List.flatten (List.map A.f b.aaa) in
    match b.bo with
    | Some b' -> b' :: ss
    | None -> ss
end

(* a.ml *)

open Asig
open Bsig

module type ASigFull = sig
  type b
  type b'
  type t = Foo of b | Bar
  val f : t -> b' list
end

module type BMAKER = functor (A : AT) -> (BT with type a = A.t
                                              and type b' = A.b')
module MakeAB(MakeB : BMAKER) = struct

module rec B1 : (BT with type a = A1.t
                     and type b' = A1.b') = MakeB(A1)
       and A1 : (ASigFull with type b = B1.t
                           and type b' = B1.t) = struct
  type b = B1.t
  type b' = b
  type t = Foo of b | Bar
  let f = function Foo b -> [ b ] | Bar -> []

end

module A = (A1 : ASigFull with type t = A1.t and type b = B1.t and type b' := B1.t)
module B = (B1 : BT with type t = B1.t and type a = A1.t and type b' := B1.t)

end

module AB = MakeAB(B.MakeB)
module A = AB.A
module B = AB.B

let a = A.Bar;;
let b = B.({ aaa = [a]; bo = None });;
let c = A.Foo b;;
let d = B.({ aaa = [a;c]; bo = Some b });;