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