在 48 小时内编写自己的 Scheme/评估，第一部分
目前，我们只是打印出我们是否识别给定的程序片段。我们即将迈出实现 Scheme 解释器的第一步：将值分配给程序片段。我们将从最基本的步骤开始，但很快你就会开始处理计算。
让我们首先告诉 Haskell 如何打印出各种可能 LispVal 的字符串表示形式。
showVal :: LispVal -> String
showVal (String contents) = "\"" ++ contents ++ "\""
showVal (Atom name) = name
showVal (Number contents) = show contents
showVal (Bool True) = "#t"
showVal (Bool False) = "#f"
这是我们第一次真正介绍模式匹配。模式匹配是一种解构代数数据类型的方法，根据其构造函数选择一个代码子句，然后将组件绑定到变量。任何构造函数都可以在模式中出现；如果标签与值的标签相同，并且所有子模式与其相应的组件匹配，则该模式与该值匹配。模式可以任意深度嵌套，匹配以从内到外，从左到右的顺序进行。如果这令人困惑，那么当我们深入评估器时，你将看到一些深度嵌套模式的示例。
现在，你只需要知道上述定义的每个子句都与 LispVal 的一个构造函数匹配，而右侧说明了如何处理该构造函数的值。
List 和 DottedList 子句的工作原理相似，但我们需要定义一个辅助函数 unwordsList 将包含的列表转换为字符串
showVal (List contents) = "(" ++ unwordsList contents ++ ")"
showVal (DottedList head tail) = "(" ++ unwordsList head ++ " . " ++ showVal tail ++ ")"
unwordsList 函数的工作原理与 Haskell Prelude 的 unwords 函数类似，它用空格将单词列表粘合在一起。由于我们正在处理一个 LispVal 列表而不是单词列表，因此我们定义了一个函数，该函数首先将 LispVal 转换为它们的字符串表示形式，然后将 unwords 应用于它。
unwordsList :: [LispVal] -> String
unwordsList = unwords . map showVal
我们对 unwordsList 的定义不包含任何参数。这是一个无点风格的例子：完全用函数组合和部分应用来编写定义，而不考虑单个值或“点”。相反，我们将它定义为几个内置函数的组合。首先，我们将 map 部分应用于 showVal，这将创建一个函数，该函数接受一个 LispVal 列表并返回其字符串表示形式列表。Haskell 函数是柯里化的：这意味着一个具有两个参数的函数，如 map，实际上是一个返回一个参数函数的函数。因此，如果你只提供一个参数，你将得到一个参数函数，你可以稍后传递、组合和应用它。在本例中，我们将它与 unwords 组合：map showVal 将 LispVal 列表转换为其字符串表示形式列表，然后 unwords 用空格将结果连接在一起。
我们在上面使用了函数 show。此标准 Haskell 函数允许你将任何类型（它是类 Show 的实例）转换为字符串。我们希望能够对 LispVal 做同样的事情，因此我们将其设为类 Show 的成员，将它的 show 方法定义为 showVal
instance Show LispVal where show = showVal
对类型类的完整处理超出了本教程的范围；你可以在 其他教程 和 Haskell 2010 报告 中找到更多信息。
让我们通过更改我们的 readExpr 函数来尝试一下，使其返回实际解析的值的字符串表示形式，而不是只返回“已找到值”。
readExpr input = case parse parseExpr "lisp" input of
Left err -> "No match: " ++ show err
Right val -> "Found " ++ show val
然后编译并运行……
$ ghc -package parsec -o parser listing4.1.hs
$ ./parser "(1 2 2)"
Found (1 2 2)
$ ./parser "'(1 3 (\"this\" \"one\"))"
Found (quote (1 3 ("this" "one")))
现在，我们从评估器的开始着手。评估器的目的是将一些“代码”数据类型映射到一些“数据”数据类型，即评估的结果。在 Lisp 中，代码和数据的类型是相同的，因此我们的评估器将返回一个 LispVal。其他语言通常具有更复杂的代码结构，具有各种语法形式。
评估数字、字符串、布尔值和引用的列表相当简单：返回数据本身。
eval :: LispVal -> LispVal
eval val@(String _) = val
eval val@(Number _) = val
eval val@(Bool _) = val
eval (List [Atom "quote", val]) = val
这引入了新的模式类型。符号 val@(String _) 与任何作为字符串的 LispVal 匹配，然后将 val 绑定到整个 LispVal，而不仅仅是 String 构造函数的内容。结果的类型为 LispVal，而不是 String。下划线是“不关心”变量，匹配任何值但不会将其绑定到变量。它可以在任何模式中使用，但在 @-模式（你将变量绑定到整个模式）和简单的构造函数测试中特别有用，在这种情况下，你只关心构造函数的标签。
最后一个子句是我们第一次介绍嵌套模式。List 包含的数据类型是 [LispVal]，一个 LispVal 列表。我们将其与特定的双元素列表 [Atom "quote", val] 匹配，该列表中的第一个元素是符号“quote”，第二个元素可以是任何东西。然后我们返回第二个元素。
让我们将 eval 集成到我们现有的代码中。首先将 readExpr 改回，使其返回表达式而不是表达式的字符串表示形式。
readExpr :: String -> LispVal
readExpr input = case parse parseExpr "lisp" input of
Left err -> String $ "No match: " ++ show err
Right val -> val
然后更改我们的主函数以读取表达式、评估它、将其转换为字符串并将其打印出来。现在我们了解了 >>= 单子排序运算符和函数组合运算符，让我们使用它们使它更加简洁。
main :: IO ()
main = getArgs >>= print . eval . readExpr . head
在这里，我们获取 getArgs 操作的结果（一个字符串列表），并将其传递到以下组合中：
- 获取第一个值 (
head)； - 解析它 (
readExpr)； - 评估它 (
eval)； - 将其转换为字符串并打印出来 (
print)。
以正常方式编译并运行代码
$ ghc -package parsec -o eval listing4.2.hs $ ./eval "'atom" atom $ ./eval 2 2 $ ./eval "\"a string\"" "a string" $ ./eval "(+ 2 2)" Fail: listing6.hs:83: Non-exhaustive patterns in function eval
我们仍然无法用这个程序做太多有用的事情（见证 (+ 2 2) 调用的失败），但基本骨架已经到位。很快，我们将使用一些函数来扩展它，使其变得有用。
接下来，我们将改进我们的 Scheme，以便我们可以将其用作简单的计算器。它还不是“编程语言”，但已经很接近了。
首先向 eval 添加一个子句来处理函数应用。请记住，函数定义的所有子句都必须放在一起，并且按文本顺序进行评估，因此这应该放在其他 eval 子句之后。
eval (List (Atom func : args)) = apply func $ map eval args
这是另一个嵌套模式，但这次我们匹配的是 cons 运算符“:”而不是字面列表。Haskell 中的列表实际上是 cons 应用和空列表的链的语法糖：[1, 2, 3, 4] = 1:(2:(3:(4:[])))。通过对 cons 本身而不是字面列表进行模式匹配，我们说“给我列表的其余部分”，而不是“给我列表的第二个元素”。例如，如果我们将 (+ 2 2) 传递给 eval，则 func 将绑定到“+”，而 args 将绑定到 [Number 2, Number 2]。
子句的其余部分由几个我们之前见过的函数和一个我们尚未定义的函数组成。我们必须递归地评估每个参数，因此我们将 eval 映射到 args 上。这就是让我们能够编写像 (+ 2 (- 3 1) (* 5 4)) 这样的复合表达式的原因。然后我们获取结果的已评估参数列表，并将它与原始函数一起传递给 apply 函数。
apply :: String -> [LispVal] -> LispVal
apply func args = maybe (Bool False) ($ args) $ lookup func primitives
内置函数 lookup 在一个键值对列表中查找一个键（它的第一个参数）。但是，如果列表中没有包含匹配键的键值对，lookup 将失败。为了表示这一点，它返回内置类型 Maybe 的一个实例。我们使用函数 maybe 来指定在成功或失败的情况下该做什么。如果函数未找到，我们返回一个 Bool False 值，等效于 #f（我们将在稍后添加更强大的错误检查）。如果找到了，我们使用 ($ args) 将其应用于参数，这是一个函数应用运算符的操作符部分。
接下来，我们定义支持的原始函数列表。
primitives :: [(String, [LispVal] -> LispVal)]
primitives = [("+", numericBinop (+)),
("-", numericBinop (-)),
("*", numericBinop (*)),
("/", numericBinop div),
("mod", numericBinop mod),
("quotient", numericBinop quot),
("remainder", numericBinop rem)]
看看 primitives 的类型。它是一个键值对列表，就像 lookup 所期望的那样，但键值对的值是从 [LispVal] 到 LispVal 的函数。在 Haskell 中，您可以轻松地将函数存储在其他数据结构中，尽管这些函数必须具有相同的类型。
此外，我们存储的函数本身也是函数 numericBinop 的结果，我们还没有定义它。它接受一个原始 Haskell 函数（通常是一个操作符部分），并用代码对其进行包装，以解包参数列表，将函数应用于它，并将结果包装在我们的 Number 构造函数中。
numericBinop :: (Integer -> Integer -> Integer) -> [LispVal] -> LispVal
numericBinop op params = Number $ foldl1 op $ map unpackNum params
unpackNum :: LispVal -> Integer
unpackNum (Number n) = n
unpackNum (String n) = let parsed = reads n :: [(Integer, String)] in
if null parsed
then 0
else fst $ parsed !! 0
unpackNum (List [n]) = unpackNum n
unpackNum _ = 0
与 R5RS Scheme 一样，我们不局限于仅两个参数。我们的数值运算可以对任何长度的列表起作用，因此 (+ 2 3 4) = 2 + 3 + 4，而 (- 15 5 3 2) = 15 - 5 - 3 - 2。我们使用内置函数 foldl1 来做到这一点。它实质上将列表中的每个 cons 运算符更改为我们提供的二元函数 op。
与 R5RS Scheme 不同的是，我们正在实现一种弱类型形式。这意味着如果一个值可以解释为一个数字（例如字符串 "2"），即使它被标记为字符串，我们也会将其用作一个数字。我们通过在 unpackNum 中添加几个额外的子句来做到这一点。如果我们正在解包一个字符串，尝试使用 Haskell 的内置 reads 函数对其进行解析，该函数返回一个包含 (解析后的值，剩余字符串) 对的列表。
对于列表，我们对包含一个元素的列表进行模式匹配，并尝试解包它。其他任何情况都将传递到下一个情况。
如果由于任何原因我们无法解析数字，我们现在将返回 0。我们将在短期内修复这个问题，以便它发出错误信号。
以正常方式编译并运行它。注意我们如何“免费”获得嵌套表达式，因为我们在每个函数参数上调用了 eval
$ ghc -package parsec -o eval listing7.hs $ ./eval "(+ 2 2)" 4 $ ./eval "(+ 2 (-4 1))" 2 $ ./eval "(+ 2 (- 4 1))" 5 $ ./eval "(- (+ 4 6 3) 3 5 2)" 3
| 练习 |
|---|