在《如何設(shè)計一門語言》里面，我講了一些語言方面的東西，還有痛快的噴了一些XX粉什么的。不過單純講這個也是很無聊的，所以我開了這個《跟vczh看實例學(xué)編譯原理》系列，意在科普一些編譯原理的知識，盡量讓大家可以在創(chuàng)造語言之后，自己寫一個原型。在這里我拿我創(chuàng)造的一門很有趣的語言 https://github.com/vczh/tinymoe/ 作為實例。

商業(yè)編譯器對功能和質(zhì)量的要求都是很高的，里面大量的東西其實都跟編譯原理沒關(guān)系。一個典型的編譯原理的原型有什么特征呢？

1. 性能低
2. 錯誤信息難看
3. 沒有檢查所有情況就生成代碼
4. 優(yōu)化做得爛
5. 幾乎沒有編譯選項

等等。Tinymoe就滿足了上面的5種情況，因為我的目標(biāo)也只是想做一個原型，向大家介紹編譯原理的基礎(chǔ)知識。當(dāng)然，我對語法的設(shè)計還是盡量靠近工業(yè)質(zhì)量的，只是實現(xiàn)沒有花太多心思。

為什么我要用Tinymoe來作為實例呢？因為Tinymoe是少有的一種用起來簡單，而且?guī)炜梢杂卸鄰?fù)雜寫多復(fù)雜的語言，就跟C++一樣。C++11額標(biāo)準(zhǔn)庫在一起用簡直是愉快啊，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了——當(dāng)然這個程序并沒有用到任何standard library的東西。說到這里大家可能意識到了，Tinymoe的名字可以是不定長的token組成的！沒錯，后面大家會慢慢意識到這種做法有多么的強大。

后面是print函數(shù)和main函數(shù)。Tinymoe是嚴(yán)格區(qū)分語句和表達(dá)式的，只有sentence和block開頭的函數(shù)才能作為語句，而且同時只有phrase開頭的函數(shù)才能作為表達(dá)式。所以下面的程序是不合法的：

phrase main

    (print "Hello, world!") + 1

end

原因就是，print是sentence，不能作為表達(dá)式使用，因此他不能被+1。

Tinymoe的函數(shù)參數(shù)都被寫在括號里面，一個參數(shù)需要一個括號。到了這里大家可能會覺得很奇怪，不過很快就會有解答了。為什么要這么做，下一個例子就會告訴我們。

print函數(shù)用的redirect to是Tinymoe聲明FFI（Foreign Function Interface）的方法，也就是說，當(dāng)你運行了print，他就會去host里面找一個叫做printf的函數(shù)來運行。不過大家不要誤會，Tinymoe并沒有被設(shè)計成可以直接調(diào)用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想讓每一行代碼都可以被念出來，所以才這么設(shè)計的。當(dāng)然，大家肯定都知道怎么算start + (start+1) + … + (end-1) + end了，所以應(yīng)該很容易就可以看懂這個函數(shù)里面的代碼具體是什么意思。

在這里可以稍微多做一下解釋。the result是一個預(yù)定義的變量，代表函數(shù)的返回值。只要你往the result里面寫東西，只要函數(shù)一結(jié)束，他就變成函數(shù)的返回值了。Tinymoe的括號沒有什么特殊意思，就是改變優(yōu)先級，所以那一句循環(huán)則可以通過添加括號的方法寫成這樣：

repeat with (the current number) from (start) to (end)

大家可能會想，repeat with是不是關(guān)鍵字？當(dāng)然不是！repeat with是standard library里面定義的一個block函數(shù)。大家知道block函數(shù)的意思了吧，就是這個函數(shù)可以帶一個block。block有一些特性可以讓你寫出類似try-catch那樣的幾個block連在一起的大block，特別適合寫庫。

到了這里大家心中可能會有疑問，循環(huán)為什么可以做成庫呢？還有更加令人震驚的是，break和continue也不是關(guān)鍵字，是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的順序和包圍結(jié)構(gòu)什么的。repeat with是屬于REPEAT的，而break和continue聲明了自己只能直接或者間接方在REPEAT里面，因此如果你在一個沒有循環(huán)的地方調(diào)用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中間的代碼的委托。所以你會看到代碼里面會調(diào)用它。

好了，那repeat while總是關(guān)鍵字了吧——不是！后面大家還會知道，就連

if xxx

    yyy

else if zzz

    www

else if aaa

    bbb

else

    ccc

end

也只是你調(diào)用了if、else if和else的一系列函數(shù)然后讓他們串起來而已。

那Tinymoe到底提供了什么基礎(chǔ)設(shè)施呢？其實只有select-case和遞歸。用這兩個東西，加上內(nèi)置的數(shù)組，就圖靈完備了。圖靈完備就是這么容易啊。

多重分派（Multiple Dispatch）

