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

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

У меня есть проблемы с представлением моих значений, оцененных из приложения-конструктора алгебраического типа данных (например, в 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]

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

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

Заранее спасибо.


haskell compiler-construction algebraic-data-types type-constructor
person baxbaxwalanuksiwe    schedule 09.03.2016    source источник
comment
Возможно, можно использовать GADT. Однако, даже если предположить, что эту статическую гарантию можно закодировать в GADT, я боюсь, что планка сложности значительно повысится. Я бы сначала решил упражнение только с проверками во время выполнения.   -  person chi    schedule 09.03.2016
comment
@chi: Спасибо за совет, но я не могу понять, как бы вы реализовали это с помощью GADT, поэтому я не вижу, насколько это сложнее по сравнению с проверкой во время выполнения. редактировать: Неважно, я понял   -  person baxbaxwalanuksiwe    schedule 09.03.2016

Ответы (1)


arrow_upward
3
arrow_downward

Итак, есть ряд решений. Лучше всего использовать что-то вроде sized-vector и type-natural для ограничения арности конструкторов типов и аргументов соответствовать. Если этот подход вас заинтересует, я бы посмотрел исходный код связанных библиотек, чтобы увидеть, как это делается, но он включает в себя огромное количество расширений GHC и довольно много работы.

Менее причудливое решение — использовать создание семейства типов конструкторов и типов приложений, например.

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

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

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

person walpen    schedule 09.03.2016
comment
Поскольку мне нужно использовать сопоставление с образцом в моем конструкторе, я попробую использовать векторы с заданными размерами. Если это слишком сложно, я пойду на проверку во время выполнения. Спасибо за ответ. Изменить: я мог бы использовать геттеры для доступа к значениям моего конструктора приложений, но я нахожу причудливое решение более элегантным. - person baxbaxwalanuksiwe; 10.03.2016