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

上文我构造了一个简单的Python版Symbolic Expression解释器。可以解释由Python的list, str以及其他数据类型构成的表达式。

我们可以用"set"函数赋值，用"+","-"等函数进行简单的计算，用"if"函数进行条件判断，并用"print"函数输出。例如：

["set", q("x"), 1] # 将"x"赋值为1。注意，q(expr)是['quote',expr]的简写。

['+', ["-", 3, 2], 5] # (3-2)+5

["print", q("Hello world!")] # 输出"Hello world!"

这一篇将补充更多的函数，以使得这一“语言”更加完整。

首先补充"setq"函数。因为赋值函数"set"大多数需要将第一个参数（变量名）"quote"起来，避免求值。因此我们让"setq"不要自动求变量名的值。

# 函数定义：
@call_by_name
def setq(context, key, value):
    context[key]=_eval(context,value)
    return value

# 用例：
["set", q("x"), 5]
["setq", "x", 5] # 和上一个表达式效果相同。

看到，与set不同，setq用@call_by_name标记要求按名传入；而在内部，将value求值。


LISP语言中，整个程序是一系列的表，被按顺序一个一个地求值。它也允许顺序结构。这里，我定义"begin"函数，作为“顺序结构”。

# 函数定义：
@call_by_name
def begin(context, *exprs):
    rv = None
    for expr in exprs:
        rv = _eval(context, expr)
    return rv

# 用例：
[“begin",
  ["set", q("x"), 3],
  ["set", q("y"), ["+", "x", 5]],
  ["print", y],
]

"begin"函数取任意多个参数。求值时，会按顺序求出每个参数的值，返回最后一个参数的值，其他参数返回值将被忽略。

有了这个"begin"函数，我们可以把整个程序写在一整个大list中。可以看出，“begin”这个单词只是“语法糖”的作用，让人有“程序开始”，或者“块开始”的感觉，类似Pascal语言那样。


现在我们通过“begin”拥有了一种流程控制：基本的“顺序结构”。我们已经有"if"函数做条件判断。但是，目前我们没有定义“关系表达式”，因此"if"也无用武之地。下面定义"=="和"<"函数。这仅仅是Python的==和<运算符的简单封装。

# 函数定义：
@dc("==") # 别名
def equal(context, expr1, expr2):
    return expr1==expr2

@dc("<")
def less_than(context, expr1, expr2):
    return expr1<expr2

# 用例：
[“print",
  ["if", ["==", ["+", 3, 5], 8],
    "It is all right.",
    "Hey! There must be something wrong!"
  ]
]

由于LISP是一种函数式语言，实际应用中一般用递归而不是循环。因此这里暂时没有实现。但实现循环结构是很容易的。

"let"函数允许用户定义局部变量。如LISP语言：

(let
    ((a 1) (b 2))
    (+ a b)
)

第一个参数是符号绑定；返回值是最后一个参数的值。这里的a,b只在let中有效，而在let之外是无效的。我们可以认为，let定义了“局部变量”。

我们可以使用嵌套的符号表（即Context类，见上文）实现局部变量。回顾Context对象中有一个“parent”域，表示其“上级”。而eval函数中，符号求值是层级式的查找，先在本层符号表中找变量，如果没有，则到上一层寻找。我们可以这样定义"let"函数：

# 函数定义：
@call_by_name
def let(context, bindings, expr):
    new_context = Context(context)

    for k,v in bindings:
        evv = _eval(new_context, v)
        new_context[k] = evv

    return _eval(new_context, expr)

# 用例：
["let",
    [["a", 1], ["b", 2]]
    ["+", "a", "b"]
]

"let"函数的工作原理是，先创建一个新的符号表，并将上层符号表设为当前符号表。第一个参数包含多个变量的绑定，这被在新的上下文中求值，并保存在新的符号表中，这相当于一系列的"setq"函数。最后，将第二个参数在新上下文中求值，并返回。

新的上下文本身并没有被特意保留。


下面介绍"lambda"函数，允许用户定义自己的函数。

首先需要回答一个问题：什么是函数。

数学家肯定会回答，函数就是从定义域到值域的映射关系。给定定义域中的元素作为参数，必然有且只有一个值与其对应。但是，这是LISP语言，毕竟不是纯粹的数学。我们如何用sexp和求值来定义“函数”呢？

我们可以这样定义“函数”：函数就是一个部分绑定的表达式。

那么，什么是“部分绑定“？注意到["setq", "x", 5]的效果是将符号表中"x"的值设定为5。我们也可以认为，这个表达式将5与符号"x"绑定。绑定的时间是在这个表达式被求值的时候。同样，["let", [["x",5]], ["+","x",1]],可以认为，在"let"的内部，"x"与5是绑定的。

我们再观察一个Python函数：

a = 7
def myfunc(x):
    return a + x

foo(9) # 返回16
foo(10) # 返回17

我们可以发现，函数myfunc中，引用了两个变量：a和x。其中，a的值在函数myfunc被定义的时候，就已经被绑定为7了。但是，变量x，迟迟要到foo函数被调用的时候，才被绑定。第一次调用myfunc(9)的时候，x被绑定为9；第二次x被绑定为10。我们也可以说，在myfunc函数定义的时候，符号a是“绑定”的，符号x是“自由”的。

同样的函数，我们可以在LISP中用"lambda"函数定义。

(setq a 7)
(setq myfunc (lambda (x) (+ a x))) ; 定义函数。x是参数，(+ a x)是函数体。
(myfunc 9)  ; 调用函数
(myfunc 10) ; 调用函数

通过以上观察，我们可以定义：LISP函数由两部分组成：
第一部分，是形式参数表。它是一个表，包含一系列变量名（即“符号”），表示函数体中的“自由”变量。
第二部分，是一个表达式，即“函数体”。它在函数定义时定义，但在函数被“调用”时，才“求值”。

lambda和let不同，let的“体”在"let"函数被求值时就求值了；而lambda函数调用时，仅仅返回一个新的函数，而函数体并不立即求值。这里，lambda函数的返回值被赋给myfunc，而myfunc被调用时，函数体才被求值。

我们首先用一个Python对象表示一个函数。

class LambdaExpression(object):
    def __init__(self, defining_context, params, expr):
        self.defining_context = defining_context
        self.params = params
        self.expr = expr

    def __call__(self, calling_context, *args):
        new_context = Context(self.defining_context)

        for k,v in zip(self.params, args):
            new_context[k] = v

        return _eval(new_context, self.expr)

可以看出，函数被定义时，记录了形式参数表（params），以及函数体（expr）。执行时，利用传入的实际参数，使得自由的形式参数被绑定为实际参数。

也许你会注意到，函数体是在函数定义时的上下文中被求值的，而调用时的上下文完全没有利用。这关系到“静态作用域”和“动态作用域”的区别。目前这种选择是“静态作用域”。详细情况以后介绍。

我们定义"lambda"函数，用于在LISP中创建LambdaExpression对象实例。

# 函数定义
@dc("lambda")
@call_by_name
def _lambda(defining_context, params, expr):
    return LambdaExpression(defining_context, params, expr)

# 用例
["begin",
  ["setq", "a", 7],
  ["setq", "myfunc", ["lambda", ["x"], ["+", "a", "x"]]],
  ["myfunc", 9],
  ["myfunc", 10],
]

当"lambda"函数被求值时，一个新的LambdaExpression对象被赋给"myfunc"。

需要注意的是，当"let"与"lambda"嵌套使用时，"lambda"的返回值会保留其被定义时的上下文，即"let"创建的上下文。这个上下文会在每次这个LambdaExpression被调用时利用。

["begin
  ["setq", "myfunc",
    ["let", [["a", 7]],
      ["lambda", ["x"], ["+", "a", "x"]]
    ]
  ],
  ["myfunc", 9], # 值为16
  ["myfunc", 10] # 值为17
]

注意到，"let"函数中的变量"a"仅仅在"let"之内有效，但是，却随着"let"定义的Context，被保存到"myfunc"对应的LambdaExpression对象中。因此，当调用["myfunc", 9]的时候，函数体内的"a"仍然能在"myfunc"的defining_context中找到。

一旦有了lambda函数和足够的基本函数，用户就可以自己定义自己的函数了。

下面，继续定义一系列常用的函数。

