日拱一卒，伯克利YYDS，用Python写一个Lisp解释器（三）
大家好，日拱一卒，我是梁唐。本文始发于公众号Coder梁
我们继续来肝伯克利CS61A的scheme project，这是这个project的第三篇，如果漏掉了之前的建议先去补一下。
在上一篇文章当中，我们进一步完善了scheme解释器的功能，让它能够支持自定义函数等许多功能。在这一篇文章当中，我们要继续完善功能，让我们的解释器能够支持更多语法。
Special Forms
整个项目到这里我们已经完成了基础的核心部分，接下来还要处理一些特殊的类型。
我们还有很多语法没有支持，比如逻辑运算符if,and, or, cond这些。这些表达式使用频率非常高，也非常重要。
在scheme当中，只有False才是假，所有其他的值都会被视为真，包括0和nil。你可以使用scheme_primitive.py文件中的scheme_truep和scheme_falsep函数来判断一个值是true还是false。
注意：scheme传统中使用#f来表示false，#t表示true。在我们的解释器当中true, True, #t均视为等价。然而在解锁测试数据时，需要使用#t和#f
我们提供了if语句的实现，do_if_form函数作为参考。确保你已经理解了if语句的原理，再进行下面的题目。
Problem 13
实现do_and_form和do_or_form函数来完成and和or表达式的支持。
对于and语句来说，你需要从左往右evaluate所有的表达式，如果遇到结果是false，那么返回#f。否则返回最后一个子语句的结果。如果输入的语句为空，也返回#t。
对于or语句来说，我们也需要从左往右评估每一个子语句的值。如果某一个子语句的结果是true，直接返回。否则返回#f。如果输入为空，也返回#f。
在开发之前，先答题解锁测试：
python3 ok -q 13 -u
开发之后，测试：
python3 ok -q 13
答案
这两个函数逻辑并不复杂，使用递归很容易搞定。
def do_and_form(expressions, env):
"""Evaluate a (short-circuited) and form."""
# BEGIN PROBLEM 13
"*** YOUR CODE HERE ***"
if expressions is nil:
return True
elif expressions.second is nil: # Tail context
return scheme_eval(expressions.first, env)
else:
first_expr = scheme_eval(expressions.first, env)
if scheme_falsep(first_expr): # The first expression is False
return False
elif scheme_truep(first_expr): # The first expression is True
return do_and_form(expressions.second, env)
# END PROBLEM 13
def do_or_form(expressions, env):
"""Evaluate a (short-circuited) or form."""
# BEGIN PROBLEM 13
"*** YOUR CODE HERE ***"
if expressions is nil:
return False
elif expressions.second is nil: # Tail context
return scheme_eval(expressions.first, env)
else:
first_expr = scheme_eval(expressions.first, env)
if scheme_falsep(first_expr): # The first expression is False
return do_or_form(expressions.second, env)
else: # The first expression is True
return first_expr
# END PROBLEM 13
Problem 14
完善do_cond_form函数，让他能够返回第一个为true的子语句的值，如果都为false，返回else语句的值。
然而存在一些特殊情况：
- 当判断为
true的值没有对应的返回结果，那么返回该值 - 当
cond语句的某一个分支中存在多个结果语句时，返回最后一个，提示，可以使用eval_all函数
你的代码需要能通过下列测试数据：
如果cond语句既没有为true的分支也没有else语句，那么返回None
编码之前，先回答问题解锁测试：
python3 ok -q 14 -u
编码之后，进行测试：
python3 ok -q 14
答案
整个函数的框架已经搭好了，函数内部使用了while循环来遍历所有的表达式，并且实现了else语句的部分。
test表示当前的语句是否是true，如果是真，那么返回test之后的内容。但由于题目中说了，有些情况只有判断条件，没有返回结果。这个时候就要返回判断条件的结果本身，也就是test。当然也有可能表达式有多个，这种情况使用eval_all函数返回最后一个表达式的结果即可。
如果test为假则继续往下执行其他条件。
def do_cond_form(expressions, env):
"""Evaluate a cond form."""
while expressions is not nil:
clause = expressions.first
check_form(clause, 1)
if clause.first == 'else':
test = True
if expressions.second != nil:
raise SchemeError('else must be last')
else:
test = scheme_eval(clause.first, env)
if scheme_truep(test):
# BEGIN PROBLEM 14
"*** YOUR CODE HERE ***"
if clause.second == nil:
return test
return eval_all(clause.second, env)
# END PROBLEM 14
expressions = expressions.second
Problem 15
let特殊类型，它会在本地绑定symbol和value，但是这个绑定只会在原地生效，比如这个例子：
(let ((x 42) (y (* x 10))) (list x y))语句当中，绑定y时用到的x是全局的值，也就是5，而不是刚刚绑定的42。因为绑定值的操作是最后一起执行的，x和y是一起绑定的。有一点类似于以下的Python代码：
x = 5
x, y = 42, x * 10
实现make_let_frame方法，它会返回一个当前env的子frame，在这个frame当中，将symbol绑定到对应的value上。bindings scheme list包含一系列pairs，其中每一个包含一个symbol和对应的表达式。
你可能会用到下面这些函数：
check_form：这个函数用来检查binding结构check_formals：这个函数检查formal参数，确保每一个symbol都是不同的make_child_frame：这个函数（你在11题中开发的），它接收一个Pair表示formal，一个Pair表示value。返回一个绑定了formal和value的新frame
在你编码之前，先回答问题解锁测试样例：
python3 ok -q 15 -u
编码之后，进行测试：
python3 ok -q 15
答案
只要搞清楚了let语句是先评估，评估完了之后一起绑定的，这题就算是搞定了一大半。
但坑爹的是，原文的题意当中没有明确地指出这一点，这是要我们基于老师给的问题和一些描述去自己分析和推理的。所以我当时做这题的时候，还是费了一些周折。
def make_let_frame(bindings, env):
"""Create a child frame of ENV that contains the definitions given in
BINDINGS. The Scheme list BINDINGS must have the form of a proper bindings
list in a let expression: each item must be a list containing a symbol
and a Scheme expression."""
if not scheme_listp(bindings):
raise SchemeError('bad bindings list in let form')
# BEGIN PROBLEM 15
"*** YOUR CODE HERE ***"
formals, args = nil, nil
while bindings is not nil:
check_form(bindings.first, 2, 2)
formals = Pair(bindings.first.first, formals)
args = Pair(scheme_eval(bindings.first.second.first, env), args)
bindings = bindings.second
check_formals(formals)
return env.make_child_frame(formals, args)
# END PROBLEM 15
Problem 16
实现do_mu_form函数来评估特殊类型mu，mu不是一种标准的scheme表达式类型。
mu表达式类似于lambda表达式，但不同的是，当evaluate mu语句时，它是动态scope的。lambda表达式是静态scope，因为lambda表达式执行的时候，使用的env 是lambda创建时的frame。而mu使用的是表达式执行时的frame，因此是动态的。
mu表达式通过MuProcedure类实现，大部分代码已经开发好了。
完善MuProcedure类，当它被调用的时候，它依赖的外部frame是动态的，也正因此，MuProcedure类中不需要存储frame实例。
下面是一个mu表达式的例子：
编码之前，先回答问题确保理解正确：
python3 ok -q 16 -u
编码完成之后，进行测试：
python3 ok -q 16
答案
我们看下mu表达式的使用方法，其实它和lambda的语法是一样的。所以do_mu_form和do_lambda_form的逻辑也是一样的。
def do_mu_form(expressions, env):
"""Evaluate a mu form."""
check_form(expressions, 2)
formals = expressions.first
check_formals(formals)
# BEGIN PROBLEM 16
"*** YOUR CODE HERE ***"
return MuProcedure(formals, expressions.second)
# END PROBLEM 16
唯一的区别就是运行时的env，lambda是静态的，而mu是动态的。
看起来好像很复杂，但仔细思考会发现这两个在实现里的区别其实很小。只有创建子frame的时候有一些区别，lambda表达式创建运行时的frame用的是自身实例中存储的env，这样就能保证不论什么时候运行lambda，使用的都是创建时的frame。
而mu是动态的，从类的定义中我们也可以看出来，它没有env这个实例属性。那么我们在创建子frame的时候用的就不是本身存储的env，而是外界传入的。外界传入的env是在运行时传入的，这样就可以保证了，mu运行时依赖的外部变量是动态的。
代码只有一行，但理清楚这里面的逻辑却不简单。
class MuProcedure(Procedure):
"""A procedure defined by a mu expression, which has dynamic scope.
_________________
< Scheme is cool! >
-----------------
\ ^__^
\ (oo)\_______
(__)\ )\/\
||----w |
|| ||
"""
def __init__(self, formals, body):
"""A procedure with formal parameter list FORMALS (a Scheme list) and
Scheme list BODY as its definition."""
self.formals = formals
self.body = body
# BEGIN PROBLEM 16
"*** YOUR CODE HERE ***"
def make_call_frame(self, args, env):
return env.make_child_frame(self.formals, args)
# END PROBLEM 16
def __str__(self):
return str(Pair('mu', Pair(self.formals, self.body)))
def __repr__(self):
return 'MuProcedure({0}, {1})'.format(
repr(self.formals), repr(self.body))
到这里，整个scheme的解释器就算是完成了。
但解释器除了要支持解释执行scheme代码之外，其实还有很多其他的内容。在附加题当中，老师给我们留了两个非常困难的问题：尾递归和尾递归的运行优化。
这部分内容比较困难，而且涉及到更多的知识，因此我们单独成篇，放在之后的文章当中和大家分享。
转载自:https://juejin.cn/post/7095991018645880840