自從《序》胡扯了快一個(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分為兩部分，一部分是介紹語法的，另一部分是介紹一個(gè)最小的標(biāo)準(zhǔn)庫是如何實(shí)現(xiàn)出來的，地址在 https://github.com/vczh/tinymoe/wiki 不帶問號(hào)的那些都是寫完了的。

系列文章的目標(biāo)

在介紹Tinymoe之前，先說一下這個(gè)系列文章的目標(biāo)。Ideally，只要一個(gè)人看完了這個(gè)系列，他就可以在下面這些地方得到入門：

• 詞法分析
• 歧義與不歧義的語法分析
• 語義分析
• 符號(hào)表
• 全文CPS變換
• 編譯生成高效的其他語言的代碼
• 編譯生成自己的指令集
• 帶GC的虛擬機(jī)
• 類型推導(dǎo)（intersection type，union type，concept mapping）
• 跨過程分析（inter-procedural analyzing）

當(dāng)然，這并不能讓你成為一個(gè)大牛，但是至少自己做做實(shí)驗(yàn)，搞一點(diǎn)高大上的東西騙師妹們是沒有問題了。

Tinymoe設(shè)計(jì)的目標(biāo)

雖然想法很多年前就已經(jīng)有了，但是這次我想把它實(shí)現(xiàn)出來，是為了完成《如何設(shè)計(jì)一門語言》的后續(xù)。光講大道理是沒有意義的，至少得有一個(gè)例子，讓大家知道這些事情到底是什么樣子的。因此Tinymoe有一點(diǎn)教學(xué)的意義，不管是使用它還是實(shí)現(xiàn)它。

首先，處理Tinymoe需要的知識(shí)點(diǎn)多，用于編譯原理教學(xué)。既然是為了展示編譯原理的基礎(chǔ)知識(shí)，因此語言本身不可能是那種爛大街的C系列的東西。當(dāng)然除了知識(shí)點(diǎn)以外，還會(huì)讓大家深刻的理解到，難實(shí)現(xiàn)和難用，是完全沒有關(guān)系的！Tinymoe用起來可爽了，啊哈哈哈哈哈。

其次，Tinymoe容易嵌入其他語言的程序，作為DSL使用，可以調(diào)用宿主程序提供的功能。這嚴(yán)格的來講不算語言本身的功能，而是實(shí)現(xiàn)本身的功能。就算是C++也可以設(shè)計(jì)為嵌入式，lua也可以被設(shè)計(jì)為編譯成exe的。一個(gè)語言本身的設(shè)計(jì)并不會(huì)對如何使用它有多大的限制。為了讓大家看了這個(gè)系列之后，可以寫出至少可用的東西，而不僅僅是寫玩具，因此這也是設(shè)計(jì)的目標(biāo)之一。

第三，Tinymoe語法優(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的語言，因此對復(fù)雜邏輯的描述能力特別強(qiáng)。唯一的前提就是，你懂得如何給Tinymoe寫庫。很好的使用和很好地實(shí)現(xiàn)一個(gè)東西是相輔相成的。我在設(shè)計(jì)Tinymoe之初，很多pattern我也不知道，只是因?yàn)樵O(shè)計(jì)Tinymoe遵循了科學(xué)的方法，因此最后我發(fā)現(xiàn)Tinymoe竟然具有如此強(qiáng)大的描述能力。當(dāng)然對于讀者們本身，也會(huì)在閱讀系列文章的有類似的感覺。

最后，Tinymoe是一個(gè)動(dòng)態(tài)類型語言。這純粹是我的個(gè)人愛好了。對一門動(dòng)態(tài)類型語言做靜態(tài)分析那該多有趣啊，啊哈哈哈哈哈哈。

Tinymoe的設(shè)計(jì)哲學(xué)

當(dāng)然我并不會(huì)為了寫文章就無線提高Tinymoe的實(shí)現(xiàn)難度的。為了把他控制在一個(gè)正常水平，因此設(shè)計(jì)Tinymoe的第一條就是：

一、小規(guī)模的語言核心+大規(guī)模的標(biāo)準(zhǔn)庫

其實(shí)這跟C++差不多。但是C++由于想做的事情實(shí)在是太多了，譬如說視圖包涵所有范式等等，因此就算這么做，仍然讓C++本身包含的東西過于巨大（其實(shí)我還是覺得C++不難怎么辦）。

語言核心小，實(shí)現(xiàn)起來當(dāng)然容易。但是你并不能為了讓語言核心小就犧牲什么功能。因此精心設(shè)計(jì)一個(gè)核心是必須的，因?yàn)樗心阆胍遣幌爰尤胝Z言的功能，從此就可以用庫來實(shí)現(xiàn)了。

