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