1

我Expr为算术运算上课

class Expr a where
  mul :: a -> a -> a 
  add :: a -> a -> a
  lit :: Integer -> a

我想“解析”这样的东西： mul ( add (lit 3) (lit 2)) (lit 4) = (3+2)*4

我有数据类型：

data StackExp = PushI Integer
              | PushB Bool
              | Add
              | Mul
              | And
              | Or
                deriving Show

和

type Program = [StackExp] --i use this type for function of stack calculator later

我的任务是：我需要Expr为类型创建实例Program

更具体 - 我想做这个转变： mul ( add (lit 3) (lit 2)) (lit 4)->>>[PushI 2, PushI 3, Add, PushI 4, Mul]

我有问题，因为我[[StackExp]]在实例声明的输出中收到。

我的尝试：

instance Expr Program where
  lit n = (PushI n):[]
  add exp1 exp2 = exp1:(exp2:[Add]) 
  mul exp1 exp2 = exp1:(exp2:[Mul])

我不知道如何将所有子表达式连接到列表中

---------------- 编译器错误看起来像这样------------------------

Couldn't match type `[StackExp]' with `StackExp'
    Expected type: StackExp
      Actual type: Program

…………

4

1 回答 1

3

因此，您基本上想要做的是从表达式语言的抽象语法（类型类Expr）编译为简单堆栈机器的代码（类型元素列表StackExpr）。

您立即遇到的一个问题是，仅在 Haskell 98 或 Haskell 2010 中，您不能声明[StackExpr]类的实例。例如，GHC 会抱怨

Illegal instance declaration for `Expr [StackExp]'
  (All instance types must be of the form (T a1 ... an)
   where a1 ... an are *distinct type variables*,
   and each type variable appears at most once in the instance head.
   Use -XFlexibleInstances if you want to disable this.)
In the instance declaration for `Expr [StackExp]'

为了解决这个问题，您可以将其定义Program为类型同构（而不是像现在这样仅作为类型同义词）：

newtype Program = P [StackExp] deriving Show

然后使 Program 成为 Expr 类的实例。（或者，您可以FlexibleInstances按照上面的错误消息的建议启用。）

现在我们可以编写所需的实例声明：

instance Expr Program where
  mul (P x) (P y) = P (x ++ y ++ [Mul])
  add (P x) (P y) = P (x ++ y ++ [Add])
  lit n           = P [PushI n]

也就是说，对于乘法和加法，我们首先编译操作数，然后分别产生MulorAdd指令；对于文字，我们生成相应的推送指令。

有了这个声明，我们得到，例如：

> mul (add (lit 3) (lit 2)) (lit 4) :: Program
P [PushI 3,PushI 2,Add,PushI 4,Mul]

（与您的示例不太一样。您将操作数的顺序交换为Add。由于加法是可交换的，我将假设此版本也是可以接受的。）

当然，为堆栈程序编写一个小型评估器会更有趣：

eval :: Program -> [Integer]
eval (P es) = go es []
  where
    go [] s                   = s
    go (PushI   n : es) s     = go es (n : s)
    go (Add : es) (m : n : s) = go es ((m + n) : s)
    go (Mul : es) (m : n : s) = go es ((m * n) : s)

（请注意，我在这里忽略了处理布尔值的指令，因为无论如何您似乎只处理整数表达式。）

现在，以您为例，

> eval (mul (add (lit 3) (lit 2)) (lit 4))
[20]

这似乎是正确的。

于 2013-05-04T20:23:35.630 回答