摘要：接下來(lái)，我們實(shí)現(xiàn)虛擬機(jī)這個(gè)類(lèi)。在虛擬機(jī)中我們需要兩個(gè)堆棧以及一些內(nèi)存空間來(lái)存儲(chǔ)程序本身譯者注這里的程序請(qǐng)結(jié)合下文理解。截止現(xiàn)在，恭喜你，一個(gè)虛擬機(jī)就完成了。實(shí)際上，一個(gè)好的程序空間布局很有可能把主程序當(dāng)成一個(gè)名為的子例程。

原文地址：Making a simple VM interpreter in Python

更新：根據(jù)大家的評(píng)論我對(duì)代碼做了輕微的改動(dòng)。感謝 robin-gvx、 bs4h 和 Dagur，具體代碼見(jiàn)這里

Stack Machine 本身并沒(méi)有任何的寄存器，它將所需要處理的值全部放入堆棧中而后進(jìn)行處理。Stack Machine 雖然簡(jiǎn)單但是卻十分強(qiáng)大，這也是為神馬 Python，Java，PostScript，F(xiàn)orth 和其他語(yǔ)言都選擇它作為自己的虛擬機(jī)的原因。

首先，我們先來(lái)談?wù)劧褩！Ｎ覀冃枰粋€(gè)指令指針棧用于保存返回地址。這樣當(dāng)我們調(diào)用了一個(gè)子例程（比如調(diào)用一個(gè)函數(shù)）的時(shí)候我們就能夠返回到我們開(kāi)始調(diào)用的地方了。我們可以使用自修改代碼(self-modifying code)來(lái)做這件事，恰如 Donald Knuth 發(fā)起的 MIX 所做的那樣。但是如果這么做的話你不得不自己維護(hù)堆棧從而保證遞歸能正常工作。在這篇文章中，我并不會(huì)真正的實(shí)現(xiàn)子例程調(diào)用，但是要實(shí)現(xiàn)它其實(shí)并不難（可以考慮把實(shí)現(xiàn)它當(dāng)成練習(xí)）。

有了堆棧之后你會(huì)省很多事兒。舉個(gè)例子來(lái)說(shuō)，考慮這樣一個(gè)表達(dá)式(2+3)*4。在 Stack Machine 上與這個(gè)表達(dá)式等價(jià)的代碼為 2 3 + 4 *。首先，將 2 和 3 推入堆棧中，接下來(lái)的是操作符 +，此時(shí)讓堆棧彈出這兩個(gè)數(shù)值，再把它兩加合之后的結(jié)果重新入棧。然后將 4 入堆，而后讓堆棧彈出兩個(gè)數(shù)值，再把他們相乘之后的結(jié)果重新入棧。多么簡(jiǎn)單啊！

讓我們開(kāi)始寫(xiě)一個(gè)簡(jiǎn)單的堆棧類(lèi)吧。讓這個(gè)類(lèi)繼承 collections.deque：

from collections import deque

class Stack(deque):
push = deque.append

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

現(xiàn)在我們有了 push、pop 和 top 這三個(gè)方法。top 方法用于查看棧頂元素。

接下來(lái)，我們實(shí)現(xiàn)虛擬機(jī)這個(gè)類(lèi)。在虛擬機(jī)中我們需要兩個(gè)堆棧以及一些內(nèi)存空間來(lái)存儲(chǔ)程序本身（譯者注：這里的程序請(qǐng)結(jié)合下文理解）。得益于 Pyhton 的動(dòng)態(tài)類(lèi)型我們可以往 list 中放入任何類(lèi)型。唯一的問(wèn)題是我們無(wú)法區(qū)分出哪些是字符串哪些是內(nèi)置函數(shù)。正確的做法是只將真正的 Python 函數(shù)放入 list 中。我可能會(huì)在將來(lái)實(shí)現(xiàn)這一點(diǎn)。

我們同時(shí)還需要一個(gè)指令指針指向程序中下一個(gè)要執(zhí)行的代碼。

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

