Пишу компилятор в функциональном стиле. Проверка типов в настоящее время довольно проста: это (в основном) просто функция от Expr
до Type
.
Теперь я хочу добавить шаг в рабочий процесс, который сохраняет информацию о типе для последующих этапов. Есть несколько способов сделать это (таблицы символов и т. д.), но самый простой — преобразовать в IR, который выглядит как AST, но содержит информацию о типе. Например, если тип данных AST:
datatype Expr = Literal of int
| Add of Expr * Expr
| ...
Тогда типизированный IR будет:
type TExpr = Type * TExpr'
datatype TExpr' = TLiteral of int
| TAdd of TExpr * TExpr
| ...
Итак, моя цель сейчас — преобразовать мою проверку типов в аннотатор типов: функцию Expr -> TExpr
вместо Expr -> Type
. Вот мой вопрос: Как бы вы это сделали, не добавляя кучу шаблонного беспорядка в функцию проверки типов?
Наивно, мне пришлось бы добавлять код упаковки и распаковки повсюду, разрушая простую удобочитаемость функции проверки типов в ее нынешнем виде. То есть кейс для Add
в контролере типов на данный момент выглядит так:
let lhs_t = check lhs in
let rhs_t = check rhs in
case (lhs_t, rhs_t) of
(Int, Int) => Int
| (_, _) => Error
Красиво и чисто! Точно соответствует печатному суждению в формализме! ❤️????
Если бы я испортил проверку типов с дополнительной логикой перевода, это выглядело бы так (теперь check
имеет тип Expr -> TExpr
):
(* Recursive calls to translate the children. *)
let lhs_typed = check lhs in
let rhs_typed = check rhs in
(* We don't care about the expression for checking, just the resulting
* type. So extract that from each child. *)
let lhs_t, _ = lhs_typed in
let rhs_t, _ = rhs_typed in
case (Int, Int) =>
(* Construct a TExpr with the new type. *)
(Int, TAdd (lhs_typed, rhs_typed))
| (_, _) => Error
Это неприятно смешало интересную логику проверки типов со скучным шаблоном для разрушения и построения TExpr
. ????????
Есть ли способ разделить эти компоненты? То есть может ли логика проверки типов жить в одной рекурсивной функции, в то время как механизм перевода выступает в качестве ее внешнего клиента? Бонусные баллы, если вы по-прежнему легко запускаете проверку типов без выполнения перевода, если хотите.
Дополнительный контекст: это следует за опцией «Отдельный IR» от Edward Z. Запись Янга на тему "Проблема набора AST". Я рассмотрел универсальное программирование в духе . но не совсем подходит для этого случая. Связанные, но разные вопросы по SO: