Write Yourself a Scheme in 48 Hours(4)

4. 求值，第一部分

4.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 构造符匹配，而右手边部分告诉对那个构造符的值做什么。

列表和 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 定义并没有包括任何的参数。这只一个 point-free 风格的例子：完全按照函数结合和局部应用的方式写定义，而不看待独个的值或者点。相应的，我们用一组内建函数定义这个函数。首先，我们给 showVal 部分应用 map ，就创建了一个接受一个 LispVal 列表然后返回他们的字符串表现形式的列表。 Haskell 函数是 curried ：这表明一个有两个参数的函数，像 map ，真正是一个返回一个有一个参数的函数的函数。作为结果，如果你之使用一个参数，你会返回一个可以传递、结合、应用的单参数函数。在这个例子里，我们把它和 unwords 函数结合 :map showVal 转换一个 LispVal 列表成为它们字符串表达式的列表，然后 unwords 将结果用空白字符结合在一起。

我们在上面是用 show 函数。这个标准 Haskell 函数让你转换任意是 class Show 实例的类型成为一个字符串。我们希望对 LispVal 做同样的事情，所以我们让它成为 class Show 的一个成员，定义它的 show 方法：

 

instance Show LispVal where show = showVal

 

类型类的全部论述超过了这个教程的范围 ; 你可以在其他的教程和 Haskell 98 report 找到更多的信息。

让我们试试改变我们的 readExpr 函数，让它返回值实际解析值的字符串表现形式，而不仅仅是 "Found value” 。

 

readExpr input = case parse parseExpr "lisp" input of
    Left err -> "No match: " ++ show err
    Right val -> "Found " ++ show val

 

 

继续编译并运行：

 

jdtang@debian:~/haskell_tutorial/code$ ghc -package parsec -o parser  listing4.1.hs
jdtang@debian:~/haskell_tutorial/code$ ./parser "(1 2 2)"
Found (1 2 2)
jdtang@debian:~/haskell_tutorial/code$ ./parser "'(1 3 (\"this\" \"one\"))"
Found (quote (1 3 ("this" "one")))

 

4.2 开始一个求值器： Primitives

现在，我们开始编写一个最初的求值器。这个求值器的目的是在于映射一些“代码”数据类型到另一些“数据”数据类型，即求值器的结果。在 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 然后将整个 LispVal 绑定给 val ，而不仅仅是 String 构造器的值。它的结果是 LispVal 类型而不是 String 类型。下划线是 "don't care” 变量，它与任意没有绑定的值匹配并绑定。它能用在任何模式中，但是与 @- 模式一起最有用（这里你将变量与整个模式绑定），当你只对构造符标签感兴趣的时候下划线同简单的构造符测试一起也非常有用。