這時(shí)候我們?cè)黾右恍┓奖闶褂玫暮瘮?shù)省得以后多敲鍵盤(pán)。

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

然后我們?cè)黾右粋€(gè) dispatch 函數(shù)來(lái)完成每一個(gè)操作碼做的事兒（我們并不是真正的使用操作碼，只是動(dòng)態(tài)展開(kāi)它，你懂的）。首先，增加一個(gè)解釋器所必須的循環(huán)：

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

誠(chéng)如您所見(jiàn)的，這貨只好好的做一件事兒，即獲取下一條指令，讓指令指針執(zhí)自增，然后根據(jù)操作碼分別處理。dispatch 函數(shù)的代碼稍微長(zhǎng)了一點(diǎn)。

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,
        "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):
        # push numbers on the data stack
        self.push(op)
    elif isinstance(op, str) and op[0]==op[-1]==""":
        # push quoted strings on the data stack
        self.push(op[1:-1])
    else:
        raise RuntimeError("Unknown opcode: "%s"" % op)

基本上，這段代碼只是根據(jù)操作碼查找是都有對(duì)應(yīng)的處理函數(shù)，例如 * 對(duì)應(yīng) self.mul，drop 對(duì)應(yīng) self.drop，dup對(duì)應(yīng) self.dup。順便說(shuō)一句，你在這里看到的這段代碼其實(shí)本質(zhì)上就是簡(jiǎn)單版的 Forth。而且，Forth 語(yǔ)言還是值得您看看的。

總之捏，它一但發(fā)現(xiàn)操作碼是 * 的話就直接調(diào)用 self.mul 并執(zhí)行它。就像這樣：

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

其他的函數(shù)也是類(lèi)似這樣的。如果我們?cè)?dispatch_map 中查找不到相應(yīng)操作函數(shù)，我們首先檢查他是不是數(shù)字類(lèi)型，如果是的話直接入棧；如果是被引號(hào)括起來(lái)的字符串的話也是同樣處理－－直接入棧。

截止現(xiàn)在，恭喜你，一個(gè)虛擬機(jī)就完成了。

讓我們定義更多的操作，然后使用我們剛完成的虛擬機(jī)和 p-code 語(yǔ)言來(lái)寫(xiě)程序。

# Allow to use "print" as a name for our own method:
from __future__ import print_function

# ...

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

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 print(self):
    sys.stdout.write(str(self.pop()))
    sys.stdout.flush()

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

讓我們用我們的虛擬機(jī)寫(xiě)個(gè)與 print((2+3)*4) 等同效果的例子。

Machine([2, 3, "+", 4, "*", "println"]).run()

你可以試著運(yùn)行它。

現(xiàn)在引入一個(gè)新的操作 jump, 即 go-to 操作

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

它只改變指令指針的值。我們?cè)倏纯捶种D(zhuǎn)是怎么做的。

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

這同樣也是很直白的。如果你想要添加一個(gè)條件跳轉(zhuǎn)，你只要簡(jiǎn)單的執(zhí)行 test-value true-value false-value IF JMP 就可以了.（分支處理是很常見(jiàn)的操作，許多虛擬機(jī)都提供類(lèi)似 JNE 這樣的操作。JNE 是 jump if not equal 的縮寫(xiě)）。

下面的程序要求使用者輸入兩個(gè)數(shù)字，然后打印出他們的和和乘積。

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

over、read 和 cast_int 這三個(gè)操作是長(zhǎng)這樣滴：

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

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

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

以下這一段程序要求使用者輸入一個(gè)數(shù)字，然后打印出這個(gè)數(shù)字是奇數(shù)還是偶數(shù)。

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

這里有個(gè)小練習(xí)給你去實(shí)現(xiàn)：增加 call 和 return 這兩個(gè)操作碼。call 操作碼將會(huì)做如下事情 ：將當(dāng)前地址推入返回堆棧中，然后調(diào)用 self.jmp()。return 操作碼將會(huì)做如下事情：返回堆棧彈棧，將彈棧出來(lái)元素的值賦予指令指針（這個(gè)值可以讓你跳轉(zhuǎn)回去或者從 call 調(diào)用中返回）。當(dāng)你完成這兩個(gè)命令，那么你的虛擬機(jī)就可以調(diào)用子例程了。

創(chuàng)造一個(gè)模仿上述程序的小型語(yǔ)言。我們將把它編譯成我們的機(jī)器碼。

 import tokenize
 from StringIO import StringIO

# ...

def parse(text):
tokens =   tokenize.generate_tokens(StringIO(text).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))

常量折疊（Constant folding）是窺孔優(yōu)化（peephole optimization）的一個(gè)例子，也即是說(shuō)再在編譯期間可以針對(duì)某些明顯的代碼片段做些預(yù)計(jì)算的工作。比如，對(duì)于涉及到常量的數(shù)學(xué)表達(dá)式例如 2 3 +就可以很輕松的實(shí)現(xiàn)這種優(yōu)化。

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

采用常量折疊遇到唯一問(wèn)題就是我們不得不更新跳轉(zhuǎn)地址，但在很多情況這是很難辦到的（例如：test cast_int jmp）。針對(duì)這個(gè)問(wèn)題有很多解決方法，其中一個(gè)簡(jiǎn)單的方法就是只允許跳轉(zhuǎn)到程序中的命名標(biāo)簽上，然后在優(yōu)化之后解析出他們真正的地址。

如果你實(shí)現(xiàn)了 Forth words，也即函數(shù)，你可以做更多的優(yōu)化，比如刪除可能永遠(yuǎn)不會(huì)被用到的程序代碼（dead code elimination）

我們可以創(chuàng)造一個(gè)簡(jiǎn)單的 PERL，就像這樣

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

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

用一些簡(jiǎn)單的程序來(lái)測(cè)試我們的 REPL

> 2 3 + 4 * println
Constant-folded 2+3 to 5
Constant-folded 5*4 to 20
20
> 12 dup * println
144
> "Hello, world!" dup println println
Hello, world!
Hello, world!
你可以看到，常量折疊看起來(lái)運(yùn)轉(zhuǎn)正常。在第一個(gè)例子中，它把整個(gè)程序優(yōu)化成這樣 20 println。

當(dāng)你添加完 call 和 return 之后，你便可以讓使用者定義自己的函數(shù)了。在Forth 中函數(shù)被稱(chēng)為 words，他們以冒號(hào)開(kāi)頭緊接著是名字然后以分號(hào)結(jié)束。例如，一個(gè)整數(shù)平方的 word 是長(zhǎng)這樣滴

: square dup * ;

實(shí)際上，你可以試試把這一段放在程序中，比如 Gforth

$ gforth
Gforth 0.7.3, Copyright (C) 1995-2008 Free Software Foundation, Inc.
Gforth comes with ABSOLUTELY NO WARRANTY; for details type `license"
Type `bye" to exit
: square dup * ;  ok
12 square . 144  ok

你可以在解析器中通過(guò)發(fā)現(xiàn) : 來(lái)支持這一點(diǎn)。一旦你發(fā)現(xiàn)一個(gè)冒號(hào)，你必須記錄下它的名字及其地址（比如：在程序中的位置）然后把他們插入到符號(hào)表（symbol table）中。簡(jiǎn)單起見(jiàn)，你甚至可以把整個(gè)函數(shù)的代碼（包括分號(hào)）放在字典中，譬如：

symbol_table = {
"square": ["dup", "*"]
# ...
    }

當(dāng)你完成了解析的工作，你可以連接你的程序：遍歷整個(gè)主程序并且在符號(hào)表中尋找自定義函數(shù)的地方。一旦你找到一個(gè)并且它沒(méi)有在主程序的后面出現(xiàn)，那么你可以把它附加到主程序的后面。然后用

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

#!/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
" % 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("
KeyboardInterrupt")

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("
** 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("
** 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("")