日拱一卒，伯克利太有创意了，用Python解释Python

TechFlow-承志

发布于 2022-09-21 11:48:42

6270

发布于 2022-09-21 11:48:42

文章被收录于专栏：TechFlowTechFlow

作者 | 梁唐

出品 | 公众号：Coder梁（ID：Coder_LT）

大家好，日拱一卒，我是梁唐。

我们继续伯克利CS61A公开课之旅，这一次我们做的是这门课的实验10。

这节实验课很有意思，它是Scheme project的基础实验课。在这节课上我们将会用Python写一个简单的Python解释器，支持一些简单的变量定义、函数调用和lambda表达式。

整个实验的难度不高，但质量很不错，很有意思。算是为我们理解程序的编译过程打下一个简单的基础，之前做Scheme解释器项目吃力的同学可以先做一下这个，再回过头做Scheme，会更容易上手很多。原本的课程安排也是这个顺序。

公开课视频链接：https://www.bilibili.com/video/BV16W411W76H

实验资料：https://inst.eecs.berkeley.edu//~cs61a/sp19/lab/lab10/

整个实验课的完整代码我也放在了GitHub上，可以点击「阅读原文」跳转。

首先，我们需要先去实验课的网站下载实验文件：

这一次的实验有一点点特殊，可能是因为间隔有一些久了，18年的实验内容当中提供的ok有一些问题，运行的时候会报错。所以我去找了19年的资料作为代替，19年中的ok可以顺利运行。

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

Topics

Interpreters

解释器

解释器是一个程序，它允许你通过一个固定的编程语言和计算机进行交互。它能理解你输入的表达式，执行对应的行为得到结果。

在Project 4当中，你将会使用Python编写一个Scheme的解释器。我们这节课用的Python解释器中的绝大部分都是用C语言编写的。计算机本身使用硬件来解释机器码（一系列0和1代表基础的运行执行比如相加、从内存读取信息等）

当我们谈论解释器的时候，有两种语言在起作用：

被解释/被实现的语言，在这个实验当中，你将会使用PyCombinator语言
底层实现的语言，在这个实验当中，你将会使用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之后的结果

下图展示这些模块之间是如何协作的：

PyCombinator Interpreter

今天我们来创建PyCombinator，我们自己的Python基础解释器。在这次实验的末尾，你将会能够使用一系列primite比如add,mul和 sub（你可以在下方expr.py中看到完整的清单）。更令人兴奋的是，我们还能够在你实现的解释器当中创建和调用lambda函数。

你将会实现一些关键部分，让我们能够evaluate下方的表达式：

你可以阅读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：

使用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是如何展示的。

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

答案

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：

在当前环境中evaluate operator
在当前环境中evaluate operands
将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有三个步骤：

制作parent环境的拷贝，对于字典d，你可以通过d.copy()获取拷贝
在拷贝当中更新上LambdaFunction的参数以及传入方法的参数
使用新创建的环境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异常的好地方。试试看吧！

喜欢本文的话不要忘记三连~

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2022-05-14，如有侵权请联系 cloudcommunity@tencent.com 删除

serverless

python

r 语言

本文分享自 Coder梁微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

serverless

python

r 语言

登录后参与评论

0 条评论

热度