淺談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

Minecraft 可堆疊式物品儲存系統

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

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


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

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



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

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

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

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

以下為建造說明影片：

使用Rust 實作regular expression tester

其實這個功能很早以前就已經完成了，將正規表示式對轉換成Non-Deterministic Automata(NFA) ，來match字串，
先前的實作有一些問題，因為再建 NFA的時候，狀態是使用整數來表示，在轉換成NFA時，正規表示式的Concatenate, Choose, Repeat 需要將兩個NFA 結合成一個，因為由Empty 或Literal 直接建NFA時，編號一定是從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 相似得多。

Rust 中實作型別運算子重載

最近在實作computation books第九章，用到很多Rust運算子重載的部分
運算子重載嘛，可以對自己定義的struct 或是enum 使用運算子，這樣就能寫出Vec3 + Vec3　這樣比較漂亮的寫法，不用Vec3.add(Vec3)，啊雖然兩個本質上沒什麼兩樣啦
這章定義一個Sign的類別，分為<正>、<負>、<零>和<未知>，我們要實作他的乘法和加法：

enum Sign {
  POSITIVE,
  NEGATIVE,
  ZERO,
  UNKNOWN,
}

Rust可重載的運算子可以在這裡找到：
https://doc.rust-lang.org/std/ops/index.html

另外是比較運算子，包括PartialEq 跟PartialOrd：
https://doc.rust-lang.org/std/cmp/

例如我們要重載乘法運算子，以下是網站上的定義：

pub trait Mul<RHS = Self> {
  type Output;
  fn mul(self, rhs: RHS) -> Self::Output;
}

實作時當然就是先以use這個trait，然後實作這trait並加入相關的函式：

use std::ops::Mul;
impl Mul for Sign {
  type Output = Sign;
  fn mul(self, rhs: Self) -> Self {
    if self == Sign::ZERO || rhs == Sign::ZERO {
      Sign::ZERO
    } else if self == Sign::UNKNOWN || rhs == Sign::UNKNOWN {
      Sign::UNKNOWN
    } else if self == rhs {
      Sign::POSITIVE
    } else {
      Sign::NEGATIVE
    }
  }
}

這樣就完成了，現在我們就能這樣寫了：

assert_eq!(Sign::NEGATIVE, Sign::POSITIVE * Sign::NEGATIVE);

另外常遇到的問題是，將運算子重載和Rust 的泛型一起用時，例如，我們定義sum_of_square 這個function，並希望使用泛型：

fn inner_product<T: Copy>(lhs: T, rhs: T) -> T {
  lhs*lhs + rhs*rhs
}

這樣編譯並不會過，因為泛型T 並不適用乘法跟加法，我們需要告訴編譯器，只有實作Mul跟Add trait的型別才能通過。同時指定Output 型別同樣為T，文件上並沒有講如何實作這部分，我忘記是在哪找到要這樣寫的，就為了那個Output=T花了我超多時間RRRRR，反正Rust 的文件就是這樣…

fn inner_product<T: Mul<T, Output=T>+Add<T, Output=T>+Copy>

如果你要不同的實作，例如我要能夠跟i32 相加，那就是：

fn foo<T: Add<i32, Output=T>>(x: T) -> T { x+1 }

個人覺得：相較之下，C++運算子重載的語法真的相當的複雜（事實上我覺得我已經不會寫了Orz），rust 簡潔不少，使用trait 中的function name來實作也比C++ 用 operator+, operator* 好讀很多。

有關於文中所提Sign 的實作，可見：
https://github.com/yodalee/computationbook-rust/blob/master/programming_in_toyland/signs/sign.rs

Rust recursive structure

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

在建tree的部分，C++ 可能會定義介面用的base class ，再定義下面的derived class，這樣就能用base class 作為介面建tree，Rust 中我們可以用enum 做到這點，enum 除了像C like 的用法，也能指向物件，內含匿名或是有名的物件，我在這裡都是用匿名物件來實作：
https://doc.rust-lang.org/book/enums.html

#[derive(Clone)]
pub enum Node {
   Number(i64),
   Add(Box<node>, Box<node>),
   Multiply(Box<node>, Box<node>),
   Boolean(bool),
   LessThan(Box<node>, Box<node>),
   Variable(String),
   DoNothing,
   Assign(String, Box<node>),
   If(Box<node>, Box<node>, Box<node>),
   Sequence(Box<node>, Box<node>),
   While(Box<node>, Box<node>),
}

之所以要Box<Node> 而不是Node，在rustc --explain E0072 中有介紹，大體是recursive structure 裡，子物件若要包含父物件，一定要是Box 或是Reference &，否則程式算不出Node 需要多大。

用了enum 之後，其他function 的實作也就是在enum 上實作，並用match 來處理所有enum 可能出現的結果，例如我的reducible() 實作：

fn reducible(&self) -> bool {
  match *self {
    Node::Number(_) | Node::Boolean(_) | Node::DoNothing => false,
    _ => true,
  }
}

另外一個要注意的，是用了Box之後，前一篇我這樣寫：
http://yodalee.blogspot.tw/2015/11/rust-understanding-computation_5.html

pub fn reduce(self) -> Option {
 match self {
   Number(value) => Some(Number(value)),
   Add(l, r) => match (*l, *r) {
     (Number(i), Number(j)) => Some(Number(i+j)),
     (_, _) => None,
   }, 
   Nil => None,
 }
}

……reduce會將原本的node 替換掉，只能用self 當參數（好其實是我用&self就會出一些很詭異的錯誤，我還不知道怎麼解）

這個問題出在，我的寫法是Add(l, r) => ………
這樣的意思是，如果我們match Add，裡面的l, r的所有權<有可能>會被轉移掉，例如return l，或是return Box<l>，reduce function 又是寫 reduce(&self) 的話，表示我self 是跟人用reference 借來的，我不能又把self的所有權又送出去，所以rustc 會警告match *self這行：

cannot move out of borrowed content

即便你的code 沒有這麼做，rust 還是不允許這麼寫。
如果是 match self 當然沒這問題，但就如上所述，這會變成文中所述<reduce 就只能呼叫一次，之後原本持有的變數就不能再用>的結果，因為match self 的時候self的所有權就轉移掉了。
可編譯的寫法是：Add(ref l, ref r)，表示我l, r 仍然是借用，而借用的內容是傳不回去的，這樣一路從self下來都是借用，就沒有所有權轉移的問題；要傳回一個跟l 或r 一樣的內容，就要在Node 的屬性加上#[derive(Clone)]，用 l.clone()複製一個新的物件，試圖去dereference l 或r(*l, *r)同樣都會被rust 拒絕。

使用trait：
在本來的範例中他是將程式碼分到不同的資料夾，並用require_relative '../syntax/add' 的方式來擴展原有的程式，Rust不允許使用在上層資料夾裡面的程式碼，我這裡是利用trait 來達成模組化的目的。
Syntax.rs 中只定義AST 裡所需要的物件。
其他的function 我們都用trait 來定義，如果我們要用small_step 的reduce，就use reduce::{Reduce}，裡面就實作相關的function，好處是若main不需要reduce 的功能，不要use 這個trait 即可。

相關的原始碼可以看這裡：
https://github.com/yodalee/computationbook-rust/tree/master/the_meaning_of_programs