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

咱们持续伯克利CS61A公开课之旅，这一次咱们做的是这门课的试验10。

这节试验课很有意思，它是Scheme project的根底试验课。在这节课上咱们将会用Python写一个简略的Python解说器，支持一些简略的变量界说、函数调用和lambda表达式。

整个试验的难度不高，但质量很不错，很有意思。算是为咱们了解程序的编译进程打下一个简略的根底，之前做Scheme解说器项目费劲的同学可以先做一下这个，再回过头做Scheme，会更简略上手许多。原本的课程安排也是这个次序。

课程链接

试验原始文档

我的Github

首先，咱们需求先去试验课的网站下载试验文件：

日拱一卒，伯克利CS61A，教你用Python写一个Python解释器

这一次的试验有一点点特殊，可能是由于间隔有一些久了，18年的试验内容傍边供给的ok有一些问题，运转的时分会报错。所以我去找了19年的材料作为替代，19年中的ok可以顺畅运转。

19年的这节试验课和18年大部分一样，只不过多了几道Scheme言语的练习题。我看了一下，这几道题许多咱们之前都做过相似的，所以本文还是基于18年的试验内容撰写的，19年课件中新增的标题大家感兴趣可以自己做做看。

日拱一卒，伯克利CS61A，教你用Python写一个Python解释器

Topics

Interpreters

解说器

解说器是一个程序，它允许你经过一个固定的编程言语和核算机进行交互。它能了解你输入的表达式，履行对应的行为得到成果。

在Project 4傍边，你将会运用Python编写一个Scheme的解说器。咱们这节课用的Python解说器中的绝大部分都是用C言语编写的。核算机本身运用硬件来解说机器码（一系列0和1代表根底的运转履行比方相加、从内存读取信息等）

当咱们议论解说器的时分，有两种言语在起作用：

  1. 被解说/被完成的言语，在这个试验傍边，你将会运用PyCombinator言语
  2. 底层完成的言语，在这个试验傍边，你将会运用Python来完成PyCombinator言语

留意，底层言语需求和被完成的言语不同。实践上，这节课咱们将会运用Python完成一个小版别的Python（PyCombinator）。这种idea被称为元循环评估。

实在国际傍边，需求解说器运用了Read-Eval-Print Loop（REPL）。这个循环会等候用户的输入，然后分三步履行：

  • Read：解说器获取用户的输入（一个string），而且将它传递给lexer 和 parser

    • lexer将用户的输入的字符串转化成atomic片段（tokens），就像已完成言语的“words”
    • parser接纳tokens而且将它们重新整理成底层运转的言语可以识别的数据结构

  • Eval：在eval和apply中交替递归evaluate表达式来取得一个只

    • Eval读入一个表达式并依据言语的规矩evaluate成果。Evaluate一个call表达式会需求调用apply来将一个现已evaluate得到的操作运用在它的操作数上
    • Apply接纳一个操作（函数），将它运用在call表达式的参数上。Apply也可以调用eval来做更多的工作，所以eval和apply相互递归得到成果

  • Print：展现用户输入evaluate之后的成果

下图展现这些模块之间是怎么协作的：

日拱一卒，伯克利CS61A，教你用Python写一个Python解释器

PyCombinator Interpreter

今日咱们来创建PyCombinator，咱们自己的Python根底解说器。在这次试验的结尾，你将会可以运用一系列primite比方add,mul和 sub（你可以在下方expr.py中看到完好的清单）。更令人兴奋的是，咱们还可以在你完成的解说器傍边创建和调用lambda函数。

你将会完成一些要害部分，让咱们可以evaluate下方的表达式：

日拱一卒，伯克利CS61A，教你用Python写一个Python解释器

