/** * * @source: /assets/org-info.js * * @licstart The following is the entire license notice for the * JavaScript code in /assets/org-info.js. * * Copyright (C) 2012-2013 Free Software Foundation, Inc. * * * The JavaScript code in this tag is free software: you can * redistribute it and/or modify it under the terms of the GNU * General Public License (GNU GPL) as published by the Free Software * Foundation, either version 3 of the License, or (at your option) * any later version. The code is distributed WITHOUT ANY WARRANTY; * without even the implied warranty of MERCHANTABILITY or FITNESS * FOR A PARTICULAR PURPOSE. See the GNU GPL for more details. * * As additional permission under GNU GPL version 3 section 7, you * may distribute non-source (e.g., minimized or compacted) forms of * that code without the copy of the GNU GPL normally required by * section 4, provided you include this license notice and a URL * through which recipients can access the Corresponding Source. * * @licend The above is the entire license notice * for the JavaScript code in /assets/org-info.js. * */
HOME | EDIT | RSS | ARCHIVE | INDEX | ABOUT

用Haskell48小时写你个Scheme

前言

everyone-out-of-the-universe.gif

你可以当这是 Write Yourself a Scheme in 48 Hours 的笔记,但并不是中文版。所以只是按我的理解来解释,如果有看不懂或者描述有误欢迎留言或者Pull Request。

而且,歪果仁比较啰嗦,所以除了例子,别的啰嗦都略掉了,可能看这个写Scheme只要24小时吧 偷笑

这本笔记带有 org-info.js,因此你可以使用快捷键

  • n 翻下一页
  • p 翻上一页
  • u 上级section
  • h Home
  • 更多快捷键可以按 ? 查看

好了,现在开始用Haskell来实现Scheme吧

跑起来

haskell.png

Hello World

一切从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

原因是 do 只是 >>= (aka flatMap) 和 >> 的语法糖,flatmap 永远应该返回同样类型的 Monad

getArgs >>= (\args -> putStrLn ("Hello, " ++ args !! 0))

现在我们跑一些这个 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, 这样可以根据用户输入来获取名字,并打印

语法分析

robot-what.gif

写个简单的parser

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

cabal install parsec

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

定义 parser

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

然后实现一个简单的可以解析一些 scheme 符号的 parser

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

symbol 等于 oneOf blahblah, 返回一个 Parser Monad, 里面是 Char 类型

Parse

下面我们用这个 parser 试试 parse 一下

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

tadah, 这时出现了 case, 如果用 scala 的童鞋就毫不陌生了,没用过 pattern matching的童鞋看过来

这一大坨 parse symbol "lisp" input 是一个表达式, 调用 parse 函数, 传入 3 个参数 symbol, ="lisp"=, input. 其中, input 是 readExpr 的参数.

我们来看下 parse 的类型签名, 可能更清楚一点 才怪

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

好吧,先忽略掉中间那一大坨,来看看 -> 最右边的类型是个 Either ParseError a, 读出来就是 Either ParserError or a, 这就是 parse 函数的 返回值 类型了, 这个类型总之是个 Either, 里面要么是 ParserError 要么是个 a, 而 a 就是前面 Text.Parsec.Prim.Parsec s () a 里的 a

Either

先不管细节,大体上来说, parse 接收 一个 Parsec 类型, 一个描述, 一个 Stream 类型, 返回一个 Either

先看 readExpr 什么效果:

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

这时明显走的是 Left err -> "No match: " ++ show err 这个分支, 而

> readExpr "*"
"Found value"

走的是 Right 分支.

所以在我们来解释 case, 根据代换原则, case 的就是 parse 的返回值 Either, Either 是一个 ADT, union type, scala里面是 trait + case class. 所以 Either 其实就是几种类型的 union. 当 case 一个 Either 的时候, 我们可以 match 两个类型, Left 或者 Right. 而通常来说 Right 里面永远会放 right 的东西, 所以 Left 就是不 right 的咯.

pattern matching

下来是 of 后面的 blah -> blah blah

如果是 Left err Left 的内容就会绑定到 err, -> 右边的表达式就可以用到绑定 err 了.

同理, 也可以拿到 Right 的内容并绑定到 val

空白符

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

spaces :: Parser ()
spaces = skipMany1 space

这里我们定义了 spaces 函数, 这也是为什么要在之前的 import 的时候 hidingParsec 里的 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

有了这个抽象数据类型 ADT,我们就可以将parse的内容转换成 scheme 的 ADT, 首先,试试 parse 个 String

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

首先, parseString 返回类型 Parser LispVal, 实现中把 char, many和 char 都链起来, 意思是先 parse 一个双引号字符, 再 parse many 个不是双引号字符的字符, 返回的 Parser 的内容放入 x, 继续 parse 一个双引号. 最后用我们刚构造的 ADT 构造一个 String 出来.

其中 $ 是上一章说过的将左结合表达式转换成右结合, 等价于 return (String x). 好处是尽量少些括号是代码更可读.

另外一点就是 return, 如果不是用 return, 返回值会是 LispVal 类型, 但是期望的是 Parser. 因此在 do 这个 context 中, 所有的 monad 都是 Parser, 比如 char, many, 都是返回 Parser 类型. 那么到最后一个表达式, 可以简单的用 return 根据上下文把 LispVal 包到 Parser monad 中.

parseAtom

atom 的parser 也比较直接, 正常的 atom

  • 第一个字母可以是符号
  • 剩下的部分可以是多个符号数字或者字符
  • #t 是 True, #f 是 False
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

这里出现了另外一个Parsec的组合子 <|>, 其实是 Parser monad 的或, 也就是如果前面的成功, 就不会继续尝试后面的 Parser.

另一个新东西是 let, 它定义了新的绑定 atom, 到 first:rest 上.

_ 匹配所有剩下的 case

parseNumber

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

many1 digit 匹配一个或多个数字, 返回一个 Parser String

(Number . read) 就是 Number compose read, 也就是先 apply read, 返回的结果 apply 给 Number.

组合好的函数还是不能处理 many1 digit 返回的 Parser String, 因为 read 期待一个 String 类型.

所以我们使用 LiftM 将组合好的函数, lift 成 Monad(确切的说是 Applicative), 在这个context, Monad 就是 Parser

最后

有了这几个 parser, 可以用我们刚见过的 <|> 把它们拼起来

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

用我们的新 parser 放到 readExpr 中:

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

求值,第一部分

to String

在真的开始 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"

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

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

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(' ')

实现 show 类型类

上节的 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)"

待续…

  • 错误处理及异常
  • 求值,第二部分
  • 来造个REPL
  • 变量与赋值
  • 定义函数
  • IO
  • 标准库
  • 其他东西