Tratamiento de dependencias circulares en OCaml

Question

Escribo un intérprete para un lenguaje experimental. Tres de los constructos principales del lenguaje son definiciones, enunciados y expresiones. Las definiciones pueden contener declaraciones y expresiones, las declaraciones pueden contener definiciones y expresiones, y un tipo de expresión puede contener declaraciones. Represento a todos estos utilizando tipos de unión para que pueda usar fácilmente la coincidencia de patrones en ellos. Idealmente, me gustaría poner el código para estos en diferentes archivos, pero OMake se queja de problemas de dependencia circular. Hasta donde yo sé, no se permiten las definiciones de tipo circulares en los módulos.

La única forma que conozco para resolver esto es definir los tres tipos a la vez:

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

Parece que esto requiere todo el código para este tipo estén en el mismo archivo. ¿Hay alguna forma de evitar esto? ¿Cómo manejas las definiciones circulares en tu código?

Answer 1

Las definiciones recursivas deben aparecer en el mismo archivo. Si desea separar definiciones, declaraciones y expresiones en módulos separados, puede hacerlo usando recursive modules, pero aún deberán aparecer en el mismo archivo. DAG-ifying entre archivos de dependencias es una de las molestias de OCaml.

Answer 2

Esto se resuelve fácilmente mediante la parametrización de los tipos sobre los tipos se refieren a:

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

Esta técnica se llama "desatar el nudo recursiva" (en referencia al nudo gordiano) y fue descrito en un artículo OCaml Journal .

Cheers, Jon Harrop.

Answer 3

Otra solución utilizada a menudo es abstraer los tipos en las interfaces. Como los tipos son abstractos en las interfaces, estas interfaces no dependen recursivamente. En las implementaciones, puede especificar los tipos, y dado que las implementaciones dependen solo de las interfaces, tampoco son recursivas.

El único problema es que, con esta solución, ya no puede hacer coincidir patrones en estos tipos fuera de su implementación.

Personalmente, pero es probable que sea una cuestión de gusto, me gusta tener todos los tipos de mi programa definidos en un solo módulo (creo que ayuda en la legibilidad del programa). Entonces, esta restricción de OCaml no es realmente un problema para mí.