2016年4月21日 星期四

淺談rust option type

強者我同學qcl 做了一系列的簽名檔,大體的概念就是用女友狂炸執行緒,以下是C++ version:
int main(int argc, char *argv[]) {
  QCL *qcl = new QCL();
  Girl *gf = qcl->findGirlfriend();
  printf(“%s\n”, gf→name());
  return 0;
}
qcl@QCLS:~$ g++ qcl.cc
qcl@QCLS:~$ ./a.out
Segmentation fault

另外還有許多版本:python, java, objective C(太強啦都會寫objective C)等等
最近心血來潮寫了一個rust version ,發現正好可以藉此說明option type 的概念,這樣的設計見諸於一些較新的語言,和較舊語言的新標準,如java ver 8和C++,rust 版本如下:
fn main() {
  let qcl = QCL{};
  let gf = qcl.findGirlfriend();
  println!(“{}”, gf.unwrap().name());
}
qcl@QCLS:~$ rustc qcl.rs
qcl@QCLS:~$ ./qcl
thread '<main>' panicked

上面的code 裡,QCL struct 的 findGirlfriend()的宣告如下,它回傳的不是如C++中的Girl,而是Option<Girl>:
fn findGirlfriend(&self) -> Option<Girl>
所謂option type 是用在函式回傳值可能不會回傳東西的時候,包含了兩種可能的變體:Some或None,其基本定義:
pub enum Option<T> {
  None,
  Some(T),
}

例如文中出現的getGirlfriend,亦或在dictionary 查詢的getValue()
若是some 則可存取其中的內容;None 則類似null 的設計,如上例中用unwrap()強行取用內容會造成執行緒崩潰

在上例中,遇到option,比較正規的寫法應該是:
match gf {
  Some(girl) => println!("{}", girl.name()),
  None => println!("Not found"),
}
藉此迴避None 把thread 給炸了,直接unwrap相對在C/C++ version 就是沒去比較return 的pointer == NULL或在python 裡面沒寫 is None,亦或是Golang 裡面沒寫err != nil。

的確,加上match去辨識回傳值是否為None,就跟用了== NULL或is None看似相差無幾,但這裡有個至關緊要的差異,option type 就是option type ,None 只會出現在這裡,若girlfriend 回傳值不是option ,就一定要回傳一個Girl 的實體,不管存取它的name 之後是<林志玲>還是<qcl的右手>,它就必須是一個Girl,儘管解出來是<qcl的右手>它仍然夠格當一位適當的女友。

在其他語言中的Null則不然,我們看到C++ 回傳了一個Null pointer,Null 是空的東西,它什麼都不是;但他被視為Girl pointer,因此我們可以存取它的name,它可以被賦值給任何一種pointer,它又什麼都是,Null 如同變形蟲一樣通過對Girl 的型別檢查,這樣簡單的例外設計有極高的自由,卻也容易出錯。

使用option 讓設計師知道girlfriend有可能為None,也無法對option type 使用來自Girl 的函式與資料,編譯器能在編譯時清楚的指出這類錯誤,並強制設計師在編寫時使用match 檢查,從而避免None 在執行緒中四處散佈,並到了執行時才將執行緒炸掉,如上文中都已經知道可能是None了,又強行unwrap 程式會爆是自己活該。

如果我們用上面的例子寫個比喻:
C語言和允許Null 的語言大概就像:你女友的名字呀,拿去;噢qcl你沒女友呀…干我屁事!你還是自盡吧你
使用Option 的語言會比較貼心一點:女友的名字嗎,嘿qcl 呀,你有可能沒有女友噢,最好處理一下

有關rust 裡option 的相關文件:
https://doc.rust-lang.org/std/option/
https://en.wikipedia.org/wiki/Option_type

關於Null 的一些延伸閱讀:
https://linux.cn/article-6503-1.html
http://openhome.cc/Gossip/Programmer/Null.html

2016年4月20日 星期三

Minecraft 可堆疊式物品儲存系統

Minecraft 因為遊戲時間一久,玩家通常會累積大量物品,另外如果利用生怪磚建造農場,或者之前出現過的巨大化農場,大量物品儲存系統算是相當重要。

