原文。
https://en.wikibooks.org/wiki/Write_Yourself_a_Scheme_in_48_Hours/Evaluation,_Part_1
开始求值
现在，我们仅仅能打印出来我们是否能够将给定的代码片段分辨出来而已。我们现在将向一个能够正常工作的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函数与Prelude库中的unwords函数类似，它把列表中的的单词用空格粘在一起。因为我们要处理的是LispVal而不是单词组成的列表，我们需要定义一个函数将LispVal转换成为对应的字符串形式然后再对它们使用unwords函数：
unwordsList :: [LispVal] -> String
unwordsList = unwords . map showVal
我们的unwordsList定义并没有包含任何的参数。这就是一个point-free编程的例子：完全通过函数组合和局部调用的方式来进行定义，而单独的看待值或者说参数。相反的，这里我们使用了一组内建函数的组合来定义这个函数。首先，我们将showVal函数传递给map从而通过局部调用的方式创建了一个接受LispVal列表然后返回他们的字符串形式的列表的函数。Haskell函数是柯里化的：这意味着某个有两个参数的函数，例如map，实际上是一个会返回一个只一个参数的函数的函数。因此，如果你只使用一个参数去调用它，你就会得到一个可以传递，结合或是之后在进行调用的单参数函数。在这个例子里，我们将它和unwords函数结合：map showVal转换一个LispVal列表成为它们的字符串形式的列表，然后unwords将结果用空白字符结合在一起。
我们在上面使用了show函数。这个标准Haskell函数让你能够将任意是Show实例的类型转换成为一个字符串。我们希望对LispVal也能够做同样的事情，因此我们将它定义成class Show的一个成员，并将它的show方法直接定义成showVal：
instance Show LispVal where show = showVal
完整的类型类的介绍不在这次教程的范围之内；你可以在其他教程或是Haskell 98 report里找到更多的相关信息。
让我们再试试看改变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变量，而不仅仅是String构造器中的值。它是LispVal类型而不是字符串类型的。下划线是一个任意变量，它会匹配一个任意的没有与变量绑定的值。它能出现在任何的模式中，但是在和@-模式一起（你将变量与整个模式绑定）或是当你只对构造器的类型感兴趣的时候它会特别的有用。
在最后一个分支里我们会第一次看到一个嵌套的模式。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）
- 转换结果成字符串并打印出来。
像之前那样编译并运行程序：
$ 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)都计算不了），但是一个基本的框架已经有了。接下来，让我们通过扩展基本函数的方式来让我们的解释器变得有用一些。
添加基本操作
接下来，我们来对我们的解释器进行一些改进从而可以支持基本的计算。虽然它还不是完整的“编程语言”，但也不远了。
我们首先给eval函数添加一个模式，从而让它可以处理函数调用。记住函数定义中的所有子句都必须放在一起，它们会依次进行匹配和求值，因此我们把这个表达式放在其他子句的后面：
eval (List (Atom func : args)) = apply func $ map eval args
这里又是一个嵌套模式，但这次我们尝试使用构造操作符:进行匹配而不是像之前那样使用一个列表的形式。事实上在Haskell中，列表也仅仅是一个用来表示cons函数调用串的语法糖而已：[1, 2, 3, 4] = 1:(2:(3:(4:[])))。通过匹配cons本身而不是一个字符串列表，我们就像是在“获取列表的剩下的部分”而不是仅仅“获取列表的第二个元素”。例如，如果我们传递(+ 2 2 )给eval函数，func变量会与+绑定而args变量会与[Number 2, Number 2]进行绑定。
剩下部分包括了一些我们之前已经熟悉的函数以及最后一个我们还没有定义的函数。由于我们必须递归的对每一个参数进行求值，因此我们对每一个参数调用eval函数。这允许我们能够进行(+2 (- 3 1) (* 5 4))这样的复合表达式。然后我们再将计算过后的参数传递给先前的函数再进一步进行求值：
apply :: String -> [LispVal] -> LispVal
apply func args = maybe (Bool False) ($ args) $ lookup func primitives
内置函数lookup会在Pair列表搜索关键字（Pair的第一个元素）。然而，如果列表里没有包含对应的关键字，查找就会出错。因此该函数会返回一个Haskell的内建类型Maybe的实例从来避免程序异常。我们使用maybe函数来分别指定当成功或失败的情况下分别进行什么样的处理。当函数没有找到的情况，我们返回一个False值，即是#f（之后会添加更健壮的错误检查机制）。而如果找到了，我们就通过函数呼叫符这样($ args)来将它应用到函数的参数。
接下来，我们来定义一些需要支持的基础操作：
primitives :: [(String, [LispVal] -> LispVal)]
primitives = [("+", numericBinop (+)),
("-", numericBinop (-)),
("*", numericBinop (*)),
("/", numericBinop div),
("mod", numericBinop mod),
("quotient", numericBinop quot),
("remainder", numericBinop rem)]
看下primitivs函数的类型。事实上它是一个Pair类型的列表，恰好是能和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 4 3) = 15-5-3-2。我们是使用内建函数foldl1
来实现这一点的。事实上它即是将列表中每一个连接操作符都替换成了我们提供的二元函数op。
与R5RS Scheme不同，我们的解释器使用了一种弱输入的方式。这意味着如果一个值能够被解释成一个数字（例如字符串“2”)，我们就会将它看做一个数字，尽管它也许被标记成一个字符串。我们给unpackNum函数添加了一系列子句从使它能够解析各式各样的字符串。如果我们希望分解一个字符串并尝试用Haskell的内建函数reads去解析它，该函数就会返回一个（分析值，剩余值）对的列表给我们。
而对于列表的情况，我们直接尝试将它和一个单元素列表进行匹配并分解。匹配失败的话则会直接掉入第二个情况。
如果由于某些原因我们无法对数字进行解析，那么我们就暂时直接返回0作为结果。我们之后会对它进行修复并让它提示一个错误信息。
像之前那样编译并运行程序。注意到我们并没有做什么特殊的处理就直接能够对嵌套的表达式进行求值了，这是拜我们之前对函数每个参数进行求值所赐：
$ 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
习题
- 添加对R5RS中的类型测试数的原生支持 :symbol?，string?和number?等。
- 修改unpackNum函数让它当输入值不是一个数字的时候总是返回0，即使它是一个可以被解析成数字的字符串或者列表。
- 添加对R5RS中的symbol-handling functions的支持。symbol是指我们在之前的LispVal类型中被称作Atom的东西。