你可以阅读repl.py中 Read-Eval-Print 循环的代码，下面是REPL组件的一个概述：

  • Read：reader.py中read函数调用了接下来的两个函数来对用户的输入做语法分析（parse）。

    • reader.py中tokenize函数用来做lexer（词法分析），将用户输入的字符串拆分成token
    • reader.py中read_expr函数对tokens做parse，转换成expr.py中Expr子类的实例

  • Eval：表达式（表明为Expr目标）被evaluate成合适的值（表明为Value目标，也在expr.py文件中）

    • Eval：每一个表达式类型都用它专属的eval办法，用来做evaluate
    • Apply：call表达式evaluate时会调用操作符（operator）的apply办法，并将它运用在传入的参数上。关于lambda表达式来说，apply会调用eval来先evaluate函数的主体

  • Print：调用value的__str__办法，将得到的内容打印出来

在这次试验傍边，你只需求完成expr.py中Eval和Apply过程。

你可以经过以下指令发动PyCombinator解说器：

python3 repl.py

试着输入数字或许lambda 表达式（比方lambda x, y: x + y）来观察evaluate之后的成果。

现在任何称号（比方add）以及call表达式比方（add(2, 3)）都会输出None。你需求完成Name.eval以及CallExpr.eval来让咱们能在解说器中够观察names和call表达式。

假如你想要更好地了解咱们的输入是怎么被读入以及转化成Python代码的，你可以在运转解说器的时分运用--read flag：

日拱一卒，伯克利CS61A，教你用Python写一个Python解释器

运用Ctrl-C或Ctrl-D退出解说器。

Required Questions

Q1: Prologue

序文

在咱们编写代码之前，让咱们来了解解说器傍边现已写好的部分。

下面是咱们完成的简介：

  • repl.py包括了REPL循环逻辑，它会重复从用户输入傍边读取表达式，evaluate它们，将它们的成果打印出来（你不需求彻底了解这个文件中的代码）
  • reader.py包括了咱们解说器的reader部分。函数read调用函数tokenize和read_expr来讲表达式字符串转化成Expr目标（你不需求彻底了解这些代码）
  • expr.py包括了咱们解说器对表达式和值的表明。Expr和Value的子类囊括了PyCombinator言语傍边一切表达式和值的类型。global环境是一个包括了一切pritimite函数绑定的字典。相同可以在文件的底部找到代码

运用ok指令来测验你对reader的了解，你可以一边参阅reader.py一边回答问题。

python3 ok -q prologue_reader -u

运用ok指令来测验你对Expr和Value的了解，你可以一边参阅expr.py一边回答问题。

python3 ok -q prologue_expr -u

Q2: Evaluating Names

咱们想要在PyCombinator中完成的第一个表达式类型是name。在咱们的程序傍边，name是一个Name类的实例。每一个实例具有一个string属性，它代表变量的称号。比方x。

之前咱们说过，变量名对应的值依赖于当时环境。在咱们的完成傍边，环境被表明成一个字典，它存储name（string）和它们值（Value类的实例）的映射。

Name.eval办法将当时环境作为参数env，返回环境中绑定在Name上的值。顺次完成以下逻辑：

  • 假如name存在在环境中，找到它的值并返回
  • 假如name不存在，抛出NameError反常，并供给合适的信息：
raise NameError('your error message here (a string)')

def eval(self, env):
    """
    >>> env = {
    ...     'a': Number(1),
    ...     'b': LambdaFunction([], Literal(0), {})
    ... }
    >>> Name('a').eval(env)
    Number(1)
    >>> Name('b').eval(env)
    LambdaFunction([], Literal(0), {})
    >>> try:
    ...     print(Name('c').eval(env))
    ... except NameError:
    ...     print('Exception raised!')
    Exception raised!
    """
    "*** YOUR CODE HERE ***"

运用ok指令进行测验：

python3 ok -q Name.eval

现在你完成了name的evaluate逻辑，你可以像是检查一些primitive函数一样检查变量了。你也可以试着检查一些没有界说的变量，看看NameError是怎么展现的。

日拱一卒，伯克利CS61A，教你用Python写一个Python解释器

但很遗憾，这些函数现在还只能看，不能用，接下来咱们会完成它们。

答案

def eval(self, env):
    if self.string in env:
        return env[self.string]
    raise NameError("The name: {} is not defined".format(self.string))