譬如說，Tinymoe通過有條件地暴露continuation，要求編譯器在編譯Tinymoe的時(shí)候做一次全文CPS變換。這個(gè)東西說容易也不是那么容易，但是至少比你做分支循環(huán)異常處理什么的全部加起來要簡單多了吧。所以我只提供continuation，剩下的控制流全部用庫來做。這樣有三個(gè)好處：

1. 語言簡單，實(shí)現(xiàn)難度降低。
2. 為了讓庫可以發(fā)揮應(yīng)有的作用，語言的功能的選擇十分的正交化。不過這仍然在一定的程度上提高了學(xué)習(xí)的難度。但是并不是所有人都需要寫庫對吧，很多人只需要會(huì)用庫就夠了。通過一點(diǎn)點(diǎn)的犧牲，正交化可以充分發(fā)揮程序員的想象能力。這對于以DSL為目的的語言來說是不可或缺的。
3. 標(biāo)準(zhǔn)庫本身可以作為編譯器的測試用例。你只需要準(zhǔn)備足夠多的測試用例來運(yùn)行標(biāo)準(zhǔn)庫，那么你只要用C++（假設(shè)你用C++來實(shí)現(xiàn)Tinymoe）來跑他們，那所有的標(biāo)準(zhǔn)庫都會(huì)得到運(yùn)行。運(yùn)行結(jié)果如果對，那你對編譯器的實(shí)現(xiàn)也就有信心了。為什么呢，因?yàn)闃?biāo)準(zhǔn)庫大量的使用了語言的各種功能，而且是無節(jié)操的使用。如果這樣都能過，那普通的程序就更能過了。

說了這么多，那到底什么是小規(guī)模的語言核心呢？這在Tinymoe上有兩點(diǎn)體現(xiàn)。

第一點(diǎn)，就是Tinymoe的語法元素少。一個(gè)Tinymoe表達(dá)式無非就只有三類：函數(shù)調(diào)用、字面量和變量、操作符。字面量就是那些數(shù)字字符串什么的。當(dāng)Tinymoe的函數(shù)的某一個(gè)參數(shù)指定為不定個(gè)數(shù)的時(shí)候你還得提供一個(gè)tuple。委托（在這里是函數(shù)指針和閉包的統(tǒng)稱）和數(shù)組雖然也是Tinymoe的原生功能之一，但是對他們的操作都是通過函數(shù)調(diào)用來實(shí)現(xiàn)的，沒有特殊的語法。

簡單地講，就是除了下面這些東西以外你不會(huì)見到別的種類的表達(dá)式了：

1

"text"

sum from 1 to 100

sum of (1, 2, 3, 4, 5)

(1+2)*(3+4)

true

一個(gè)Tinymoe語句的種類就更少了，要么是一個(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就不是語法元素嗎？這個(gè)真不是，他們是標(biāo)準(zhǔn)庫定義好的函數(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)十分簡單，譬如說你要定義一年四季的符號(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)類型語言，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)庫，里面定義了很多if-else/repeat/try-catch-finally等控制流，甚至連coroutine都可以用continuation、select-case和遞歸來做。

這也是小規(guī)模的語言核心+大規(guī)模的標(biāo)準(zhǔn)庫所要表達(dá)的意思。如果可以提供一個(gè)feature A，通過他來完成其他必要的feature B0, B1, B2…的同時(shí)，將來說不定還有人可以出于自己的需求，開發(fā)DSL的時(shí)候定義feature C，那么只有A需要保留下來，所有的B和C都將使用庫的方法來實(shí)現(xiàn)。

這么做并不是完全有益無害的，只是壞處很小，在"Tinymoe的實(shí)現(xiàn)難點(diǎn)"里面會(huì)詳細(xì)說明。

二、擴(kuò)展后的東西跟原生的東西外觀一致

這是很重要的。如果擴(kuò)展出來的東西跟原生的東西長得不一樣，用起來就覺得很傻逼。Java的string不能用==來判斷內(nèi)容就是這樣的一個(gè)例子。雖然他們有的是理由證明==的反直覺設(shè)計(jì)是對的——但是反直覺就是反直覺，就是一個(gè)大坑。

