原文compilers-for-free，主要用Ruby來描述，意譯為主，文章太長了，typo/翻譯錯誤等請留言，謝謝。
最後，對編譯器解釋器感興趣的可以看看
目錄
- 介紹
- 執行
- 解釋
- 編譯
- 部分求值
- 應用
- 二村映射
- 總結
介紹
我喜歡編程，尤其喜歡元編程。當Ruby開發者討論元編程時他們說的通常是“讓程序來寫程序”，因為Ruby有很多這方面的特性，如 BasicObject#instance_eval, Module#define_method還有BasicObject#method_missing，這讓我們寫的程序能在運行時新增功能。
但是我發現元編程還有另一種更有趣的方面：操縱程序表示的程序（programs that manipulate representations of programs）。這些程序將一些程序的源碼作為輸入，然後在其上做一些事情，如分析，求值，翻譯或者轉換。
這是一個由解釋器、編譯器和靜態分析器組成的世界，我覺得它很迷人，我們能編寫的最純粹、最自指（self-referential）的軟件。
我會給你展示這個世界，並讓你對程序有不同的看法。我不會說一些很複雜的技術，我只會說很酷的技術，告訴你操縱其他程序的程序是有趣的，並希望能激勵你繼續探索這方面的知識。
執行
我們從一個最熟悉的東西開始：程序執行。
假設我們有一個要運行的程序，以及一台運行它的機器。運行程序的第一步是把程序放到機器裏面。然後我們輸入一些數據作為程序的——命令行參數，或者配置文件，或者標準輸入，又或者其它的——總之我們把這些輸入放到了機器裏面。
原則上，程序在機器上執行，讀取輸入，併產生一些輸出：
但實際上，上圖只可能發生在那些硬件能直接執行該程序的情況。對於一個裸機，這意味着除非你的程序是用機器代碼寫的，否則就不可能像上圖那樣。（如果程序使用一些高級語言寫的，那麼機器要想理解這門語言，必須套一個語言虛擬機，比如Java字節碼之於JVM）。我們需要一個解釋器或者編譯器。
解釋
解釋器的大致工作機制如下：
- 它讀取程序源碼，接着
- 它解析程序源碼，構造出抽象語法樹（Abstract syntax tree，AST），最終
- 解釋器遍歷AST並求值
我們試着構造一門玩具語言SIMPLE的解釋器，然後逐步討論。SIMPLE非常的直觀，類似於Ruby，但也不完全一樣。下面是一個SIMPLE的示例代碼：
a = 19 + 23
x = 2; y = x * 3
if (a < 10) { a = 0; b = 0 } else { b = 10 }
x = 1; while (x < 5) { x = x * 3 }
和Ruby不同的是，SIMPLE明確區分表達式和語句。表達式求值得到一個值。比如表達式19 + 23求值得到42，表達式x * 3將當前x的值乘以3。語句求值不產生任何值，但是可能有副作用（side effect）導致當前的值被修改。對賦值語句a = 19 + 23求值會將a的值修改為42。
除了賦值外，SIMPLE還有一些語句：序列語句（挨個求值，逗號隔開），條件語句（if (…) { … } else { … }），循環語句（while (…) { … }）。這些語句不會直接影響變量的值，但是它們的代碼塊中可能包含賦值語句，這些賦值語句就會影響變量的值。
有一個名為Treetop的Ruby庫，可以很容易的構造解析器，所以我們會使用Treetop來構造SIMPLE的解析器。（這裏不討論Treetop的細節，如果想了解更多請參見Treetop documentation）
在使用Treetop之前，我們還得寫一個語法文件，就像下面：
grammar Simple
rule statement
sequence
end
rule sequence
first:sequenced_statement '; ' second:sequence
/
sequenced_statement
end
rule sequenced_statement
while / assign / if
end
rule while
'while (' condition:expression ') { ' body:statement ' }'
end
rule assign
name:[a-z]+ ' = ' expression
end
rule if
'if (' condition:expression ') { ' consequence:statement
' } else { ' alternative:statement ' }'
end
rule expression
less_than
end
rule less_than
left:add ' < ' right:less_than
/
add
end
rule add
left:multiply ' + ' right:add
/
multiply
end
rule multiply
left:term ' * ' right:multiply
/
term
end
rule term
number / boolean / variable
end
rule number
[0-9]+
end
rule boolean
('true' / 'false') ![a-z]
end
rule variable
[a-z]+
end
end
這個語法文件包含一些rules，它們很好的显示了表達式和語句有哪些。sequence rule是兩個用逗號隔開的語句，while rule表示一個由關鍵字while開頭，後面跟一個圓括號包裹的條件表達式，再後面跟一個花括號包裹的代碼體。assignment rule表示變量名跟一個等號，再跟一個表達式。然後number，boolean和variable這些rules分別表示数字字面值，布爾字面值和變量名字。
當我們寫完語法文件，就可以使用Treetop讀取它，Treetop會生成一個解析器。解析器的代碼用Ruby的class組織，所以我們可以實例化解析器，然後給它一個表示字符串讓它解析。
假設語法文件名字是simple.treetop，然後我們用IRB演示一下：
>> Treetop.load('simple.treetop')
=> SimpleParser
>> SimpleParser.new.parse('x = 2; y = x * 3')
=> SyntaxNode+Sequence1+Sequence0 offset=0, "x = 2; y = x * 3" (first,second):
SyntaxNode+Assign1+Assign0 offset=0, "x = 2" (name,expression):
SyntaxNode offset=0, "x":
SyntaxNode offset=0, "x"
SyntaxNode offset=1, " = "
SyntaxNode+Number0 offset=4, "2":
SyntaxNode offset=4, "2"
SyntaxNode offset=5, "; "
SyntaxNode+Assign1+Assign0 offset=7, "y = x * 3" (name,expression):
SyntaxNode offset=7, "y":
SyntaxNode offset=7, "y"
SyntaxNode offset=8, " = "
SyntaxNode+Multiply1+Multiply0 offset=11, "x * 3" (left,right):
SyntaxNode+Variable0 offset=11, "x":
SyntaxNode offset=11, "x"
SyntaxNode offset=12, " * "
SyntaxNode+Number0 offset=15, "3":
SyntaxNode offset=15, "3"
解析器產生了一個名為具體語法樹（concrete syntax tree）的數據結構，也叫解析樹（parse tree），它包含了一大堆細節，但是實際上我們不需要這麼多細節，我們更希望一個抽象語法樹（abstract syntax tree），它包含更少的細節，更具表現力。
為了產出抽象語法樹，我們需要聲明一些類，它們是最後生成的抽象語法樹的節點。這些通過Struct很容易完成：
Number = Struct.new :value
Boolean = Struct.new :value
Variable = Struct.new :name
Add = Struct.new :left, :right
Multiply = Struct.new :left, :right
LessThan = Struct.new :left, :right
Assign = Struct.new :name, :expression
If = Struct.new :condition, :consequence, :alternative
Sequence = Struct.new :first, :second
While = Struct.new :condition, :body
現在，我們定義了一堆用來表示表達式和語句的node類：簡單的表達式如Number，Boolean只有包含一個value，二元表達式如Add，Multiply有left和right兩個表達式。Assign語句的name表示變量名，還有一個expression表示賦值語句的右側，等等等等。
Treetop還允許這些node類攜帶語義動作，這個語義動作是一個Ruby方法。我們可以用這個特性將具體語法樹的節點轉換為抽象語法樹的節點，讓我們把這個表示語義動作的方面命名為#to_ast。
下面展示了如何定義number，boolean和變量的語義動作方法：
rule number
[0-9]+ {
def to_ast
Number.new(text_value.to_i)
end
}
end
rule boolean
('true' / 'false') ![a-z] {
def to_ast
Boolean.new(text_value == 'true')
end
}
end
rule variable
[a-z]+ {
def to_ast
Variable.new(text_value.to_sym)
end
}
end
當Treetop應用number這條rule時，它繼續調用後面緊跟着的to_ast方法，這個方法把整数字面值轉換為一個整数字符串（使用String#to_i），然後用Number包裹創造處integer常量。#to_ast的實現在boolean和variable的rule中與之類似，它們最終都構造出合適的AST節點。
下面是一些二元表達式的#to_ast實現：
rule less_than
left:add ' < ' right:less_than {
def to_ast
LessThan.new(left.to_ast, right.to_ast)
end
}
/
add
end
rule add
left:multiply ' + ' right:add {
def to_ast
Add.new(left.to_ast, right.to_ast)
end
}
/
multiply
end
rule multiply
left:term ' * ' right:multiply {
def to_ast
Multiply.new(left.to_ast, right.to_ast)
end
}
/
term
end
在上面三個例子中，#to_ast遞歸地調用具體語法樹的左右子表達式的#to_ast，將它們轉換為AST，然後把它們組合起來，放到一個類中。
語句也類似
rule sequence
first:sequenced_statement '; ' second:sequence {
def to_ast
Sequence.new(first.to_ast, second.to_ast)
end
}
/
sequenced_statement
end
rule while
'while (' condition:expression ') { ' body:statement ' }' {
def to_ast
While.new(condition.to_ast, body.to_ast)
end
}
end
rule assign
name:[a-z]+ ' = ' expression {
def to_ast
Assign.new(name.text_value.to_sym, expression.to_ast)
end
}
end
rule if
'if (' condition:expression ') { ' consequence:statement
' } else { ' alternative:statement ' }' {
def to_ast
If.new(condition.to_ast, consequence.to_ast, alternative.to_ast)
end
}
end
一樣的，#to_ast遞歸調用子表達式或者子語句的#to_ast將它們轉換為AST，然後組合成一個正確的AST類。
當所有的#to_ast都定義完成后，我們對具體語法樹的根節點調用#to_ast，遞歸地將整個樹轉換為AST：
>> SimpleParser.new.parse('x = 2; y = x * 3').to_ast
=> #<struct Sequence
first=#<struct Assign
name=:x,
expression=#<struct Number value=2>
>,
second=#<struct Assign
name=:y,
expression=#<struct Multiply
left=#<struct Variable name=:x>,
right=#<struct Number value=3>
>
>
>
儘管Treetop的設計目的是產出具體語法樹，但是用我們定義的node類和語義動作生成的AST是更簡單的結構。代碼x = 2; y = x * 3的AST如下圖所示：
它告訴我們x = 2; y = x * 3 是一個序列語句，包含兩個賦值語句：第一個將Number 2賦值給x，第二個將Variable x和Number 3相乘，即Multiply，結果賦值給y。
現在我們獲得類AST，可以遍歷它並求值。我們為每個AST node類定義一個#evaluate方法，它將對當前節點以及節點的子樹求值。當定義好所有的#evaluate方法后，可以調用AST樹的根節點的#evaluate求值。
下面是Number,Boolean,Variable的#evaluate定義
class Number
def evaluate(environment)
value
end
end
class Boolean
def evaluate(environment)
value
end
end
class Variable
def evaluate(environment)
environment[name]
end
end
environment（環境）參數是一個哈希表，它將每個變量名和值關聯起來。比如說，一個 { x: 7, y: 11 }的environment表示有兩個變量，x和y，它們的值分別是7和11.我們假設每個SIMPLE程序的初始environment是一個空的哈希表。後面我們會看到語句求值如何改變environment。
當我們求值Number或者Boolean時，我們不關心它們是否在environment中，因為我們總是返回一個值，這個值是AST node構建的時候的那個值。如果我們對Variable求值，就得看看environment是否存在這個變量的值。
所以如果我們創建一個Number AST節點，然後用空environment開始求值，我們得到原始的Ruby整數：
>> Number.new(3).evaluate({})
=> 3
Boolean與之類似:
>> Boolean.new(false).evaluate({})
=> false
如果我們對一個名為y的Variable求值，並且environment是之前那個，那麼我們得到11，然而如果environment中的y的值是另一個，那麼對名為y的Variable求值也會得到另一個：
>> Variable.new(:y).evaluate({ x: 7, y: 11 })
=> 11
>> Variable.new(:y).evaluate({ x: 7, y: true })
=> true
下面是二元表達式的#evaluate定義
class Add
def evaluate(environment)
left.evaluate(environment) + right.evaluate(environment)
end
end
class Multiply
def evaluate(environment)
left.evaluate(environment) * right.evaluate(environment)
end
end
class LessThan
def evaluate(environment)
left.evaluate(environment) < right.evaluate(environment)
end
end
這些實現遞歸地求值左右子表達式，然後對結果執行一些運算。如果是Add節點，那麼結果相加；如果是Multiply節點，結果相乘；如果是LessThan節點，結果用<運算符進行比較。
當我們對一個Multiply表達式x * y求值時，environment的x為2，y為3，那麼結果是6:
>> Multiply.new(Variable.new(:x), Variable.new(:y)).
evaluate({ x: 2, y: 3 })
=> 6
如果在相同environment中對LessThan表達式x < y求值，得到結果true：
>> LessThan.new(Variable.new(:x), Variable.new(:y)).
evaluate({ x: 2, y: 3 })
=> true
對於語句，#evaluate稍有不同。因為對語句求值會更新environment的值，而不是像表達式求值那樣簡單的返回一個值。表達式的#evaluate接受一個environment參數，返回一個新的environment，返回的environment與environment參數的差異就是語句的效果導致的。
直接影響變量的語句有Assign：
class Assign
def evaluate(environment)
environment.merge({ name => expression.evaluate(environment) })
end
end
要求值Assign，我們得先求值右邊的表達式，得到一個值，然後使用Hash#merge創建一個修改后的environment。
如果我們在空environment中對x = 2求值，我們會得到一個新的environment，裡面包含了變量名x到值2的映射關係：
>> Assign.new(:x, Number.new(2)).evaluate({})
=> {:x=>2}
類似的，對y = x * 3求值，會在新的environment中關聯變量名y和值6:
>> Assign.new(:y, Multiply.new(Variable.new(:x), Number.new(3))).
evaluate({ x: 2 })
=> {:x=>2, :y=>6}
對序列語句的求值是先求第一個語句，作為中間environment，然後求第二個語句，用中間environment作為第二個語句求值的environment，得到最終的environment：
class Sequence
def evaluate(environment)
second.evaluate(first.evaluate(environment))
end
end
如果序列語句中有兩個賦值，那麼第二個賦值將是最終贏家：
>> Sequence.new(
Assign.new(:x, Number.new(1)),
Assign.new(:x, Number.new(2))
).evaluate({})
=> {:x=>2}
最後，我們還需要為If和While增加#evaluate：
class If
def evaluate(environment)
if condition.evaluate(environment)
consequence.evaluate(environment)
else
alternative.evaluate(environment)
end
end
end
class While
def evaluate(environment)
if condition.evaluate(environment)
evaluate(body.evaluate(environment))
else
environment
end
end
end
If語句根據它的條件選擇求值兩個子語句中的一個。While在條件為true的情況下反覆對循環體求值。
現在，我們已經為所有表達式和語句實現了#evaluate，我們可以解析簡單的SIMPLE程序，然後得到AST。讓我們看看在空environment中對x = 2; y = x * 3求值會得到什麼：
>> SimpleParser.new.parse('x = 2; y = x * 3').
to_ast.evaluate({})
=> {:x=>2, :y=>6}
正如期待的那樣，x和y的最終結果分別是2和6。
讓我們嘗試更複雜的程序：
>> SimpleParser.new.parse('x = 1; while (x < 5) { x = x * 3 }').
to_ast.evaluate({})
=> {:x=>9}
這個程序將初始化x為1，然後反覆的將它翻三倍，直到它大於5。當求值結束，x的值為9，因為9是最小的大於等於5且三倍之於x的值。
以上，我們實現了一個解釋器：解析器讀取源代碼，生成具體語法樹，然後語法制導翻譯將具體語法樹轉換為AST，最後遍歷AST求值。
解釋器是單階段執行（single-stage execution）。我們可以將源程序和其它數據（在SIMPLE的例子中是初始的空environment）作為解釋器的輸入，然後解釋器基於輸入得到輸出：
所有的過程都發生在運行時——程序執行階段
編譯
現在我們了解了解釋器是如何工作的，那編譯器呢？
編譯器將源碼解析為AST，然後遍歷它，和解釋器一樣的套路。但是不同的是，編譯器不根據AST節點語義執行代碼，它是生成代碼。
讓我們寫一個SIMPLE到JavaScript的編譯器來解釋這個過程。現在不為AST node定義#evaluate方法，我們定義一個#to_javascript方法，這個方法將所有表達式和語句節點轉換為JavaScript代碼字符串。
下面是Number，Boolean，Variable的#to_javascript定義：
require 'json'
class Number
def to_javascript
"function (e) { return #{JSON.dump(value)}; }"
end
end
class Boolean
def to_javascript
"function (e) { return #{JSON.dump(value)}; }"
end
end
class Variable
def to_javascript
"function (e) { return e[#{JSON.dump(name)}]; }"
end
end
上面的每個#to_javascript都會生成一個JavaScript的函數，這個函數接受一個environment參數e，然後返回一個值。對於Number表達式，返回的是Number所表達的整數：
>> Number.new(3).to_javascript
=> "function (e) { return 3; }"
我們可以獲取編譯后的JavaScript代碼，然後在瀏覽器console界面，或者Node.js REPL中調用JavaScript函數：
// 譯註：下面是JavaScript代碼
> program = function (e) { return 3; }
[Function]
> program({ x: 7, y: 11 })
3
類似的，Boolean AST節點編譯后也是一個JS函數，它返回true或者false：
>> Boolean.new(false).to_javascript
=> "function (e) { return false; }"
SIMPLE的Variable AST節點編譯後會在環境e中查找合適的變量，並返回這個值：
>> Variable.new(:y).to_javascript
=> "function (e) { return e[\"y\"]; }"
很顯然，上面的函數返回的內容取決於環境e的內容：
> program = function (e) { return e["y"]; }
[Function]
> program({ x: 7, y: 11 })
11
> program({ x: 7, y: true })
true
下面是二元表達式的#to_javascript實現
class Add
def to_javascript
"function (e) { return #{left.to_javascript}(e) + #{right.to_javascript}(e); }"
end
end
class Multiply
def to_javascript
"function (e) { return #{left.to_javascript}(e) * #{right.to_javascript}(e); }"
end
end
class LessThan
def to_javascript
"function (e) { return #{left.to_javascript}(e) < #{right.to_javascript}(e); }"
end
end
我們將二元表達式的左右子表達式編譯成JavaScript的函數，然後外面再用JavaScript代碼包裹。當這段代碼真正執行的時候，左右子表達式的js函數都會被調用，得到值，然後兩個值做加法、乘法或者比較運算。讓我們以x * y為例，看看編譯過程：
>> Multiply.new(Variable.new(:x), Variable.new(:y)).to_javascript
=> "function (e) { return function (e) { return e[\"x\"]; }(e) *
function (e) { return e[\"y\"]; }(e); }"
然後將編譯得到的JavaScript代碼（和上面一樣，只是看起來更美觀）放到支持的環境中運行：
> program = function (e) {
return function (e) {
return e["x"];
}(e) * function (e) {
return e["y"];
}(e);
}
[Function]
> program({ x: 2, y: 3 })
6
接下來是語句的#to_javascript，If用的是JavaScript的條件語句，While是JavaScript的循環，諸如此類。最外面和表達式一樣用一個JavaScript函數包裹，該函數接受一個環境e，語句可以更新環境。
class Assign
def to_javascript
"function (e) { e[#{JSON.dump(name)}] = #{expression.to_javascript}(e); return e; }"
end
end
class If
def to_javascript
"function (e) { if (#{condition.to_javascript}(e))" +
" { return #{consequence.to_javascript}(e); }" +
" else { return #{alternative.to_javascript}(e); }" +
' }'
end
end
class Sequence
def to_javascript
"function (e) { return #{second.to_javascript}(#{first.to_javascript}(e)); }"
end
end
class While
def to_javascript
'function (e) {' +
" while (#{condition.to_javascript}(e)) { e = #{body.to_javascript}(e); }" +
' return e;' +
' }'
end
end
之前我們試過解釋器解釋x = 1; while (x < 5) { x = x * 3 }，現在我們試試編譯器編譯：
>> SimpleParser.new.parse('x = 1; while (x < 5) { x = x * 3 }').
to_ast.to_javascript
=> "function (e) { return function (e) { while (function (e)
{ return function (e) { return e[\"x\"]; }(e) < function (e)
{ return 5; }(e); }(e)) { e = function (e) { e[\"x\"] =
function (e) { return function (e) { return e[\"x\"]; }(e) *
function (e) { return 3; }(e); }(e); return e; }(e); } return
e; }(function (e) { e[\"x\"] = function (e) { return 1; }(e);
return e; }(e)); }"
儘管編譯后的代碼比源程序還長，但是至少我們已經將SIMPLE代碼轉換為了JavaScript代碼。如果我們在JavaScript的環境中運行編譯后的代碼，我們會獲得和解釋執行一樣的結果——x最終是9:
> program = function (e) {
return function (e) {
while (function (e) {
return function (e) {
return e["x"];
}(e) < function (e) {
return 5;
}(e);
}(e)) {
e = function (e) {
e["x"] = function (e) {
return function (e) {
return e["x"];
}(e) * function (e) {
return 3;
}(e);
}(e);
return e;
}(e);
}
return e;
}(function (e) {
e["x"] = function (e) { return 1; }(e);
return e;
}(e));
}
[Function]
> program({})
{ x: 9 }
這個編譯器相當的傻——想讓它聰明些需要付出更多的努力——但是它向我們展示了如何在只能運行JavaScript的機器上執行SIMPLE程序。
編譯器是雙階段執行（two-stage execution）。首先我們提供源程序，編譯器接受它並生成目標程序作為輸出。接下來，我們拿出目標程序，給它一些輸入，然後允許它，得到最終結果：
編譯和解釋的最終結果是一致的——源代碼加輸入都最終變成了輸出——但是它將執行過程分成了兩個階段。第一個階段是編譯時，當目標程序生成后，第二個階段是運行時，這一階段讀取輸入和目標程序，最終得到輸出。
好消息是一個好的編譯器生成的目標程序會比解釋器執行的更快。將計算過程分成兩個階段免除了運行時的解釋開銷：解析源代碼，構造AST，遍歷AST樹這些過程都在編譯時完成，它們不影響程序運行。
（編譯還有其它性能受益，比如編譯器可以使用更簡潔的數據結構和優化讓目標程序跑的更快，尤其是在確定了目標程序運行的機器的情況下。）
壞消息是編譯會比解釋更難實現，原因有很多：
- 編譯器必須要考慮兩個階段。當我們寫解釋器的時候，我們只需要關心解釋器的執行，但是編譯器還需要考慮到它生成的代碼在運行時的行為
- 編譯器開發者需要懂兩門編程語言。解釋器用一門編程語言編寫，運行也是這一門語言，而我們的SIMPLE編譯器使用Ruby寫的，生成的目標程序代碼卻是JavaScript片段。
- 將動態語言編譯為高效的目標程序生來就難。像Ruby和JavaScript這種語言允許程序在運行時改變程序自身或者新增代碼，因此程序源碼的靜態表示沒有必要告訴編譯器它想知道的關於自己在運行時的情況。
總結來說，寫解釋器比寫編譯器要簡單，但是解釋程序比執行編譯后的程序要慢。解釋器只有一個階段，只用一門語言，並且動態語言也是沒問題的——如果程序在運行時自身改變了，這沒問題，因為AST可以同步更新，解釋器也工作正常——但是這種簡潔和靈活性會招致運行時性能懲罰。
理想情況下我們想只寫一個解釋器，但是我們程序要想運行的快一些，通常還是需要再寫個編譯器。
部分求值
程序員總是使用解釋器和編譯器，但還有另一種操縱程序的程序不太為人所知：部分求值器。部分求值器是解釋器和編譯器的混合：
解釋器立即執行程序，編譯器生成程序稍後執行，而部分求值器立刻執行部分代碼，然後剩下的代碼稍後執行。
部分求值器讀取程序（又叫subject program）和程序的輸入，然後只執行部分代碼，這些代碼直接依賴輸入。當這些部分被求值后，剩下的程序部分（又叫residual program）作為輸出產出。
部分求值（partial evaluation）允許我們提取程序的一部分執行。現在我們不必一次提供程序的所有輸入，我們可以只提供一些，剩下的以後提供。
現在，我們不用一次執行整個subject program，我們可以將它和一些程序輸入放到部分求值器裏面。部分求值器將執行subject program的一部分，產生一個residual program；接下來，我們執行residual program，並給它剩下的程序輸入：
部分求值的總體效果是，通過將一些工作從未來（當我們打算運行程序時）移到現在，將單階段執行變成了兩個階段，程序運行時可以少執行一些代碼。
部分求值器將subject program轉換為AST，這一步和解釋器編譯器一樣，接着讀取程序的部分輸入。它分析整個AST找到哪些地方用到了程序的部分輸入，然後這些地方被求值，使用包含求值結果的代碼代替。當部分求值完成時，AST重新轉換為文本形式，即輸出為residual program。
真的構建一個部分求值器太龐大了，不太現實，但是我們可以通過一個示例來了解部分求值的過程。
假設有一個Ruby程序#power，它計算x的n次冪：
def power(n, x)
if n.zero?
1
else
x * power(n - 1, x)
end
end
現在讓我們扮演一個Ruby部分求值器的角色，假設我們已經獲得了足夠的程序輸入，知道將用實參5作為第一個形參n調用power。我們可以很容易地生成一個新版本的方法，稱之為#power_5，其中形參n已被刪除，所有出現n的地方都被替換為5（這也叫常量傳播）：
def power_5(x)
if 5.zero?
1
else
x * power(5 - 1, x)
end
end
我們找到了兩個表達式——5.zero?和5 - 1——這是潛在的部分求值對象。讓我們選一個，對5.zero?求值，用結果false代替這個表達式：
def power_5(x)
if false
1
else
x * power(5 - 1, x)
end
end
這個部分求值行為使得我們還能再求值整個條件語句——if false ... else ... end總是走else分支（稀疏常量傳播）：
def power_5(x)
x * power(5 - 1, x)
end
現在對5 - 1求值，用常量4代替（常量摺疊）：
def power_5(x)
x * power(4, x)
end
現在停一下，因為我們知道#power的行為，這裡有一個優化機會，用#power方法的代碼代替這裏的power(4,x)調用（內聯展開），然後再用4代替所有形參n
def power_5(x)
x *
if 4.zero?
1
else
x * power(4 - 1, x)
end
end
情況和之前一樣，我們知道4.zero?，用false代替：
def power_5(x)
x *
if false
1
else
x * power(4 - 1, x)
end
end
繼續，知道條件語句走else分支：
def power_5(x)
x *
x * power(4 - 1, x)
end
知道4 - 1的值是3:
def power_5(x)
x *
x * power(3, x)
end
如此繼續。通過將#power調用內聯，然後對常量表達式求值，我們能用乘法代替它們，直到0：
def power_5(x)
x *
x *
x *
x *
x * power(0, x)
end
讓我們再手動展開一次：
def power_5(x)
x *
x *
x *
x *
x *
if 0.zero?
1
else
x * power(0 - 1, x)
end
end
我們直到0.zero?是true：
def power_5(x)
x *
x *
x *
x *
x *
if true
1
else
x * power(0 - 1, x)
end
end
這是我們第一次在例子中遇到if true而不是if false的情況，現在選擇then分支，而不是else分支：
def power_5(x)
x *
x *
x *
x *
x *
1
end
最終效果是，我們把#power_5轉換為x重複乘以自身五次，然後乘以1。乘以1對計算沒有影響，所以可以消除它，最終得到的代碼如下：
def power_5(x)
x * x * x * x * x
end
下面是圖形化的過程：
#power加上程序輸入5，最終經過部分求值，得到residual program#power_5。沒有新的代碼產生，#power_5的代碼是由#power組成的，只是重新安排並以新的方式結合在一起。
#power_5的優勢是當輸入為5的時候它比#power跑的更快。#power_5簡單的重複乘以x五次，而#power是執行了五次遞歸的方法調用，零值檢查，條件計算和減法。這些工作都由部分求值器完成，然後結果保留在residual program中，現在redisual program只依賴未知的程序輸入x。
所以，如果我們直到n為5，那麼#power_5就是#power優化改進版。
注意部分求值和部分應用(partial application)是不一樣的。基於部分應用的#power_5和部分求值得到的residual program是不一樣的：
def power_5(x)
power(5, x)
end
通過部分應用，我們固定一個常量到代碼中，成功的將#power轉換為了#power_5，這個實現也是沒問題的：
>> power_5(2)
=> 32
但是這個版本的#power_5不見得比#power更高效——實際上它還會慢一些，因為它引入了額外的方法調用。
或者，我們也可以不定義新的方法，而是用Method#to_proc和Proc#curry將#power柯里化（currying）為一個過程，然後用實參5調用柯里化后的過程：
>> power_5 = method(:power).to_proc.curry.call(5)
=> #<Proc (lambda)>
接着，我們調用部分應用后的代碼，傳入的參數是#power的第二個形參，即x：
>> power_5.call(2)
=> 32
不難看出，部分應用和部分求值很像是，但是仔細審視后可以看出，部分應用是程序內的行為：當我們寫代碼時，部分應用允許我們固定一些參數，然後得到一個方法的更少參數的版本。而部分求值是程序外部的行為：它是一個源碼級別的轉換，通過特化一些程序輸入，可以得到更高效的方法的版本。
應用
部分求值有很多有用的應用場景。固定程序的一些輸入，即特化，可以提供兩方面的好處：我們可以編寫一個通用的、靈活的程序來支持許多不同的輸入，然後，當我們真正知道如何使用這個程序時，我們可以使用一個部分求值器來自動生成一個特化后的版本，該版本移除了代碼的通用性，但是提高了性能。
例如，像nginx或[Apache(http://httpd.apache.org/)這樣的web服務器在啟動時會讀取配置文件。該文件的內容會影響服務器後續每個HTTP請求的處理，因此web服務器必須花費一些執行時間來檢查其配置數據，以決定要做什麼。如果我們對web服務器使用部分求值器專門針對一個特定的配置文件進行部分求值，我們將得到一個新版本，它只執行該文件所說的操作；在啟動期間解析配置文件並在每個請求期間檢查其數據的開銷將不再是程序的一部分。
另一個經典的例子是光線跟蹤。要製作一部攝影機在三維場景中移動的電影，我們可能最終會使用光線跟蹤器渲染數千個單獨的幀。但是如果場景對於每一幀都是相同的，我們可以使用一個部分求值器來專門處理光線跟蹤器對於我們特定場景的描述，我們會得到一個新的光線跟蹤器，它只能渲染該場景。然後，每次我們使用專門的光線跟蹤器渲染幀時，都會避免讀取場景文件、設置表示其幾何體所需的數據結構以及對光線在場景中的行為做出與相機無關的決策的開銷。
一個更實際（有一些爭議）的例子是OpenGL管道。在OS X中，OpenGL管道的一部分是用LLVM中間語言編寫的，這其中包括一些GPU硬件就實現了的。不管GPU支持與否，都可以用軟件的方式實現，而有了部分求值，Apple公司可以對LLVM部分求值，刪除掉特定GPU上不需要的代碼，剩下的代碼是硬件沒有直接實現的。
二村映射
首先，我想說一個cool story。
1971年，Yoshihiko Futamura在Hitachi Central Research Laboratory工作時發表了一些有趣的論文。他在思考部分求值如何更早的處理subject program的一些輸入，然後產出後續可以執行的residual program。
具體來說，Futamura將解釋器作為部分求值的輸入並思考了一些問題。他意識到解釋器只是一個計算機程序而已，它讀取輸入，執行，然後得到輸出。解釋器的輸入之一是源碼，但是除了這個比較特別外解釋器和普通程序沒啥兩樣。
他在思考，如果我們先用部分求值器做一些解釋器的工作，會發生什麼？
如果我們使用部分求值器特化解釋器和它的某個程序的輸入，我們會得到residual program。然後，我們可以用程序的剩下的輸入加上residual program，得到最終結果：
最終效果和用解釋器直接運行程序一樣，只是現在單階段執行變成了兩階段。
Futamura注意到residual program讀取剩下的程序輸入，然後產生輸出，我們通常把這個residual program稱為目標程序——一個能被底層機器直接執行的源程序的新版本。這意味着部分求值器讀取源程序，產出目標程序，它實際上扮演了編譯器的角色。
看起來難以置信。它是怎麼工作的？讓我們看一個示例。下面是SIMPLE解釋器的top level環境：
source, environment = read_source, read_environment
Treetop.load('simple.treetop')
ast = SimpleParser.new.parse(source).to_ast
puts ast.evaluate(environment)
解釋器讀取源程序和初始化environment（從哪讀的我們不關心）。它加載Treetop語法文件，實例化解析器，然後解析器產出AST，然後對AST求值並輸出。#evaluate的定義和前面解釋器小結是一樣的。
讓我們想象一下將這個解釋器和SIMPLE源代碼 x = 2; y = x * 3作為輸入放入Ruby部分求值器。這意味這上面代碼中的#read_source將返回字符串 x = 2; y = x * 3，所以我們可以用字符串代替它：
source, environment = 'x = 2; y = x * 3', read_environment
Treetop.load('simple.treetop')
ast = SimpleParser.new.parse(source).to_ast
puts ast.evaluate(environment)
現在，讓我手動做一下複寫傳播，由於source變量只在代碼中用到了一次，我們可以完全消除它，用值代替：
environment = read_environment
Treetop.load('simple.treetop')
ast = SimpleParser.new.parse('x = 2; y = x * 3').to_ast
puts ast.evaluate(environment)
構造AST的數據都已經備起了，Treetop語法文件也準備好了，現在我們還知道待解析的字符串是什麼。讓我們手動求值表達式，創建一個手工AST代替解析過程：
environment = read_environment
ast = Sequence.new(
Assign.new(
:x,
Number.new(2)
),
Assign.new(
:y,
Multiply.new(
Variable.new(:x),
Number.new(3)
)
)
)
puts ast.evaluate(environment)
我們將解釋器簡化為讀取環境、構建AST字面值、在AST根節點上調用#evaluate。
在特定節點上調用#evaluate會發生什麼？我們早已直到每種節點的#evaluate定義，現在可以遍歷樹，然後找到AST節點的#evaluate調用，進行部分求值，和我們之前對#power做的差不多。AST包含了所有我們需要的數據，所以我們可以逐步將所有的#evaluate歸納為幾行Ruby代碼：
對於Number和Variable，我們直到它的值和變量名字，所以我們可以將這些信息傳播到其它節點。對於Multiply和Assign節點，我們可以內聯方法調用。對於序列語句，我們可以先內聯first.evaluate再內聯second.evaluate，使用臨時變量保持中間environment。
下面的代碼隱藏了大量的細節，但重要的是，我們擁有最終代碼和數據，它們可以幫助我們對AST根節點的#evaluate方法進行部分求值：
def evaluate(environment)
environment = environment.merge({ :x => 2 })
environment.merge({ :y => environment[:x] * 3 })
end
讓我們回到解釋器的主要代碼：
environment = read_environment
ast = Sequence.new(
Assign.new(
:x,
Number.new(2)
),
Assign.new(
:y,
Multiply.new(
Variable.new(:x),
Number.new(3)
)
)
)
puts ast.evaluate(environment)
既然我們已經生成了AST根節點的#evaluate方法，現在我們可以對ast.evaluate(environment)部分求值，方法是展開這個調用：
environment = read_environment
environment = environment.merge({ :x => 2 })
puts environment.merge({ :y => environment[:x] * 3 })
這個Ruby代碼和原始的SIMPLE代碼產生了相同的行為：它將x設置為2，將y設置為x乘以3，x和y都存放到environment中。所以，從某種意義上說，我們通過對解釋器進行部分求值，將SIMPLE程序編譯為Ruby代碼——雖然還有一些其它environment的內容，但是總之，我們最終的Ruby代碼做的還是x = 2; y = x * 3這件事。
和#power那個例子一樣，我們沒有寫Ruby代碼，residual program是重新安排解釋器的代碼並以新的方式結合在一起，這樣它就完成了與最初的SIMPLE程序相同的功能。
這種方式被稱為第一二村映射(first futamura projection)：如果我們將源代碼和解釋器一起進行部分求值，我們將得到目標程序。
Futamura很高興他意識到了這一點。然後他繼續思考更多，他繼續意識到將源代碼和解釋器一起進行部分求值得到目標程序這件事本身，其實就是給一個程序多個參數。如果我們先使用部分求值來完成部分求值器的一些工作，然後通過運行剩餘程序來完成其餘的工作，會發生什麼情況？
如果我們用部分求值來特化部分求值器的一個輸入—— 解釋器——我們會得到residual program。然後後面我們可以運行這個residual program，將源程序作為輸入，得到目標程序，最後運行目標程序，傳入剩餘程序輸入，得到最終結果：
總體的效果與給出程序輸入，直接用解釋器運行源程序行為一致，但現在執行已分為三個階段。
Futamura注意到residual program讀取源程序產生目標程序，這個過程是我們常說的編譯器做的事情。這意味着部分求值器將解釋器作為輸入，輸出來編譯器。換句話說，部分求值器此時成了編譯器生成器。
這種方式被稱為第二二村映射(second futamura projection)：如果我們將部分求值器和解釋器一起進行部分求值，我們將得到編譯器。
Futamura很高興他意識到了這一點。然後他繼續思考更多，他繼續意識到將部分求值器和解釋器一起進行部分求值得到編譯器這件事本身，其實就是給一個程序多個參數。如果我們先使用部分求值來完成部分求值器的一些工作，然後通過運行剩餘程序來完成其餘的工作，會發生什麼情況？
如果我們用部分求值來特化部分求值器的一個輸入—— 部分求值器——我們會得到residual program。然後後面我們可以運行這個residual program，將解釋器作為輸入，得到編譯器，最後運行編譯器，將源程序作為輸入得到目標程序，在運行目標程序，給它剩下的程序輸入，得到最終結果：
總體的效果與給出程序輸入，直接用解釋器運行源程序行為一致，但現在執行已分為四個階段。
Futamura注意到residual program讀取解釋器產生編譯器，這個過程是我們常說的編譯器做的事情。這意味着部分求值器產出來一個編譯器生成器。換句話說，部分求值器此時成了編譯器生成器的生成器。
這種方式被稱為第三二村映射(third futamura projection)：如果我們將部分求值器和部分求值器一起進行部分求值，我們將得到編譯器生成器。
謝天謝地，我們不能再進一步了，因為如果我們重複這個過程，我們仍然會對部分求值器本身進行部分求值。只有三個二村映射。
結論
二村映射非常有趣，但不是說有了它編譯器工程師就是多餘的了。部分求值是一種適用於任何計算機程序的完全通用的技術；當應用於解釋器時，它可以消除解析源代碼和操作AST的開銷，但它不會自動地發明和創造具備工業級水平的編譯器的數據結構和優化。 我們仍然需要聰明的人寫編譯器，使我們的程序盡可能快地運行。
如果你想了解更多關於部分求值的知識，有一本叫做“Partial Evaluation and Automatic Program Generation”的免費書籍詳細的討論了它。LLVM的JIT，PyPy工具鏈的一部分——即RPython和VM以及它底層依賴的JIT）——也使用相關技術讓程序更高效執行。這些項目與Ruby直接相關，因為Rubinius依賴LLVM，還有一個用Python編寫的Ruby實現，名為Topaz，也依賴PyPy工具鏈。
撇開部分求值不談，Rubinius和JRuby也是高質量的編譯器，代碼很有趣，可以免費下載。如果你對操縱程序的程序感興趣，你可以深入Rubinius或JRuby，看看它們是如何工作的，並且（根據Matz的RubyConf 2013主題演講提到的）參与它們的開發。
本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理
【其他文章推薦】
※網頁設計公司推薦不同的風格，搶佔消費者視覺第一線
※廣告預算用在刀口上，台北網頁設計公司幫您達到更多曝光效益
※自行創業缺乏曝光? 網頁設計幫您第一時間規劃公司的形象門面
※南投搬家公司費用需注意的眉眉角角，別等搬了再說!
※教你寫出一流的銷售文案?
