【文章內(nèi)容簡介】 PARC 在一個寄存器窗口里則有 24個通用寄存 器 (8 in， 8 local， 8 out)。假如一個 VM 采用基于寄存器的架構(gòu) (它接受的指令集大概就是二地址或者三地址形式的 )，為了高效執(zhí)行，一般會希望能把源架構(gòu)中的寄存器映射到實際機器上寄存器上。但是 VM里有些很重要的輔助數(shù)據(jù)會經(jīng)常被訪問，例如一些 VM會保存源指令序列的程序計數(shù)器 (program counter， PC)，為了效率，這些數(shù)據(jù)也得放在實際機器的寄存器里。如果源架構(gòu)中寄存器的數(shù)量跟實際機器的一樣，或者前者比后者更多，那源架構(gòu)的寄存器就沒辦法都映射到實際機器的寄存器上；這樣 VM實現(xiàn)起來比較麻煩，與能 夠全部映射相比效率也會大打折扣。如果一個 VM 采用基于棧的架構(gòu)，則無論在怎樣的實際機器上，都很好實現(xiàn) 它的源架構(gòu)里沒有任何通用寄存器，所以實現(xiàn) VM 時可以比較自由的分配實際機器的寄存器。于是這樣的 VM可移植性就比較高。作為優(yōu)化，基于棧的 VM 可以用編譯方式實現(xiàn)， 求值棧 實際上也可以由編譯器映射到寄存器上，減輕數(shù)據(jù)移動的開銷?；氐街黝}，基于棧與基于寄存器的架構(gòu)，誰更快 ?看看現(xiàn)在的實際處理器，大多都是基于寄存器的架構(gòu)，從側(cè)面反映出它比基于棧的架構(gòu)更優(yōu)秀。而對于 VM來說，源架構(gòu)的求值?；蛘呒拇嫫鞫伎赡苁怯脤嶋H機器的 內(nèi)存來模擬的，所以性能特性與實際硬件又有點不同。一般認為基于寄存器的架構(gòu)對 VM來說也是更快的，原因是：雖然零地址指令更緊湊，但完成操作需要更多的 load/store 指令，也意味著更多的指令分派 (instruction dispatch)次數(shù)與內(nèi)存訪問次數(shù)；訪問內(nèi)存是執(zhí)行速度的一個重要瓶頸，二地址或三地址指令雖然每條指令占的空間較多，但總體來說可以用更少的指令完成操作，指令分派與內(nèi)存訪問次數(shù)都較少。這方面有篇被引用得很多的論文講得比較清楚， Virtual Machine Showdown： Stack Versus Registers，是在 VEE 2021 發(fā)表的。 VEE是 Virtual Execution Environment 的縮寫，是 ACM下 SIGPLAN 組織的一個會議，專門研討虛擬機的設(shè)計與實現(xiàn)的?？梢匀フ艺疫@個會議往年的論文，很多都值得讀。 樹遍歷解釋器圖解在演示基于棧與基于寄存器的 VM的例子前，先回頭看看更原始的解釋器形式。前面提到解析器的時候用了 i=a+b*c 的例子，現(xiàn)在讓我們來看看由解析器生成的 AST要是交給一個樹遍歷解釋器，會如何被解釋執(zhí)行呢 ?用文字說不夠形象，還是看圖吧：這是對 AST 的后序遍歷 ：假設(shè)有一個 eval(Node n)函數(shù)，用于解釋 AST 上的每個節(jié)點；在解釋一個節(jié)點時如果依賴于子樹的操作，則對子節(jié)點遞歸調(diào)用 eval(Node n)，從這些遞歸調(diào)用的返回值獲取需要的值 (或副作用 )也就是說子節(jié)點都 eval 好了之后，父節(jié)點才能進行自己的 eval典型的后序遍歷。 (話說，上圖中節(jié)點左下角有藍色標(biāo)記的說明那是節(jié)點的 內(nèi)在屬性 。從屬性語法的角度看，如果一個節(jié)點的某個屬性的值只依賴于自身或子節(jié)點，則該屬性被稱為 綜合屬性 (synthesized attribute)；如果一個節(jié)點的某個屬性 只依賴于自身、父節(jié)點和兄弟節(jié)點，則該屬性被稱為 繼承屬性(inherited attribute)。上圖中節(jié)點右下角的紅色標(biāo)記都只依賴子節(jié)點來計算，顯然是綜合屬性。 )SquirrelFish 之前的 JavaScriptCore、 CRuby 之前的 CRuby 就都是采用這種方式來解釋執(zhí)行的?？赡苄枰f明的：左值與右值在源代碼 i=a+b*c 中，賦值符號左側(cè)的 i 是一個標(biāo)識符，表示一個變量，取的是變量的 左值 (也就是與變量 i綁定的存儲單元 )；右側(cè)的 a、 b、 c雖然也是變量，但取的是它們的右值 (也就是與變量綁定 的存儲單元內(nèi)的值 )。在許多編程語言中，左值與右值在語法上沒有區(qū)別，它們實質(zhì)的差異容易被忽視。一般來說左值可以作為右值使用，反之則不一定。例如數(shù)字 1，它自身有值就是 1，可以作為右值使用；但它沒有與可賦值的存儲單元相綁定，所以無法作為左值使用。左值不一定只是簡單的變量，還可以是數(shù)組元素或者結(jié)構(gòu)體的域之類，可能由復(fù)雜的表達式所描述。因此左值也是需要計算的。優(yōu)先級、結(jié)合性與求值順序這三個是不同的概念，卻經(jīng)常被混淆。通過 AST 來看就很容易理解：(假設(shè)源碼是從左到右輸入的 )所謂優(yōu)先級，就是不同操作相鄰出現(xiàn)時， AST 節(jié)點與根的距離的關(guān)系。優(yōu)先級高的操作會更遠離根，優(yōu)先級低的操作會更接近根。為什么 ?因為整棵 AST 是以后序遍歷求值的，顯然節(jié)點離根越遠就越早被求值。所謂結(jié)合性，就是當(dāng)同類操作相鄰出現(xiàn)時，操作的先后順序同 AST 節(jié)點與根的距離的關(guān)系。如果是左結(jié)合，則先出現(xiàn)的操作對應(yīng)的 AST節(jié)點比后出現(xiàn)的操作的節(jié)點離根更遠；換句話說，先出現(xiàn)的節(jié)點會是后出現(xiàn)節(jié)點的子節(jié)點。所謂求值順序，就是在遍歷子節(jié)點時的順序。對二元運算對應(yīng)的節(jié)點來說，先遍歷左子節(jié)點再遍歷右子節(jié)點就是左結(jié)合，反之則是右結(jié)合。這三個概念與運算的聯(lián)系都很緊密，但實際描述的 是不同的關(guān)系。前兩者是解析器根據(jù)語法生成AST時就已經(jīng)決定好的，后者則是解釋執(zhí)行或者生成代碼而去遍歷 AST 時決定的。在沒有副作用的環(huán)境中，給定優(yōu)先級與結(jié)合性，則無論求值順序是怎樣的都能得到同樣的結(jié)果；而在有副作用的環(huán)境中，求值順序會影響結(jié)果。賦值運算雖然是右結(jié)合的，但仍然可以用從左到右的求值順序；事實上 Java、 C等許多語言都在規(guī)范里寫明表達式的求值順序是從左到右的。上面的例子中就先遍歷的 =的左側(cè)，求得 i的左值；再遍歷 =的右側(cè)，得到表達式的值 23；最后執(zhí)行=自身，完成對 i的賦值。所以如果你要問：賦值在類似 C的語言里明明是右結(jié)合的運算，為什么你先遍歷左子樹再遍歷右子樹 ?上面的說明應(yīng)該能讓你發(fā)現(xiàn)你把結(jié)合性與求值順序混為一談了?？纯?Java 從左到右求值順序的例子： Java 代碼 publicclass EvalOrderDemo{publicstaticvoid main(String args){int arr=newint1]； int a=1； int b=2； arr[0]=a+b； }}由 javac 編譯，得到 arr[0]=a+b 對應(yīng)的字節(jié)碼是： Java bytecode 代碼 //左子樹：數(shù)組下標(biāo) //a[0aload_1iconst_0//右子樹：加法 //aiload_2//biload_3//+iadd//根節(jié)點：賦值 iastore 從樹遍歷解釋器進化為基于棧的字節(jié)碼解釋器的前端如果你看到樹形結(jié)構(gòu)與后序遍歷，并且知道后綴記法 (或者逆波蘭記法， reverse Polish notation)的話，那敏銳的你或許已經(jīng)察覺了：要解釋執(zhí)行 AST，可以先通過后序遍歷 AST生成對應(yīng)的后綴記法的操作序列，然后再解釋執(zhí)行該操作序列。這樣就把樹形結(jié)構(gòu)壓扁，成為了線性結(jié)構(gòu)。樹遍歷解釋器對 AST 的求值其實隱式依賴于調(diào)用棧： eval(Node n)的遞歸調(diào)用關(guān)系是靠調(diào)用棧來維護的。后綴表達式的求值則通常顯式依賴于一個棧，在遇到操作數(shù)時將其壓入棧中，遇到運算時將合適數(shù)量的值從棧頂彈出進行運算，再將結(jié)果壓回到棧上。這種描述看起來眼熟么 ?沒錯，后綴記法的求值中的核心數(shù)據(jù)結(jié)構(gòu)就是前文提到過的 求值棧 (或者叫操作數(shù)棧，現(xiàn)在應(yīng)該更好理解了 )。后綴記法也就與基于棧的架構(gòu)聯(lián)系了起來：后者可以很方便的執(zhí)行前者。同理，零地址指令也與樹形結(jié)構(gòu)聯(lián)系了起來：可以通過一個棧方便的把零地址指令序列再轉(zhuǎn)換回到樹的形式。 Java 字節(jié)碼與 Java 源碼聯(lián)系緊密，前者可以看 成后者的后綴記法。如果想在 JVM 上開發(fā)一種語義能直接映射到 Java上的語言，那么編譯器很好寫：秘訣就是后序遍歷 AST。那么讓我們再來看看，同樣是 i=a+b*c 這段源碼對應(yīng)的 AST，生成 Java 字節(jié)碼的例子： (假設(shè) a、 b