这些是表处理函数，处理list数据。

# cons函数，将first前置到rest列表的前端。
# 事实上，LISP一般用“广义表”，一种链表实现，所以经常用cons构造链表。这里只是为了方便。
@dc()
def cons(context, first, rest):
    return [first]+rest
# 例如 ["cons", 1, q([2,3,4,5])] -> [1,2,3,4,5]

# first取第一个元素。有的LISP方言中也叫CAR，Haskell中称为head。
@dc("first","car","head")
def first(context, lst):
    return lst[0]
# 例如 ['first', q([1,2,3,4,5])] -> 1

# rest取“除了第一个以外，其余的元素”。有的LISP方言中也叫CDR，Haskell中称为tail。
@dc("rest","cdr","tail")
def rest(context, lst):
    return lst[1:]
# 例如 ['rest', q([1,2,3,4,5])] -> [2,3,4,5]

# concat连接若干个表
@dc()
def concat(context, lists):
    result_list = []
    for lst in lists:
        result_list.extend(lst)
    return result_list
# 例如 ['concat', q([[1], [2,3,4], [5,6]])] -> [1,2,3,4,5,6]

# append只是提供方便，连接所有的参数，每个参数都是一个表。
@dc()
def append(context, *lists):
    return concat(context, lists)
# 例如 ['append', q([1]), q([2,3,4]), q([5,6])] -> [1,2,3,4,5,6]

另一个IO函数：read。

"read"函数，这是Python函数input()的简单绑定，求值时，从键盘读取一个Python表达式。
@dc("read")
def _read(context):
    return input()

下面定义一些“高阶函数”。“高阶函数”是函数式编程的重要概念。它取另一个函数作为参数。没错，在函数式编程中，函数就是头等公民，可以像变量一样被传入和返回。

事实上，Python已经提供了内置的filter,map和reduce三个高阶函数。这里只是它们的简单封装。

@dc("filter")
def _filter(context, predicate, lst):
    return filter(lambda elem: predicate(context, elem), lst)

@dc("map")
def _map(context, func, lst):
    return map(lambda elem: func(context, elem), lst)

@dc("reduce")
def _reduce(context, func, lst):
    return reduce(lambda lhs,rhs: func(context, lhs, rhs), lst)

# partition和filter类似。它返回一个列表，里面有两个元素。第一个是满足某个条件的，和filter返回的一样；第二个则是不满足该条件的，即filter的返回值的相反的部分。
@dc()
def partition(context, predicate, lst):
    return [_filter(context, predicate, lst),
            _filter(context, lambda ctx,x: not predicate(ctx,x), lst)]

最后，展示一个用PLisp编写的“快速排序”算法。

['begin',
        # 先定义"qsort"函数。
        ['setq', 'qsort', ['lambda', ['lst'], ['if',
            ['null', 'lst'], 'lst', # 空表快速排序是本身
            ['let',
                [
                    ['pivot', ['first', 'lst']], # 取首元素为轴
                    ['others', ['rest', 'lst']],
                    ['parts', ['partition', # 把元素分割成两部分
                        ['lambda', ['x'], ['<', 'x', 'pivot']], 'others']],
                    ['left', ['first', 'parts']], # 左边比轴大
                    ['right', ['first', ['rest', 'parts']]], ＃ 右边比轴小
                    ],
                ['append', # 左右两边各自递归排序，并串接。
                    ['qsort','left'], ['list', 'pivot'], ['qsort', 'right']]
                ]
            ]]],
        ['print', q("How many?")],
        ['setq', 'n', ['read']], # 用户输入数据的个数
        ['setq', 'readn', ['lambda', ['to-read'], # 定义readn函数：读取n个数，返回一个由这些数构成的列表。
            ['if', ['==', 'to-read', 0], q([]),
                ['cons', ['read'], ['readn', ['-', 'to-read', 1]]]]]],
        ['setq', 'numbers', ['readn', 'n']], # 读数
        ['print', 'numbers'], # 输出原列表
        ['print', ['qsort','numbers']], # 排序并输出
        ]

运行过程：

引用

How many?
5
1
5
2
4
3
[1, 5, 2, 4, 3]
[1, 2, 3, 4, 5]