Q3: Evaluating Call Expressions

现在，让咱们为call表达式增加evaluate逻辑，比方add(2, 3)。记住，call表达式具有一个操作符和0或多个操作数。

在咱们的完成傍边，一个call表达式被表明成了CallExpr实例。每一个CallExpr实例都用operator和operands属性。operator是Expr的实例，由于每个call表达式可以具有多个操作数，所以operands是一个Expr实例的list。

比方在add(3, 4)对应的CallExpr中：

  • self.operator是Name('add')
  • self.operands是[Literal(3), Literal(4)]

在CallExpr.eval中，经过三个过程完成对call表达式的evaluate：

  1. 在当时环境中evaluate operator
  2. 在当时环境中evaluate operands
  3. 将operator得到的成果（是一个函数）运用在operands evaluate之后的成果上

提示：operator和operands都是Expr的实例，你可以调用它们的eval办法来evaluate它们。而且你可以经过调用函数的apply办法来运用一个函数（PrimitiveFunction或LambdaFunction的实例），它们接纳一个参数的list（Value实例）

def eval(self, env):
    """
    >>> from reader import read
    >>> new_env = global_env.copy()
    >>> new_env.update({'a': Number(1), 'b': Number(2)})
    >>> add = CallExpr(Name('add'), [Literal(3), Name('a')])
    >>> add.eval(new_env)
    Number(4)
    >>> new_env['a'] = Number(5)
    >>> add.eval(new_env)
    Number(8)
    >>> read('max(b, a, 4, -1)').eval(new_env)
    Number(5)
    >>> read('add(mul(3, 4), b)').eval(new_env)
    Number(14)
    """
    "*** YOUR CODE HERE ***"

运用ok指令来进行测验：

python3 ok -q CallExpr.eval

现在，你现已完成了evaluate call表达式的办法，咱们可以运用咱们的解说器来核算一些简略的表达式了，比方sub(3, 4)或许add(mul(4, 5), 4)。翻开你的解说器来做一些cool的运算。

答案

def eval(self, env):
    operator = self.operator.eval(env)
    operands = [op.eval(env) for op in self.operands]
    return operator.apply(operands)

Optional Questions

Q4: Applying Lambda Functions

咱们可以做一些根底的数学运算了，但假如咱们可以完成一些咱们自界说的函数这会更加风趣。

一个lambda函数被表明成LambdaFunction类的实例。假如你看一下LambdaFunction.__init__，你将会看到每一个lambda函数具有三个实例属性：parameters, body和parent。比方咱们看一个比方lambda f, x: f(x)。关于对应的LambdaFunction实例，咱们将会具有以下属性：

  • parameters——一个string的list，比方['f', 'x']
  • body——一个Expr，比方CallExpr(Name('f'), [Name('x')])
  • parent——一个咱们用来查找变量的parent环境，留意，这是lambda函数被界说时分的环境。LambdaFunction被创建在LambdaExpr.eval办法中，所以创建时的环境便是LambdaFunction的parent环境

假如你尝试输入lambda表达式，你将会看到它返回一个lambda函数。然而假如你想要调用一个lambda函数，比方(lambda x: x)(3)它会输出None。

你将要完成LambdaFunction.apply办法，这样咱们就可以调用咱们的lambda函数了。这个办法接纳一个arguments list，包括传递给函数的参数值。在evaluate lambda函数时，你需求保证lambda函数的formal parameter（形式参数）和实践入参可以对应。为了做到这一点，你需求修改你evaluate 函数body的环境。

运用LambdaFunction有三个过程：

  1. 制造parent环境的复制，关于字典d，你可以经过d.copy()获取复制
  2. 在复制傍边更新上LambdaFunction的参数以及传入办法的参数
  3. 运用新创建的环境evaluate body 
