用Haskell48小时写你个Scheme

一切从hello开始，说好的用Haskell实现，先来看Haskell写一个hello world 有多麻烦

module Main where
import System.Environment
main :: IO ()
main = do
  args <- getArgs
  putStrLn ("Hello, " ++ args !! 0)

module 可以稍后介绍，其中

• import System.Environment 可以将 getArgs 引进来
• do 后面是一个块，就是一坨坨表达式，更重要的是还可以在do 里面用这样的 value <- monad 的玩意。如果写过scala，跟 for 是一样一样的。
• getArgs 类型为 IO[String], 意思是 IO Monad 中有个 [String] 类型的值
• <- 相当于取出来 IO 中的 [String], 所以 args 现在是 [String]
• 双叹号 !! 是 List 的取 index 操作，这里则是取 args 第一个 String
• ++ 号就是 concat, 用于连接两个 List
• 注意 do 里面只允许一种 Monad，这里面则只允许 IO Monad

现在我们跑一些这个 hello.hs, 过程跟 gcc 差不多

❯ ghc hello.hs -o hello
[1 of 1] Compiling Main             ( hello.hs, hello.o )
Linking hello ...
hello ⏎
❯ ./hello jichao
Hello, jichao

前面出现了好些操作符，比如 ++ !! ，当它们堆叠到一起如果没有括号，很难分辨哪些表达式会先求值，所以先让我们熟悉一下常见的操作符，都有哪些结合律，以及优先级顺序

操作符	优先级	结合律	什么鬼
.	9	右	函数组合，比如 flat . map 就是 先map，结果再flat
!!	9	左	取 List index 上的值 [1,2] !! 0 -- > 1
^,^^,**	8	右	幂
*,/	7	左	乘，除
+,-	6	左	加，减
:	5	右	Cons, 1:2:[] 相当于 Cons(1,Cons(2, []))
++	5	右	List 连接
`elem`, `notElem`	4	左	方法作为二元操作符时
==, /=, <, <=, >= , >	4	左	等不等大不大
&&	3	右	与
||	2	右	或
>>=, >>	1	左	Monadic Bind
=<<	1	右	反向的 Monadic Bind
$	0	右	强行改右结合

1. 修改helloword成读两个参数，并打印
2. 把两个参数给的数字相加，输出结果
3. 使用 getLine 替换 getArgs, 这样可以根据用户输入来获取名字，并打印

语法分析，需要引入著名的Parsec库, 当然,在这之前得先安装 Parsec

cabal install parsec

如果没有 cabal 都没装, 请 brew install cabal, 非mac用户对不住了,我也不知道怎么装,自行google吧.

import Text.ParserCombinators.Parsec hiding (spaces)
import System.Environment

symbol :: Parser Char
symbol = oneOf "!#$%&|*+-/:<=>?@^_~"

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

> :t parse
parse
  :: Text.Parsec.Prim.Stream s Data.Functor.Identity.Identity t =>
     Text.Parsec.Prim.Parsec s () a
     -> SourceName -> s -> Either ParseError a

> readExpr "a"
"No match: \"lisp\" (line 1, column 1):\nunexpected \"a\""

> readExpr "*"
"Found value"

现在我们能拿到 scheme 的 symbol 了, 作为一个 parser 还需要过滤掉一些没用的空白符, 比如说空格先:

spaces :: Parser ()
spaces = skipMany1 space

这里我们定义了 spaces 函数, 这也是为什么要在之前的 import 的时候 hiding 掉 Parsec 里的 spaces

readExpr input = case parse (spaces >> symbol) "lisp" input of
    Left err -> "No match: " ++ show err
    Right val -> "Found value"

这里将 spaces 用 >> 拼到 symbol 前面, >> 读 bind, 在不同的 monad 中, >> 的行为也不一样, 这里作为 Parsec Monad, >> 意思是用 spaces 去 parse, 结果丢弃掉, 然后再用 symbol 去 parse.

到现在为止我们的parser也只能说打印是否找到合法的输入, 但是还不能真正的将输入字符parse成为数据结构.

