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

站长

2024年06月13日 21:51 · 阅读数 57

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

我们继续来肝伯克利CS61A，今天看的是这门课最后一个project，非常干货非常硬核。

我们要写一个Lisp语言的解释器，代码量不算很大，但很考验思维，20道题我足足爆肝了10个小时才做完。个人感觉比当年《编译原理》最后的课程设计还要硬核。做完之后，会对代码的编译/解释过程有一个相对比较深刻的理解。

课程链接

项目原始文档

Github

由于这个project的内容非常多，如果放在一篇文章里实在是太长，因此会分成几个部分连续更新，如果感兴趣请持续关注。

Scheme 解释器读入Scheme语句，evaluate它们的值，再打印出来。和Python解释器类似：

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

老师提供的框架代码当中已经支持了单个运算符的计算，如上图当中，我们输入2可以返回2。但对于下面两种计算还不支持，需要我们完成。

Scheme的各种方言对于符号都比较宽容，我们要实现的解释器中的变量不仅支持大写和小写字母，还支持这些符号：!$%&*/:<=>?@^_~-+.

项目结构

整个项目以Read-Eval-Print的流程执行，即读入-运算-输出。在开始编码之前，请先阅读下列说明：

Read: 这一步骤将用户的输入（字符串形式）转换成解释器内部的类型（Python中的Pair类）
- Lexical analysis 词法分析：这一步骤已经完成，在scheme_tokens.py文件的tokenize_lines函数当中。这个函数返回一个Buffer（在buffer.py中）。你可以忽略这部分代码
- Syntactic analysis 句法分析：这个过程发生在scheme_reader.py文件的scheme_read和read_tail函数。这两个函数将Scheme语句转化成Python内部表示，这两个函数需要实现
Eval：这个步骤计算Scheme语句的值，这部分代码在scheme.py文件中
- Eval 发生在scheme_eval函数中，如果是特殊形式的表达式，会调用对应的do_?_form函数。你将会实现scheme_eval函数和do_?_form函数的部分代码
- Apply 发生在scheme_apply函数中，scheme_apply调用primitive类的apply方法，或者在evaluate用户定义的过程时创建新的frame(environment)。在这个例子当中，apply方法调用eval_all方法，eval_all方法又会调用scheme_eval方法，它们之间互相递归调用。如果你看不懂这段说明，不需要纠结，直接看代码会更清晰
Print: 这个步骤会调用结果的__str__函数输出结果
Loop: 这个步骤会调用scheme.py文件中的read_eval_print_loop函数，你可以忽略这部分代码

Exceptions 当你开发Scheme解释器的时候，你会发现Python本身在执行Scheme语句的时候会抛出各种异常，并且导致解释器中断。这些异常当中有一些可能是由于你程序的bug，也有一些是用户编写的Scheme语句有误。对于用户语句中的bug，需要handle这些异常，并且抛出SchemeError。

所有的SchemeError异常需要被handle，并且被scheme.py中的read_eval_print_loop函数打印出来。理想情况下，解释器中不应该出现无法被handle的异常。

运行解释器

使用如下命令运行：

python3 scheme.py

如果你想要测试已经写好的scheme代码，可以将代码放入.scm文件中，以如下命令运行：

python3 scheme.py tests.scm

目前的代码可以处理简单的表达式，比如：

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

可以使用Ctrl + D或者exit语句退出解释器：

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

Part I: The Reader

项目的第一个部分处理读入和转换用户的输入，我们的Reader将会将Scheme代码转换成Python代码表达，具体内容可以参考下表：

Input Example	Scheme Data Type	Our Internal Representation
scm> 1	Numbers	Python's built-in int and float values
scm> x	Symbols	Python's built-in string values
scm> #t	Booleans (#t, #f)	Python's built-in True, False values
scm> (+ 2 3)	Pairs	Instances of the Pair class, defined in scheme_reader.py
scm> nil	nil	The nil object, defined in scheme_reader.py

在我们的实现当中，我们已经将用户的读入转化成了Buffer的实例。比如说，(+ (2 . 3))的输入转化成的buffer会包含以下token(,+,(,2,.,3,),)。你可以阅读buffer.py代码中的注释获得更多细节，如果看不懂也可以忽略这个部分的代码。

你需要实现scheme_read和read_tail这两个互相递归的函数。这两个函数有相同的输入src，它是一个Buffer类的实例。buffer.py文件中定义了关于src的两个函数，你将会用到它们：

