在Haskell中扩展数据类型

Question

这里是Haskell新手。

我为一种最小的类汇编语言写了一个求值器。

现在，我想扩展该语言以支持一些语法糖，然后将其编译回仅使用基本操作符。我的想法是我不想再碰求值器模块了。

在OO方式中，我认为可以扩展原始模块以支持语法糖操作符，在这里提供翻译规则。

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

是否有实现这一功能的方法?

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

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

有关这种方法的更多信息，以及关于表达式问题的一般信息，请查看第9频道Ralf Laemmel的视频1和2。

然而，正如在评论中注意到的，这个解决方案改变了语义。例如，表达式列表不再合法:

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

使用类型签名的余积的更通用的解决方案在功能珍珠"Data types A la carte"中提出。参见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(一个Exp值)看作实现Eval接口的对象。如果你有一个issomethingthatcanbeevaluate类型的对象，显然你不能安全地将它转换成更具体的东西;

Answer 3

语法糖通常由解析器处理;您将扩展(不是在OO继承的意义上)解析器来检测新的结构，并将它们转换为您的求值器可以处理的结构类型。

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)

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

原始模块中的函数签名需要使用Expr Core(而不仅仅是Expr)

一个糖函数应该有以下类型签名:

Desugar :: Expr Extended -> Expr Core

您可能还对论文"树木生长"中描述的更复杂的方法感兴趣。