講到這里，我不得不說，Tinymoe也可以寫類，也可以繼承，不過他跟傳統(tǒng)的語言不一樣的，類是沒有構(gòu)造函數(shù)、析構(gòu)函數(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ù)你傳給他的不同的幾何圖形而使用不同的公式。當(dāng)所有的類型判斷都失敗的時候，就會掉進(jìn)那個沒有任何類型聲明的函數(shù)，從而引發(fā)一場。嗯，其實try/catch/finally/raise都是函數(shù)來的——Tinymoe對控制流的控制就是如此強大，啊哈哈哈哈。就連return都可以自己做，所以Tinymoe也不提供預(yù)定義的return。

那phrase (a) and (b) are the same shape怎么辦呢？沒問題，Tinymoe可以同時指定多個參數(shù)的類型。而且Tinymoe的實現(xiàn)具有跟C++虛函數(shù)一樣的性質(zhì)——無論你有多少個參數(shù)標(biāo)記了類型，我都可以O(shè)(n)跳轉(zhuǎn)到一個你需要的函數(shù)。這里的n指的是標(biāo)記了類型的參數(shù)的個數(shù)，而不是函數(shù)實例的個數(shù)，所以跟C++的情況是一樣的——因為this只能有一個，所以就是O(1)。至于Tinymoe到底是怎么實現(xiàn)的，只需要看《如何設(shè)計一門語言》第五篇（http://www.shnenglu.com/vczh/archive/2013/05/25/200580.html）就有答案了。

Continuation Passing Style

為什么Tinymoe的控制流都可以自己做呢？因為Tinymoe的函數(shù)都是寫成了CPS這種風(fēng)格的。其實CPS大家都很熟悉，當(dāng)你用jquery做動畫，用node.js做IO的時候，那些嵌套的一個一個的lambda表達(dá)式，就有點CPS的味道。不過在這里我們并沒有看到嵌套的lambda，這是因為Tinymoe提供的語法，讓Tinymoe的編譯器可以把同一個層次的代碼，轉(zhuǎn)成嵌套的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相關(guān)的函數(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ù)字，而且每產(chǎn)生一個數(shù)字還會打印出一句話。但是接下來我在循環(huán)里面只取前5個，打印前4個，因此執(zhí)行結(jié)果就是

當(dāng)！

CPS風(fēng)格的函數(shù)的威力在于，每一個函數(shù)都可以控制他如何執(zhí)行函數(shù)結(jié)束之后寫在后面的代碼。也就是說，你可以根據(jù)你的需要，干脆選擇保護(hù)現(xiàn)場，然后以后再回復(fù)。是不是聽起來很像lua的coroutine呢？在Tinymoe，coroutine也可以自己做！

雖然函數(shù)最后被轉(zhuǎn)換成了CPS風(fēng)格的ast，而且測試用的生成C#代碼的確也是原封不動的輸出了出來，所以運行這個程序耗費了大量的函數(shù)調(diào)用。但這并不意味著Tinymoe的虛擬機也要這么做。大家要記住，一個語言也好，類庫也好，給你的接口的概念，跟實現(xiàn)的概念，有可能完全不同。yield return寫出來的確要花費點心思，所以《序言》我也不講這么多了，后續(xù)的文章會詳細(xì)介紹這方面的知識，當(dāng)然了，還會告訴你怎么實現(xiàn)的。

尾聲

這里我挑選了四個例子來展示Tinymoe最重要的一些概念。一門語言，要應(yīng)用用起來簡單，庫寫起來可以發(fā)揮想象力，才是有前途的。yield return例子里面的main函數(shù)一樣，用的時候多清爽，清爽到讓你完全忘記yield return實現(xiàn)的時候里面的各種麻煩的細(xì)節(jié)。

所以為什么我要挑選Tinymoe作為實例來科普編譯原理呢？有兩個原因。第一個原因是，想要實現(xiàn)Tinymoe，需要大量的知識。所以既然這個系列想讓大家能夠看完實現(xiàn)一個Tinymoe的低質(zhì)量原型，當(dāng)然會講很多知識的。第二個原因是，我想通過這個例子向大家將一個道理，就是庫和應(yīng)用 、編譯器和語法、實現(xiàn)和接口，完全可以做到隔離復(fù)雜，只留給最終用戶簡單的部分。你看到的復(fù)雜的接口，并不意味著他的實現(xiàn)是臃腫的。你看到的簡單的接口，也不意味著他的實現(xiàn)就很簡潔。

Tinymoe目前已經(jīng)可以輸出C#代碼來執(zhí)行了。后面我還會給Tinymoe加上靜態(tài)分析和類型推導(dǎo)。對于這類語言做靜態(tài)分析和類型推導(dǎo)又很多麻煩，我現(xiàn)在還沒有完全搞明白。譬如說這種可以自己控制continuation的函數(shù)要怎么編譯成狀態(tài)機才能避免掉大量的函數(shù)調(diào)用，就不是一個容易的問題。所以在系列一邊做的時候，我還會一邊研究這個事情。如果到時候系列把編譯部分寫完的同時，這些問題我也搞明白的話，那我就會讓這個系列擴展到包含靜態(tài)分析和類型推導(dǎo)，繼續(xù)往下講。