用Python来实现Python解释器(上)

在我们用Python实现一个Python解释器之前，需要了解一下，计算机编程语言，解释器，以及Python是如何工作的。

计算机编程语言，它主要分为三类：机器语言、汇编语言、高级语言。

机器语言是一种计算机可以直接识别并执行的二进制指令集。由于其可以直接交给CPU执行，所以是最快的，但是它需要我们记住每一个指令的代码与对应的动作，想想我们写代码的时候是操作一串串的01序列，难度得有多大。

为了克服机器语言的缺点，人们就用一些助记符来代替机器码，也就是使用一些与实际意义相近的缩略词来代替动作，例如ADD、SUB、MOV等，这就有了很大的进步，可以方便的编写，但是它仍然是对机器进行操作的，相较于高级程序语言更接近于底层，所以汇编语言是低级语言。

不论是机器语言还是汇编语言都是面向硬件的操作，它们对于机器是依赖的，不同的设备对应的编写方式可能不同。然而，高级语言是面向用户的语言，我们只要编写好程序内容，通过编译或者解释程序，就可以对机器进行操作。这里提到的编译或者解释程序就是一个翻译工具，将人类看懂的语言翻译成机器能看懂的东西。

解释器（英语：interpreter），是一种程序，能够把编程语言一行一行解释运行。解释器像是一位“中间人”，每次运行程序时都要先转成另一种语言再作运行，因此解释器的程序运行速度比较缓慢。它不会一次把整个程序翻译出来，而是每翻译一行程序叙述就立刻运行，然后再翻译下一行，再运行，如此不停地进行下去。

解释器的好处是它消除了编译整个程序的负担，程序可以拆分成多个部分来模块化，但这会让运行时的效率打了折扣。相对地，编译器已一次将所有源代码翻译成另一种语言，如机器代码，运行时便无需再依赖编译器或额外的程序，故而其运行速度比较快。

Python解释器是一个虚拟机,模拟真实计算机的软件。我们这个虚拟机是栈机器，它用几个栈来完成操作（与之相对的是寄存器机器，它从特定的内存地址读写数据）。

Python解释器也可以叫字节码解释器：它的输入是一些命令集合称作字节码。当你写Python代码时，词法分析器，语法解析器和编译器生成code object让解释器去操作。每个code object都包含一个要被执行的指令集合 --- 它就是字节码 --- 另外还有一些解释器需要的信息。字节码是Python代码的一个中间层表示：它以一种解释器可以理解的方式来表示源代码。这和汇编语言作为C语言和机器语言的中间表示很类似。

Python的字节码（Bytecode）与字节码指令序列

