在 Haskell 中扩展数据类型

Question

Haskell 新手在这里。

我为一种最小的类似汇编的语言编写了一个评估器。

现在，我想扩展该语言以支持一些语法糖，然后我将编译回仅使用原始运算符。我的想法是我不想再次触摸评估器模块。

我认为，以面向对象的方式做事，可以扩展原始模块以支持语法糖运算符，并在此处提供翻译规则。

除此之外，我只能考虑重写两个模块中的数据类型构造函数，以便它们不会发生名称冲突，并从那里继续，就好像它们是完全不同的东西一样，但这意味着一些冗余，因为我必须重复（只是使用其他名称）操作员的共同点。同样，我认为这里的关键字是扩展。

有没有一种实用的方法可以实现这一点？

感谢您花时间阅读这个问题。

Answer 1

这个问题被 Phil Wadler 命名为“表达问题”，用他的话说：

目标是按情况定义一种数据类型，可以在数据类型上添加新情况并在数据类型上添加新函数，而无需重新编译现有代码，同时保留
静态类型安全。

拥有可扩展数据类型的一种解决方案是使用类型类。

作为一个例子，我们假设我们有一种简单的算术语言：

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

有关此方法的更多信息，请参阅一般的表达问题，查看Ralf Laemmel的视频1 和2。

但是，正如评论中所注意到的，这个解决方案改变了语义。例如，表达式列表不再合法：

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

函数珍珠 “数据类型点菜”。另请参阅 Wadler 对本文的评论。

Answer 2

你可以使用存在类型来做一些更像OOP的事情：

-- 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 的成员，因此我们无法进行模式匹配或执行其他任何东西未在类型类中指定。在 OOP 术语中，将 Exp 视为实现 Eval 接口的对象。如果您有一个 ISomethingThatCanBeEvaluated 类型的对象，显然您无法安全地将其转换为更具体的对象；这同样适用于 Exp。

Answer 3

语法糖通常由解析器处理；您可以扩展（不是在 OO 继承的意义上）解析器来检测新的构造并将它们转换为您的评估器可以处理的结构类型。

Answer 4

一个（更简单的）选项是向 AST 添加类型，以区分核心和扩展：

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)

表达式要么是核心，要么是扩展：编译器将确保它仅包含相同类型的子表达式。

原始模块中的函数签名需要使用 Expr Core （而不仅仅是 Expr）。Desugar

函数将具有以下类型签名：

Desugar :: Expr Extended -> Expr Core

您可能还对论文'生长的树'。