src.remove_front()：删除src的第一个token并返回。比如[4, '.', 3, ')']，调用remove_front函数之后将会返回4，剩余的src为['.', 3, ')']。
src.current()：返回src的第一个token，但不会删除。

Problem 1

首先，实现scheme_read和read_tail函数，它们可以用来转换list表达式和primitive表达式。我们需要注意Problem2中带有.的pair。这两个函数的机制如下：

scheme_read函数从src中移出足够数量的token组成单一的scheme表达式，并且将表达式转换成内部的结构（参考上表）
read_tail读入list或者pair中剩余的内容，我们可以假设list或者pair中的左括号已经被scheme_read删除了。它将会读入右括号前的所有的内容。表达式将会以嵌套Pair实例的形式返回

简单来说，scheme_read返回buffer中的下一个完整的scheme语句，read_tail返回buffer或者list中剩余的部分组成的语句。这两个方法都会修改buffer，删除已经处理过的token。

两个函数的逻辑依赖于src中的第一个token，参考如下：

scheme_read:

如果当前token是字符串nil，返回nil对象
如果当前token是(，当前表达式是一个pair或list。调用read_tail函数获取src中剩余的内容，返回read_tail的结果
如果当前token是'，buffer中剩余的部分将会被视为一个quote语句。你可以在Problem 7之前先忽略
如果下一个token不是一个delimiter（分隔符），那么它一定是一个self-evaluating，这个词很难翻译，可以理解成它本身就是结果，比如数字、变量名等，这种情况可以直接返回
如果上面几种情况都不满足，抛出异常（已经实现）

read_tail:

如果已经没有token，说明缺少)，抛出异常（已经实现）
如果token是)，说明已经到达语句的末尾。删除token，并且返回nil对象
如果token是'.', 说明当前的表达式是一个带点的pair，在Problem 2中处理它
If the token is ., the current expression is a dotted pair. Implement this in Problem 2.
如果上面几种情况都没有出现，说明src是一个表达式的开头，执行以下逻辑：
- 读入buffer中下一个完整的表达式（提示：你应该调用哪个方法获取完整的表达式？）
- 读入原表达式剩余的部分，直到遇到)，（提示：你应该调用哪个方法读入剩余表达式？）
- 将结果以Pair实例的形式返回

在你开始编码之前，测试一下你是否已经理解了题意：

python3 ok -q 01 -u

开发完成之后测试：

python3 ok -q 01

解答

代码的结构和上面说明的部分几乎是完全匹配的，如果实在没法理解这两个函数的原理，照着上面的说明实现即可。

scheme_read函数中几乎没有难点，read_tail函数最后的else分支可能稍微有点困难。我们返回的结果是Pair(scheme_read(src), read_tail(src))，这是一个经典的递归结构。

前文说了，else分支表示我们读到了一个新的表达式的开头。所以我们要调用scheme_read(src)获取下一个完整的表达式。

为什么之后还要调用一下read_tail呢？是因为scheme的表达式是有嵌套的。比如说：(define (f x y) (+ x y))，我们在read_tail中遇到了(f x y)语句的左括号，这是一个子语句的开头。我们调用scheme_read可以读到紧跟着的完整语句，即(f x y)，但是这个语句只是完整语句的一个部分。剩下的内容(+ x y))是define语句的剩余部分，之后紧跟着调用read_tail正是为了获取类似这种情况的剩余部分。

scheme_read中会调用read_tail，而read_tail又会调用scheme_read。这就是为什么说明中会特地提到，这是两个互相递归调用的函数。

对于新手来说觉得有些难以理解是正常的，毕竟这是伯克利的高强度project，强如地表顶级的名校伯克利也有很多同学被它难住。如果觉得困难，可以先编码，再反复思考加深理解。

def scheme_read(src):
    """Read the next expression from SRC, a Buffer of tokens.
    
    >>> scheme_read(Buffer(tokenize_lines(['nil'])))
    nil
    >>> scheme_read(Buffer(tokenize_lines(['1'])))
    1
    >>> scheme_read(Buffer(tokenize_lines(['true'])))
    True
    >>> scheme_read(Buffer(tokenize_lines(['(+ 1 2)'])))
    Pair('+', Pair(1, Pair(2, nil)))
    """
    if src.current() is None:
        raise EOFError
        val = src.remove_front() # Get the first token
        if val == 'nil':
            # BEGIN PROBLEM 1
            "*** YOUR CODE HERE ***"
            return nil
        # END PROBLEM 1
    elif val == '(':
        # BEGIN PROBLEM 1
        "*** YOUR CODE HERE ***"
        return read_tail(src)
    # END PROBLEM 1
