Fw: [心得] 寫一個自己的程式語言 -- ACLang

[suhorng ( )]

※ [本文轉錄自 Programming 看板 #1K6QEZAk ]

作者: wayfarer (maniac) 看板: Programming
標題: [心得] 寫一個自己的程式語言 -- ACLang
時間: Wed Sep 17 23:07:04 2014

寫一個自己的程式語言 -- ACLang  (æ- klæng)

ACLang 是個 C-Like 的動態型別語言，目前大部份語法已完成，
目標是成為 Embedded-Scripting Language，開發 Plugin 用。
這篇只是在寫 ACLang 過程中隨手的心得而已，有興趣就看一下吧。


ACLang 完整程式碼在：
  https://github.com/madedit/aclang

編譯好的Win32執行檔可在此下載：
  http://sourceforge.net/projects/aclang/files/?source=navbar
  可輸入多行程式碼，最後要按 Ctrl+D & Enter 才是真正開始執行輸入的程式。
  可用：
  printAST(1); 開啟印出 AST 的功能
  printIR(1);  開啟印出 LLVM IR 的功能
  printGC(1);  開啟印出 GC delete 的功能。

對開發自己語言有興趣的可先參考此篇文章：
  http://gnuu.org/2009/09/18/writing-your-own-toy-compiler/
  Writing Your Own Toy Compiler Using Flex, Bison and LLVM


以下心得文開始：

* 手寫 Lexer & Language Syntax：

  ACLang 是 C-Like 的語法，純粹只是個人喜好。
  我並沒有使用 Lex/Flex 之類的工具來做，
  第一是 Lexer 的功能算是簡單的，
  就只是處理輸入的一整段程式碼，切成一個一個的 Token；
  第二就是有些語法用 Lex 來做不夠彈性，錯誤處理也比較麻煩。

  一開始是參考 D 的語法來寫的，所以會有一些 D 才有的語法小功能，像是：
  * var i = 987_654_321;            //可在數字中隨意插 _
  * print( 0x8000_0000_0000_0000 );
  * var b = 0b0110_0011;            //二進位數字 0b 開頭
  * var a = /+ /+  +/ +/ 100;       //階層式的範圍註解 /+ +/

  ACLang 也參考了很多 Squirrel (http://squirrel-lang.org/)，
  像 array, table 型別是從 Squrriel 來的，而 Squirrel 也參考很多 Lua。

  ACLang 裡對要使用的變數都要先明確的用 var 或 local 宣告，
  避免像 Lua 變數打錯字還是當做有效變數(只是值是nil)的問題。

  用 var 宣告表示此變數會存到一個指定的 table 中，如：
    var ::a = 10;       //在 root-table 新增變數 a
    var this.t = {};    //在 this-table 新增變數 t
    var t.x = "abc";    //在 t table 新增變數 x
  因為 t 沒有指定 scope，所以會以 this-table 為第一順位。

  變數的 scope 就是以指定的為主，有 :: (root-table) 與 this. (this-table)
  若沒指定就先找 local變數，再找 this-table，最後找 root-table。

  local 則表示此變數只會存在現在的執行的 function 中，
  當離開此 function 即無法存取此 local 變數，除非用 return 的方式傳出。
  以效率來說盡量使用 local 變數會比較好。

  每個 function 都會有個隱性的 this-table，
  若是在 global 的話， this-table 就是 root-table 。


* Parser & AST，使用 GNU Bison：

  網路上可找到 ANSI C 的 yacc 語法檔，我是用這個再修改成 ACLang 的語法。
  Parser 透過 Lexer 取得每個 Token，再由建立好的表格找到這
  一系列 Token 對應到的程式區塊，然後執行這個程式區塊，
  這個程式區塊裡面就是產生 AST (Abstract Syntax Tree) 的程式碼。

  寫語法定義一定會遇到很多 conflicts，只有想辦法消除了。
  像 if(ooo) xxx; 跟 if(ooo) xxx; else yyy; 就一定會衝到，
  就只能用 %nonassoc %prec 來解了。

  就跟 Lexer 一樣，用 Bison 來做 parser 會遇到的問題就是不夠彈性，
  還有錯誤處理有些麻煩的問題，Bison 印出來的錯誤訊息太過制式化了，
  除非以後 Parser 也要改成自己手寫的，不然就只能先這樣了。

* Code Generation：

  在經過 Parser 產生 AST 後，每個 AST 可對應到一個 LLVM::Value*，
  這樣可很簡單的針對每一個 AST 寫個 codegen 的 function 出來，
  回傳值都是 LLVM::Value* 。

  大部份 IR 指令都可用 LLVM::IRBuilder 裡包裝好的 function 來產生。

  ACLang 使用 LLVM 的 JIT 功能做中介層，但底層還是 C++ 寫的Code，
  例如 var a = "123" + 456; 這個加法的運算實際會去呼叫 ACLang
  向 LLVM JIT 註冊的一個全域函式 opAddVar()，這個函式裡面才會
  去判斷兩個變數的型別再來決定要做整數相加還是字串連結。

  LLVM 有提供 CppBackend 的功能，就是可以把 LLVM IR 轉換成 C++ 的 code，
  有時候不知道怎麼create某些 IR，就可以用這個作為參考。

  以後 ACLang 的 C++ 底層也可用 LLVM 的 CppBackend 轉成 LLVM 的 IR，
  再利用LLVM的IR最佳化提升效能。不過這也是個大工程，以後有空再說吧。

* Data Type & Variable

  ACLang 是動態型別語言，目前有以下類型：
  * integer: int32 & int64
  * float: float & double
  * string
  * array
  * table
  * function
  * userfunc: C/C++寫的 function 再 bind 到VM中，stdlib中的都是(如 print)

  變數Variable在使用前必須用 var 或 local 明確宣告，例如：
    var a, b, c=[1,2,3];
    for(a,b : c) print(a, b);

    for(local c, d : [1,2,3]) print(c, d);

    local t = { a=10 };
    var t.b = 20; //在 table t 新增 b 變數

  function也是變數的一種，可當參數傳遞：
    function f1(f) { f(100); }
    var f2 = function(i) { print(i); };
    f1(f2);

* Virtual Machine：

  VM 在 ACLang 只是個包裝所有功能的架子。
  VM.runCode(code) 會 compile 傳進來的 code，
  用 LLVM JIT 編譯成一段 function 再去執行它。
  VM 裡有個最主要的 RootTable，所有的資料都是存在裡面。

* Garbage Collection：

  GC 已是現代程式語言必備的功能，讓你只需要 new ，不需要管 delete，
  由語言幫你檢查並 delete 不再使用的資料。

  ACLang 有個中央控管的資料結構 root-table，所以實作 GC 並不是非常困難。
  ACLang 使用的是 Tri-Color Incremental Mark & Sweep GC ，

  所有的 Variable, Function...等等一切資料都會在 root-table 裡面，
  然後當要產生物件時都是透過 gc.createObject()，
  GC再將產生物件都存在一個 List 裡面，存實際 new 出來的所有變數，
  然後只要去 mark root-table 裡面的變數，
  若沒被 mark 到就表示此變數是無主孤魂不再被使用，可以被回收刪除了。

  這個演算法的好處是可以使用 gc.incrementalGC(time) 告訴此次gc會花多少時間，
  讓使用者決定本次要花多久來做 GC，例如在遊戲中每個frame花個一個clock來做GC。

  當然也可使用 gc.completeGC() 做一次完整的GC，這就可能會花很久時間了，
  若是在遊戲中你就可能會發現遊戲lag一下。

* Error Handling：

  * Compile-Time Error
    在Compile階段會有 Lexer&Parser&LLVM JIT編譯時的錯誤，
    比較先進的Compiler都可以在遇到一個錯誤時設法壓住這個錯誤，
    繼續Compile剩下的Code，看能不能再找到更多的錯，
    ACLang 沒這麼強，只能一次處理一個錯。

  * Run-Time Error
    目前還沒有完整實作，只有最基本的，在執行時遇到錯誤就印出錯誤訊息，
    然後用 setjmp/longjmp 跳回一開始設定的插入點，結束程式。
    例如字串除數字：
      var a = "123" / 10;
    目前只會印一行錯誤訊息而已，以後還需要印出 CallStack 跟行號，
    才能讓使用者能更清楚是哪裡發生錯誤。

* StdLib：

  像是 print(), typeof() 之類的都是用 C++ 寫的function，
  再 bind 回 ACLang VM 中使用的 userfunc。
  以後會再增加字串處理、數學函式、檔案讀寫等等的標準函式庫。

  目前要bind function還是必須寫個 wrapper function才能讓 ACLang VM使用，
  以後或許可以再改進用 C++ template 的方式做。

* 效能：

  雖然是用 LLVM 的 JIT 產生 native code，但是 ACLang 是動態型別的語言，
  所以還是必須在執行時期動態判斷變數的型別，才能正確的進行運算，
  例如: var a = "abc" + 123; //a會等於"abc123"，123先轉成字串，再連接起來
  因此效能就比不上靜態型別的語言。

  還有在每次call function時都會產生一些暫時的變數用來傳遞參數，
  這也是很花時間，需要再做改進。

* TODO：

  * 類似 OOP 裡 class 的繼承功能 與 Operator Overloading
    目前已有初步的想法了，會用類似 Lua 的 metatable 的作法，
    這個是之後會優先實作的功能。

  * namespace
    其實就是用 table 包著 table 來實作就可以了。

  * delegate
    可改變傳給 function 的 this-table。

  * 移除 LLVM JIT 產生的 function
    ACLang 每個 function 裡實際上是包著 JIT 產生的 function pointer，
    目前當 function 被 gc delete 掉後，JIT的function還是存在著，
    之後要再看看怎樣移除。


對寫個自己的 Programing Language 有興趣的話可以一起討論, Thanks~~


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.136.11.150
※ 文章網址: http://www.ptt.cc/bbs/Programming/M.1410966435.A.2AE.html
推 suhorng: 推
→ suhorng: 請問可以轉錄嗎?
→ wayfarer: 可以，請隨意。
※ 發信站: 批踢踢實業坊(ptt.cc)
※ 轉錄者: suhorng (111.248.47.80), 09/17/2014 23:46:54
推 NilPtr: 高手  是說我最近剛好也想研究LLVM呢
推 NilPtr: 補推。是說Lua的型態頗有趣，就是用Union包了一堆東西