def apply(self, arguments):
    """
    >>> from reader import read
    >>> add_lambda = read('lambda x, y: add(x, y)').eval(global_env)
    >>> add_lambda.apply([Number(1), Number(2)])
    Number(3)
    >>> add_lambda.apply([Number(3), Number(4)])
    Number(7)
    >>> sub_lambda = read('lambda add: sub(10, add)').eval(global_env)
    >>> sub_lambda.apply([Number(8)])
    Number(2)
    >>> add_lambda.apply([Number(8), Number(10)]) # Make sure you made a copy of env
    Number(18)
    >>> read('(lambda x: lambda y: add(x, y))(3)(4)').eval(global_env)
    Number(7)
    >>> read('(lambda x: x(x))(lambda y: 4)').eval(global_env)
    Number(4)
    """
    if len(self.parameters) != len(arguments):
        raise TypeError("Cannot match parameters {} to arguments {}".format(
            comma_separated(self.parameters), comma_separated(arguments)))
    "*** YOUR CODE HERE ***"

运用ok进行测验：

python3 ok -q LambdaFunction.apply

当你完成之后，你可以尝试这个新特征。翻开你的解说器，尝试着创建和调用你自己的lambda函数。由于函数咱们解说器傍边的value，所以咱们可以尝试玩一下高阶函数：

$ python3 repl.py
> (lambda x: add(x, 3))(1)
4
> (lambda f, x: f(f(x)))(lambda y: mul(y, 2), 3)
12

答案

标题的描绘很长，但其实只要了解了其间的原理，完成本身并不杂乱。

其间关于函数形式参数和实践参数之间数量判别的部分教师现已替咱们做好了，咱们只需求将它们一一对应上，然后更新在环境的复制中，再调用body.eval得到成果即可。

def apply(self, arguments):
    if len(self.parameters) != len(arguments):
        raise TypeError("Cannot match parameters {} to arguments {}".format(
            comma_separated(self.parameters), comma_separated(arguments)))
        "*** YOUR CODE HERE ***"
        env = self.parent.copy()
        for k, v in zip(self.parameters, arguments):
            env[k] = v
        return self.body.eval(env)

Q5: Handling Exceptions

解说器看起来十分酷，看起来能用了对吗？但实践上还有一种情况咱们没有处理。你能想到一个简略的没有界说的核算吗？（比方说和除法相关）尝试着看看会发生什么，这很坑爹不是吗？咱们得到了一大串报错，而且退出了解说器。所以咱们希望可以优雅地handle这种情况。

试着再次翻开解说器，看看进行一些过错界说会发生什么，比方add(3, x)。咱们得到了一个简短的报错，告诉咱们x没有被界说，但咱们仍然可以持续运用解说器。这是由于咱们的代码handle了NameError反常，防止它让咱们的程序溃散。让咱们看看怎样handle反常：

在课上，你现已学过了怎么抛出反常。但捕获反常相同重要。咱们需求运用try/except句子块来捕获反常，而不是让它直接抛给用户而且导致程序溃散。

try:
    <try suite>
except <ExceptionType 0> as e:
    <except suite 0>
except <ExceptionType 1> as e:
    <except suite 1>
...

咱们在可能会抛出反常的句子<try suite>外面加上这个代码块。假如有反常被抛出，程序将会检查<except suite>找到抛出反常对应的类型。你可以具有许多except句子。

try:
    1 + 'hello'
except NameError as e:
    print('hi')  # NameError except suite
except TypeError as e:
    print('bye') # TypeError except suite

在上面的比方中，将1和hello做加法会抛出TypeError。Python将会寻觅可以handleTypeError的代码块，并找到了第二个except句子。通常，咱们想要履行咱们想要handle的反常的类型，比方OverflowError或许ZeroDivisionError（或两者都要），而不是handle一切的反常。

留意，咱们可以运用as e界说反常，这会将反常目标赋值给变量名e。这在咱们想要运用反常相关信息的时分会很有用。

>>> try:
...     x = int("cs61a rocks!")
... except ValueError as e:
...     print('Oops! That was no valid number.')
...     print('Error message:', e)

你可以看看repl.py中咱们handle反常的部分，这也是咱们处理核算中过错define反常的好地方。试试看吧！