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