Lidando com dependências circulares no OCaml

Question

Estou escrevendo um intérprete para uma linguagem experimental.Três das principais construções da linguagem são definições, declarações e expressões.As definições podem conter declarações e expressões, as declarações podem conter definições e expressões e um tipo de expressão pode conter declarações.Eu represento tudo isso usando tipos de união para poder usar facilmente a correspondência de padrões neles.Idealmente, eu gostaria de colocar o código deles em arquivos diferentes, mas o OMake reclama de problemas de dependência circular.Até onde eu sei, definições de tipo circular entre módulos não são permitidas.

A única maneira que conheço de resolver isso é definir todos os três tipos de uma vez:

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

Parece que isso exige que todo o código dos tipos esteja no mesmo arquivo.Existe alguma maneira de contornar isso?Como você lida com definições circulares em seu código?

Answer 1

As definições recursivas precisam aparecer no mesmo arquivo.Se quiser separar definições, instruções e expressões em módulos separados, você pode fazer isso usando módulos recursivos, mas eles ainda precisarão aparecer no mesmo arquivo.As dependências entre arquivos do DAG são um dos aborrecimentos do OCaml.

Answer 2

Isso é facilmente resolvido parametrizando seus tipos de acordo com os tipos aos quais eles se referem:

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

Esta técnica é chamada de "desamarrar o nó recursivo" (em referência ao nó górdio) e foi descrita em um Diário OCaml artigo.

Saúde, Jon Harrop.

Answer 3

Outra solução frequentemente utilizada é abstrair os tipos nas interfaces.Como os tipos são abstratos nas interfaces, essas interfaces não são recursivamente dependentes.Nas implementações você pode especificar os tipos, e como as implementações dependem apenas das interfaces, elas também não são recursivas.

O único problema é que, com esta solução, você não pode mais fazer correspondência de padrões nesses tipos fora de sua implementação.

Pessoalmente, mas provavelmente é uma questão de gosto, gosto de ter todos os tipos do meu programa definidos em um módulo (acho que ajuda na legibilidade do programa).Então, essa restrição do OCaml não é realmente um problema para mim.