Cyclic dependencies and modular design

Learning
1

I’ve been dealing with a design problem for quite a while now, where cyclic dependencies are the fundamental problem, and I’m having some problems resolving it elegantly.
I’m coming from C, where cyclic dependencies are both possible and quite easily resolvable.

The following is a very simplified image of the files in the project which are of interest:

ast.ml (doesn’t actually have an interface, I’m not too keen on copying the whole type)

type loc = string * (int * int) * (int * int)
and id = string * loc
and decl = 
  | Decl_Func of decl_func
and decl_func = {
  df_Name: id;
  mutable df_SymTab: sym_tab option;
}
(* goes on for about 100 more types *)

symtab.mli

type t
type symbol =
  | Sym_Func of Ast.decl_func

val lookup_by_id: Ast.id -> symbol

(there are more files to be added in the future)

Each of the implementations is quite large. Which means I absolutely do not want to make everything recursive modules, since that would mean the implementation file will be 10kloc or even more, with a ton of code which is not really related (beyond the big recursive type).

How would I solve this, while still maintaining a somewhat modular design?

1 Like
2

I’ve improved the example, to actually use something resembling the actual case I’m encountering.

Further, I’ve come across two potential solutions: ppx_include and “untying the recursive knot” (parameterizing the type).

So far, I think the ppx_include may work.

3

Async_kernel uses a recursive Types module that includes just the type definitions of the recursively-defined modules, so the actual modules themselves can still be defined in separate files.

4

To expand on the suggestion, perhaps something like this could work?

module type SYMBOL_TABLE = sig
  type t

  type symbol

  val empty :
    t

  val add :
    symbol -> t -> t
end

module type SYMBOL = sig
  type table

  type t =
    | Literal of string
    | Foobar of table
end

module Make_symbol (B : SYMBOL_TABLE) :
  SYMBOL with type table = B.t
= struct
  type table = B.t

  type t =
    | Literal of string
    | Foobar of table
end

module Make_symbol_table (K : SYMBOL) :
  SYMBOL_TABLE with type symbol = K.t
= struct
  type symbol = K.t

  type t = symbol list

  let empty =
    []

  let add s t =
    s :: t
end

module rec Symbol : SYMBOL with type table = Table.t = Make_symbol (Table)
and Table : SYMBOL_TABLE with type symbol = Symbol.t = Make_symbol_table (Symbol)

You could have a file symbol_table_intf.ml and a file symbol_intf.ml with the module type stuff, then define the functors in their respective files (i.e., symbol_table.ml and symbol.ml) and then instantiate both functors (just a couple of lines) elsewhere.