作者 | 梁唐
出品 | 公众号：Coder梁（ID：Coder_LT）
大家好，日拱一卒，我是梁唐。
我们继续来肝伯克利CS61A的scheme project，这是这个project的第二篇，如果漏掉了之前的建议先去补一下。
原始文档：https://inst.eecs.berkeley.edu/~cs61a/sp18/proj/scheme/#interpreter-details
在上一篇文章当中我们实现了将scheme代码转化成Python实现以及scheme中的一些核心功能，在这一篇文章当中我们要进一步完善功能，使得我们的解释器能够支持用户自定义过程。
User-Defined Procedures
用户自定义过程可以被表达为LambdaProcedure类的实例。
LambdaProcedure实例中包含三个实例属性：
formals是一个scheme list，对应的是过程当中的参数名（字符串类型）body也是一个scheme表达式的list，对应过程的逻辑主体env对应过程定义时的frame
Problem 8
修改eval_all函数（它会被do_begin_form函数调用），让它完善支持begin格式数据。
begin表达式执行时会顺序执行所有的子语句，begin表达式的结果是最优一个子语句运行的值，如：
如果eval_all接收的参数是nil，那么返回Python中的None，代表未定义的scheme值。
在你开发之前，先测试确保你对问题的理解：
代码语言：javascript复制python3 ok -q 08 -u完成之后进行测试：
代码语言：javascript复制python3 ok -q 08答案
eval_all函数是在begin语句调用的，会返回最后一个自语句的结果。
所以我们要做的就是判断当前的表达式是否是最后一项，我们可以利用递归来搞定。如果expressions.second是nil，那么说明expressions就是最后一项，返回它evaluate的结果，否则进行递归。
def eval_all(expressions, env):
"""Evaluate each expression im the Scheme list EXPRESSIONS in
environment ENV and return the value of the last."""
# BEGIN PROBLEM 8
if expressions == nil:
return None
elif expressions.second is nil: # Tail context
return scheme_eval(expressions.first, env, True)
else:
scheme_eval(expressions.first, env)
return eval_all(expressions.second, env)
# END PROBLEM 8
Problem 9
实现do_lambda_form函数，它能够创建LambdaProcedure实例。
你现在还不能调用一个用户自定义的过程，你可以通过输入lambda表达式进入解释器验证创建过程。
在Scheme中，在过程的主体当中放置多个表达式是合法的。body属性是LambdaProcedure类的实例属性，LambdaProcedure实例中的body属性是一个scheme list，表示过程主体。
在开始编码之前，先测试一下对题目的理解：
代码语言：javascript复制python3 ok -q 09 -u
完成之后，进行测试：
代码语言：javascript复制python3 ok -q 09
答案
这道题只需要我们能够创建LambdaProduce实例，并不需要我们实现调用的部分。
因此很简单，看懂每一个参数代表的意义之后，调用LambdaProduce构造函数即可。
def do_lambda_form(expressions, env):
"""Evaluate a lambda form."""
check_form(expressions, 2)
formals = expressions.first
check_formals(formals)
# BEGIN PROBLEM 9
"*** YOUR CODE HERE ***"
return LambdaProcedure(formals, expressions.second, env)
# END PROBLEM 9
Problem 10
目前，我们的define功能可以将名称绑定到自定义过程了：
但是我们希望能用更简洁的形式来表达：
修改do_define_form函数，让它能够对于缩写版本的自定义过程也能支持。确保，它能够搞定多表达式的情况。
在编码之前，先确保题意理解正确：
代码语言：javascript复制python3 ok -q 10 -u
编码之后，进行测试：
代码语言：javascript复制python3 ok -q 10
通过define创建的自定义过程，本质上是LambdaProcedure的实例
答案
我们观察一下输入，对于自定义过程而言，它define的具体内容是一个表达式而非一个symbol。
即，对于我们的do_define_form函数而言，当它传入的expressions.first是一个Pair而非一个symbol的时候，说明这是在定义自定义过程。
这个过程的名称是expressions.first.first，它的传参是expressions.first.second。它的运算主体是expressions.second。
这题的逻辑不难，可能比较困难的是上面这三个变量的路径。我们可以代入一个样例来看：(define (square x) (* x x))，对于这个例子，do_define_form函数接收到的表达式是((square x)(*x x))。
expressions.first也是一个scheme list，它是(square x)，而自定义过程的主体部分自然就是expressions.second。有一个具体的例子之后，逻辑会好梳理很多。
def do_define_form(expressions, env):
"""Evaluate a define form."""
check_form(expressions, 2)
target = expressions.first
if scheme_symbolp(target):
check_form(expressions, 2, 2)
# BEGIN PROBLEM 6
"*** YOUR CODE HERE ***"
env.define(target, scheme_eval(expressions.second.first, env))
return target
# END PROBLEM 6
elif isinstance(target, Pair) and scheme_symbolp(target.first):
# BEGIN PROBLEM 10
"*** YOUR CODE HERE ***"
name = target.first
env.define(name, LambdaProcedure(target.second, expressions.second, env))
return name
# END PROBLEM 10
else:
bad_target = target.first if isinstance(target, Pair) else target
raise SchemeError('non-symbol: {0}'.format(bad_target))
Problem 11
实现Frame类中的make_child_frame方法：
- 将
self作为parent创建新的Frame实例（已经提供） - 如果变量的数量和值的数量对不上，那么抛出
SchemeError异常 - 将变量和对应的值绑定在新创建的
Frame上
编码之前先进行测试，确保理解正确
代码语言：javascript复制python3 ok -q 11 -u
编码之后，测试：
代码语言：javascript复制python3 ok -q 11
答案
我们看下make_child_frame的函数签名，它接收两个参数分别是formals和vals，代表我们要绑定的变量名和值。
所以我们在这里并不需要关心变量名和对应的值是怎么处理的，我们只需要将它们绑定即可。绑定的方法也非常简单，就是存储到self.bindings当中。
我们要做的就只有两件事，第一件事是判断formals和vals的长度是否相等，这有专门的函数可以使用。
第二件事是遍历formals和vals，但它们一一绑定。
class Frame:
"""An environment frame binds Scheme symbols to Scheme values."""
def __init__(self, parent):
"""An empty frame with parent frame PARENT (which may be None)."""
self.bindings = {}
self.parent = parent
def __repr__(self):
if self.parent is None:
return '<Global Frame>'
s = sorted(['{0}: {1}'.format(k, v) for k, v in self.bindings.items()])
return '<{{{0}}} -> {1}>'.format(', '.join(s), repr(self.parent))
def define(self, symbol, value):
"""Define Scheme SYMBOL to have VALUE."""
# BEGIN PROBLEM 3
"*** YOUR CODE HERE ***"
self.bindings[symbol] = value
# END PROBLEM 3
def lookup(self, symbol):
"""Return the value bound to SYMBOL. Errors if SYMBOL is not found."""
# BEGIN PROBLEM 3
"*** YOUR CODE HERE ***"
if symbol in self.bindings:
return self.bindings[symbol]
if self.parent is not None:
return self.parent.lookup(symbol)
# END PROBLEM 3
raise SchemeError('unknown identifier: {0}'.format(symbol))
def make_child_frame(self, formals, vals):
child = Frame(self) # Create a new child with self as the parent
# BEGIN PROBLEM 11
"*** YOUR CODE HERE ***"
if scheme_length(formals) != scheme_length(vals):
raise SchemeError('Term amount unmatch with formals and vals')
for _ in range(scheme_length(formals)):
formal = formals.first
val = vals.first
child.define(formal, val)
formals = formals.second
vals = vals.second
# END PROBLEM 11
return child
Problem 12
实现LambdaProcedure类中的make_call_frame方法，这个方法会被scheme_apply方法调用。
它会选择合适的parent frame调用make_child_frame创建一个新的Frame实例，绑定函数入参和对应的值。
lambda函数是lexically scoped，这个概念我也不知道怎么翻译。意思是说lambda函数运行时的frame是labmda函数创建时frame的子frame。
我们要使用env中的make_call_frame函数创建子frame，而非直接使用env。
在你开始编码之前，先回答问题：
代码语言：javascript复制python3 ok -q 12 -u
开发完成之后，进行测试：
代码语言：javascript复制python3 ok -q 12
当这题完成之后，你的scheme解释器应该有如下功能：
- 通过
lambda表达式创建新的过程 - 通过
define表达式定义变量和过程 - 调用创建的自定义过程
答案
这道题不难，因为make_child_frame我们之前已经开发好了，直接调用它返回新的frame即可。
class LambdaProcedure(Procedure):
"""A procedure defined by a lambda expression or a define form."""
def __init__(self, formals, body, env):
self.formals = formals
self.body = body
self.env = env
def make_call_frame(self, args, env):
"""Make a frame that binds my formal parameters to ARGS, a Scheme list
of values, for a lexically-scoped call evaluated in environment ENV."""
# BEGIN PROBLEM 12
"*** YOUR CODE HERE ***"
return self.env.make_child_frame(self.formals, args)
# END PROBLEM 12
def __str__(self):
return str(Pair('lambda', Pair(self.formals, self.body)))
def __repr__(self):
return 'LambdaProcedure({0}, {1}, {2})'.format(
repr(self.formals), repr(self.body), repr(self.env))
我们遵循着题目一题一题做下来，也没有很费力就搞定了解释器的基本功能。但是我们只是完成了题目要求的功能，而对于整个项目结构和代码设计的理解其实还不够深入。
我个人建议大家不能仅仅满足于搞定题目，这个项目是非常值得我们学习的，当中的原理也需要我们深入挖掘。
大家不妨试着回答一下这个问题：
我们只是实现了定义frame和创建lambda表达式，但是没有针对lambda式调用时候的结果做特殊的处理。那么当我们执行lambda表达式的时候，它是怎么计算出答案的？
好了，scheme解释器这个项目我们先聊到这里，还有一些功能没有完成，将会放到下一篇文章当中，欢迎大家继续关注。
喜欢本文的话不要忘记三连~
