语言设计：在 Haskell 中解析表达式的计算是如何工作的？

Question

我正在用 Haskell 编写一种简单的语言，但在计算算术和关系表达式时遇到了问题。起初我编写了一个评估函数，然后我意识到我需要单独的函数来评估我语言的各个方面。所以我有一个算术评估函数，一个关系评估函数，然后是一个通用评估函数。

问题来自于实际生产一些可以使用的东西，我认为这是因为无法将我的其他 eval 函数与我的主要 eval 函数联系起来。但是，我不确定我是否错误地进行了评估。我相信也许像“foldl1”这样的函数在评估中实施会更有用。我第一次从 48 小时内编写自己的计划 Wikibook 中了解到这个函数，它似乎比评估每个可能的表达式更有用。我不确定这将如何在我当前的代码中实现，除非我为每个表达式都有一个函数。例如，如果我有一个像“1 + 1”这样的表达式，我当前的解析器会将其解析为“1 Add 1”，但如果我使用 foldl1，我可以有一个函数来获取这个表达式的每个部分，并在参数上“折叠”运算符。即使我将当前的评估函数与 foldl1 的想法合并，我仍然预见到从它评估任何有意义的东西（不仅仅是整数或字符串）的问题。

任何方向或帮助将不胜感激。

下面我通过数据类型和我的评估功能包括在内：

data HenryVal = Atom String
              | String String 
              | Integer Integer
              | Bool Bool
              | Not HenryVal
              | Neg HenryVal
              | List [HenryVal]
              | Seq [HenryVal]
              | Assign String HenryVal
              | If HenryVal HenryVal HenryVal
              | While HenryVal HenryVal
              | Skip
              | ABinary ABinOp HenryVal HenryVal
              | BBinary BBinOp HenryVal HenryVal
              | RBinary RBinOp HenryVal HenryVal

data BBinOp = And | Or deriving (Show)
data RBinOp = Greater | Less deriving (Show)
data ABinOp = Add
            | Subtract
            | Multiply
            | Divide
              deriving (Show)

evalABinOP :: HenryVal -> ABinOp -> HenryVal -> HenryVal
evalABinOP (Integer a) Add (Integer b) = Integer (a + b)
evalABinOP (Integer a) Multiply (Integer b) = Integer (a * b)
evalABinOP (Integer a) Divide (Integer b) = Integer (a `div` b)
evalABinOP (Integer a) Subtract (Integer b) = Integer (a - b)

evalRBinOp :: HenryVal -> RBinOp -> HenryVal -> HenryVal
evalRBinOp (Integer a) Greater (Integer b) = if a > b then (Bool True) else (Bool False)
evalRBinOp (Integer a) Less (Integer b) = if a < b then (Bool True) else (Bool False)

evalStmt :: HenryVal -> [HenryVal]
evalStmt (Assign var val) = [val]

evalCond :: HenryVal -> Bool
evalCond (Bool cond) = if cond == True then True else False


eval :: HenryVal -> HenryVal
eval val@(Atom _) = val
eval val@(String _) = val
eval val@(Integer _) = val
eval val@(Bool _) = val
eval val@(Neg _) = val
eval val@(Not _) = val
eval (List [Atom "quote", val]) = val
eval val@(List _) = val
eval val@(Seq _) = val
eval (If cond a b) = if (evalCond cond) then (eval a) else (eval b) 
eval (Assign var val) = eval val
eval (Seq (Atom func : args)) = apply func $ map eval args
eval (ABinary op x y) = evalABinOP x op y
eval (RBinary op x y) = evalRBinOp x op y

错误信息：

./hask "[4 + 4]"
"No match: "Henry" (line 1, column 4):
unexpected "+"
expecting space, "(", "if", ";Do", "skip", identifier, letter, digit, "\"" or "[""

在 48 小时内为自己写一个计划：https : //en.wikibooks.org/wiki/Write_Yourself_a_Scheme_in_48_Hours/Evaluation,_Part_1

Answer 1

我不确定使用foldl1在这里对你有多大帮助。在“Write Yourself a Scheme” wikibook 中，该foldl1函数用于将“二进制”函数（如+和 ）-应用于可能长度大于 2 的参数列表的特定目的。在 Lisp 中，(+ 1 2 3)与 Haskell 表达式的含义相同：

foldl1 (+) [1,2,3]

所以对于这个特定的目的，foldl1是一种评估 Lisp 算术表达式的好方法。如果您有一个HenryVal类似的构造函数，ABinary ABinOp [HenryVal]并且您希望参数列表具有相同的折叠行为，那么您可能需要使用 for foldl1。

那么，我们如何解决您遇到的问题。如果我可以冒个险，我想你可能正在看这样的表达：

ABinary Add (ABinary Add (Integer 1) (Integer 2)) (Integer 3)

并意识到您的评估者无法处理它，因为evalABinOp没有任何情况下其中一个参数是另一个ABinary而不是一个Integer，对吗？

好吧，诀窍是使用递归。在 中evalABinOp，递归计算参数，确保它们是整数，然后进行算术运算。所以，像这样：

evalABinOp :: HenryVal -> ABinOp -> HenryVal -> HenryVal
evalABinOp e1 op e2
  = let Integer v1 = eval e1
        Integer v2 = eval e2
    in Integer $ calc v1 op v2
  where
    calc a Add b = a + b
    calc a Multiply b = a * b
    calc a Divide b = a `div` b
    calc a Subtract b = a - b

然后，在向 中添加deriving (Show)实例后HenryVal，您可以看到：

> eval $ ABinary Add (ABinary Add (Integer 1) (Integer 2)) (Integer 3)
Integer 6

作为我刚刚想到的替代方案，您可以保留 的原始定义evalABinOp，原样：

evalABinOp :: HenryVal -> ABinOp -> HenryVal -> HenryVal
evalABinOp (Integer a) Add (Integer b) = Integer (a + b)
evalABinOp (Integer a) Multiply (Integer b) = Integer (a * b)
evalABinOp (Integer a) Divide (Integer b) = Integer (a `div` b)
evalABinOp (Integer a) Subtract (Integer b) = Integer (a - b)

而是修改相应的evalcase 使其递归：

eval (ABinary op x y) = evalABinOp (eval x) op (eval y)

这将具有相同的效果。