最后一个子句是我们第一次介绍嵌套模式。包含 Lisp 的数据的类型是 [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

 

接下来改变我们的主函数来读入一个表达式，然后求值，将它转换成一个字符串，最后将结果答应出来。现在我们知道 >>=monad 连续操作符和函数结合操作符，让我们使用它们来让这段代码更简明。

main :: IO ()
main = getArgs >>= putStrLn . show . eval . readExpr . (!! 0)

 

这儿，我们我们使用 getArgs 的值 ( 一个字符串列表）然后将它传入下面的组合中：

1. 取出第一个元素（ (!!0) ）。这个表示法是 operator section ：它告诉编译器部分应用列表索引操作符到 0, 返回一个取出任何列表第一个元素的函数。

2. 分析它 (readExpr)

3. 求值 (eval)

4. 转换结果成一个字符串 (show)

5. 打印结果 (putStrLn)

正常编译并运行这段代码：

debian:/home/jdtang/haskell_tutorial/code# ghc -package parsec -o eval  listing4.2.hs
debian:/home/jdtang/haskell_tutorial/code# ./eval "'atom" 
atom
debian:/home/jdtang/haskell_tutorial/code# ./eval 2
2
debian:/home/jdtang/haskell_tutorial/code# ./eval "\"a string\""
"a string"
debian:/home/jdtang/haskell_tutorial/code# ./eval "(+ 2 2)"

Fail: listing6.hs:83: Non-exhaustive patterns in function eval

 

我们仍然不能用这个程序做太有用的事情 ( 像 (+ 2 2) 表达式失败 ) ，但是最基础的骨架已经在这里了。很快，我们就能用一些函数扩展它让它更有用。

4.3 添加基本的 primitives

接下来，我们将改进我们的 Scheme 让我们能用它作为一个简单的计算器。这仍然不是一个 " 编程语言 " 但是它更接近。

从添加一个子句来处理函数声明的求值开始。记住所有的函数定义子句必须放在一起并以文本顺序求值，所以这个应该放在其他求值语句的后面：

eval (List (Atom func : args)) = apply func $ map eval args

这是另一个嵌套模式的例子，但是这一次我们匹配构造操作符 ":” 而不是一个字面量列表。 Haskell 中的列表是语法糖来改变构建操作和空表 :[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 在 pairs 列表里查找一个关键字 (pair 的第一个元素 ) 。然而，如果表里没有任何的一对包含匹配的关键字，查找会出错。表达这种情况，函数返回一个内建类型 Maybe 的实例。我们使用 maybe 函数指出成功或失败各自做什么。如果函数没有找到，我们返回一个布尔 False 值，相当于 #f （我们之后添加更健壮的错误检查）。如果它找到了，我们将它应用到用 ($ args) 的参数， an operator section of the function application operator.

接下来，我们定义我们支持的原始函数列表：

primitives :: [(String, [LispVal] -> LispVal)]
primitives = [("+", numericBinop (+)),
              ("-", numericBinop (-)),
              ("*", numericBinop (*)),
              ("/", numericBinop div),
              ("mod", numericBinop mod),
              ("quotient", numericBinop quot),
              ("remainder", numericBinop rem)]

 

看看 primitivs 的类型。它是一个 pair 列表，恰好是 lookup 期待的，但是 pairs 的值是从 [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 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 我们用内建函数 fold1 来做这个事情。它本质上改变列表中每一个构建操作符成我们提供的二进制函数 ,op 。

不像 R5RS Scheme ，我们用一种弱输入的方式实现。这意味着如果一个值能够被解释成一个数字 ( 像 String “2”) ，我们就将它作为一个数字，尽管它被标记为一个字符串。如果我们解开一个字符串，尝试用 Haskell 内建 reads 函数分析它，就会返回一个 ( 分析值，原始值 ) 对的列表。

对于列表，我们用单元素列表模式匹配在尝试解开它。任何其它情况都会进入下一个情况。

如果我们因为任何原因不能解析数字，我们目前都会返回 0 。我们会马上修改它让它返回一个错误信号。

正常编译并运行。 Note how we get nested expressions "for free" because we call eval on each of the arguments of a function:

debian:/home/jdtang/haskell_tutorial/code# ghc -package parsec -o eval  listing4.3.hs
debian:/home/jdtang/haskell_tutorial/code# ./eval "(+ 2 2)" 4
debian:/home/jdtang/haskell_tutorial/code# ./eval "(+ 2 (-4 1))"
2
debian:/home/jdtang/haskell_tutorial/code# ./eval "(+ 2 (- 4 1))"
5
debian:/home/jdtang/haskell_tutorial/code# ./eval "(- (+ 4 6 3) 3 5 2)"
3

 

习题：

1 、添加一个原始函数来执行各种 R5RS 中的类型测试函数 :symbol? ， string? ， number? 等等。

2 、改变 unpackNum 函数让它当值不是一个数的时候总是返回 0, 无论它是否是一个可以被解析成数字的字符串或者列表。

3 、添加 R5RS 中的符号操作函数。一个符号是我们在我们的数据构造符中称作 Atom 的数据。