Расширение типа данных в Haskell

Question

новичок Хаскелла здесь.

Я написал оценщик для минимального языка, похожего на ассемблер.

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

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

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

Есть ли функциональный способ сделать это?

Спасибо, что нашли время прочитать этот вопрос.

Answer 1

Фил Вадлер назвал эту проблему «проблемой выражения», по его словам:

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

Одним из решений для расширения типа данных является использование классов типов.

В качестве примера давайте предположим, что у нас есть простой язык для арифметики:

data Expr = Add Expr Expr | Mult Expr Expr | Const Int

run (Const x) = x
run (Add exp1 exp2)  = run exp1 + run exp2
run (Mult exp1 exp2) = run exp1 * run exp2

например,

ghci> run (Add (Mult (Const 1) (Const 3)) (Const 2))
5

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

class Expr a where
    run :: a -> Int


data Const = Const Int

instance Expr Const where
    run (Const x) = x


data Add a b = Add a b

instance (Expr a,Expr b) => Expr (Add a b) where
    run (Add expr1 expr2) = run expr1 + run expr2


data Mult a b = Mult a b

instance (Expr a, Expr b) => Expr (Mult a b) where
    run (Mult expr1 expr2) = run expr1 * run expr2

Теперь давайте расширим язык, добавив вычитания:

data Sub a b = Sub a b

instance (Expr a, Expr b) => Expr (Sub a b) where
    run (Sub expr1 expr2) = run expr1 - run expr2

например,

ghci> run (Add (Sub (Const 1) (Const 4)) (Const 2))
-1

Для получения дополнительной информации об этом подходе ив общем, по проблеме выражения, посмотрите видео Ральфа Леммеля 1 и 2 на канале 9.

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

[Add (Const 1) (Const 5), Const 6] -- does not typecheck

Более общее решение, использующее побочные продукты сигнатур типов, представлено в функциональном перле "Типы данных a la carte" .См. Также комментарий Вадлера на бумаге.

Answer 2

Вы можете сделать что-то более похожее на ООП, используя экзистенциальные типы :

-- We need to enable the ExistentialQuantification extension.
{-# LANGUAGE ExistentialQuantification #-}

-- I want to use const as a term in the language, so let's hide Prelude.const.
import Prelude hiding (const)

-- First we need a type class to represent an expression we can evaluate
class Eval a where
  eval :: a -> Int

-- Then we create an existential type that represents every member of Eval
data Exp = forall t. Eval t => Exp t

-- We want to be able to evaluate all expressions, so make Exp a member of Eval.
-- Since the Exp type is just a wrapper around "any value that can be evaluated,"
-- we simply unwrap that value and call eval on it.
instance Eval Exp where
  eval (Exp e) = eval e

-- Then we define our base language; constants, addition and multiplication.
data BaseExp = Const Int | Add Exp Exp | Mul Exp Exp

-- We make sure we can evaluate the language by making it a member of Eval.
instance Eval BaseExp where
  eval (Const n) = n
  eval (Add a b) = eval a + eval b
  eval (Mul a b) = eval a * eval b

-- In order to avoid having to clutter our expressions with Exp everywhere,
-- let's define a few smart constructors.
add x y = Exp $ Add x y
mul x y = Exp $ Mul x y
const   = Exp . Const

-- However, now we want subtraction too, so we create another type for those
-- expressions.
data SubExp = Sub Exp Exp

-- Then we make sure that we know how to evaluate subtraction.
instance Eval SubExp where
  eval (Sub a b) = eval a - eval b

-- Finally, create a smart constructor for sub too.
sub x y = Exp $ Sub x y

Делая это, мы фактически получаем один расширяемый тип, чтобы вы могли, например, смешивать расширенные и базовые значения в списке:

> map eval [sub (const 10) (const 3), add (const 1) (const 1)]
[7, 2]

Однако, поскольку теперь единственное, что мы можем знать о значениях Exp, это то, что они как-то являются членами Eval, мы не можем выполнять сопоставление с образцом или делать что-либо еще, что не указано в классе типов. В терминах ООП представьте значение Exp exp как объект, который реализует интерфейс Eval. Если у вас есть объект типа ISomethingThatCanBeEvaluated, очевидно, вы не можете безопасно преобразовать его во что-то более конкретное; то же самое относится к Exp.

Answer 3

Синтаксический сахар обычно обрабатывается парсером; вы бы расширили (не в смысле наследования ОО) синтаксический анализатор для обнаружения новых конструкций и преобразования их в те структуры, которые может обрабатывать ваш оценщик.

Answer 4

(более простой) вариант - добавить тип к вашему AST, чтобы отличить Core от Extended:

data Core = Core
data Extended = Extended

data Expr t 
  = Add (Expr t) (Expr t)
  | Mult (Expr t) (Expr t)
  | Const Int 
  | Sugar t (Expr t) (Expr t)

Выражение является Core или Extended: компилятор будет гарантировать, что оно содержит только подвыражения одного типа.

Сигнатурам функций в исходном модуле нужно будет использовать Expr Core (вместо просто Expr)

Функция Desugar будет иметь следующую сигнатуру типа:

Desugar :: Expr Extended -> Expr Core

Вас также может заинтересовать более сложный подход, описанный в статье « Деревья, которые растут ».