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