elif val == "'":
    # BEGIN PROBLEM 7
    "*** YOUR CODE HERE ***"
    # END PROBLEM 7
elif val not in DELIMITERS:
    return val
else:
    raise SyntaxError('unexpected token: {0}'.format(val))
    
    def read_tail(src):
        """Return the remainder of a list in SRC, starting before an element or ).
        
        >>> read_tail(Buffer(tokenize_lines([')'])))
        nil
        >>> read_tail(Buffer(tokenize_lines(['2 3)'])))
        Pair(2, Pair(3, nil))
        >>> read_line('(1 . 2)')
        Pair(1, 2)
        """
        try:
            if src.current() is None:
                raise SyntaxError('unexpected end of file')
            elif src.current() == ')':
                # BEGIN PROBLEM 1
                "*** YOUR CODE HERE ***"
                src.remove_front()
                return nil
            # END PROBLEM 1
        elif src.current() == '.':
            # BEGIN PROBLEM 2
            "*** YOUR CODE HERE ***"
            # END PROBLEM 2
        else:
            # BEGIN PROBLEM 1
            "*** YOUR CODE HERE ***"
            return Pair(scheme_read(src), read_tail(src))
        # END PROBLEM 1
    except EOFError:
        raise SyntaxError('unexpected end of file')

Problem 2

现在，完善read_tail函数，加入支持dotted pair的代码。我们来回顾一下dotted pair的定义：

scheme中的list是有Pair的嵌套来表达的。list中最后一个pair的second 属性是nil。比如说(1 2 3)使用Pair表示就是Pair(1, Pair(2, Pair(3, nil)))
当最后一个pair的second属性不为nil时会显示一个点，比如(1 2 . 3)Python表示就是Pair(1, Pair(2, 3))

当scheme_read读入(1 2 .3)调用read_tail时，此时的src为1 2 . 3)。最外层的Pair中的两个元素分别是1和一个内侧的Pair，内侧的Pair拥有的两个值是2和3。由于它是list中的最后一个pair，并且不以nil结尾，所以两个元素中间会出现一个.

此时read_tail需要返回Pair(1, Pair(2, 3))

dotted pair的.后面只能有一个元素，否则的话就是syntax error。你需要完善read_tail函数代码，判断.的后面只能有一个元素，否则的话抛出SyntaxError，不要忘了移除右括号。

提示：

为了判断.后面是否只有一个元素，读取.之后的表达式，检查它们的下一个token是不是右括号

在你开始编码之前先回答问题确保题意理解正确

python3 ok -q 02 -u

开发完成之后进行测试：

python3 ok -q 02

解答

这道题不难，题目中已经说得非常清楚了。我们只需要在出现.的时候，判断下一个元素的后一位是否是)即可。如果不是)，抛出异常，否则返回。

代码为# BEGIN PROBLEM 2注释中间的部分。

def read_tail(src):
    try:
        if src.current() is None:
            raise SyntaxError('unexpected end of file')
        elif src.current() == ')':
            # BEGIN PROBLEM 1
            "*** YOUR CODE HERE ***"
            src.remove_front()
            return nil
        # END PROBLEM 1
    elif src.current() == '.':
        # BEGIN PROBLEM 2
        "*** YOUR CODE HERE ***"
        src.remove_front()
        val = scheme_read(src)
        if src.remove_front() != ')':
            raise SyntaxError('unexpected .')
            return val
        # END PROBLEM 2
    else:
        # BEGIN PROBLEM 1
        "*** YOUR CODE HERE ***"
        return Pair(scheme_read(src), read_tail(src))
    # END PROBLEM 1
except EOFError:
        raise SyntaxError('unexpected end of file')

现在已经开发完了parser的部分，执行以下代码进行测试，确保通过所有测试样例：

python3-mdoctestscheme_reader.py-v

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

Part II: The Evaluator

接下来我们要开发第二个部分Evaluator，即进行运算的核心逻辑。

