[译]使用 Python 编写虚拟机解释器

为了保证程序能正常执行，你应该考虑剔除 jmp 操作。否则的话，你不得不解析它们。它确实能执行，但是你得按照用户编写程序的顺序保存它们。举例来说，你想在子例程之间移动，你要格外小心。你可能需要添加 exit 函数用于停止程序（可能需要告诉操作系统返回值），这样主程序就不会继续执行以至于跑到子例程中。

实际上，一个好的程序空间布局很有可能把主程序当成一个名为 main 的子例程。或者由你决定搞成什么样子。

如您所见，这一切都是很有趣的，而且通过这一过程你也学会了很多关于代码生成、链接、程序空间布局相关的知识。

更多能做的事儿

你可以使用 Python 字节码生成库来尝试将虚拟机代码为原生的 Python 字节码。或者用 Java 实现运行在 JVM 上面，这样你就可以自由使用 JITing。

同样的，你也可以尝试下register machine。你可以尝试用栈帧（stack frames）实现调用栈（call stack），并基于此建立调用会话。

最后，如果你不喜欢类似 Forth 这样的语言，你可以创造运行于这个虚拟机之上的自定义语言。譬如，你可以把类似 (2+3)*4 这样的中缀表达式转化成 2 3 + 4 * 然后生成代码。你也可以允许 C 风格的代码块 { ... } 这样的话，语句 if ( test ) { ... } else { ... } 将会被翻译成

if
jmp


 jmp


 jmp

例子，

Address  Code
-------  ----
 0       2 3 >
 3       7        # Address of true-block
 4       11       # Address of false-block
 5       if
 6       jmp      # Conditional jump based on test

# True-block

7     \"Two is greater than three.\"  
8       println
9       15       # Continue main program
10       jmp

# False-block (\"else { ... }\")
11       \"Two is less than three.\"
12       println
13       15       # Continue main program
14       jmp

# If-statement finished, main program continues here
15       ...

对了，你还需要添加比较操作符 != < <= > >=。

我已经在我的 C++ stack machine 实现了这些东东，你可以参考下。

我已经把这里呈现出来的代码搞成了个项目 Crianza，它使用了更多的优化和实验性质的模型来吧程序编译成 Python 字节码。

祝好运！

完整的代码

下面是全部的代码，兼容 Python 2 和 Python 3

你可以通过 这里 得到它。

#!/usr/bin/env python
# coding: utf-8

\"\"\"
A simple VM interpreter.

Code from the post at http://csl.name/post/vm/
This version should work on both Python 2 and 3.
\"\"\"

from __future__ import print_function
from collections import deque
from io import StringIO
import sys
import tokenize


def get_input(*args, **kw):
\"\"\"Read a string from standard input.\"\"\"
if sys.version[0] == \"2\":
    return raw_input(*args, **kw)
else:
    return input(*args, **kw)


class Stack(deque):
push = deque.append

def top(self):
    return self[-1]


class Machine:
def __init__(self, code):
    self.data_stack = Stack()
    self.return_stack = Stack()
    self.instruction_pointer = 0
    self.code = code

def pop(self):
    return self.data_stack.pop()

def push(self, value):
    self.data_stack.push(value)

def top(self):
    return self.data_stack.top()

def run(self):
    while self.instruction_pointer < len(self.code):
        opcode = self.code[self.instruction_pointer]
        self.instruction_pointer += 1
        self.dispatch(opcode)

