Write You a Scheme

撸了个 Scheme 解释器,也算是拿 Haskell 做过东西了(虽然只是个玩具

最大的体会就是,既熟悉了 Haskell,也巩固了 Scheme (虽然看过 SICP 但是并不是很明白它的 quosiquote 和 call/cc 之类的鬼东西

本来是打算自己定义一门语言(像这个),但是发现挺麻烦的(大雾),而且我比较关心的也是解释执行的过程,于是还是决定把 Scheme 实现一下。大体上是跟着 Write Yourself a Scheme in 48 Hours 来的,在它的基础上增加了 Continuation 之类的玩意儿

0. Parser

虽然 Lisp 的语法接近没有,但是还是总还是需要一个 Parser。Haskell 写Parser 的利器便是 parsec 。其实一开始有点想自己实现一个简单的 parser combiner ,但是最后还是懒(

Lisp 语法——所谓 S-expressions ,其实就是嵌套的列表,语法定义非常的简单


List → Expr (spaces) List | Expr

Expr → '(' List ')' | Atom

当然其实还有 quote 、dotted 之类的语法糖,也就是多加几个分支而已。

接下来便开始愉快的写代码了。写 Haskell 第一步当然是考虑类型。Scheme 语言内的数据类型这个解释器暂且实现四种:Number 整型、Float 浮点、String 字符串以及 Bool 。再加上语法中的 ListDottedList 以及通用的标识符 Atom ,便可以定义一个有 7 个值( constructor )的类型 LispVal


data LispVal = Atom String

| List [LispVal]

| DottedList [LispVal] LispVal

| Number Integer

| Float Double

| String String

| Bool Bool

当然,顺便让他们能够被 show 一下


instance Show LispVal where

show (Atom name) = name

show (List contents) = "(" ++ unwordsList contents ++ ")"

show (DottedList h t) = "(" ++ unwordsList h ++ " . " ++ show t ++ ")"

show (String ctns) = "\"" ++ ctns ++ "\""

show (Number num) = show num

show (Float num) = show num

show (Bool True) = "#t"

show (Bool False) = "#f"



unwordsList :: [LispVal] -> String

unwordsList = unwords . map show

然后便是拼 parsec 的组合子,将语法对应解析到七个 constructor 上


type LispParser = Parser LispVal



parseExpr :: LispParser

parseExpr = parseString <|> parseNumber <|> parseListSugar <|> parseAtom <|> do

_ <- char '('

x <- try parseList <|> parseDottedList

_ <- char ')'

return x

分别按照对应的语法规则实现 parseString parseNumber parseAtom parseList parseDottedList 即可(参考),其中 parseListSugar 用于解析 quote 之类的语法糖。

1. 执行、规约

如何将一个 S 表达式变成一个值?

最普通的情况,考虑一个 S 表达式表达函数调用。我们都知道 lambda calculus 的三条规则:

α-conversion: changing bound variables (alpha);

β-reduction: applying functions to their arguments (beta);

η-conversion: which captures a notion of extensionality (eta).

实现执行 Lisp 语句,实际上就是实现 β 规约——代换求值的过程。将一个 List 看作为 ((λV1.λV2.λV3.(...).E) ...) E3') E2') E1') ,作代换 E [V:=E'] 直到得到一个不能再规约的 β 范式。

得到了 β 范式之后呢?在实际的编程中表达式总会有一个值。经过上述过程之后得到的 β 范式,在实际中可能有两种形式:只包含一个自由变量的表达式 M,或者一个 lambda 表达式 λV.E 。

显然,如果最后的结果是只包含一个自由变量的表达式,我们的程序运行结果就是这个自由变量所对应的值。那么这个值到底是多少呢?这就涉及到一个很常见的 闭包 概念。如果规约结果是个函数,类似的,程序的运行结果可能是一个函数,而在这里还有另外一种可能—— Lisp 是一种不支持默认的函数部分应用的语言,如果规约出的 β 范式结果是一个函数,也有可能是程序出错——参数数目不一致。

这里暂且不讨论如何得到最后的结果,先实现对一个 Lisp 表达式进行 β 规约的 eval 函数。

由于存在抛错(参数数目不匹配)的情况,首先需要定义一个异常类型(利用 Control.Monad.Error 包),并实现从 Either 类型中获取值


-- import

import Control.Monad.Error



-- type

data LispError = NumArgs Integer [LispVal]



extractValue :: ThrowsError a -> a

extractValue (Right val) = val

extractValue _ = undefined



instance Show LispError where

show (NumArgs expr found) = "Expected " ++ show expr ++ " args; found values " ++ unwordsList found



instance Error LispError where

noMsg = Default "An error has occurred"

strMsg = Default



type ThrowsError = Either LispError

目前为止,我们的 eval 过程只是对表达式进行规约,接受的参数类型为 LispVal ,返回值也是一个 LispVal ,当然也可能抛异常。


eval :: LispVal -> ThrowsError LispVal

接着我们考虑如何表达一个函数。

从 λ 表达式和 Lisp 函数的形式来看,有两个要素——形参和函数体。我们可以用一个包含两个字段的 record 来表示。


data LispFunc = LispFunc {

paramsList :: [String],

body :: [LispVal]

}

并且函数应该作为语言中的一个类型


data LispVal = Atom String

| List [LispVal]

| DottedList [LispVal] LispVal

| Number Integer

| Float Double

| String String

| Bool Bool

| Lambda LispFunc

然后 show 一下


show (Lambda LispFunc { paramsList = params }) =

"(lambda (" ++ unwords (map show params) ++ ") ...)"

在 Scheme 中,表示一个函数的语法为 (lambda (params) (body)) 。如果在执行过程中碰到这种形式的表达式,我们会把它规约为一个函数。用模式匹配很容易做到。


eval (List (Atom "lambda" : List params : funcBody)) =

makeFunction params funcBody



-- makeFunction

makeFunction :: [LispVal] -> [LispVal] -> LispVal

makeFunction args funcBody = Lambda $ LispFunc (map show args) funcBody

然后考虑通用的函数调用语句 (function params...)

{- 妈呀写的好累 -}

{- TODO -}