这个部分一共有14题，分量非常大，因此这一篇文章当中只会包含这部分的第一个模块Core Functionality。剩下的两个模块将放在下一篇文章当中。

在目前的代码当中，我们的evaluator只能运算self-evaluating表达式：数字、boolean和nil。

阅读scheme.py文件中Eval/Apply和Environment两个部分。

scheme_eval会在给定的env当中计算Scheme表达式的结果。这个函数接近完善，只缺失了调用表达式的逻辑
当计算一些特殊形式的表达式时，scheme_eval会调用scheme.py中对应的do_xxx_form的函数
scheme_apply将一个过程应用在一些参数上，这个函数已经完成了
执行内置和用户自定义的过程时，会用到Procedure类中的.apply函数和make_call_frame函数
Frame类实现了一个环境帧（存储函数调用时需要的变量）
LambdaProcedure类代表用户自定义过程

这些就是解释器需要用到的模块，scheme.py文件中剩下的部分定义了一些特殊形式和输入输出的处理。

在开始编码之前，检测一下对于各个模块的理解，通过了才能开启eval_apply中的测试数据

python3 ok -q eval_apply -u

Problem 3

实现Frame类中的define和loopup方法。每一个Frame对象拥有以下属性，Frame可以理解成方法栈。在函数调用时，入参、外部环境变量等信息均存在Frame当中。

bindings：这是一个字典，用来存储frame中绑定的值。存储scheme 符号（symbol表示成Python中的字符串）和scheme值的映射
parent：parent Frame，即当前frame的父frame，全局的frame的parent为None

define函数输入一个symbol和value，将value和symbol绑定在对应的frame上

lookup函数输入一个symbol，返回frame上绑定的值。如果当前frame中找不到symbol，则去父frame中寻找，如果父frame中依然没有，则继续往上追溯，一直到全局frame。如果依然没有找到，抛出SchemeError，如果中途找到，返回最先找到的绑定值

在开发代码之前，先完成测试解锁测试数据：

python3 ok -q 03 -u python3 ok -q 03

开发完成之后，进行测试：

python3 ok -q 03

当完成这个部分的开发之后，你的解释器将能够访问到一些内置的过程，如：

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

不过目前还只是访问，想要能够调用这些过程，还需要我们继续开发。

解答

理解了Frame的作用，这两个函数还是挺容易实现的。

define尤其简单，已经给定了symbol和value，我们只需要将它们的映射关系存储在字典当中即可。

lookup需要我们先判断symbol是否在当前的frame中，如果存在，直接返回。如果不存在，判断父frame是否为空，如果为空，抛出异常，如果不为空，递归调用即可。

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))

Problem 4

想要调用primitive 过程例如+,-这些，需要我们实现PrimitiveProcedure类中的apply方法。

Primitive 过程会调用Python中对应的实现，比如说Scheme中+这个过程会调用Python中的add方法。

scheme_primitives.py文件当中已经替我们开发好了一系列Scheme primitive过程。所有加上了@primitive注解的函数，都会被添加进全局的PRIMITIVES列表当中，并且被绑定进global frame。

PrimitiveProcedure类拥有两个实例属性：

fn是一个Python函数，对应scheme的一个primitive过程，比如add函数对应scheme里的+
use_env是一个bool类型的标记，表示这个primitive过程是否需要用到当前的frame作为参数。

PrimitiveProducedure中的apply方法接收一个list的参数和当前的环境。注意这里的args参数是一个Scheme中的list，在Python中以Pair对象的形式存储。你的代码需要包含以下功能：

将scheme list转化成Python list（已经实现）
如果self.use_env是True，将当前的环境env作为Python list中的最后一个参数
调用self.fn函数，使用*args作为传参
如果调用函数的过程当中抛出了TypeError异常，说明传入的参数错误。使用try/expcept代码块来捕获异常，并且抛出合适的SchemeError异常作为提示

在开始编码之前，使用如下命令进行答题，并解锁测试样例：

python3 ok -q 04 -u

完成之后，进行测试：

python3 ok -q 04

解答

这道题几乎没有难度，其实就是根据self.use_env判断是否要把env作为self.fn的传参。如果为True就要用作参数，否则不用。

注意一下self.fn调用的过程可能会有异常抛出，所以要加上try/except代码块，进行异常捕获。