簡單的儲存系統要利用漏斗和箱子即可,如下圖所示的垂直儲存系統設計:


這樣的設計在擴展性方便較差,要更多箱子就要往下延伸,通常在建築物裡面要打掉樓板比較不適合。

水平的儲存系統可利用長條漏斗,連接到一般箱子和陷阱箱子交錯放置的箱子列中,如下圖所示:



上面兩種設計共有問題在於:漏斗中都會殘留儲存的物品,很難確定現在究竟儲存了多少東西,另外,漏斗就是要傳送物品的,東西就應該要放在箱子裡面怎麼能殘留在漏斗中呢?

本文展示一種新型的儲存系統設計,能避免物品殘留在漏斗中:

基本架構如下,儲存同樣是用箱子列和側面的進貨漏斗,不一樣的是進貨漏斗上加上一層控制漏斗,最上面才是物品傳送鏈。

透過比較器感測進貨漏斗那是否有物品,一但有物品將會將控制漏斗關閉,使控制漏斗不會再進貨, 儲存箱滿了,漏斗中頂多殘留一個物品,確保物品都儲存在箱子中。

以下為建造說明影片:

2016年4月1日 星期五

使用Rust 實作regular expression tester

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

這是之前版本的 toNFA:
toNFA with u32

可以看到因為使用整數來表示狀態,為了避免第二個NFA 接到第一個上面時,第二個NFA 的狀態和第一個的重複,必須實作一些必要的函式,例如FARule 的shift 將規則中的狀態都偏移一個數值;如果像Choose 或Repeat ,需要建一個新的start state,則兩個 NFA的 rule都要shift;另外像accept state也要用iterator的方式 shift,總之就是各種麻煩。

相對的在書中的例子,使用Ruby實作的關係,他直接使用Ruby Object來當作他的狀態,絕對不會有重複的問題,就像這裡的start_state:
class Choose
  def to_nfa_design
    first_nfa_design = first.to_nfa_design
    second_nfa_design = second.to_nfa_design
    start_state = Object.new
    accept_states = first_nfa_design.accept_states + second_nfa_design.accept_states
    rules = first_nfa_design.rulebook.rules + second_nfa_design.rulebook.rules
    extra_rules = [first_nfa_design, second_nfa_design].map { |nfa_design|
      FARule.new(start_state, nil, nfa_design.start_state)
    }
    rulebook = NFARulebook.new(rules + extra_rules)
    NFADesign.new(start_state, accept_states, rulebook)
  end
end
當然Rust 也是可以這樣做,只是麻煩些,畢竟Ruby 是動態語言,要用什麼東西當狀態都可以直接使用,Rust 需要明確的指定型別,某種程度它用Ruby 實作也是一種語言的霸凌Orz。

相對應的修改如下:
首先我們先建一個空的state,裡面不用內容,功用就跟Ruby 的Object 差不多:
Struct State;
這樣就可以建state了:
let start_state = State{};
let next_state = State{};
let rule = FARule(start_state, c, next_state);
NFA(start_state, next_state, rule);

因為Rust 在struct 的比較的時候,會直接把struct 拆開比較裡面的值,所以上面 start_state == next_state 會是true,解決方法在於自己實做比較的方法,改成比較struct 的位址即可避免不同struct 被認定成相同:
impl PartialEq for State {
  fn eq(&self, rhs: &Self) -> bool {
    self as *const _ == rhs as *const _
  }
}

另外 Rust 會避免同個struct 被兩個不同的地方擁有,當我們使用了某個State當作start_state,我的rule 就沒辦法再用這個State 了,上面的code 在建nfa 的時候會報錯,因為start_state 跟next_state 已經move 到FARule 中了。 因此我們狀態不能直接使用state 而必須用rust 的 Reference Count: Rc。
https://doc.rust-lang.org/std/rc/struct.Rc.html
用Rc<State> 當作state,這樣
let start_state = Rc::new(State{});
let next_state = Rc::new(State{});
let rule = FARule(start_state.clone(), c, next_state.clone());
就可以避免重複使用start_state 的問題,同時 start_state == start_state.clone() 也會是true。

以下是修改後的toNFA:
toNFA with struct state
相較起來簡單的多,也跟Ruby code 相似得多。