官方錄影:http://osdc2014.pixnet.net/album/video/513236976
網友錄影:http://www.ustream.tv/recorded/46017954

投影片

以下是每一頁的講稿,如果你懶得看影片的話 :) (不過實際講時一定會與講稿有出入的XD

1

大家好,我今天所要談的主題是用Go來實作程式語言的執行環境的一些經驗,然後藉由這些例子來介紹一些Go的特性。

2

我是布魯斯許,大家可以透過這個id在twitter和github上找到我。右邊這張是我的照片。
我曾在Trend Micro和GoodLife實習過,現在則是國立中正大學資工所的碩二學生。除了以上的角色外,我也是

3

我們家貓的坐墊。

4

我們今天要談的,就如同標題所說的,主要是Go這個語言。Go從2009年發表以來,已經發展得越來越成熟,在1.0之後語法也穩定下來,所以越來越多人選擇使用它來寫丟上production的系統。

5

因此我們可以在許多不同的領域中看到Go的身影,有人用它來寫web framework啦,有人用它來寫網站的back-end API,也有像docker這種重量級的open source project

6

而在System Programming的領域,Go也是成果豐碩。由於它的效能不錯,加上易讀好寫的語法,有不少人在寫system program的時候,會跳過C優先考慮以Go來作為實作的語言。

7

但是就我的感覺來說,在程式語言執行環境上面,Go的相關work好像就相對比較少。所以我自己出於興趣,便開始在這方面作點小小的實驗。

8

一開始,我是以看來最簡單的語言作為踏腳石,所以我開了一個project叫bbfi,大家可以在github上面找到。
它是一個brain-beep-,呃,因為這裡應該是普遍級的場所所以我要自主消音一下。的interpreter,之後我將它改寫成virtual machine的版本。

9

它最初是用C來實作,後來的VM版本才改用Go來寫。在探討之前,我想可能有些人沒有聽過brain-beep-,所以接下來就稍微介紹一下…

10

11

首先,brain-beep-是個極簡化的語言,它的語法是由8個operators所構成,而每一個operators又可以很輕易地轉換成相對應的C code。
接下來就來看看實際的brain-beep- interpreter怎麼作。有人30秒審過服貿,我們今天不用三十秒讓你看懂brain-beep- interpreter

12

這邊是一支awk的script,它的作用就是將brain-beep-的code轉換成C的source code,其實說穿了就是source-to-source的compiler啦。
從這裡我們可以看到各個operators的作用,像是對值作+-,移動pointer,迴圈之類的動作。

13

從上一頁我們可以看到寫個brain-beep-的interpreter還蠻直覺的,但是有一好沒兩好,因為interpreter的運作方式是來一個打一個,來一雙還是只能打一個,這樣就會讓我們沒辦法對code來作最佳化。
如果我們稍微留意一下,就會發現其實這裡面有許多地方可以作最佳化,比方說+-值的動作,我們常常會連續作不止一次,可能加個8、9次之類的,但是我們又不能把語法改成+8、+9像在講神裝一樣,一般來說我們都會假設語法是不能修改的,以免多頭馬車多套標準,影響到程式的流通性,當然我知道有些公司壓根不care這種東西,但這不在我們討論的範圍內。

14

回到bbfi,我們如何解決這個問題呢?既然我們不能修改原本的syntax,那就來自定一套內部使用的bytecode,然後寫個Virtual Machine來執行它吧。藉由自定bytecode,我們就可以讓+-值的動作有參數而不是一次一加一次一減,也可以讓pointer operation一次跳到很後面,大大增加了作最佳化的可能性。

15

實作上,就如同前面所說的,bbfi

16

似乎好像

17

是用Go寫的。或許大家猛然一看這些code segment會有種在看C code的錯覺,沒有嗎?呃,至少我當初是直接當C來寫啦。我覺得這也是為什麼Go會這麼熱門的原因,對於慣C的programmer來說,只要克服一些像是資料型態放後面這種語法上的不同,就可以輕易地上手,甚至還有pointer可以用,而對動態語言使用者,Go的syntax sugar也不算少,像我這種兩邊都略懂略懂的人就更不用說了。

18

講到這裡,我想有些人可能會敲碗說brain-beep-這語言也太簡單了,雖然說沒有三十秒那麼誇張,可是拿來作例子也是咻咻咻地就講完了,有沒有其它語言可以拿來說嘴呢?

19

既然我對外一概宣稱我自己是Rubyist,那來寫個Ruby VM也是個很正常的事對吧?所以接下來會以RunVM的開發過程作為探討的主題。RunVM最大的特色,除了用Go來寫已經各本滿天飛的Ruby VM外,最主要是打算將Software Transactional Memory引入Ruby中,免除在VM裡大量使用Global Interpreter Lock的需要,別擔心,今天不會講到這麼深入。
當然,這裡必須先作個聲明,RunVM的開發現在仍處於很初期的階段,我也還沒有勇氣把repo設為public,還請大家多多包涵這裡的黑箱作業,請你們相信這一定Z>B。

20

就如同前面所說,brain-beep-確實是個很簡單的語言,所以我們可以讀入一個operator後直接執行相對應的動作,但是對於大多數的程式語言來說,事情沒有那麼簡單。如果各位對compiler原理有些許的了解,大概就會知道我們在作編譯之前,一開始會有三個階段的工作需要完成,分別是作這三項的分析。
Lexical analysis是指我們怎麼把文字切割成相對應的token,比方說while會是keyword,而ma19可能是個變數名稱。
Syntax analysis則是根據這些token,再比對我們定義的語法確認現在是哪一條規則,像是while後面應該接布林運算式,而不是if這個keyword這樣的規則。
Semantic analysis則是分析各個語法樹節點的值,例如某個變數的型態。

21

傳統上,大家會用所謂的lexer和parser generator來處理這三個階段,,Go裡面其實有包含了他們自己的yacc版本,但是問題在於它就只是個parser generator而已,必須另外找個相搭配的lexer。偏偏Go上面也只有golex這個project,好死不死又已經有好幾年沒維護了,這幾乎等同於是要你自己來寫。當然我知道寫個lexer可能對各位在座的大大沒什麼,像是c9s大大明天會談到的gutscript就是用goyacc加上自製的lexer,不過我是沒什麼sense也比較懶,所以便開始找尋有沒有其它的方案。

22

後來我找到了2004年發表的Parsing Expression Grammar,簡稱PEG,裡面用的定義方式跟regular expression很像我就不綴述了,它是lexer+parser generator二合一的產物,在作lexical analysis的時候同時進行syntax parsing,更重要的是,有人寫了Go的版本。

23

不過大家最常用的,反而是在PEG最初的C版本實作裡面,開發者額外定義的延伸PEG語法的LEG,主要是從傳統的lex和yacc中將一些PEG欠缺的功能,其中最重要的,莫過於是semantic value的支援,你可以使用double dollar-sign($$)來指定當下語法規則的semantic value,也可以指定一個變數名稱給某規則回傳的semantic value並且使用它。這些擴充讓整體的語法分析更有彈性,也讓原本使用傳統工具的開發者更容易上手或者轉換原有的定義至LEG。對我來說更棒的是有個ruby的subset implementation叫tinyrb,是用leg來定義語法,所以理論上可以無痛轉移。一切聽來很完美,但是

24

它沒有Go的版本。
好吧,看來到頭來還是無可避免地必須捲起袖管來寫code了。

25

幸好Go版本的PEG到兩個月以前都還有commit,還已經update到Go v1的標準,所以可以正常運作,這代表我只要幫它新增那些額外的功能就好了,當然按照莫非定律,事情永遠沒有你想的那麼簡單,這等下會詳述。如果大家有興趣的話可以先上github看看,目前的版本基本上已經完成幾乎是所有的LEG extension feature,唯二還沒作出來的就是optional semicolon還有exception。

26

既然要修改PEG當然不免俗地要跳進source code裡好好調查一番,所以接下來就來介紹我當初心得的懶人包。PEG實作的方式如同大多數的compiler一樣,會先經過一個bootstrap stage,所以一開始我是先從PEG產生出來用於bootstrap的go source code來看最終成品大概是什麼樣子,我的第一個想法就是

27

……沒錯,或許因為是姓氏一樣都姓go,所以goto也是Go神聖不可分割的一部份。PEG所產生出來的parser code裡大量使用goto來作branching或exception handling。

28

接著注意到的是一個充滿anonymous functions的陣列,每一個function代表一條syntax rule,彼此可以互相呼叫。每個function的body就是在對該rule作lexical scanning和parsing。這樣複雜的code當然不會是手刻出來的,所以實際上的作法還是先定義出整個PEG的語法後再compile成我們最終看到的PEG。這時候就必須問一個很重要的問題:

29

你知道怎麼種出又大又美的語法樹嗎?

30

在PEG裡面,AST node主要分為三種類型,最基本的字元節點,內含多個子節點的list type,以及作為語法operator的Fixed type。

31

這裡直接用圖來說明,上層的Type Alternate是個list,代表規則可能的branch路徑。左邊Type Query是代表出現0次或1次的,稍微了解regular expression的朋友應該知道我在講什麼,那是什麼東西在此規則下呢?是個Type Name的node,其實就是呼叫另外一個rule。右邊的Type Sequence又是另外一個list type,不過它比較單純,可以想作它是一般的array。

32

在種出這棵樹之後,接下來就是將它砍下來轉成先前看到的source code了。這裡PEG會先對AST作一些處理,像是檢查有沒有left recursion的問題,再輸出預設的template,裡頭包含了一些parsing所需的function,之後,才開始作complication。complication的方式是用一堆closure來對當下的context作處理。

33

以上是原本PEG實作的部份,至於我fork出來的LEG部份,花最多時間的當然就是semantic value的部份

34

首先這裡使用了stack來儲存各節點的值,當有一條規則要取得其它節點的semantic value時,只要從stack的相對位置來取值即可。因為一個節點的semantic value是可以被賦予變數名稱的,所以在C版本裡面,是用#DEFINE的preprocessor directive將變數名稱取代回stack裡的位置,但是Go裡面沒有#DEFINE可用,所以我是先去找Go的language spec,然後借用它對identifier的語法定義,再用regular expression一個一個去取代。再來就是我前陣子才發現的問題,因為一般我們直覺想到的方法,是遇到相對應的節點時才動態對stack作push和pop的動作嘛,可是LEG為了要讓指定的變數名稱在同一條規則的每一個都能夠被access到,所以是先push一定數目,然後透過relative index去access,所以在我要import tinyrb的.leg時才發現這個差異。

35

36

既然可以使用LEG來定義語法了,我們就可以建樹後再compile成RunVM的bytecode。當我們可以執行Ruby code之後,第一個遇到的問題,就是如何處理Ruby object,如果說Go跟C一樣完全沒有OO的能力,那就得用很多時間或奇技淫巧來處理各種不同的Ruby object structure。

37

不過雖然Go不是純OO語言,但是它也有支援interface,對,就跟你所期待的一樣,跟Java的interface有異曲同工之妙。只要某個strucutre有定義了跟你宣告的interface一模模一樣樣的functions,它就可以被當作是那個interface type,使用時就不用再管它實際上的型態。當然Go也提供了機制讓你去查詢它實際的type,這裡就不多談了。

38

另外,前面有提到RunVM “打算” 引入STM的設計,所以大家都知道言下之意就是……這同時也是當初為什麼選擇Go的原因,因為Go有coroutine可以用。goroutine看起來好像沒什麼了不起,它基本上是map到thread上,Go也提供了傳統的mutex來控制goroutine。如果只是這樣,那好像不需要一定要用Go嘛。

39

不過Go其實提供了另一個機制,叫channel,你可以把值丟進去,比方說把文字檔裡的每一行傳進去,讓有空閒的goroutine去將值取出來作處理,這樣就可以不使用相較之下比較容易出錯的lock機制了。所以回到STM,因為STM是以transaction為主體,所以我目前 “預計” 的設計是將transaction丟進channel內,讓goroutine自行取用。

40

那,最後又到了最嘴炮的future works的部份,這方面嘛,第一件事情當然是要把repo給open出來,雖然現在已經是以MIT license來開發,但是大家看不到好像沒什麼用,況且在Open Source Developer Conference上講不open的東西好像有點不倫不類……啊,我沒有在指特定的誰。第二件事情,可能就是需要額外的幫手不然我覺得我太容易富奸了,關於這點,其實我前幾天有徵求過c9s大大的幫忙,不過被打槍了。最後一件事,就是看明年還能不能來跟大家繼續介紹RunVM part 2,雖然我比較想講另外一個比較潮的議題,這就留待明年再說了,畢竟如果RunVM作不完我也不用想畢業了。

41

今天就大概講到這裡,不知道各位有什麼問題嗎?