Эволюция структуры данных

Я пытаюсь написать компилятор для C-подобного языка на Haskell. Компилятор прогрессирует, преобразовывая AST. Первый проход анализирует входные данные для создания AST, завязывая узел с таблицей символов, чтобы можно было найти символы до того, как они будут определены, без необходимости использования прямых ссылок.

AST содержит информацию о типах и выражениях, и между ними могут быть связи; например sizeof(T)— это выражение, которое зависит от типа T, а T[e]— это тип массива, который зависит от константного выражения е.

Типы и выражения представлены типами данных Haskell следующим образом:

data Type = TypeInt Id
          | TypePointer Id Type -- target type
          | TypeArray Id Type Expr -- elt type, elt count
          | TypeStruct Id [(String, Type)] -- [(field name, field type)]
          | TypeOf Id Expr
          | TypeDef Id Type

data Expr = ExprInt Int -- literal int
          | ExprVar Var -- variable
          | ExprSizeof Type
          | ExprUnop Unop Expr
          | ExprBinop Binop Expr Expr
          | ExprField Bool Expr String -- Bool gives true=>s.field, false=>p->field

Где Unopвключает такие операторы, как адрес (&) и разыменование (*), а Binopвключает такие операторы, как плюс (+), и время (*) и т. д.

Обратите внимание, что каждый тип присвоен уникальный идентификатор. Это используется для построения графа зависимости типов для обнаружения циклов, которые приводят к бесконечным типам. Как только мы убедимся, что в графе типов нет циклов, можно безопасно применять к ним рекурсивные функции, не попадая в бесконечный цикл.

Следующим шагом является определение размера каждого типа, назначение смещений для полей структуры и замена ExprFieldарифметикой указателя.При этом мы можем определить тип выражений и исключить ExprSizeofs, ExprFields, TypeDefs и TypeOfs. из графа типов, поэтому наши типы и выражения эволюционировали и теперь выглядят примерно так:

data Type' = TypeInt Id
           | TypePointer Id Type'
           | TypeArray Id Type' Int -- constant expression has been eval'd
           | TypeStruct Id [(String, Int, Type')] -- field offset has been determined

data Expr' = ExprInt Type' Int
           | ExprVar Type' Var
           | ExprUnop Type' Unop Expr'
           | ExprBinop Type' Binop Expr' Expr'

Обратите внимание, что мы убрали некоторые конструкторы данных и немного изменили некоторые другие. В частности, Type'больше не содержит никаких Expr', и каждое Expr'определило свой Type'.

Итак, наконец, вопрос: лучше ли создать два почти идентичных набора типов данных или попытаться объединить их в один тип данных?

Сохранение двух отдельных типов данных делает явным, что некоторые конструкторы больше не могут появляться. Однако функция, которая выполняет свертывание констант для вычисления константных выражений, будет иметь тип:

foldConstants :: Expr -> Either String Expr'

Но это означает, что мы не сможем выполнить свертывание констант позже с помощью Expr's (представьте себе некоторый проход, который манипулирует Expr'и хочет сложить все появившиеся константные выражения). Нам потребуется другая реализация:

foldConstants' :: Expr' -> Either String Expr'

С другой стороны, сохранение одного типа решило бы проблему свертывания констант, но не позволило бы средству проверки типов применять статические инварианты.

Кроме того, что мы помещаем в неизвестные поля (такие как смещения полей, размеры массивов и типы выражений) во время первого прохода? Мы могли бы затыкать дыры с помощью undefinedили error "*hole*", но это похоже на ожидающую катастрофу (например, указатели NULL, которые вы можете даже не проверял).Мы могли бы изменить неизвестные поля на Maybes и закрыть дыры с помощью Nothing(например, указатели NULL, которые мы можемпроверить), но было бы раздражающим в последующих проходах продолжать извлекать значения из Maybes, которые всегда будут Justs.