Dealing with circular dependencies in OCaml

Question

I'm writing an interpreter for an experimental language. Three of the main constructs of the language are definitions, statements, and expressions. Definitions can contain statements and expressions, statements can contain definitions and expressions, and one kind of expression can contain statements. I represent all of these using union types so I can easily use pattern matching on them. Ideally, I would like to put the code for these in different files, but OMake complains about circular dependency issues. As far as I know, circular type definitions across modules are not allowed.

The only way I know of to solve this is to define all three types at once:

type defn = ...
and stmt = ...
and expr = ...

It seems like this requires all the code for types to be in the same file. Is there any way around this? How do you deal with circular definitions in your code?

Answer 1

Recursive definitions need to appear in the same file. If you want to separate definitions, statements, and expressions into separate modules, you can do so using recursive modules, but they will still need to appear in the same file. DAG-ifying inter-file dependencies is one of the annoyances of OCaml.

Answer 2

This is easily solved by parameterizing your types over the types they refer to:

type ('stmt, 'expr) defn = ...
type ('defn, 'expr) stmt = ...
type ('defn, 'stmt) expr = ...

This technique is called "untying the recursive knot" (in reference to Gordian's knot) and was described in an OCaml Journal article.

Cheers, Jon Harrop.