Реализация алгебраических типов данных в моем компиляторе

Я пытался написать небольшой компилятор в течение последних нескольких недель, читая замечательный учебник Стивена Дила "напишу тебе Хаскелла". В настоящее время я пишу интерпретатор, прежде чем писать компилятор.

У меня есть проблемы с представлением моих значений, вычисленных из приложения-конструктора алгебраических типов данных (например, в Haskell Just 1, Left "error", и т.д...).

Мои значения в настоящее время представлены следующим типом: 

data Value
    = Int Integer
    | Flt Double
    | Chr Char
    | Str String
    | Lam Name AST.Expr (Scope Value)
    | HLam (Value -> Value)

Как реализовать конструкторы типов ?

До сих пор я думал об этом: 

data Value
    = Int Integer
    | Flt Double
    | Chr Char
    | Str String
    | App Constr [Value]  -- Constr applied of [Value]
    | Lam Name AST.Expr (Scope Value)
    | HLam (Value -> Value)

-- Constructor ID and signature
-- would be translated to a lambda abstraction
data Constr = Constr Name [Type]

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

Есть ли другое решение ?

Заранее благодарю.

1 2
haskell compiler-construction algebraic-data-types

1 ответ:

Таким образом, существует ряд решений. Самое модное-использовать что-то вроде размер-вектор и тип-естественный, чтобы ограничить arity конструкторов типов и аргументов для соответствия. Если этот подход вас интересует, я бы посмотрел на исходный код связанных библиотек, чтобы увидеть, как это делается, но он включает в себя огромное количество расширений GHC и довольно много работы.

Менее причудливым решением является использование create a family of constructor types and app types, как в.

data Const0 
data Const1
-- etc.
data ConstN

data App0 = App0 Const0
data App1 = App1 Const1 Value
-- etc.
data AppN = AppN ConstN Value Value ... Value

data AppI = AppI0 App0 | AppI1 App1 | ... | AppIN App1N

Для этого требуется произвести вручную или автоматически довольно много шума.

Откровенно говоря, я ожидаю, что усилия по применению этого инварианта на уровне типов не стоят того, чтобы приносить пользу. Вместо этого я бы предложил использовать интеллектуальные конструкторы для обеспечения этого на уровне значений.
2