PLisp: 集成在Python中的LISP语言实现 (1)

tyxiayu

看了一点LISP的书，猛然觉得，LISP的原理很简单。LISP里面只有1种数据结构：Symbolic Expression，简称sexp。程序本身也是sexp，处理的数据也是sexp。也就是，如果你能解释用sexp写成的程序，你就制成了LISP解释器。
LISP里面，sexp分为两种：表和原子。list（表），内部有序地包含0个或多个sexp。除此之外，其他东西都是atom（原子），比如symbol（符号，类似“标识符”）, 数字，字符串，布尔值等。例外是nil，既是表（空表）又是原子。
LISP的执行，就是sexp的求值（evaluation）过程。求值规则如下：
- 非符号的原子，解释为其本身。
- 符号，解释为其在符号表中对应的值。符号表是一个“符号->值”的对应表。
- 表，将其第一个元素求值，得到一个函数，将其他元素求值，作为这个函数的参数。然后调用函数，返回值作为这个表的值。（如果函数是特殊函数，则参数先不求值，即“按名传递”；一般函数，参数先求值，即“按值传递”）

下面，我要利用Python实现一种LISP方言。
我不想写解析器（parser），因为Python本身已经提供了足够的数据结构。Python中有list数据结构（数组），类似LISP中的表。Python字符串看成symbol也可以。其他的数据类型可以都作为普通的原子。
于是，我们可以用Python表达式：

["+", ["*", 3, 4], ['*', 5, 6]]

表示LISP的表达式：

(+ (* 3 4) (5 6))


又如，Python表达式：

["let",
[['x', 2],
['y', 3]],
['*', x, y]]

表示LISP的表达式：

(let
((x 2)
(y 3))
(* x y))


解释的过程，就可以写成一个Python函数，输入一个Python表达式，输出另一个Python表达式。中间可以用副作用来处理IO。

如何实现呢？
首先，求值需要一个符号表，这个任何语言都一样，记录变量（或者LISP的符号）对应的值。而LISP的符号表会随着求值的过程（副作用）而改变。

class Context(UserDict):
def __init__(self, parent=None):
UserDict.__init__(self)
self.parent = parent

Context类表示一个符号表，或者说LISP求值的“上下文”。Context只不过是一个dict而已，输入符号，对应到值。这个parent稍候解释，因为context可以嵌套。
然后，每个LISP函数都可以用Python函数表示。定义为由“上下文和参数的笛卡尔积”到python值的映射。简而言之，每个LISP函数对应的Python函数，除了“普通参数”以外，还要Context作为额外的参数。比如：

def add(context, one, another):
return one + another
# ['+', 1, 2] calls this function and evaluates to 3

这个函数和符号表无关，不读取符号表，也不改变符号表。
又如：

def _set(context, key, value):
context[key] = value
return value
# ['set', 'x', 40] calls this function and sets symbol 'x' to 40

这是一个“赋值函数”，通过修改符号表，将符号key的对应于value的值。
而

def _print(context, expr):
print expr
return expr
# ['print', ['quote', 'hello world!']] calls this function and prints "hello world!" to standard output

这个完全依赖求值的副作用，打印输出。
函数的基本形式就是这样。
基本的LISP执行环境需要几个基本的LISP函数。最基本的当然是eval函数了。LISP中，eval的功能是将一个表达式求值。我定义Python函数_eval，为了避免和内置函数eval命名冲突。

def _eval(context, expr): # 输入expr，求expr的值
if isinstance(expr, str): # 对于符号，查找符号表获得值
cur_context = context
# 因为符号表可以嵌套，所以迭代查找。
while cur_context is not None:
if expr in cur_context:
return cur_context[expr]
else:
cur_context = cur_context.parent
raise KeyError(expr)
elif isinstance(expr, list): # 对于表，转换成函数调用。
first, rest = expr[0], expr[1:]
func = _eval(context, first) # 递归对第一个元素求值，得到函数。
if getattr(func,"call_by_name",False)==False: # 处理特殊函数。
evrest = [_eval(context, e) for e in rest]
else:
evrest = rest
return func(context, *evrest) # 调用函数，得到返回值
else:
return expr # 对于其他原子，返回其本身。

正好分3个分支，处理了LISP求值的3种情况。
上述代码提到了“特殊函数”。一般的函数，调用前，要将参数求值，再传入。如：

(+ (- 9 3) 4)

必须先求出(- 9 3)的值：6，才能传入"+"函数。
但是，另外一些函数需要“按名传递”，即根据某些条件，选择性地求值。如：

(if (eq (+ 1 1) 2) right wrong)

if函数是条件函数。先求第一个参数的值，如果是真，则求第二个参数的值，第三个参数不求值；如果是假，求第三个参数的值，第二个参数不动。
因此，对于这些特殊的LISP函数，需要在Python函数上做一些标记。我的做法是，在定义函数后，给这些函数设置其call_by_name的值为True。或者用@decorator更简单。
典型的if函数，定义如下：

@call_by_name
def _if(context, condition, iftrue, iffalse=None):
if _eval(context, condition):
return _eval(context, iftrue)
else:
return _eval(context, iffalse)

@call_by_name内部完成call_by_name=True的赋值工作。而函数体内部，先用_eval函数求第一个参数的值，对于真假两种情况，分别调用两个分支。
另一个典型的“按名传递”的函数是quote，这个函数避免其内部的符号被求值。LISP中：

(quote abc)
'abc

两者求值都得到符号abc。由于quote如此常用，因此LISP中有特殊的引号'语法，方便quote函数的应用。
在Python中：

@call_by_name
def quote(context, expr):
return expr
def q(expr):
return ['quote',expr]

quote函数不对expr求值，而直接返回expr。我还定义了Python函数q，类似LISP的'，方便书写。
有了以上基本函数，其实可以编一些简单的程序了。以下是一个演示。

# 首先，使用之前，要实例化一个Context对象：
default_context = Context()
# 然后，将基本函数加入这个符号表
default_context["eval"] = _eval
default_context["print"] = _print
default_context["quote"] = quote
default_context["set"] = set
default_context["+"] = add
# 最后，用eval函数求值即可。
# 这是Hello world
_eval(default_context, ["print", q("Hello world!")])
# 屏幕上显示Hello world!
# 赋值语句
_eval(default_context, ["set", q("x"), 5])
# 改变符号表，"x"对应整数5。
# 计算简单的加法
result = _eval(default_context, ["+", ["+", 1, "x"], 3])
print result
# 输出9


总结：
通过以上程序，可以看出，这种实现，输入是完全合法的Python表达式，输出也是Python表达式。求值仅仅是用Python语言做了Python表达式的处理而已。
根据目前定义的函数，这个“语言”功能还非常简单；但是，下篇将引入更多函数，使得这个“语言”逐渐趋近于功能完备的程序设计语言。