модельное моделирование в ocaml

Question

У меня есть набор типов Ocaml для представления дерева синтаксиса. Есть типы для программы, классы, методы, выражение и т.д. Например, метод представлен типом записи, как это:

type method = { return:typeid; args:typeid list; body:expr } 

Она включает в себя тип возвращаемого значения, типа для каждого аргумента, и тело определение. Я хочу напечатать проверку дерева синтаксиса и создать новый вид дерева, который очень похож на старый, за исключением того, что каждое выражение имеет явный typeid (известный только после проверки типов), связанный с ним.

Одним из вариантов являются объявить параллельный набор типов:

type typed_expr = expr * typeid 
type typed_method = { return:typeid; args:typeid list; body:typed_expr } 
(* ... there are more types *) 

typed_method необходим потому, что typed_expr другого типа. Но я не хочу поддерживать два почти идентичных набора типов для неконтролируемого АСТ и проверенного АСТ.

Альтернативный подход состоит в определении выражение следующим образом:

type expr = {...; typ:typeid option} 

Это позволяет мне использовать одни и те же определения типа как для входа на проверки и на выходе. Разница в том, что я перемещаю много проверок на потребительский код проверенного дерева синтаксиса. Здесь заключен контракт, что поле typ никогда не будет None в выводе типа проверки, и всегда будет None на входе для ввода типа.

Теперь, каждый раз, когда я использовал типизированное дерево, единственный способ получить доступ к внутреннему значению поля typ - это сначала проверить, является ли он None (чего не должно быть). Это делает все последующие потребительские коды уродливыми из-за дополнительных проверок.

Ни один из этих подходов не кажется мне приятным. Как бы вы это сформулировали?

Answer 1

Первое лучше, чем второе: может быть паршиво иметь 2 набора типов данных, которые выглядят одинаково, но это безопасно: инвариант, о котором вы должны заботиться во втором подходе, решается типами. Фактически реализация компилятора OCaml использует такой подход: см. parsetree.mli и typedtree.mli.

Между первым и вторым, вы можете определить типы данных, чьи typ поля параметрируются:

type 'typ expr = { ...; typ : 'typ } 

Затем вы можете использовать unit expr для нетипизированного АСТ и typeid expr для типизированного AST.

Я по-прежнему предпочитаю первый подход к использованию разных типов данных для нетипизированного и типизированного, так как часто бывает, что АСТ двух миров могут иметь некоторые другие отличия, чем типы.