2019年11月16日 星期六

把一顆樹寫出來是會有多難

故事是這樣子的,之前小弟發下豪語想用 Rust PEG 寫一個 C Parser,然後…就沒有然後了。好啦當然不是,不然就不會有這篇文了。
總之最近經過一陣猛烈的攪動之後,我的 parser 能處理的文法終於接近當年在學校修 compiler 的時候所要求的 B language 了,說來慚愧,當年寫 compiler 作業的時候 parser 只是裡面一個作業,要在 2-3 週裡面寫完的,結果現在搞半天寫不出個毛,果然上班跟上學還是不一樣,在學校可以全心全意投入寫 code ,週末的時候還可以熬個夜把作業寫出來;現在上班白天要改公司的 code ,晚上回家累個半死不想寫 code 只想開卡車(欸。

本篇講到的程式碼目前還沒推到遠端上,相關的程式碼可以參考:
AST 的資料結構:cast
型別的資料結構:ctype
既然現在可以處理比較複雜的文法了,再來要做什麼?想說就像作業的要求一樣,把我們處理好的 AST 用 graphviz 寫出去,是會有多難?

整個 dump graphviz 的進入點是一個函式,接收要倒出來的 AST 跟一個 out,out 的型別是 std::io::Write 的 dyn Write,這樣不管你是要寫到 stdout, stderr 還是寫到檔案都能傳進來,介面會是一樣的,函式的實作當然就是直接了當的把該印的東西都寫出去;另外實作一個 dump_node 幫我們把寫出一個 node 給獨立出來,id 會自動不斷累加,讓 node 的編號不會重複。
fn dump_graphviz(ast: CastTop, out: &mut dyn Write) {
    writeln!(out, "Digraph AST").unwrap();
    writeln!(out, "{{").unwrap();
    writeln!(out, "label = \"AST_Graph.gv\"").unwrap();
    writeln!(out, "node{} [label = \"PROGRAM_NODE\"]", 0).unwrap();
    ast.make_node(out, &mut 0);
    writeln!(out, "}}").unwrap();
}
fn dump_node(out: &mut dyn Write, id: &mut u32, label: &str) {
    *id += 1;
    writeln!(out, "node{} [label = \"{}\"]", id, label).unwrap();
}
另外我們要實作的是 make_node,這裡很自然的就是先宣告一個 trait,AST 裡面所有的物件都要實作這個 trait ,就都有 make_node 可以用了。
trait ToGraphviz {
  fn make_node(&self, out: &mut dyn Write, id: &mut u32);
}

impl ToGraphviz for CastTop {
  fn make_node(&self, out: &mut dyn Write, id: &mut u32) {
    match self {
      CastTop::FuncDeclList(v) => {
        let cur_id = *id;
        for decl in v {
          dump_node(out, id, "DECLARATION_NODE FUNCTION_DECL");
          decl.make_node(out, id);
        }
        if *id != cur_id { // new node
          writeln!(out, "node{} -> node{} [style = bold]", cur_id, cur_id + 1).unwrap();
        }
      },
    }
  }
}

impl ToGraphviz for FuncDecl {
  fn make_node(&self, out: &mut dyn Write, id: &mut u32) {
    let parent = *id;
    dump_node(out, id, &format!("IDENTIFIER_NODE {} NORMAL_ID", "int"));
    dump_node(out, id, &format!("IDENTIFIER_NODE {} NORMAL_ID", self.fun_name));
    dump_node(out, id, "PARAM_LIST_NODE");
    dump_node(out, id, "BLOCK_NODE");

    for i in parent..*id {
      writeln!(out, "node{} -> node{} [style = {}]",
          i, i+1, if i == parent {"bold"} else {"dashed"}).unwrap();
    }
  }
}
* :本來的作業要求連結第一個 child 的必須是實線,其他的用虛線,這裡沿用
這個實作的問題顯而易見,我們的輸出的實作跟資料綁死了,所以每個 node 裡面的實作都是大費周章,而且 code 很醜。
我們要更抽象化一點,其實輸出樹的邏輯是這樣子的:先寫 child 的 node,然後是自己,回傳自己的 id 給 parent,這樣上一層的人才能畫 edge 出來。
我們實作一個 dump_children 的函式,這個函式會用現在的 id 印出現在的 parent,然後把它跟所有傳進來的 children 畫線連起來:
fn dump_children(out: &mut dyn Write, id: &mut u32, label: &str, children: &[u32]) -> u32 {
  writeln!(out, "node{} [label = \"{}\"]", id, label).unwrap();
  let mut prev = *id;
  for child in children {
    writeln!(out, "node{} -> node{} [style = {}]", prev, child,
        if prev == *id { "bold" } else { "dashed" }).unwrap();
    prev = *child;
  }
  *id+=1;
  *id-1
}
因為 Rust 函式參數沒有預設值也沒有 overload,為了方便我們可以創一個 dump_nochild 的函式,這樣比較方便:
fn dump_nochild(out: &mut dyn Write, id: &mut u32, label: &str) -> u32 {
  dump_children(out, id, label, &[])
}
現在 make_node 的實作都可以用 dump_children 或 dump_nochild 實作,先對自己的 child 們呼叫 make_node,把回傳值(也就是 child 們印完的 root)收集起來再用 dump_children 印出去就行了:
impl ToGraphviz for CastTop {
  fn make_node(&self, out: &mut dyn Write, id: &mut u32) -> u32 {
    match self {
      CastTop::FuncDeclList(v) => {
        let children : Vec<_> = v.iter().map(|n| n.make_node(out, id)).collect();
        dump_children(out, id, "PROGRAM_NODE", &children);
      },
    }
    *id
  }
}

impl ToGraphviz for FuncDecl {
  fn make_node(&self, out: &mut dyn Write, id: &mut u32) -> u32 {
    let children = [
      dump_nochild(out, id, "IDENTIFIER_NODE int NORMAL_ID"),
      dump_nochild(out, id, &format!("IDENTIFIER_NODE {} NORMAL_ID", self.fun_name)),
      dump_nochild(out, id, "PARAM_LIST_NODE"),
      dump_nochild(out, id, "BLOCK_NODE")];
    dump_children(out, id, "DECLARATION_NODE FUNCTION_DECL", &children)
  }
}
這樣看起來就好多了,不過我們還能更進一步,仔細觀察上面的 dump_children 的話,就會發現我們還能用 fold 的方式改寫:
// print node, and link with all children
fn dump_children(out: &mut dyn Write, id: &mut u32, label: &str, children: &[u32]) -> u32 {
  *id+=1;
  writeln!(out, "node{} [label = \"{}\"]", id, label).unwrap();
  children.iter().fold(*id, |mut prev, child| {
      writeln!(out, "node{} -> node{} [style = {}]", prev, child,
          if prev == *id { "bold" } else { "dashed" }).unwrap();
      prev = *child;
      prev});
  *id
}
老實說,每次我費了這麼大的工夫,把一堆本來很黃很暴力的 code 改簡單,變成最後那樣的很純很 Functional 的 code,我都會在內心懷疑個 100 遍,費這麼大功夫是真的有比較快嗎?當然在維護上可能會好一點,但 Rust compiler 能保證抽象化真的是零成本的嗎?這可能是值得好好討論的議題。

每個函式都要帶著 out 跟 id 走,很不方便,用一個 struct 把它們裝起來:
struct DumpGraphviz {
  out: Box<dyn Write>,
  id: u32
}
dump_children 跟 dump_nochild 變成 DumpGraphviz 的實作,介面變成:
fn dump_children(&mut self, label: &str, children: &[u32]) -> u32
fn dump_nochild(&mut self, label: &str) -> u32
make_node 的介面則是:
fn make_node(&self, visit: &mut DumpGraphviz) -> u32
整體就變得清爽多了。
天底下沒有新鮮事,其實我就是在實作 visitor pattern,只是還沒把 visitor 整個抽出來讓不同的 visitor 可以在這上面實作。最後輸出的成品長這個樣子:

我有個小小的體悟,就是寫程式不要妄想一步登天,除非如強者我同學 AZ 大大那樣一眼就把超大程式的架構都畫出來,而且實作起來都不會亂掉。
我上一次的實作就是衝太快,翻著 C standard 想要一開始就照著 C standard 實作,然後文法寫得亂七八糟反而連簡單的文法都會大噴射無法處理;與其如此,不如先支援基本的功能,等 parser 跟文法處理都完善之後再慢慢把其他功能加上去。
我覺得用蓋房子比喻的話,寫大程式要像西敏寺那樣的大教堂一樣,先從一個功能完整的小教堂開始,然後把小部分拆掉蓋個更大更豪華的(有看過一個動畫片在演示這個過程的,只不過沒有公開版);如果一次就想蓋個超大的教堂,最後可能弄成一團廢墟,連禮拜的功能都沒有。

2019年11月4日 星期一

從 Coscup 小談 Rust

這篇其實有點拖稿,畢竟 COSCUP 都是幾個月前的事了;這次在 COSCUP 投稿了 Rust 議程軌,覺得可以來說說對 Rust 的一點感想。Rust 從問世、正式發佈到現在也差不多要 7 年,感覺近年來有愈來愈紅的趨勢,一種社群上面看一看發現大家都用過 Rust 的感覺。

今年的 COSCUP 專門開了一個 Rust 議程軌,而且感覺議程的內容正在提升,不再是一堆語言介紹,有更多的是在介紹用 Rust 實作的資料庫、web assembly 、類神經網路的應用,可以預見 Rust 正在走出推廣階段,前往實際應用的領域。
不過我們還是要回來問,Rust 在哪裡會有<十倍生產力>?也就是在哪裡可以把東西做得比其他語言十倍好,像是要推人工智慧大家就會推 Python;要寫高效能的網路可能會用 golang,有哪個領域是非用 Rust 不可的嗎?現在有些風聲是區塊鏈的合約和交易語言,但我對這塊應用的大小有點存疑。

Rust 天生尷尬在它的定位上,它的目標是一個安全高效的系統程式語言,它也的確有潛力做到這點,但整體看來 Rust 可能是幾大系統程式語言裡數一數二複雜的,可能只輸給 C++,配上最新加上去的 Async 可能差不多就比肩了(欸。
確實 Rust 從源頭來看,受到大量函數式語言和語法的啟發,語法上看得出核心來自一個優異的語言團隊並吸收了各類語言的優點;編譯時進行的所有權確認和以 mod 為編譯單位,雖然讓 Rust 編譯慢得像烏龜,卻也大量消除程式在執行時出錯的機會,或者因為設計師<忘記>而導致的問題。
Rust 不可能是一款早期的語言,它浪費太多運算資源在編譯檢查,在 C 語言發跡的年代不會浪費資源去做那些檢查,換來的就是 Rust 編譯器數一數二的 GY 程度,這個不行那個也不行,搞得寫 code 的人跟編譯器都很累……。

我認為 Rust 要走的會是一條很艱難的道路,Rust 內建的複雜性天生就拒絕了一些簡單的應用,用 Rust 寫起來太過繁瑣了,動態語言能搞定的網路服務開發速度是第一,程式設計師上手的速度還有開發的速度來看,沒理由不用動態語言;而一些偏底層的應用,特別是對從 C/C++ 來的人來說,Rust 根本就不可理喻,明明我用 C 系列一下就可以搞定的,誰跟你在那邊 4 種 String 還有一堆 Option 要處理?一眼看穿的程式實在用不上 Rust,有人覺得 Rust 可以在嵌入式系統上挑戰 C,我看再過 100 年都不太可能。
Rust 的優勢,要來到所謂的大型系統程式才會出現,透過編譯器的強制,把一些難以檢測到的記憶體問題給挑出來,當然用 C++20 的一些特性可以做到一樣的效果,但沒有編譯的強制只靠設計師所受的教育,在大型系統下畢竟不是一個妥當的做法,畢竟設計師也是人,不可能不犯錯,或者偷懶或者忘記,一不小心就引入 C++ 的舊語法 -- 那些為了向後相容絕對不會移除的部分。

但問題就在於:大型系統幾不太可能整個重寫,更別提底層所依賴的都是經過千錘百鍊的 C/C++ 函式庫,像 Mozilla 那樣決定把瀏覽器核心整個抽換掉真的是神經勇敢,市面上的大公司哪幾家做過一樣的事?
可以預期 Rust 幾年之內,都會是用滲透的方式慢慢進到各大公司的系統當中,也許是一個新實作的子系統或是重寫某些小部分,用 FFI binding 的方式和既有的系統銜接,但要成為主流我看還要努力一段時間才行。

其實我是覺得語言比語言氣死人,不過 Rust 對 go 一直是一個大家很有興趣的話題(雖然說兩個根本是完全不同的東西),我個人滿推薦 LoWeiHang 翻譯的這篇文章