从零实现一个 Lisp 解释器第一篇－类型定义与解析

• 从零实现一个-Lisp-解释器第一篇-类型定义与解析.html
• 从零实现一个-Lisp-解释器第二篇-函数.html
• 从零实现一个-Lisp-解释器第三篇-状态与变量.html
• 从零实现一个-Lisp-解释器第四篇-lambda-函数与控制语句.html

完整代码地址：https://github.com/cycoe/lisp-interpretor

参考博客：https://www.defmacro.org/ramblings/lisp-in-haskell.html

又开一个新坑，这次是使用 Haskell 从零开始写一个 Lisp 解释器，将支持基 础类型和函数定义求值等功能。因为只是学习用途所以暂时不考虑性能，后面也 会通过连载的方式对功能进行逐步完善。

对于 Python 或 C++ 等语言，一般都是通过写一个 Hello world 程序来作为入 门。但 Haskell 不同，当你写出一个输出 Hello world 的程序时，其实你已经 用到了 IO Monad 这种从未见过的概念，虽然你在使用时对它并不了解。所以对 于 Haskell 来说，写一个 Hello world 程序在对程序原理的理解上并没有比写 一个 Lisp 解释器简单太多。

我们首先从最简单的情况入手，作为一个解释器至少要支持整数和符号。Lisp 中的符号与命令式语言中的变量相对应，符号可以理解为从一个字符串到表达式 的绑定。那么可以定义如下的代数结构表示 LispExpr，即 Lisp 表达式可以是 一个整数或者一个符号。

data LispExpr = LispInt Integer
              | LispSymbol String

那么我们就可以通过 LispInt 10 或者 LispSymbol "a" 这种方式构造一个 Lisp 表达式，这也成为后续操作的基础。

解释器的运行过程可以分为几个步骤：

1. 读取用户输出并解析为 Lisp 表达式（parse）
2. 对 Lisp 表达式求值（eval）
3. 输出求值结果（show）

用户输入是整个运行过程的源头，我们需要针对整型和符号定义对应的解析器。 这里我们使用 Parsec 库定义组合子进行解析操作，将字符串解析为 Lisp 表达 式。

intP :: GenParser Char st LispExpr
intP = LispInt <$> do
  sign <- option "" (string "-")
  num <- many1 digit
  return . read $ sign ++ num

symbolP :: GenParser Char st LispExpr
symbolP = LispSymbol <$> do
  f <- firstAllowed
  r <- many $ firstAllowed <|> digit
  return (f:r) where
    firstAllowed = oneOf "+-*/" <|> letter

lispP :: GenParser Char st LispExpr
lispP = try intP <|> try symbolP

与解析过程相对应的，我们需要一个函数将 Lisp 表达式重新格式化为字符串用 于输出。在 Haskell 中可格式化为字符串的类型我们一般会声明为 Show 类型 类的实例，实现它的 show 接口来完成格式化。

instance Show LispExpr where
  show :: LispExpr -> String
  show (LispInt i)    = show i
  show (LispSymbol s) = s

到目前为止，我们已经可以对整型和符号进行解析和输出，快来试一下吧。

a = runParser lispP "" "" "a"
show <$> a
-- Just a
i = runParser lispP "" "" "123"
show <$> i
-- Just 123

最后是对 LispExpr 进行求值的函数，这个函数我们命名为 eval 。对 LispInt 求值的结果就是它本身，而 LispSymbol 有点复杂。LispSymbol 表示 的是从一个字符串到 Lisp 表达式的绑定，那么我们需要定义一个数据结构来表 示这种绑定，Haskell 中可以使用 Map 来表示这种绑定关系。

import qualified Data.Map as Map
type Context = Map.Map String LispExpr

那么最后就可以实现这个求值函数。

eval :: Context -> LispExpr -> LispExpr
eval ctx (LispInt i)    = (LispInt i)
eval ctx (LispSymbol s) = ctx Map.! s

使用 eval 对 LispInt 和 LispSymbol 进行求值。整型 123 求值后就是它本身， 而符号 a 求值是从我们传入的符号表中查找对应的 Lisp 表达式进行返回。

eval Map.empty (LispInt 123)
-- 123
eval (Map.fromList [("a", LispInt 123)]) (LispSymbol "a")
-- 123