整理 rust module 的安排方式

故事是這樣子的,兩年前因為傳說中的 jserv 大神的推薦,我讀了 Understanding Computation 這本書,讀完覺得學到很多東西,深受啟發; 後來大概花了兩個月的時間,用Rust 重寫了裡面所有的範例程式碼,目前在 github 上查了一下, 我應該是除了原作實作之外,實作最完整的一個,可謂一人之下,萬人之上(誤。

最近因為一些原因,把之前的實作打開來看,馬上關上,假的!趕快在筆電前面打坐。
當初到底怎麼寫這麼醜,還查到有些章節的內容沒有實作完,那時候可能太難不會寫,先跳過結果就忘了QQ……最近這一兩個禮拜陸續花了一點時間整理。

這次整理的一大修正,是把本來是散在各處的原始碼,重新照 rust 慣例統整到 src 資料夾下面,並使用 cargo 管理,帶來的好處包括有:

  1. 可以一次 cargo build 編譯所有程式
  2. 引入 cargo test 代替本來編譯成執行檔用 println debug 的實作
  3. 在各章的內容間重用 module ,提升重用比例
  4. 另外也能使用網路上其他人寫的 Rust module(其實這才是原初整理的目的)

例如在我之前實作的程式碼,在寫 finite automata 時,dfa, nfa 各自有一個實作,使用 u32 作為狀態; 但到了 regular expression 的時候,為了產生 nfa 就不能用 u32 作為狀態,於是我複製了一版 nfa, 改成用 object pointer 作為狀態, 兩者程式碼的重複率就非常高,這次也一併改成 generic 的 nfa 實作,兩邊就能分享同一套程式碼。

...

使用rust closure實作fizzbuzz

之前用Rust 重寫Understanding Computation 裡面的ruby code,目前從 github 上來看,我的 Rust code 應該是僅次於原作者的 code,完成度最高的一個版本。
從去年五月,把大部分的 code 完成以來,唯一一個沒寫的章節:chapter 6 的 fizzbuzz,最近終於實作出來了\weee/。

...

使用Rust 實作regular expression tester

其實這個功能很早以前就已經完成了,將正規表示式對轉換成Non-Deterministic Automata(NFA) ,來match字串,

先前的實作有一些問題,因為再建 NFA的時候,狀態是使用整數來表示。
在轉換成NFA時,正規表示式的 Concatenate, Choose, Repeat 需要將兩個NFA 結合成一個,因為由Empty 或Literal 直接建NFA時, 編號一定是從 0 開始,兩個都包含狀態 0 的狀態機,直接結合起來絕對不會是對的,需要讓兩邊的狀態都不一樣才行。
當然也不可能用亂數來作為狀態,畢竟以亂數作為狀態,連一個NFA裡面有哪些狀態都不知道,結合時根本就無法檢查是否有衝突。

...

Rust 中實作型別運算子重載

最近在實作computation books第九章,用到很多Rust運算子重載的部分。
運算子重載嘛,可以對自己定義的struct 或是enum 使用運算子,這樣就能寫出 Vec3 + Vec3 這樣比較漂亮的寫法,不用 Vec3.add(Vec3),

...

Rust 遞迴結構 recursive structure

之前實作Computation book的範例程式碼,一直卡關的第2章原始碼解析的部分,最近突然有了大幅的進展 (因為在網路上找到一個別人寫好的相關原始碼),讓我突然頓悟rust 相關的設計,這裡解釋一些常用的技巧。

...