rust langでturing machineもどき

github.com

rustの線形型やリージョン推論をすごいすごい言っていたりするのにコードを書いていないのは良くないので、 rust langの練習用にチューリングマシンエミュレータのようなものを作った。

あまり説明する気のない説明

状態Sと、記号と空白記号の集合Lをenumを使った代数的データ構造で定義し、
関数stepをs ∈ Sとテープ上の l ∈ Lによって状態を遷移させる遷移関数とする。sとlはmatch syntaxで判別する。
テープは構造体で表し、Vectorと現在の参照位置をusizeで持った。

enum L {
    Blank,
    X,
    One,
    Zero,
}


let mut tape = [L::Blank, L::One, L::Zero, L::Zero, L::One, L::Blank ];

これは 1001 を表す

{0,1}で表される単語wとその反転reverse w = w'が並んでいるww'なテープを得たときのみState::start()がtrueを返す。 雰囲気はテストコードを見て感じ取って欲しい。

$cargo test
or 
$cargo run 

で9つのテストコードかmain関数が走るようになっている。

ちょっと大変だったこと

テープの表現は

struct State<'a> {
    tape: &'a mut Vec<L>,
    ptr: usize,
}

と書いている。
Vectorで無限長のテープの表現、ptrで今の参照位置だ。変数名ptrなのにvalueなのが気持ち悪いとか言わないで欲しい。 しばらくの間は

struct State<'a> {
    tape: &'a Vec<L>,
    ptr: usize,
}

としていたのだけれど、これだと

impl<a'> State<'a>{

  fn assign(&mut self, n : usize, v : L) {
     let ref mut tape = self.tape;
      tape[n] =  v;
  }

}

のような関数はコンパイルエラー。なぜかというと、selfはmutableでborrowingしているのにVectorはimmutableになって変更できないため。
構造体内の参照はmutable or immutableを選べるとはしらなかった。 あとlet ref mut tape = sefl.tape.clone()でvectorの参照をclone()してくれると思って書いていたら値も丸ごとcloneしていた。

fn f(v : &mut Vec<usize>){                                  
    let mut vec = v.clone();                                
    vec[1] = 1;                                             
}

fn main() {
    let mut vec : Vec<usize> = vec![0,0,0,0];
    f(&mut vec);
    for v in &vec {
    println!("{}", v);
    }
}

--出力
0
0
0
0

次のお題

マークアップ言語パーサを書く。