2015年11月6日 星期五

使用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

沒有留言:

張貼留言