這種例子還有很多，譬如說go的數(shù)組和表的類型啦，go本身如果不要數(shù)組和表的話，是寫不出長得跟原生數(shù)組和表一樣的數(shù)組和表的。其實(shí)這也不是一個(gè)大問題，問題是go給數(shù)組和表的樣子搞特殊化，還有那個(gè)反直覺的slice的賦值問題（會(huì)合法溢出?。?，類似的東西實(shí)在是太多了。一個(gè)東西特例太多，坑就無法避免。所以其實(shí)在我看來，go還不如給C語言加上erlang的actor功能了事。

反而C++在這件事情上就做得很好。如果你對C++不熟悉的話，有時(shí)候根本分不清什么是編譯器干的，什么是標(biāo)準(zhǔn)庫干的。譬如說static_cast和dynamic_cast長得像一個(gè)模板函數(shù)，因此boost就可以用類似的手法加入lexical_cast和針對shared_ptr的static_pointer_cast和dynamic_pointer_cast，整個(gè)標(biāo)準(zhǔn)庫和語言本身渾然一體。這樣子做的好處是，當(dāng)你在培養(yǎng)對語言本身的直覺的時(shí)候，你也在培養(yǎng)對標(biāo)準(zhǔn)庫的直覺，培養(yǎng)直覺這件事情你不用做兩次。你對一個(gè)東西的直覺越準(zhǔn)，學(xué)習(xí)新東西的速度就越快。所以C++的設(shè)計(jì)剛好可以讓你在熬過第一個(gè)階段的學(xué)習(xí)之后，后面都覺得無比的輕松。

不過具體到Tinymoe，因?yàn)門inymoe本身的語法元素太少了，所以這個(gè)做法在Tinymoe身上體現(xiàn)得不明顯。

Tinymoe的實(shí)現(xiàn)難點(diǎn)

首先，語法分析需要對Tinymoe程序處理三遍。Tinymoe對于語句設(shè)計(jì)使得對一個(gè)Tinymoe程序做語法分析不是那么直接（雖然比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)記住。第二遍分析是不帶歧義的語法分析，目標(biāo)是把所有的函數(shù)頭抽取出來，然后組成一個(gè)全局符號(hào)表。第三遍分析就是對函數(shù)體里面的語句做帶歧義的語法分析了。因?yàn)門inymoe允許你定義變量，所以符號(hào)表肯定是一邊分析一邊修改的。于是對于"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)語法分析做到"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)于這方面的語法知識(shí)可以點(diǎn)擊這里查看。

正因?yàn)槿绱?，我們需要首先知道函?shù)的定義，然后才能分析函數(shù)體里面的代碼。雖然這在一定程度上造成了Tinymoe的語法分析復(fù)雜度的提升，但是其復(fù)雜度本身并不高。比C++簡單就不說了，就算是C、C#和Java，由于其語法元素太多，導(dǎo)致不需要多次分析所降低的復(fù)雜度被完全的抵消，結(jié)果跟實(shí)現(xiàn)Tinymoe的語法分析器的難度不相上下。

其次，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í)候，為了簡單我在單元測試?yán)锩嬷苯赢a(chǎn)生了對應(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的語句組成的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è)美妙的特性幾乎所有語言都做不到，啊哈哈哈哈哈。

當(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ì)對GC產(chǎn)生額外的壓力，所有的壓力仍然來源于你自己所創(chuàng)建的數(shù)據(jù)結(jié)構(gòu)。

第三，Tinymoe需要?jiǎng)討B(tài)類型語言的類型推導(dǎo)。當(dāng)然你不這么做而把Tinymoe的程序當(dāng)JavaScript那樣的程序處理也沒有問題。但是我們知道，正是因?yàn)閂8對JavaScript的代碼進(jìn)行了類型推導(dǎo)，才產(chǎn)生了那么優(yōu)異的性能。因此這算是一個(gè)優(yōu)化上的措施。

最后，Tinymoe還需要跨過程分析和對程序的控制流的化簡（譬如continuation轉(zhuǎn)狀態(tài)機(jī)等）。目前具體怎么做我還在學(xué)習(xí)當(dāng)中。不過我們想，既然repeat函數(shù)是通過遞歸來描述的，那我們能不能通過對所有代碼進(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ì)得到提升，我對你們的科普也會(huì)做得更好。

后記

雖然還不到五千字，但是總覺得寫了好多的樣子?？傊蚁Ｍx者在看完《零》和《一》之后，對接下來需要學(xué)習(xí)的東西有一個(gè)較為清晰的認(rèn)識(shí)。