高級語言虛擬機的計算模型？

高級語言虛擬機常見的有stack-based VM和register-based VM，還有別的類型嗎？

---

Stack-based VM 和 register-based VM 的主要關注點是以下三者的交互：

• 計算（線性指令）
• 局部變數
• 臨時計算值

同樣是執行線性指令，stack-based VM只可以通過load/store指令來隨機訪問局部變數，而計算則總是發生在求值棧上——臨時計算值都在求值棧上；而register-based VM則基本上可以在任何操作中都隨機訪問局部變數，局部變數和臨時計算值都統一的放在虛擬寄存器里。

我以前寫過一個關於stack-based 與 register-based VM的文，有興趣的話可以參考：虛擬機隨談（一）：解釋器，樹遍歷解釋器，基於棧與基於寄存器，大雜燴

用線性指令的指令集的角度來看這兩者，

• stack-based的指令集對應於「0地址指令」
• register-based的指令集則對應於「3地址指令」（或者特例的「2地址指令」）

——然而如果沒有「線性指令」這個要素，我們通常也就不使用stack- / register-based VM這樣的說法了。

最典型的情況就是一個遍歷抽象語法樹（AST）的解釋器，它沒有線性指令——程序邏輯通過AST來表現；而它的執行環境的實現也不一定要關心用寄存器還是求值棧來存放臨時值——這些可以隱含在遞歸遍歷樹的調用棧上。

例如說，

a + b + c


這樣的表達式，對應這樣的AST：

+
/
+ c
/
a b


然後假如我們有個超簡單的遍歷AST的解釋器實現如下的話：

class AddNode : Node {
public Node Left { get; set; }
public Node Right { get; set; }

public int Interpret(Context ctx) {
int leftVal = Left.Interpret(ctx); // recursively evaluate left child
int rightVal = Right.Interpret(ctx); // recursively evaluate right child
return leftVal + rightVal;
}
}


可以看到這個解釋器在跑 Right.Interpret(ctx) 的時候，leftVal 作為解釋器（Interpret()方法）自身的一個局部遍歷存在調用棧上，這個作用就跟一個stack-based VM的求值棧是非常相似的，只是隱含在調用中了而已。但因為這裡不涉及線性代碼，一般就不會把它叫做「stack-based VM」。

-------------------------------------------

然而上面這個例子要想向stack-based VM更貼近一點也是完全可以的——編程語言處理器的實現有相當大的自由度。

例如說這個「Context」對象，假如裡面的實現是這樣：

class Context {
private StackFrame _topFrame;

public void PushFrame() {
var newFrame = new StackFrame { CallerFrame = _topFrame };
_topFrame = newFrame;
}

public void PopFrame() {
_topFrame = _topFrame.CallerFrame;
}

public void PushValue(int value) {
_topFrame.PushValue(value);
}

public int PopValue() {
_topFrame.PopValue();
}
}

class StackFrame {
public StackFrame CallerFrame { get; set; };
private int[] _locals;
private Stack& _evaluationStack;

public void PushValue(int value) {
_evaluationStack.Push(value);
}

public int PopValue() {
return _evaluationStack.Pop();
}

public void LoadLocal(int index) {
PushValue(_locals[index]);
}

public void StoreLocal(int index) {
_locals[index] = PopValue();
}
}


然後把AddNode.Interpret()的實現修改為：

class AddNode : Node {
public Node Left { get; set; }
public Node Right { get; set; }

public void Interpret(Context ctx) {
Left.Interpret(ctx); // recursively evaluate left child
Right.Interpret(ctx); // recursively evaluate right child
int rightVal = ctx.PopValue();
int leftVal = ctx.PopValue();
ctx.PushValue(leftVal + rightVal);
}
}


這樣我們的Context里的StackFrame結構就跟一個stack-based VM的棧幀是相似的了，實際執行過程本質上也跟執行線性代碼的解釋器很相似——只要把遞歸解釋的過程提取出來，把後序遍歷樹的過程拉直成線性代碼，就得到了一個stack-based VM。

AST解釋器與stack-based VM / register-based VM的選擇其實是正交的，雖說AST解釋器選用靠近stack-based的方式實現是更直觀而常見的做法，要想做成向register-based VM的方向靠攏也不是做不到。

=====================================

除了AST之外，還有許多其它描述程序語義的表現方式。

其中一種是CPS（Continuation-Passing Style）。寫一個基於CPS的解釋器也是很常見的事情。當然這也會涉及到計算（指令）與局部變數（或者說binding）/臨時計算值的交互問題，實現的時候也可以向stack-based或register-based的方向靠攏。

=====================================

另外，要說局部變數的存儲，其實最偷懶的辦法用個hashmap也是完全可以的，存下 symbol -&> value 的映射。這樣存儲的局部變數也可以通過 symbol 來「隨機訪問」，只不過就不是像一般的（虛擬）寄存器那樣通過編號（下標）去隨機訪問了——前者性能自然不及後者好，但勝在實現起來超級簡單 &>_&<

---

這倆的區別僅限於load和store是否需要按stack順序和可以隨意使用reg，以及相關指令有些區別，都是順序執行編譯後的代碼

還有一種模型是直接解釋ast，用遞歸來做，實現比較簡單

---

推薦閱讀：