日拱一卒，伯克利YYDS，用Python写一个Lisp解释器（五）

大家好，日拱一卒，我是梁唐。本文始发于公众号Code梁

我们继续来肝伯克利CS61A的scheme project，今天我们来聊最后一个部分，附加题部分。

虽然附加题只有两道题，但是要想把这两道题说清楚并不简单，所以特地预留了完整一篇文章的篇幅来详细阐述。

课程链接

项目原始文档

Github

我们先来看题：

Problem 20

完成scheme.py文件中的函数optimize_tail_calls，它会返回scheme_eval函数的替代品。使得我们的解释器能够支持尾递归。

Thunk类表示需要在frame当中评估的表达式。当scheme_optimized_eval受到一个非atomic表达式时，它会返回Thunk类的实例。否则的话，它会一直调用original_scheme_eval函数，直到函数返回值是一个确定的值，而不是Thunk。

一个成功的实现需要修改之前的一些代码，包括已经提供给的源代码。所有尾递归的调用scheme_eval时需要额外传入一个True作为第三个参数，你的目标是决定什么样的表达式计算能够使用尾递归优化。

当你完成开发之后，你需要打开下面这行代码的注释：

scheme_eval = optimize_tail_calls(scheme_eval)

当你完成之后，进行测试：

python3 ok -q 20

答案

我估计如果是没有看过相关课程视频的同学看到这里会觉得云里雾里，不知道尾递归是什么。

尾递归是递归场景当中的一个优化场景，比如下面这个例子：

同样是计算阶乘，上面的方式使用的是递归，下面的方式使用的是迭代。它们的时间复杂度是一样的，都是O(n)。

问题在于空间复杂度，使用递归实现的空间复杂度也是线性的，而下面迭代的方式需要的空间是常数级的。为什么会有这么大的差别呢？是因为我们在进行递归的时候，每一次递归的时候都会创建新的环境frame来存储环境变量。每递归深一层，就需要多创建些变量。

在这个例子当中，我们每次递归的时候都会创建n, k两个值，一共最多递归n层， 那么需要创建的变量数就是O(n)。

但如果我们仔细思考，会发现，其实没有必要。因为我们直接返回的就是下一层递归的结果factorial(n-1, k * n)。在我们调用递归的时候，参数已经传递进去了，递归返回的时候也不依赖任何环境变量。所以我们在递归调用完成的时候，其实就没有必要保留当前的frame了。

也就是说对于factorial函数来说，当我们调用它自身的时候，n, k这两个参数就已经完成了使命。在之后的递归执行过程当中，都不再需要它们了，那么它们也就没有继续存储的必要了。在递归调用之后，就可以释放了。

因此加上这个优化之后，可以将尾递归的空间复杂度进行减小，尾递归优化就指的这种。

很明显，尾递归优化是有条件的，最大的条件就是递归当中不能有变量的依赖，也可以理解成递归是函数返回之前最后一步操作。比如还是计算阶乘，我们稍微修改一下，改成这样：

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n-1)

虽然是类似的逻辑，但这就不是尾递归了，原因也很简单，因为递归不再是返回之前执行的最后一个步骤了，它还多了一个* n的步骤。既然要* n，那么我们就需要存储下这个n的值，也就是说有了存储依赖，那么就不能进行优化了。

其实scheme_optimized_eval函数的逻辑本身并不复杂，代码框架老师都已经搭好，我们只需要照着题意实现即可。

class Thunk:
    """An expression EXPR to be evaluated in environment ENV."""
    def __init__(self, expr, env):
        self.expr = expr
        self.env = env

def optimize_tail_calls(original_scheme_eval):
    """Return a properly tail recursive version of an eval function."""
    def optimized_eval(expr, env, tail=False):
        """Evaluate Scheme expression EXPR in environment ENV. If TAIL,
        return a Thunk containing an expression for further evaluation.
        """
        if tail and not scheme_symbolp(expr) and not self_evaluating(expr):
            return Thunk(expr, env)
        else:
            result = Thunk(expr, env)
        # BEGIN
        "*** YOUR CODE HERE ***"
        while (isinstance(result, Thunk)):
            result = original_scheme_eval(result.expr, result.env)
        return result
        # END
    return optimized_eval

