这是一篇Lisp解释器的教程。参考国外某大神的Lisp（其实是其中的一种叫做Scheme的方言）的解释器的过程。

正好在学编译原理，准备搞一些事情，这个project纯当一个搞事情的前奏。因为一年多前简略的看过了SICP，所以对LISP语言有一定小小的理解，所以开一个LISP语言的解释器，对编译上的理解可能会非常的有帮助。

另外，国内能够自主写出编译器的人实在是太少，这一行业上可能更多的引用国外大神的博客内容，所以搬运和翻译加上自主原创的这种过程也是极有必要的。

作者：岐山凤鸣，引用请加上本站域名

内容：作者原创

参考：http://norvig.com/lispy.html

参考：http://blog.jobbole.com/47659/

参考：关于符号类型：http://blog.csdn.net/xiao_wanpeng/article/details/8441562

插曲：这么久没有更新，很大一部分原因因为数据丢失，有道云笔记略坑。

概述

没错，来到了项目中最最核心的内容，就是eval函数，一个很邪恶的函数，可以直接执行解析为语法树的语法结构。

再来回顾一下eval函数的作用。

>>> code = '(+ 4 (+ 5 6))'
>>> eval(parse(code))
15

>>> code = '(define x 123)'
>>> eval(parse(code))
123

>>> code = 'display "hello world"'
>>> eval(parse(code))
hello world

比如(+ 4 (+ 5 6))经过parse解析后为一棵列表树[’+’, 4, [’+’, 5, 6]]，那么eval(parse(code))的作用就是将这棵树解析为add(4, add(5, 6))，这样应该就懂了eval函数的作用。

初版eval

先直接上eval部分的代码吧，第一个版本的很少很少：

def eval(x, env = global_env):
	if isinstance(x, Symbol):
		return env.find(x)[x]

	elif not isinstance(x, list):
		return x

	elif x[0] == _quote:
		(_, exp) = x
		return exp
	
	elif x[0] == _if):
		(_, test, conseq, alt) = x
		exp = (conseq if eval(test ,env) else alt)
		return eval(exp, env)

	elif x[0] == _define:
		(_, var, exp) = x
		env[var] = eval(exp, env)

	else:
		proc = eval(x[0], env)
		args = [eval(arg, env) for arg in x[1:]]
		return proc(*args)

没错，最简单的一个eval就是如上所示，分了六个分支，分别表示，如果x[0]是：

记号：则根据标准环境返回相应记号的对应的操作类型，如’+’, 则返回op.add函数
数字：直接返回该数字
引用：返回引用后面所有的内容，如(quote “hello world”)，则返回“hello world”
条件if：(if (> x 10) (* x 5) (/ x 5)), if后包含了test, conseq, alt三个东西，于是判断if语句的时候先递归调用eval(parse(‘(> x 10)’)),得到真则返回conseq, 即eval(parse(‘(* x 5)’))，得到假则返回alt，即eval(parse(‘(/ x 5)’))
宏定义define: 改变标准环境的env值，将(define x 10)，变成’x’:10的键值对形式加入到env的字典当中
其他：(操作类型操作数操作数操作数…)，于是先用proc保存操作类型，然后用args表保存后面所有的操作数，再调用proc(*args)将所有的参数传递进去后调用

举几个例子

>>> code = '(+ 4 (+ 5 6))'
>>> eval(parse(code))
15

>>> code = '(define x 123)'
>>> eval(parse(code))
123

还是用上面两个个例子，首先第一个

>>> code = '(+ 4 (+ 5 6))'
>>> eval(parse(code))
15

step1: parse后得到的结果是[’+’, 4, [’+’, 5, 6]]

step2: 然后开始eval, 第一次调用eval, 进入else部分，proc得到返回值为op.add，args为[4, eval([’+’, 5, 6])], step2暂停，进入step3

step3: 所以现在求eval([’+’, 5, 6]), 进入else部分，proc得到返回值为op.add, args为(5, 6)，传入op.add, 即调用op.add(5, 6)，返回11

step4: 所以step2继续，args为[4, 11], 传入op.add(4, 11), 所以返回15，即最后的结果

第二个例子

>>> code = '(define x 123)'
>>> eval(parse(code))
123

step1: parse得到的结果为[‘define’, ‘x’, 123]

step2: 然后开始eval, 第一次调用eval, 进入define分支，设置env[‘x’] = eval(123)，即env[‘x’] = 123, 宏定义结束

至此最初版的eval的示例就结束了。其实差不多相当于写了一个前缀表达式的计算器而已，不过对于初学者也颇有收益

下一节就做一个综合，把这个简单的’计算器’给讲完，然后我们继续在已有的这个小计算器的基础上进行扩展。

所有代码：

# eval

def eval(x, env = global_env):
	if isinstance(x, Symbol):
		return env.find(x)[x]

	elif not isinstance(x, list):
		return x

	elif x[0] == _quote:
		(_, exp) = x
		return exp
	
	elif x[0] == _if:
		(_, test, conseq, alt) = x
		exp = (conseq if eval(test ,env) else alt)
		return eval(exp, env)

	elif x[0] == _define:
		(_, var, exp) = x
		env[var] = eval(exp, env)

	else:
		proc = eval(x[0], env)
		args = [eval(arg, env) for arg in x[1:]]
		return proc(*args)

测试示例（也可以自行添加）：

['/', 5, 6]
['/', 5, ['+', 7, ['-', 9, 6]]]
['sqrt', 9]
['sin', ['+', 7, 8]]