使用Rust 實作Understanding Computation

Understanding Compuation (http://computationbook.com/) 是一本滿有意思的書，它很純粹的介紹<計算>這件事，第一從程式的syntax、DFA、Deterministic Pushdown Automata到Turing Machine，第二部分則從Turing Machine 開始，列舉了很多的種運算模型都能達到和Turing Machine 同樣的運算能力；相反的，從Halting problem跟所有衍生的問題，它也告訴你運算就是有它的極限。

書裡的範例都附有Ruby code，全部放在作者的github 上面，讓人隨時可以測試：
https://github.com/tomstuart/computationbook

最近興起一個念頭，把這上面的code 全部用Rust 重寫一遍，順便當Rust的練習，現在還在實作一開始的syntax 部分；之前針對這部分寫了有關trait 的內容，不過後來被我刪掉了，因為我發現在Rust 裡面其實有更好的實作方式。
之前我說的是，設定trait 為base object，下轄的node impl這個trait，這樣Box<base>就可以容得下所有有實作這個trait 的struct，就像：

trait Expr {
  fn to_s(&self) -> String
}

struct Add {
  l: Box,
  r: Box,
}

impl Expr for Add {
  fn to_s(&self) -> String {
    self.l.to_string() + “ + ” + &self.r.to_string()
  }
}

但其實這樣根本寫不出來（要不就是極度麻煩），在reduce 的時候，要把Add裡面的box 換成另一個value，或是Add reduce 到一個Number，受限於Rust pointer的Owner設計，操作Box需要一層又一層的檢查，這裡就不細講那悲劇性的結果，事實上根本就沒有結果，code 根本不到能動的地步。

反思一下，多看了幾個Rust by Example，突然發現新的寫法：
註：主要是這篇rust 裡linked list 的寫法：
http://rustbyexample.com/custom_types/enum/testcase_linked_list.html

利用Rust 的enum，把相關的struct 都收進一個enum裡面，這個寫法還滿鮮的，而且跟書裡Ruby 的寫法比較不同。
用Ruby若要實作每個node 的reducible function，因為Ruby 偏向OO語言，書中是在每個struct …或class裡面實作reducible function；Rust 因為所有的種類node都由enum管理，會變成這樣寫：

pub enum Syntax {
  Add (Box, Box),
  Number (i32),
  Nil,
}

impl Syntax {
  pub fn reducible(&self) -> bool {
    match *self {
      Number(value) => false,
      Add(ref l, ref r) => true,
      Nil => false,
    }
  }
}

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,
  }
}

註：其實我也不知道需不需要Nil 這個type。

我們要針對每個不同的型態去實作它們的函式，有些相對簡單，例如reducible()，只有variable 跟number兩樣會是false，其他就用 '_' 全部消掉，雖然所有型態的function 擠在同一個impl 裡面感覺很煩躁，不過好像沒更好的實作方式，這某種程度上來說也是語言設計上的限制吧？

另外上面也可以看到，在reducible跟reduce上，我們的寫法有些許不同，reducible使用的是&self當參數，它不會持有這個syntax的所有權；相反的reduce會將原本的node 替換掉，只能用self 當參數（好其實是我用&self就會出一些很詭異的錯誤，我還不知道怎麼解）
在使用上這會有點差別，reducible 可以一直呼叫，reduce 就只能呼叫一次，之後原本持有的變數就不能再用，我們必須用let將它的所有權轉給另一個變數，如下：

let a = Add(Box::new(Number(1)), Box::new(Number(2)));
println!("{}", a.reducible());
println!("{}", a.reducible());
let m = Add(Box::new(Number(4)), Box::new(Number(10)));
//println!("{}", m.reduce());
let m = m.reduce();
println!("{}", m.reducible());

上面註解的那行不能這麼做，之後m不再持有回傳值的所有權，之後呼叫m.reducible()會形成compile error。
其實這樣滿奇怪的，總覺得這樣用起來限制也太多；當然我們可以把syntax 再封裝到一個struct裡面，每次reduce就自動做一次let m = m.reduce()，使用者就無法亂用reduce()讓編譯爆掉，再研究要怎麼寫比較好囉…

我的code 都會放在這裡，雖然說現在真的沒什麼內容，現在還在實作ch1 的內容，而且感覺還沒進到Rust 的思考領域，寫的東西感覺大有問題……
https://github.com/yodalee/computationbook-rust

https://github.com/yodalee/computationbook-rust/tree/ch1-the-syntax