返回Thunk的意思是，返回中间结果，而非创建递归调用的环境进行递归。虽然我们创建了Thunk实例，但是传入的都是已经有的对象的引用，所以并不会带来过大的空间消耗，可以近似于看成是线性的开销。

比较复杂的地方在于尾递归的判断， 我们需要找到能够进行尾递归的地方，将它的函数调用额外增加一个参数True。

大概有这么几处，我列举在下面：

• eval_all函数
• do_if_form函数
• do_and_form函数
• do_or_form函数
• Promise类
• do_cons_steam_form类

只要理解了尾递归的原理，代码就水到渠成了。

Problem 21

macros允许语言本身被用户拓展，简单的macros可以被define-macro特殊类型实现。不过必须以定义过程的形式执行，它也会创建一个过程，就像是define一样。然而这个过程拥有一个特殊的的evaluate规则：它先应用参数，而不是先evaluate参数，再evaluate结果。

最终的评估过程在被调用的frame当中，就好像macro的返回值被粘贴到代码当中替代macro一样。可以参考一下例子：

上面的代码定义了一个macro叫做for，它运行的逻辑有些像是map，但它不需要lambda关键字。它将(* i i)这个计算逻辑应用在(1 2 3)这个list上。

为了实现define-macro，完善函数do_define_macro，它会创建一个MacroProcedure的实例，并且将它绑定在do_define_form中传入的name上。最后，更新一下scheme_eval函数，让他能够支持macro语法。

提示：

使用MacroProcedure类中的apply_macro函数，将macro应用在表达式的操作数上

测试你的代码：

python3 ok -q 21

答案

我们观察一下macro表达式的组成，它当中有两个部分一个是定义部分，一个是逻辑部分，简单缩写大概是这样的格式：(define-macro (macro-name formals) (body))。

我们对照一下上面这个简写版本，不难找到定义函数的所有部分。接着我们调用MacProcedure的构造函数创建实例再绑定在env上即可。

def do_define_macro(expressions, env):
    """Evaluate a define-macro form."""
    # BEGIN Problem 21
    "*** YOUR CODE HERE ***"
    check_form(expressions, 2)
    target = expressions.first
    if isinstance(target, Pair) and scheme_symbolp(target.first):
        func_name = target.first
        formals = target.second
        body = expressions.second
        env.define(func_name, MacroProcedure(formals, body, env))
        return func_name
    else:
        raise SchemeError('invalid use of macro')
    # END Problem 21

接下来是关于macro表达式的执行，我们观察代码会发现，它继承于LambdaProcedure，也就是说它也是一种特殊的lambda语句。唯一在调用的方式上有所不同，是以一种类似于map的方式调用的。

根据提示我们需要实现MacroProcedure类中的apply_macro方法。根据macro表达式的工作原理，其实逻辑非常简单，调用complete_apply函数很简单就可以实现。

但complete_apply并不在题意的提示里，需要我们自己阅读代码发现，所以还是挺有难度的。

def complete_apply(procedure, args, env):
    """Apply procedure to args in env; ensure the result is not a Thunk."""
    val = scheme_apply(procedure, args, env)
    if isinstance(val, Thunk):
        return scheme_eval(val.expr, val.env)
    else:
        return val
    
class MacroProcedure(LambdaProcedure):
    """A macro: a special form that operates on its unevaluated operands to
    create an expression that is evaluated in place of a call."""

    def apply_macro(self, operands, env):
        """Apply this macro to the operand expressions."""
        return complete_apply(self, operands, env)

虽然只有两道附加题，但不难看出，难度还是不低的。相比于之前定义清楚的问题，这两题更加灵活，考察的范围也更大，能完完整整地把这两题做好，绝对可以说是真正地理解了scheme解释器的运行原理了。不仅是scheme，其实对于其他编程语言的编译、运行过程，也有了一个管中窥豹的效果，可以说是非常值得的。

好了，到这里，整个scheme解释器的project就算是肝完了，怎么样，有没有觉得收获满满非常有意义呢？