def dispatch(self, op):
    dispatch_map = {
        \"%\":        self.mod,
        \"*\":        self.mul,
        \"+\":        self.plus,
        \"-\":        self.minus,
        \"/\":        self.div,
        \"==\":       self.eq,
        \"cast_int\": self.cast_int,
        \"cast_str\": self.cast_str,
        \"drop\":     self.drop,
        \"dup\":      self.dup,
        \"exit\":     self.exit,
        \"if\":       self.if_stmt,
        \"jmp\":      self.jmp,
        \"over\":     self.over,
        \"print\":    self.print,
        \"println\":  self.println,
        \"read\":     self.read,
        \"stack\":    self.dump_stack,
        \"swap\":     self.swap,
    }

    if op in dispatch_map:
        dispatch_map[op]()
    elif isinstance(op, int):
        self.push(op) # push numbers on stack
    elif isinstance(op, str) and op[0]==op[-1]==\'\"\':
        self.push(op[1:-1]) # push quoted strings on stack
    else:
        raise RuntimeError(\"Unknown opcode: \'%s\'\" % op)

# OPERATIONS FOLLOW:

def plus(self):
    self.push(self.pop() + self.pop())

def exit(self):
    sys.exit(0)

def minus(self):
    last = self.pop()
    self.push(self.pop() - last)

def mul(self):
    self.push(self.pop() * self.pop())

def div(self):
    last = self.pop()
    self.push(self.pop() / last)

def mod(self):
    last = self.pop()
    self.push(self.pop() % last)

def dup(self):
    self.push(self.top())

def over(self):
    b = self.pop()
    a = self.pop()
    self.push(a)
    self.push(b)
    self.push(a)

def drop(self):
    self.pop()

def swap(self):
    b = self.pop()
    a = self.pop()
    self.push(b)
    self.push(a)

def print(self):
    sys.stdout.write(str(self.pop()))
    sys.stdout.flush()

def println(self):
    sys.stdout.write(\"%s\\n\" % self.pop())
    sys.stdout.flush()

def read(self):
    self.push(get_input())

def cast_int(self):
    self.push(int(self.pop()))

def cast_str(self):
    self.push(str(self.pop()))

def eq(self):
    self.push(self.pop() == self.pop())

def if_stmt(self):
    false_clause = self.pop()
    true_clause = self.pop()
    test = self.pop()
    self.push(true_clause if test else false_clause)

def jmp(self):
    addr = self.pop()
    if isinstance(addr, int) and 0 <= addr < len(self.code):
        self.instruction_pointer = addr
    else:
        raise RuntimeError(\"JMP address must be a valid integer.\")

def dump_stack(self):
    print(\"Data stack (top first):\")

    for v in reversed(self.data_stack):
        print(\" - type %s, value \'%s\'\" % (type(v), v))


def parse(text):
# Note that the tokenizer module is intended for parsing Python source
# code, so if you\'re going to expand on the parser, you may have to use
# another tokenizer.

if sys.version[0] == \"2\":
    stream = StringIO(unicode(text))
else:
    stream = StringIO(text)

tokens = tokenize.generate_tokens(stream.readline)

for toknum, tokval, _, _, _ in tokens:
    if toknum == tokenize.NUMBER:
        yield int(tokval)
    elif toknum in [tokenize.OP, tokenize.STRING, tokenize.NAME]:
        yield tokval
    elif toknum == tokenize.ENDMARKER:
        break
    else:
        raise RuntimeError(\"Unknown token %s: \'%s\'\" %
                (tokenize.tok_name[toknum], tokval))

def constant_fold(code):
\"\"\"Constant-folds simple mathematical expressions like 2 3 + to 5.\"\"\"
while True:
    # Find two consecutive numbers and an arithmetic operator
    for i, (a, b, op) in enumerate(zip(code, code[1:], code[2:])):
        if isinstance(a, int) and isinstance(b, int) \\
                and op in {\"+\", \"-\", \"*\", \"/\"}:
            m = Machine((a, b, op))
            m.run()
            code[i:i+3] = [m.top()]
            print(\"Constant-folded %s%s%s to %s\" %  (a,op,b,m.top()))
            break
        else:
            break
        return code

def repl():
print(\'Hit CTRL+D or type \"exit\" to quit.\')

while True:
    try:
        source = get_input(\"> \")
        code = list(parse(source))
        code = constant_fold(code)
        Machine(code).run()
    except (RuntimeError, IndexError) as e:
        print(\"IndexError: %s\" % e)
    except KeyboardInterrupt:
        print(\"\\nKeyboardInterrupt\")

def test(code = [2, 3, \"+\", 5, \"*\", \"println\"]):
print(\"Code before optimization: %s\" % str(code))
optimized = constant_fold(code)
print(\"Code after optimization: %s\" % str(optimized))

print(\"Stack after running original program:\")
a = Machine(code)
a.run()
a.dump_stack()

print(\"Stack after running optimized program:\")
b = Machine(optimized)
b.run()
b.dump_stack()

result = a.data_stack == b.data_stack
print(\"Result: %s\" % (\"OK\" if result else \"FAIL\"))
return result

def examples():
print(\"** Program 1: Runs the code for `print((2+3)*4)`\")
Machine([2, 3, \"+\", 4, \"*\", \"println\"]).run()

print(\"\\n** Program 2: Ask for numbers, computes sum and product.\")
Machine([
    \'\"Enter a number: \"\', \"print\", \"read\", \"cast_int\",
    \'\"Enter another number: \"\', \"print\", \"read\", \"cast_int\",
    \"over\", \"over\",
    \'\"Their sum is: \"\', \"print\", \"+\", \"println\",
    \'\"Their product is: \"\', \"print\", \"*\", \"println\"
]).run()

print(\"\\n** Program 3: Shows branching and looping (use CTRL+D to exit).\")
Machine([
    \'\"Enter a number: \"\', \"print\", \"read\", \"cast_int\",
    \'\"The number \"\', \"print\", \"dup\", \"print\", \'\" is \"\', \"print\",
    2, \"%\", 0, \"==\", \'\"even.\"\', \'\"odd.\"\', \"if\", \"println\",
    0, \"jmp\" # loop forever!
]).run()


if __name__ == \"__main__\":
try:
    if len(sys.argv) > 1:
        cmd = sys.argv[1]
        if cmd == \"repl\":
            repl()
        elif cmd == \"test\":
            test()
            examples()
        else:
            print(\"Commands: repl, test\")
    else:
        repl()
except EOFError:
    print(\"\")

本文系 OneAPM 工程师编译整理。想阅读更多技术文章，请访问 OneAPM 官方技术博客。