所以假设我们先来实现将读入的字符转换成值, scheme 的值有这么几种

data LispVal = Atom String
             | List [LispVal]
             | DottedList [LispVal] LispVal
             | Number Integer
             | String String
             | Bool Bool

如果你还记得之前提到的 Either 是 ADT, 那么现在这个 LispVal 就是一个 ADT, 在 haskell 定义一个 ADT 特别简单, 关键字 data 声明 LispVal 是一个ADT, 等号右边是构造器, 比如

• Atom String 表示可以通过 Atom "blah" 就创建出来一个 LispVal data, 里面包含一个 Haskell String 类型的值
• List [LispVal] 表示 List 里有一个 LispVal 类型的数组, 比如 List [Atom "blah"]
• DottedList [LispVal] LispVal 构造器接收两个参数, 一个是 LispVal 类型的数组,一个是 LispVal

所以这么定义下来, 说明 scheme 的值类型有这么6种

• Atom 即名字什么的 (foo bar)
• List 数组 (1 2 3)
• DottedList 带点数组 (1 2 . 3)
• Number 数字
• String 字符
• Bool 布尔

parseString :: Parser LispVal
parseString = do
                char '"'
                x <- many (noneOf "\"")
                char '"'
                return $ String x

parseAtom :: Parser LispVal
parseAtom = do 
              first <- letter <|> symbol
              rest <- many (letter <|> digit <|> symbol)
              let atom = first:rest
              return $ case atom of 
                         "#t" -> Bool True
                         "#f" -> Bool False
                         _    -> Atom atom

parseNumber :: Parser LispVal
parseNumber = liftM (Number . read) $ many1 digit

parseExpr :: Parser LispVal
parseExpr = parseAtom
         <|> parseString
         <|> parseNumber

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

在真的开始 eval 之前, 我们先把打印的部分实现, 比如之前能 parse 的 List 打印成 scheme 的话应该是 ()

简单的实现 premitive 类型

1: showVal :: LispVal -> String
2: showVal (String contents) = "\"" ++ contents ++ "\""
3: showVal (Atom name) = name
4: showVal (Number contents) = show contents
5: showVal (Bool True) = "#t"
6: showVal (Bool False) = "#f"

<interactive>:20:10: error: Not in scope: data constructor ‘Bool’

注意看 2,3,4 行, 还记得之前说过的 模式匹配 吗? 这里是定义带模式匹配的函数,也就是说函数 showVal 会根据匹配参数 LispVal 来找到对应真正要使用的函数. 更重要的是, 模式匹配可以 destructure 数据, 比如 (String contents) 就会匹配 String 类型的数据, 并将内容绑定到 contents 上. 这样, 后面就可以使用 contents 了.

处理完这些 premitive 类型, 接下来看看如何打印稍微复杂一些的 List 和 DottedList 吧.

showVal (List contents) = "(" ++ unwordsList contents ++ ")"
showVal (DottedList head tail) = "(" ++ unwordsList head ++ " . " ++ showVal tail ++ ")"

scheme 的 List 用括号括起来, 内容则是用空格分开的一个个元素, 例如 (1 2 3 4). DottedList 则跟名字一样, 是 head 和 tail 中间都了一个点 .

其中的 unwordsList 会将内容的元素的 showVal 值用空格连接起来.

unwordsList :: [LispVal] -> String
unwordsList = unwords . map showVal

利用的是 Haskell 的 unwords 函数, 类似于其他语言的 join(' ')

上节的 showVal 实现中, 不知道有没有注意到 Number 的实现使用了 show contents. 我们知道 contents 的类型是 Haskell 的 Integer, 之所以可以 show, 是 Integer 实现了类型类 Show.

同样的我们可以实现让 LispVal 类型实现类型类 Show

instance Show LispVal where show = showVal

同时实现类型类 Show 中的函数 show, 恩,这有些像 Interface

下面,我们就可以修改 readExpr 函数, 让他打印出 parse 出来的值

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

输出

ghc -package parsec -o parser src/listing4.1.hs
./parser "(1 2 2)"