Python 3.7.5 (default, Nov  1 2019, 02:16:38) 
[Clang 10.0.0 (clang-1000.11.45.5)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> def loop():
...     x = 0
...     while x<5:
...         if x == 4:
...             break
...         x = x +1
...         print(x)
...     return
... 
>>> loop.__code__.co_code
b'd\x01}\x00x&|\x00d\x02k\x00r*|\x00d\x03k\x02r\x18P\x00|\x00d\x04\x17\x00}\x00t\x00|\x00\x83\x01\x01\x00q\x06W\x00d\x00S\x00'
>>> list(loop.__code__.co_code)
[100, 1, 125, 0, 120, 38, 124, 0, 100, 2, 107, 0, 114, 42, 124, 0, 100, 3, 107, 2, 114, 24, 80, 0, 124, 0, 100, 4, 23, 0, 125, 0, 116, 0, 124, 0, 131, 1, 1, 0, 113, 6, 87, 0, 100, 0, 83, 0]
>>> import dis
>>> dis.dis(loop)
  2           0 LOAD_CONST               1 (0)
              2 STORE_FAST               0 (x)

  3           4 SETUP_LOOP              38 (to 44)
        >>    6 LOAD_FAST                0 (x)
              8 LOAD_CONST               2 (5)
             10 COMPARE_OP               0 (<)
             12 POP_JUMP_IF_FALSE       42

  4          14 LOAD_FAST                0 (x)
             16 LOAD_CONST               3 (4)
             18 COMPARE_OP               2 (==)
             20 POP_JUMP_IF_FALSE       24

  5          22 BREAK_LOOP

  6     >>   24 LOAD_FAST                0 (x)
             26 LOAD_CONST               4 (1)
             28 BINARY_ADD
             30 STORE_FAST               0 (x)

  7          32 LOAD_GLOBAL              0 (print)
             34 LOAD_FAST                0 (x)
             36 CALL_FUNCTION            1
             38 POP_TOP
             40 JUMP_ABSOLUTE            6
        >>   42 POP_BLOCK

  8     >>   44 LOAD_CONST               0 (None)
             46 RETURN_VALUE
>>>

首先解释一下指令序列，它们对应的格式是这样的：

以源码行号为4的代码块为例

14 LOAD_FAST 0 (x) -->加载一个变量 x
16 LOAD_CONST 3 (4) -->加载一个常量4
18 COMPARE_OP 2 (==) -->比较操作
20 POP_JUMP_IF_FALSE 24 -->如果是False跳转到24(指令在函数中的偏移)

以截取字节码的前4个长度为例讲解[100, 1, 125, 0...]

第一个100，为命令的索引，dis.opname[100]就可以得到LOAD_CONST 命令。
第二个1，为指令为指令参数。LOAD_CONST是常量集。这个指令参数，告诉我们，如何从常量集中，取出对应的参数。cond.__code__.co_consts[1]就可以取到0
第三个125，为命令的索引，dis.opname[125]就可以得到 STORE_FAST 命令。
第四个0，为指令参数。作用同上，cond.__code__.co_varnames[0]

解释5+7

假如我们得到一个这样的指令集

what_to_execute = {
    "instructions": [("LOAD_VALUE", 0),  # the first number
                     ("LOAD_VALUE", 1),  # the second number
                     ("ADD_TWO_VALUES", None),
                     ("PRINT_ANSWER", None)],
    "numbers": [7, 5] }

Python解释器是一个栈机器，所以它必须通过操作栈来完成这个加法。(Figure 1.1)解释器先执行第一条指令，LOAD_VALUE，把第一个数压到栈中。接着它把第二个数也压到栈中。然后，第三条指令，ADD_TWO_VALUES,先把两个数从栈中弹出，加起来，再把结果压入栈中。最后一步，把结果弹出并输出。

LOAD_VALUE这条指令告诉解释器把一个数压入栈中，但指令本身并没有指明这个数是多少。指令需要一个额外的信息告诉解释器去哪里找到这个数。所以我们的指令集有两个部分：指令本身和一个常量列表。（在Python中，字节码就是我们称为的“指令”，而解释器执行的是code object。）

为什么不把数字直接嵌入指令之中？想象一下，如果我们加的不是数字，而是字符串。我们可不想把字符串这样的东西加到指令中，因为它可以有任意的长度。另外，我们这种设计也意味着我们只需要对象的一份拷贝，比如这个加法 7 + 7, 现在常量表 "numbers"只需包含一个7。

你可能会想为什么会需要除了ADD_TWO_VALUES之外的指令。的确，对于我们两个数加法，这个例子是有点人为制作的意思。然而，这个指令却是建造更复杂程序的轮子。比如，就我们目前定义的三个指令，只要给出正确的指令组合，我们可以做三个数的加法，或者任意个数的加法。同时，栈提供了一个清晰的方法去跟踪解释器的状态，这为我们增长的复杂性提供了支持。

代码示例

class Interpreter:
    def __init__(self):
        self.stack = []

    def LOAD_VALUE(self, number):
        self.stack.append(number)

    def PRINT_ANSWER(self):
        answer = self.stack.pop()
        print(answer)

    def ADD_TWO_VALUES(self):
        first_num = self.stack.pop()
        second_num = self.stack.pop()
        total = first_num + second_num
        self.stack.append(total)
        
    def run_code(self, what_to_execute):
        instructions = what_to_execute["instructions"]
        numbers = what_to_execute["numbers"]
        for each_step in instructions:
            instruction, argument = each_step
            if instruction == "LOAD_VALUE":
                number = numbers[argument]
                self.LOAD_VALUE(number)
            elif instruction == "ADD_TWO_VALUES":
                self.ADD_TWO_VALUES()
            elif instruction == "PRINT_ANSWER":
                self.PRINT_ANSWER()

为了测试，我们创建一个解释器对象，然后用前面定义的 7 + 5 的指令集来调用run_code。

interpreter = Interpreter()
interpreter.run_code(what_to_execute)

显然，它会输出12

尽管我们的解释器功能受限，但这个加法过程几乎和真正的Python解释器是一样的。这里，我们还有几点要注意。

首先，一些指令需要参数。在真正的Python bytecode中，大概有一半的指令有参数。像我们的例子一样，参数和指令打包在一起。注意指令的参数和传递给对应方法的参数是不同的。

第二，指令ADD_TWO_VALUES不需要任何参数，它从解释器栈中弹出所需的值。这正是以栈为基础的解释器的特点。

下一节用Python来实现Python解释器（已发布），解释如下代码的运行

code = """
def loop():
    x = 1
    while x < 5:
        if x==4:
            break
        x = x + 1
        print(x)
    return x
print(loop())
"""

用Python来实现Python解释器(上)