在《如何設(shè)計(jì)一門語言》里面，我講了一些語言方面的東西，還有痛快的噴了一些XX粉什么的。不過單純講這個(gè)也是很無聊的，所以我開了這個(gè)《跟vczh看實(shí)例學(xué)編譯原理》系列，意在科普一些編譯原理的知識(shí)，盡量讓大家可以在創(chuàng)造語言之后，自己寫一個(gè)原型。在這里我拿我創(chuàng)造的一門很有趣的語言 https://github.com/vczh/tinymoe/ 作為實(shí)例。
商業(yè)編譯器對(duì)功能和質(zhì)量的要求都是很高的，里面大量的東西其實(shí)都跟編譯原理沒關(guān)系。一個(gè)典型的編譯原理的原型有什么特征呢？
性能低
錯(cuò)誤信息難看
沒有檢查所有情況就生成代碼
優(yōu)化做得爛
幾乎沒有編譯選項(xiàng)
等等。Tinymoe就滿足了上面的5種情況，因?yàn)槲业哪繕?biāo)也只是想做一個(gè)原型，向大家介紹編譯原理的基礎(chǔ)知識(shí)。當(dāng)然，我對(duì)語法的設(shè)計(jì)還是盡量靠近工業(yè)質(zhì)量的，只是實(shí)現(xiàn)沒有花太多心思。
為什么我要用Tinymoe來作為實(shí)例呢？因?yàn)門inymoe是少有的一種用起來簡(jiǎn)單，而且?guī)炜梢杂卸鄰?fù)雜寫多復(fù)雜的語言，就跟C++一樣。C++11額標(biāo)準(zhǔn)庫在一起用簡(jiǎn)直是愉快啊，Tinymoe的代碼也是這么寫的。但是這并不妨礙你可以在寫C++庫的時(shí)候發(fā)揮你的想象力。Tinymoe也是一樣的。為什么呢，我來舉個(gè)例子。
Hello, world!
Tinymoe的hello world程序是很簡(jiǎn)單的：
module hello world
using standard library
sentence print (message)
redirect to "printf"
end
phrase main
print "Hello, world!"
end
module指的是模塊的名字，普通的程序也是一個(gè)模塊。using指的是你要引用的模塊——standard library就是Tinymoe的STL了——當(dāng)然這個(gè)程序并沒有用到任何standard library的東西。說到這里大家可能意識(shí)到了，Tinymoe的名字可以是不定長的token組成的！沒錯(cuò)，后面大家會(huì)慢慢意識(shí)到這種做法有多么的強(qiáng)大。
后面是print函數(shù)和main函數(shù)。Tinymoe是嚴(yán)格區(qū)分語句和表達(dá)式的，只有sentence和block開頭的函數(shù)才能作為語句，而且同時(shí)只有phrase開頭的函數(shù)才能作為表達(dá)式。所以下面的程序是不合法的：
phrase main
(print "Hello, world!") + 1
end
原因就是，print是sentence，不能作為表達(dá)式使用，因此他不能被+1。
Tinymoe的函數(shù)參數(shù)都被寫在括號(hào)里面，一個(gè)參數(shù)需要一個(gè)括號(hào)。到了這里大家可能會(huì)覺得很奇怪，不過很快就會(huì)有解答了。為什么要這么做，下一個(gè)例子就會(huì)告訴我們。
print函數(shù)用的redirect to是Tinymoe聲明FFI（Foreign Function Interface）的方法，也就是說，當(dāng)你運(yùn)行了print，他就會(huì)去host里面找一個(gè)叫做printf的函數(shù)來運(yùn)行。不過大家不要誤會(huì)，Tinymoe并沒有被設(shè)計(jì)成可以直接調(diào)用C函數(shù)，所以這個(gè)名字其實(shí)是隨便寫的，只要host提供了一個(gè)叫做printf的函數(shù)完成printf該做的事情就行了。main函數(shù)就不用解釋了，很直白。
1加到100等于5050
這個(gè)例子可以在Tinymoe的主頁（https://github.com/vczh/tinymoe/）上面看到：
module hello world
using standard library
sentence print (message)
redirect to "printf"
end
phrase sum from (start) to (end)
set the result to 0
repeat with the current number from start to end
add the current number to the result
end
end
phrase main
print "1+ ... +100 = " & sum from 1 to 100
end
為什么名字可以是多個(gè)token？為什么每一個(gè)參數(shù)都要一個(gè)括號(hào)？看加粗的部分就知道了！正是因?yàn)門inymoe想讓每一行代碼都可以被念出來，所以才這么設(shè)計(jì)的。當(dāng)然，大家肯定都知道怎么算start + (start+1) + … + (end-1) + end了，所以應(yīng)該很容易就可以看懂這個(gè)函數(shù)里面的代碼具體是什么意思。
在這里可以稍微多做一下解釋。the result是一個(gè)預(yù)定義的變量，代表函數(shù)的返回值。只要你往the result里面寫東西，只要函數(shù)一結(jié)束，他就變成函數(shù)的返回值了。Tinymoe的括號(hào)沒有什么特殊意思，就是改變優(yōu)先級(jí)，所以那一句循環(huán)則可以通過添加括號(hào)的方法寫成這樣：
repeat with (the current number) from (start) to (end)
大家可能會(huì)想，repeat with是不是關(guān)鍵字？當(dāng)然不是！repeat with是standard library里面定義的一個(gè)block函數(shù)。大家知道block函數(shù)的意思了吧，就是這個(gè)函數(shù)可以帶一個(gè)block。block有一些特性可以讓你寫出類似try-catch那樣的幾個(gè)block連在一起的大block，特別適合寫庫。
到了這里大家心中可能會(huì)有疑問，循環(huán)為什么可以做成庫呢？還有更加令人震驚的是，break和continue也不是關(guān)鍵字，是sentence！因?yàn)閞epeat with是有代碼的：
category
start REPEAT
closable
block (sentence deal with (item)) repeat with (argument item) from (lower bound) to (upper bound)
set the current number to lower bound
repeat while the current number <= upper bound
deal with the current number
add 1 to the current number
end
end
前面的category是用來定義一些block的順序和包圍結(jié)構(gòu)什么的。repeat with是屬于REPEAT的，而break和continue聲明了自己只能直接或者間接方在REPEAT里面，因此如果你在一個(gè)沒有循環(huán)的地方調(diào)用break或者continue，編譯器就會(huì)報(bào)錯(cuò)了。這是一個(gè)花邊功能，用來防止手誤的。
大家可能會(huì)注意到一個(gè)新東西：(argument item)。argument的意思指的是，后面的item是block里面的代碼的一個(gè)參數(shù)，對(duì)于repeat with函數(shù)本身他不是一個(gè)參數(shù)。這就通過一個(gè)很自然的方法給block添加參數(shù)了。如果你用ruby的話就得寫成這個(gè)悲催的樣子：
repeat_with(1, 10) do |item|
xxxx
end
而用C++寫起來就更悲催了：
repeat_with(1, 10, [](int item)
{
xxxx
});
block的第一個(gè)參數(shù)sentence deal with (item)就是一個(gè)引用了block中間的代碼的委托。所以你會(huì)看到代碼里面會(huì)調(diào)用它。
好了，那repeat while總是關(guān)鍵字了吧——不是！后面大家還會(huì)知道，就連
if xxx
yyy
else if zzz
www
else if aaa
bbb
else
ccc
end
也只是你調(diào)用了if、else if和else的一系列函數(shù)然后讓他們串起來而已。
那Tinymoe到底提供了什么基礎(chǔ)設(shè)施呢？其實(shí)只有select-case和遞歸。用這兩個(gè)東西，加上內(nèi)置的數(shù)組，就圖靈完備了。圖靈完備就是這么容易啊。
多重分派（Multiple Dispatch）
講到這里，我不得不說，Tinymoe也可以寫類，也可以繼承，不過他跟傳統(tǒng)的語言不一樣的，類是沒有構(gòu)造函數(shù)、析構(gòu)函數(shù)和其他成員函數(shù)的。Tinymoe所有的函數(shù)都是全局函數(shù)，但是你可以使用多重分派來"挑選"類型。這就需要第三個(gè)例子了（也可以在主頁上找到）：
module geometry
using standard library
phrase square root of (number)
redirect to "Sqrt"
end
sentence print (message)
redirect to "Print"
end
type rectangle
width
height
end
type triangle
a
b
c
end
type circle
radius
end
phrase area of (shape)
raise "This is not a shape."
end
phrase area of (shape : rectangle)
set the result to field width of shape * field height of shape
end
phrase area of (shape : triangle)
set a to field a of shape
set b to field b of shape
set c to field c of shape
set p to (a + b + c) / 2
set the result to square root of (p * (p - a) * (p - b) * (p - c))
end
phrase area of (shape : circle)
set r to field radius of shape
set the result to r * r * 3.14
end
phrase (a) and (b) are the same shape
set the result to false
end
phrase (a : rectangle) and (b : rectangle) are the same shape
set the result to true
end
phrase (a : triangle) and (b : triangle) are the same shape
set the result to true
end
phrase (a : circle) and (b : circle) are the same shape
set the result to true
end
phrase main
set shape one to new triangle of (2, 3, 4)
set shape two to new rectangle of (1, 2)
if shape one and shape two are the same shape
print "This world is mad!"
else
print "Triangle and rectangle are not the same shape!"
end
end
這個(gè)例子稍微長了一點(diǎn)點(diǎn)，不過大家可以很清楚的看到我是如何定義一個(gè)類型、創(chuàng)建他們和訪問成員變量的。area of函數(shù)可以計(jì)算一個(gè)平面幾何圖形的面積，而且會(huì)根據(jù)你傳給他的不同的幾何圖形而使用不同的公式。當(dāng)所有的類型判斷都失敗的時(shí)候，就會(huì)掉進(jìn)那個(gè)沒有任何類型聲明的函數(shù)，從而引發(fā)一場(chǎng)。嗯，其實(shí)try/catch/finally/raise都是函數(shù)來的——Tinymoe對(duì)控制流的控制就是如此強(qiáng)大，啊哈哈哈哈。就連return都可以自己做，所以Tinymoe也不提供預(yù)定義的return。
那phrase (a) and (b) are the same shape怎么辦呢？沒問題，Tinymoe可以同時(shí)指定多個(gè)參數(shù)的類型。而且Tinymoe的實(shí)現(xiàn)具有跟C++虛函數(shù)一樣的性質(zhì)——無論你有多少個(gè)參數(shù)標(biāo)記了類型，我都可以O(shè)(n)跳轉(zhuǎn)到一個(gè)你需要的函數(shù)。這里的n指的是標(biāo)記了類型的參數(shù)的個(gè)數(shù)，而不是函數(shù)實(shí)例的個(gè)數(shù)，所以跟C++的情況是一樣的——因?yàn)閠his只能有一個(gè)，所以就是O(1)。至于Tinymoe到底是怎么實(shí)現(xiàn)的，只需要看《如何設(shè)計(jì)一門語言》第五篇（http://www.shnenglu.com/vczh/archive/2013/05/25/200580.html）就有答案了。
Continuation Passing Style
為什么Tinymoe的控制流都可以自己做呢？因?yàn)門inymoe的函數(shù)都是寫成了CPS這種風(fēng)格的。其實(shí)CPS大家都很熟悉，當(dāng)你用jquery做動(dòng)畫，用node.js做IO的時(shí)候，那些嵌套的一個(gè)一個(gè)的lambda表達(dá)式，就有點(diǎn)CPS的味道。不過在這里我們并沒有看到嵌套的lambda，這是因?yàn)門inymoe提供的語法，讓Tinymoe的編譯器可以把同一個(gè)層次的代碼，轉(zhuǎn)成嵌套的lambda那樣的代碼。這個(gè)過程就叫CPS變換。Tinymoe雖然用了很多函數(shù)式編程的手段，但是他并不是一門函數(shù)是語言，只是一門普通的過程式語言。但是這跟C語言不一樣，因?yàn)樗BC#的yield return都可以寫成函數(shù)！這個(gè)例子就更長了，大家可以到Tinymoe的主頁上看。我這里只貼一小段代碼：
module enumerable
using standard library
symbol yielding return
symbol yielding break
type enumerable collection
body
end
type collection enumerator
current yielding result
body
continuation
end
略（這里實(shí)現(xiàn)了跟enumerable相關(guān)的函數(shù)，包括yield return）
block (sentence deal with (item)) repeat with (argument item) in (items : enumerable collection)
set enumerator to new enumerator from items
repeat
move enumerator to the next
deal with current value of enumerator
end
end
sentence print (message)
redirect to "Print"
end
phrase main
create enumerable to numbers
repeat with i from 1 to 10
print "Enumerating " & i
yield return i
end
end
repeat with number in numbers
if number >= 5
break
end
print "Printing " & number
end
end
什么叫模擬C#的yield return呢？就是連惰性計(jì)算也一起模擬！在main函數(shù)的第一部分，我創(chuàng)建了一個(gè)enumerable（iterator），包含1到10十個(gè)數(shù)字，而且每產(chǎn)生一個(gè)數(shù)字還會(huì)打印出一句話。但是接下來我在循環(huán)里面只取前5個(gè)，打印前4個(gè)，因此執(zhí)行結(jié)果就是
當(dāng)！
CPS風(fēng)格的函數(shù)的威力在于，每一個(gè)函數(shù)都可以控制他如何執(zhí)行函數(shù)結(jié)束之后寫在后面的代碼。也就是說，你可以根據(jù)你的需要，干脆選擇保護(hù)現(xiàn)場(chǎng)，然后以后再回復(fù)。是不是聽起來很像lua的coroutine呢？在Tinymoe，coroutine也可以自己做！
雖然函數(shù)最后被轉(zhuǎn)換成了CPS風(fēng)格的ast，而且測(cè)試用的生成C#代碼的確也是原封不動(dòng)的輸出了出來，所以運(yùn)行這個(gè)程序耗費(fèi)了大量的函數(shù)調(diào)用。但這并不意味著Tinymoe的虛擬機(jī)也要這么做。大家要記住，一個(gè)語言也好，類庫也好，給你的接口的概念，跟實(shí)現(xiàn)的概念，有可能完全不同。yield return寫出來的確要花費(fèi)點(diǎn)心思，所以《序言》我也不講這么多了，后續(xù)的文章會(huì)詳細(xì)介紹這方面的知識(shí)，當(dāng)然了，還會(huì)告訴你怎么實(shí)現(xiàn)的。
尾聲
這里我挑選了四個(gè)例子來展示Tinymoe最重要的一些概念。一門語言，要應(yīng)用用起來簡(jiǎn)單，庫寫起來可以發(fā)揮想象力，才是有前途的。yield return例子里面的main函數(shù)一樣，用的時(shí)候多清爽，清爽到讓你完全忘記yield return實(shí)現(xiàn)的時(shí)候里面的各種麻煩的細(xì)節(jié)。
所以為什么我要挑選Tinymoe作為實(shí)例來科普編譯原理呢？有兩個(gè)原因。第一個(gè)原因是，想要實(shí)現(xiàn)Tinymoe，需要大量的知識(shí)。所以既然這個(gè)系列想讓大家能夠看完實(shí)現(xiàn)一個(gè)Tinymoe的低質(zhì)量原型，當(dāng)然會(huì)講很多知識(shí)的。第二個(gè)原因是，我想通過這個(gè)例子向大家將一個(gè)道理，就是庫和應(yīng)用 、編譯器和語法、實(shí)現(xiàn)和接口，完全可以做到隔離復(fù)雜，只留給最終用戶簡(jiǎn)單的部分。你看到的復(fù)雜的接口，并不意味著他的實(shí)現(xiàn)是臃腫的。你看到的簡(jiǎn)單的接口，也不意味著他的實(shí)現(xiàn)就很簡(jiǎn)潔。
Tinymoe目前已經(jīng)可以輸出C#代碼來執(zhí)行了。后面我還會(huì)給Tinymoe加上靜態(tài)分析和類型推導(dǎo)。對(duì)于這類語言做靜態(tài)分析和類型推導(dǎo)又很多麻煩，我現(xiàn)在還沒有完全搞明白。譬如說這種可以自己控制continuation的函數(shù)要怎么編譯成狀態(tài)機(jī)才能避免掉大量的函數(shù)調(diào)用，就不是一個(gè)容易的問題。所以在系列一邊做的時(shí)候，我還會(huì)一邊研究這個(gè)事情。如果到時(shí)候系列把編譯部分寫完的同時(shí)，這些問題我也搞明白的話，那我就會(huì)讓這個(gè)系列擴(kuò)展到包含靜態(tài)分析和類型推導(dǎo)，繼續(xù)往下講。