class PrimitiveProcedure(Procedure):
    """A Scheme procedure defined as a Python function."""

    def __init__(self, fn, use_env=False, name='primitive'):
        self.name = name
        self.fn = fn
        self.use_env = use_env

    def __str__(self):
        return '#[{0}]'.format(self.name)

    def apply(self, args, env):
        """Apply SELF to ARGS in ENV, where ARGS is a Scheme list.

        >>> env = create_global_frame()
        >>> plus = env.bindings['+']
        >>> twos = Pair(2, Pair(2, nil))
        >>> plus.apply(twos, env)
        4
        """
        if not scheme_listp(args):
            raise SchemeError('arguments are not in a list: {0}'.format(args))
        # Convert a Scheme list to a Python list
        python_args = []
        while args is not nil:
            python_args.append(args.first)
            args = args.second
        # BEGIN PROBLEM 4
        "*** YOUR CODE HERE ***"
        try:
            if self.use_env:
                return self.fn(*python_args, env)
            return self.fn(*python_args)
        except Exception as e:
            raise SchemeError('arguments are not valid, {}'.format(e))
        # END PROBLEM 4

Problem 5

scheme_eval接收一个scheme 表达式和一个环境frame，计算出scheme 表达式的结果。

scheme_eval函数大部分内容都已经实现了，它现在可以在当前frame中查找变量、返回self-evaluating表达式以及处理一些特殊的类型。

你需要实现scheme_eval函数中缺失的部分，实现调用表达式，包括：

评估operator（Procedure类的实例）
评估参数
将过程应用在评估出的参数上

你需要在前两个步骤当中递归调用scheme_eval，除此之外还有一些其他的函数你可能会用到：

check_procedure函数，当输入的参数不是一个scheme过程时会报错。你可以用它来检查你的operator是不是一个scheme过程
Pair类中的map函数，它接收一个函数作为参数，并且能够将它应用在它的所有元素中
scheme_apply函数，它可以将一个scheme过程应用在参数上

在开始编码之前，先进行测试，确保理解正确

python3 ok -q 05 -u

编码完成之后，进行测试：

python3 ok -q 05

解答

对于lisp语言来说，它的operator是写在最前面的。并且scheme_eval函数拿到的参数已经被处理成了Pair实例。也就是说已经去除掉了括号这些标记符号，所以我们直接调用expr.first拿到的就是operator，不过要注意，expr.first拿到的只是它的名称。

比如(+2 2)这个表达式，我们拿到的expr.first只是+，而add函数才是我们想要的。这个函数需要我们从env这个frame当中获取，好在题目当中已经提示我们了，可以使用递归进行获取。

为什么一定要用递归，而不是再调用一次env.lookup呢？因为expr.first也可能是一个嵌套的表达式，这种情况就没办法通过env.loopup获取了。所以一定要递归。

递归拿到operator之后，调用check_procedure进行检查，确保它是一个合法的过程。

下一步要评估operator的参数，也就是expr当中剩下的内容。评估的方法很简单，就是递归调用scheme_eval函数。

最后这些都搞定了，调用scheme_apply函数传入operator和参数以及env即可。

def scheme_eval(expr, env, _=None): # Optional third argument is ignored
    """Evaluate Scheme expression EXPR in environment ENV.

    >>> expr = read_line('(+ 2 2)')
    >>> expr
    Pair('+', Pair(2, Pair(2, nil)))
    >>> scheme_eval(expr, create_global_frame())
    4
    """
    # Evaluate atoms
    if scheme_symbolp(expr):
        return env.lookup(expr)
    elif self_evaluating(expr):
        return expr

    # All non-atomic expressions are lists (combinations)
    if not scheme_listp(expr):
        raise SchemeError('malformed list: {0}'.format(repl_str(expr)))
    first, rest = expr.first, expr.second
    if scheme_symbolp(first) and first in SPECIAL_FORMS:
        return SPECIAL_FORMS[first](rest, env)
    else:
        # BEGIN PROBLEM 5
        "*** YOUR CODE HERE ***"
        operator = scheme_eval(first, env)
        check_procedure(operator)

        scheme_cur = rest.map(lambda x: scheme_eval(x, env))
        return scheme_apply(operator, scheme_cur, env)
        # END PROBLEM 5

Problem 6

接下来我们将要实现define功能，简单回顾一下define功能，它是scheme中一个特殊的类型，可以用来定义变量和过程：

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

define这个operator的第一个参数表示了它的类型：

