自從《序》胡扯了快一個月之后，終于迎來了正片。之所以系列文章叫《看實例學編譯原理》，是因為整個系列會通過帶大家一步一步實現Tinymoe的過程，來介紹編譯原理的一些知識點。
但是第一個系列還沒到開始處理Tinymoe源代碼的時候，首先的跟大家講一講我設計Tinymoe的故事。為什么這種東西要等到現在才講呢，因為之前沒有文檔，將了也是白講啊。Tinymoe在github的wiki分為兩部分，一部分是介紹語法的，另一部分是介紹一個最小的標準庫是如何實現出來的，地址在 https://github.com/vczh/tinymoe/wiki 不帶問號的那些都是寫完了的。
系列文章的目標
在介紹Tinymoe之前，先說一下這個系列文章的目標。Ideally，只要一個人看完了這個系列，他就可以在下面這些地方得到入門：
當然，這并不能讓你成為一個大牛，但是至少自己做做實驗，搞一點高大上的東西騙師妹們是沒有問題了。
Tinymoe設計的目標
雖然想法很多年前就已經有了，但是這次我想把它實現出來，是為了完成《如何設計一門語言》的后續。光講大道理是沒有意義的，至少得有一個例子，讓大家知道這些事情到底是什么樣子的。因此Tinymoe有一點教學的意義，不管是使用它還是實現它。
首先，處理Tinymoe需要的知識點多，用于編譯原理教學。既然是為了展示編譯原理的基礎知識，因此語言本身不可能是那種爛大街的C系列的東西。當然除了知識點以外，還會讓大家深刻的理解到，難實現和難用，是完全沒有關系的！Tinymoe用起來可爽了，啊哈哈哈哈哈。
其次，Tinymoe容易嵌入其他語言的程序，作為DSL使用，可以調用宿主程序提供的功能。這嚴格的來講不算語言本身的功能，而是實現本身的功能。就算是C++也可以設計為嵌入式，lua也可以被設計為編譯成exe的。一個語言本身的設計并不會對如何使用它有多大的限制。為了讓大家看了這個系列之后，可以寫出至少可用的東西，而不僅僅是寫玩具，因此這也是設計的目標之一。
第三，Tinymoe語法優化于描述復雜的邏輯，而不是優化與復雜的數據結構和算法（雖然也可以）。Tinymoe本身是不存在任何細粒度控制內存的能力的，而且雖然可以實現復雜的數據結構和算法，但是本身描述這些東西最多也就跟JavaScript一樣容易——其實就是不容易。但是Tinymoe設計的時候，是為了讓大家把Tinymoe當成是一門可以設計DSL的語言，因此對復雜邏輯的描述能力特別強。唯一的前提就是，你懂得如何給Tinymoe寫庫。很好的使用和很好地實現一個東西是相輔相成的。我在設計Tinymoe之初，很多pattern我也不知道，只是因為設計Tinymoe遵循了科學的方法，因此最后我發現Tinymoe竟然具有如此強大的描述能力。當然對于讀者們本身，也會在閱讀系列文章的有類似的感覺。
最后，Tinymoe是一個動態類型語言。這純粹是我的個人愛好了。對一門動態類型語言做靜態分析那該多有趣啊，啊哈哈哈哈哈哈。
Tinymoe的設計哲學
當然我并不會為了寫文章就無線提高Tinymoe的實現難度的。為了把他控制在一個正常水平，因此設計Tinymoe的第一條就是：
一、小規模的語言核心+大規模的標準庫
其實這跟C++差不多。但是C++由于想做的事情實在是太多了，譬如說視圖包涵所有范式等等，因此就算這么做，仍然讓C++本身包含的東西過于巨大（其實我還是覺得C++不難怎么辦）。
語言核心小，實現起來當然容易。但是你并不能為了讓語言核心小就犧牲什么功能。因此精心設計一個核心是必須的，因為所有你想要但是不想加入語言的功能，從此就可以用庫來實現了。
譬如說，Tinymoe通過有條件地暴露continuation，要求編譯器在編譯Tinymoe的時候做一次全文CPS變換。這個東西說容易也不是那么容易，但是至少比你做分支循環異常處理什么的全部加起來要簡單多了吧。所以我只提供continuation，剩下的控制流全部用庫來做。這樣有三個好處：
語言簡單，實現難度降低。
為了讓庫可以發揮應有的作用，語言的功能的選擇十分的正交化。不過這仍然在一定的程度上提高了學習的難度。但是并不是所有人都需要寫庫對吧，很多人只需要會用庫就夠了。通過一點點的犧牲，正交化可以充分發揮程序員的想象能力。這對于以DSL為目的的語言來說是不可或缺的。
標準庫本身可以作為編譯器的測試用例。你只需要準備足夠多的測試用例來運行標準庫，那么你只要用C++（假設你用C++來實現Tinymoe）來跑他們，那所有的標準庫都會得到運行。運行結果如果對，那你對編譯器的實現也就有信心了。為什么呢，因為標準庫大量的使用了語言的各種功能，而且是無節操的使用。如果這樣都能過，那普通的程序就更能過了。
說了這么多，那到底什么是小規模的語言核心呢？這在Tinymoe上有兩點體現。
第一點，就是Tinymoe的語法元素少。一個Tinymoe表達式無非就只有三類：函數調用、字面量和變量、操作符。字面量就是那些數字字符串什么的。當Tinymoe的函數的某一個參數指定為不定個數的時候你還得提供一個tuple。委托（在這里是函數指針和閉包的統稱）和數組雖然也是Tinymoe的原生功能之一，但是對他們的操作都是通過函數調用來實現的，沒有特殊的語法。
簡單地講，就是除了下面這些東西以外你不會見到別的種類的表達式了：
1
"text"
sum from 1 to 100
sum of (1, 2, 3, 4, 5)
(1+2)*(3+4)
true
一個Tinymoe語句的種類就更少了，要么是一個函數調用，要么是block，要么是連在一起的幾個block：
do something bad
repeat with x from 1 to 100
do something bad with x
end
try
do something bad
catch exception
do something worse
end
有人可能會說，那repeat和try-catch就不是語法元素嗎？這個真不是，他們是標準庫定義好的函數，跟你自己聲明的函數沒有任何特殊的地方。
這里其實還有一個有意思的地方："repeat with x from 1 to 100"的x其實是循環體的參數。Tinymoe是如何給你自定義的block開洞的呢？不僅如此，Tinymoe的函數還可以聲明"引用參數"，也就是說調用這個函數的時候你只能把一個變量放進去，函數里面可以讀寫這個變量。這些都是怎么實現的呢？學下去就知道了，啊哈哈哈哈。
Tinymoe的聲明也只有兩種，第一種是函數，第二種是符號。函數的聲明可能會略微復雜一點，不過除了函數頭以外，其他的都是類似配置一樣的東西，幾乎都是用來定義"catch函數在使用的時候必須是連在try函數后面"啊，"break只能在repeat里面用"啊，諸如此類的信息。
Tinymoe的符號十分簡單，譬如說你要定義一年四季的符號，只需要這么寫：
symbol spring
symbol summer
symbol autumn
symbol winter
symbol是一個"與眾不同的值"，也就是說你在兩個module下面定義同名的symbol他們也是不一樣的。所有symbol之間都是不一樣的，可以用=和<>來判斷。symbol就是靠"不一樣"來定義其自身的。
至于說，那為什么不用enum呢？因為Tinymoe是動態類型語言，enum的類型本身是根本沒有用武之地的，所以干脆就設計成了symbol。
第二點，Tinymoe除了continuation和select-case以外，沒有其他原生的控制流支持。
這基本上歸功于先輩發明continuation passing style transformation的功勞，細節在以后的系列里面會講。心急的人可以先看 https://github.com/vczh/tinymoe/blob/master/Development/Library/StandardLibrary.txt 。這個文件暫時包含了Tinymoe的整個標準庫，里面定義了很多if-else/repeat/try-catch-finally等控制流，甚至連coroutine都可以用continuation、select-case和遞歸來做。
這也是小規模的語言核心+大規模的標準庫所要表達的意思。如果可以提供一個feature A，通過他來完成其他必要的feature B0, B1, B2…的同時，將來說不定還有人可以出于自己的需求，開發DSL的時候定義feature C，那么只有A需要保留下來，所有的B和C都將使用庫的方法來實現。
這么做并不是完全有益無害的，只是壞處很小，在"Tinymoe的實現難點"里面會詳細說明。
二、擴展后的東西跟原生的東西外觀一致
這是很重要的。如果擴展出來的東西跟原生的東西長得不一樣，用起來就覺得很傻逼。Java的string不能用==來判斷內容就是這樣的一個例子。雖然他們有的是理由證明==的反直覺設計是對的——但是反直覺就是反直覺，就是一個大坑。
這種例子還有很多，譬如說go的數組和表的類型啦，go本身如果不要數組和表的話，是寫不出長得跟原生數組和表一樣的數組和表的。其實這也不是一個大問題，問題是go給數組和表的樣子搞特殊化，還有那個反直覺的slice的賦值問題（會合法溢出！），類似的東西實在是太多了。一個東西特例太多，坑就無法避免。所以其實在我看來，go還不如給C語言加上erlang的actor功能了事。
反而C++在這件事情上就做得很好。如果你對C++不熟悉的話，有時候根本分不清什么是編譯器干的，什么是標準庫干的。譬如說static_cast和dynamic_cast長得像一個模板函數，因此boost就可以用類似的手法加入lexical_cast和針對shared_ptr的static_pointer_cast和dynamic_pointer_cast，整個標準庫和語言本身渾然一體。這樣子做的好處是，當你在培養對語言本身的直覺的時候，你也在培養對標準庫的直覺，培養直覺這件事情你不用做兩次。你對一個東西的直覺越準，學習新東西的速度就越快。所以C++的設計剛好可以讓你在熬過第一個階段的學習之后，后面都覺得無比的輕松。
不過具體到Tinymoe，因為Tinymoe本身的語法元素太少了，所以這個做法在Tinymoe身上體現得不明顯。
Tinymoe的實現難點
首先，語法分析需要對Tinymoe程序處理三遍。Tinymoe對于語句設計使得對一個Tinymoe程序做語法分析不是那么直接（雖然比C++什么的還是容易多了）。舉個例子：
module hello world
phrase sum from (lower bound) to (upper bound)
…
end
sentence print (message)
…
end
phrase main
print sum from 1 to 100
end
第一遍分析是詞法分析，這個時候得把每一個token的行號記住。第二遍分析是不帶歧義的語法分析，目標是把所有的函數頭抽取出來，然后組成一個全局符號表。第三遍分析就是對函數體里面的語句做帶歧義的語法分析了。因為Tinymoe允許你定義變量，所以符號表肯定是一邊分析一邊修改的。于是對于"print sum from 1 to 100"這一句，如果你沒有發現"phrase sum from (lower bound) to (upper bound)"和"sentence print (message)"，那根本無從下手。
還有另一個例子：
module exception handling
…
phrase main
try
do something bad
catch
print "bad thing happened"
end
end
當語法分析做到"try"的時候，因為發現存在try函數的定義，所以Tinymoe知道接下來的"do something bad"屬于調用try這個塊函數所需提供的代碼塊里面的代碼。接下來是"catch"，Tinymoe怎么知道catch是接在try后面，而不是放在try里面的呢？這仍然是由于catch函數的定義告訴我們的。關于這方面的語法知識可以點擊這里查看。
正因為如此，我們需要首先知道函數的定義，然后才能分析函數體里面的代碼。雖然這在一定程度上造成了Tinymoe的語法分析復雜度的提升，但是其復雜度本身并不高。比C++簡單就不說了，就算是C、C#和Java，由于其語法元素太多，導致不需要多次分析所降低的復雜度被完全的抵消，結果跟實現Tinymoe的語法分析器的難度不相上下。
其次，CPS變換后的代碼需要特殊處理，否則直接執行容易導致call stack積累的沒用的東西過多。因為Tinymoe可以自定義操作符，所以操作符跟C++一樣在編譯的時候被轉換成了函數調用。每一個函數調用都是會被CPS變換的。盡管每一行的函數調用次數不多，但是如果你的程序油循環，循環是通過遞歸來描述（而不是實現，由于CPS變換后Tinymoe做了優化，所以不存在實際上的遞歸）的，如果直接執行CPS變換后的代碼，算一個1加到1000都會導致stack overflow。可見其call stack里面堆積的closure數量之巨大。
我在做Tinymoe代碼生成的實驗的時候，為了簡單我在單元測試里面直接產生了對應的C#代碼。一開始沒有處理CPS而直接調用，程序不僅慢，而且容易stack overflow。但是我們知道（其實你們以后才會知道），CPS變換后的代碼里面幾乎所有的call stack項都是浪費的，因此我把整個在生成C#代碼的時候修改成，如果需要調用continuation，就返回調用continuation的語句組成的lambda表達式，在最外層用一個循環去驅動他直到返回null為止。這樣做了之后，就算Tinymoe的代碼有遞歸，call stack里面也不會因為遞歸而積累call stack item了。于是生成的C#代碼執行飛快，而且無論你怎么遞歸也永遠不會造成stack overflow了。這個美妙的特性幾乎所有語言都做不到，啊哈哈哈哈哈。
當然這也是有代價的，因為本質上我只是把保存在stack上的context轉移到heap上。不過多虧了.net 4.0的強大的background GC，這樣做絲毫沒有多余的性能上的損耗。當然這也意味著，一個高性能的Tinymoe虛擬機，需要一個牛逼的垃圾收集器作為靠山。context產生的closure在函數體真的被執行完之后就會被很快地收集，所以CPS加上這種做法并不會對GC產生額外的壓力，所有的壓力仍然來源于你自己所創建的數據結構。
第三，Tinymoe需要動態類型語言的類型推導。當然你不這么做而把Tinymoe的程序當JavaScript那樣的程序處理也沒有問題。但是我們知道，正是因為V8對JavaScript的代碼進行了類型推導，才產生了那么優異的性能。因此這算是一個優化上的措施。
最后，Tinymoe還需要跨過程分析和對程序的控制流的化簡（譬如continuation轉狀態機等）。目前具體怎么做我還在學習當中。不過我們想，既然repeat函數是通過遞歸來描述的，那我們能不能通過對所有代碼進行inter-procedural analyzing，從而發現諸如
repeat 3 times
do something good
end
就是一個循環，從而生成用真正的循環指令（譬如說goto）呢？這個問題是個很有意思的問題，我覺得我如果可以通過學習靜態分析從而解決它，不進我的能力會得到提升，我對你們的科普也會做得更好。
后記
雖然還不到五千字，但是總覺得寫了好多的樣子。總之我希望讀者在看完《零》和《一》之后，對接下來需要學習的東西有一個較為清晰的認識。
posted on 2014-02-10 20:53
陳梓瀚(vczh) 閱讀(16370)
評論(11) 編輯 收藏 引用 所屬分類:
跟vczh看實例學編譯原理