如果第一个参数是symbol，比如a，那么它定义的是一个变量
如果第一个参数是一个list，比如(foo x)，那么它定义的是一个过程

在开发之前，你可以先复习一下define关键字的功能，在本问题当中，只需要实现能够绑定值的功能，无需实现绑定函数的功能。

在do_define_form函数当中有两个缺失的部分，本题只需要实现第一部分，即绑定symbol和对应的值，不需要创建新的过程。

do_define_form需要返回完成绑定的变量名：

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

在开始编码之前，先进行测试，确保理解正确

python3 ok -q 06 -u

编码之后进行测试：

python3 ok -q 06

当你完成之后，你的解释器已经可以进行简单的变量定义和运算了：

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

解答

这题拐了一个弯，前面在第三题当中，我们给frame类创建了define功能，让它支持绑定变量，这题我们就需要用到define函数。

因为define的变量并不是凭空保存的，而是要作为运行时的环境变量存储的。运行时的环境变量存放在了frame当中。把这个理清楚了，代码就很好写了。我们要做的就是把变量名和对应的值存起来，这里要注意的是，值并不一定是一个数值，也可能是一个表达式。比如(define x (+2 2))，所以绑定之前要先调用scheme_eval函数进行评估。

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 ***"
        # END PROBLEM 10
    else:
        bad_target = target.first if isinstance(target, Pair) else target
        raise SchemeError('non-symbol: {0}'.format(bad_target))

Problem 7

我们已经完成了大部分核心功能，只剩下了quote表达式。

在scheme当中，quote表达式有两种写法，一种是直接使用quote关键字，还有一种是使用符号'。我们来简单复习一下：

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

quote表达式会将之后的内容原封不动的输出，我们先来实现quote表达式，实现do_quote_form函数，让它可以输出评估之前的内容。

当你完成了之后，你的解释器应当可以支持quote关键字：

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

接着完善scheme_reader.py中的scheme_read函数，让它能够支持'。首先，' <expression>需要被转义成(quote <expression>)。注意，你需要使用递归来完成转换。

比如' bagel应该被转义成Pair('quote', Pair('bagel', nil))

当完成这个部分之后，你的解释器应当支持下列用法：

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

在你开始编码之前，先确保理解准确：

python3 ok -q 07 -u

编码完成之后，进行测试：

python3 ok -q 07

解答

先是第一部分，非常简单，直接将表达式原封不动地返回即可

def do_quote_form(expressions, env):
    """Evaluate a quote form."""
    check_form(expressions, 1, 1)
    # BEGIN PROBLEM 7
    "*** YOUR CODE HERE ***"
    return expressions.first
    # END PROBLEM 7

第二部分在scheme_reader函数中，当我们读到'字符时，需要将它转化成quote。剩下的部分递归调用本身即可

def scheme_read(src):
    if src.current() is None:
        raise EOFError
    val = src.remove_front() # Get the first token
    if val == 'nil':
        # BEGIN PROBLEM 1
        "*** YOUR CODE HERE ***"
        return nil
        # END PROBLEM 1
    elif val == '(':
        # BEGIN PROBLEM 1
        "*** YOUR CODE HERE ***"
        return read_tail(src)
        # END PROBLEM 1
    elif val == "'":
        # BEGIN PROBLEM 7
        "*** YOUR CODE HERE ***"
        return Pair("quote", Pair(scheme_read(src), nil))
        # END PROBLEM 7
    elif val not in DELIMITERS:
        return val
    else:
        raise SyntaxError('unexpected token: {0}'.format(val))

这一题完成之后，我们的解释器已经能够支持如下的功能：

评估单个元素：数字、bool、nil和字符串
评估quote表达式
定义变量
调用基本运算过程（primitive procedure），如加减乘除等

这一步完成，我们算是搞定了解释器的基本框架和基本功能。

当年我们学院《编译原理》的最终项目也就做到这个程度，不过当时的项目针对的是C语言，而这个项目针对scheme。相比于C语言，scheme的语法都以前缀表达式书写，语法检查和词法检查要容易很多，但核心的知识点是类似的。

这个项目虽然不似之前的项目那么酷炫，但实打实做下来是能学到很多东西的，因此非常非常推荐大家下载下来亲自练习一下。

好了，关于这个项目先聊到这里，剩下的部分我们下篇继续，感谢大家的阅读。

转载自:https://juejin.cn/post/7094881025758609444