Learn Rust

前回扱うつもりで飛ばしてしまった、overview的なチュートリアル”Dining Philosophers” を扱います。

Dining Philosophers

並列計算に関する問題です。かのDijkstraの提示した問題をもとにした有名な話ですが、 設定を確認しておきます。

In ancient times, a wealthy philanthropist endowed a College to accommodate five eminent philosophers. Each philosopher had a room in which they could engage in their professional activity of thinking; there was also a common dining room, furnished with a circular table, surrounded by five chairs, each labelled by the name of the philosopher who was to sit in it. They sat anticlockwise around the table. To the left of each philosopher there was laid a golden fork, and in the centre stood a large bowl of spaghetti, which was constantly replenished. A philosopher was expected to spend most of their time thinking; but when they felt hungry, they went to the dining room, sat down in their own chair, picked up their own fork on their left, and plunged it into the spaghetti. But such is the tangled nature of spaghetti that a second fork is required to carry it to the mouth. The philosopher therefore had also to pick up the fork on their right. When they were finished they would put down both their forks, get up from their chair, and continue thinking. Of course, a fork can be used by only one philosopher at a time. If the other philosopher wants it, they just have to wait until the fork is available again. — C.A.R.Hoare Communicating Sequential Process June 21, 2004

テーブルを5人の哲学者が囲んでいます。 各人の左にはフォークが一つずつ、合計5本置いてあります。 彼らはこれを一本使って、テーブル中央におかれたスパゲッティ皿からフォークを使って手元に運び、 さらにもう一本で口に運びます。 哲学者は満腹になったらフォークをおき、部屋に戻って思索に耽ります。 もちろんそれぞれのフォークはひとりずつしか使えないので、 使おうとしたフォークが別の哲学者に使われていた場合、 フォークがまた使えるようになるまで待たなくてはなりません。

哲学者が食事を続けられるようにするためにはどうすればいいでしょうか。 単純なアルゴリズムとして、次が考えられます。

1. 哲学者が左にあるフォークを取る。
2. 続いて右にあるフォークを取る。
3. 食事をする。
4. 終わったら2本のフォークを置く。

このアルゴリズムはちゃんと動くでしょうか？ 例えば次のような場合を考えてみましょう。

1. 哲学者1が食事を始める。彼は左にあるフォークを取る。
2. 哲学者2が食事を始める。彼は左にあるフォークを取る。
3. 哲学者3が食事を始める。彼は左にあるフォークを取る。
4. 哲学者4が食事を始める。彼は左にあるフォークを取る。
5. 哲学者5が食事を始める。彼は左にあるフォークを取る。
6. …？誰もが右側のフォークを求めて待ち続けるようになってしまいました。

この問題の解決策はいくつかあります。たとえばWikipedia を見てください。

このチュートリアルでは独自の解放をとっているようです。 まずは問題をモデル化していきます。

struct Philosopher {
    name: String,
}

impl Philosopher {
    fn new(name: &str) -> Philosopher {
        Philosopher {
            name: name.to_string(),
        }
    }
}

fn main() {
    let p1 = Philosopher::new("Baruch Spinoza");
    let p2 = Philosopher::new("Gilles Deleuze");
    let p3 = Philosopher::new("Karl Marx");
    let p4 = Philosopher::new("Friedrich Nietzsche");
    let p5 = Philosopher::new("Michel Foucault");
}

哲学者を表す構造体を作っているようです。 structとimplがありますが、structはメンバ変数だけ、 implはメンバ関数を定義しています。 このように、構造と定義を別々に書くことができるということでしょうか？

ともかく、Philosopher構造体は、String型のnameメンバと new()メンバ関数をもっていることがわかります。

C++に引っ張られてメンバ関数と言ってしまいましたが、new()は’associated function’と呼ぶようです。 staticメンバ関数のようなものでしょうか。 new()関数は&strつまり文字列の参照を受け取り、 to_string()によってそのコピーを取り、nameに代入しています。 newという名前は構造体の新しいインスタンスを作るときによく使われるそうです。といっても、Pythonのように名前が限定されているわけではないようです。あくまで習慣というわけですね。

Stringを直接受け取らないのは、 呼び出し元でto_string()を呼ばなくていいようにするためだそうです。

この関数でも、returnは使わずexpressionを最後に書いて戻り値としていますね。

そしてmain()でnew()を呼び、哲学者を5人登場させています。 構造体のassociated functionにアクセスするときは::を使うようです。

基礎となる構造ができたので、実際の動作を付け加えていきます。

まずは哲学者に食事をさせるところからです。

use std::thread;

struct Philosopher {
    name: String,
}

impl Philosopher {
    fn new(name: &str) -> Philosopher {
        Philosopher {
            name: name.to_string(),
        }
    }

    fn eat(&self) {
        println!("{} is eating.", self.name);

        thread::sleep_ms(1000);

        println!("{} is done eating.", self.name);
    }
}

fn main() {
    let philosophers = vec![
        Philosopher::new("Judith Butler"),
        Philosopher::new("Gilles Deleuze"),
        Philosopher::new("Karl Marx"),
        Philosopher::new("Emma Goldman"),
        Philosopher::new("Michel Foucault"),
    ];

    for p in &philosophers {
        p.eat();
    }
}

まずmain()を見てみると、哲学者たちをvec!で作ることにしました。 vec!はmacroの一つで、Vec<T>という型のvectorを作るようです。 おそらく<T>はC++のtemplateのようなものでしょうね。 このvectorをforループで走査し、pに参照を代入しています。

Philosopher構造体に新たにeat()関数をつくりました。 Rustではassociated functionでなく、インスタンスに紐付いたmethodを作る場合、 selfの参照を明示的に受け取るようにするようです。 eat()関数のなかでは、selfを通してnameにアクセスしています。

さらに、eat()に時間をかけて実際に食べているようにするために、 thread::sleep_ms()関数を使いました。 これを使うためには、use std::thread;としてincludeする必要があるようです。

このコードはまだシングルスレッドです。 つまり哲学者たちはひとりずつしか食事ができません。 マルチスレッドにしてみましょう。

let philosophers = vec![
    // 略
];

let handles: Vec<_> = philosophers.into_iter().map(|p| {
    thread::spawn(move || {
        p.eat();
    })
}).collect();

for h in handles {
    h.join.unwrap();
}

handlesというvariable bindingをつくっています。 新しく作ったスレッドを扱うハンドルという意味だそうです。

少しずつ見ていきます。

philosophers.into_iter().map(|p| {

into_iter()関数は、哲学者のownershipをとるイテレータを生成します。 さらに各イテレータに対してmap()関数でclosureを渡し、呼び出しているようです。

thread::spawn(move || {
    p.eat();
})

ここでスレッドが作られ、並列に実行されます。 thread::spawn()関数はclosureを一つとり、新しいスレッドをつくってそれを実行するそうです。 ここではmoveというアノテーションを書いています。 これによって、キャプチャした値、すなわちpのownershipがclosure内に移動するようです。

ここでもthread::spawn()にセミコロン;をつけず、expressionとして戻り値を返しています。

}).collect();

最後にcollect()を呼んでいます。 この関数はmap()の結果をまとめ、’collection of some kind’を作りますが、 どんな型にまとめるかの情報が必要になります。 それがhandlesを定義するときに型注釈として書いたVec<_>というわけです。 collect()の戻り値をvectorに指定するが、その内部の型はRustの型推論で決めよ、ということらしいです。

forループも変わっています。 操作するのはスレッドを扱うhandlesになり、ループ内部ではそれをjoin()しています。 unwrap()については現時点ではよくわかりません。

ともかく、これでマルチスレッドができました。 実行してみると、例えば以下のような出力になり、並列に実行されていることが確認できます。

Judith Butler is eating.
Gilles Deleuze is eating.
Karl Marx is eating.
Emma Goldman is eating.
Michel Foucault is eating.
Judith Butler is done eating.
Gilles Deleuze is done eating.
Karl Marx is done eating.
Emma Goldman is done eating.
Michel Foucault is done eating.

さて、フォークをモデル化するのを忘れていました。 新しいstructを追加します。

use std::sync::Mutec;

struct Table {
    forks: Vec<Mutex<()>>,
}

フォークをmutexとみなし、それが置いてあるTableをつくりました。 Mutexには内部の型を指定するようですが、今回は内部の値を使用するわけではないので、単に空tuple()としています。

このTableを組み込みましょう。

順に見ていきます。

まずstd::sync::Arcもincludeします。 std::sync内のものを複数includeするときはこんな書き方もできるんですね。

struct Philosopher {
    name: String,
    left: usize,
    right: usize,
}

Philosopher構造体に二つのフィールドを追加しました。 left, rightがそれぞれフォークを表します。 型がusizeとなっているのは、フォークのvectorのindexを受け取るためのようです。

    fn new(name: &str, left: usize, right: usize) -> Philosopher {
        Philosopher {
            name: name.to_string(),
            left: left,
            right: right,
        }
    }

Philosopher::new()も書き直します。使用するフォークのindexをとるようにしました。

    fn eat(&self, table: &Table) {
        let _left = table.forks[self.left].lock().unwrap();
        let _right = table.forks[self.right].lock().unwrap();

        println!("{} is eating.", self.name);

        thread::sleep_ms(1000);

        println!("{} is done eating.", self.name);
    }

eat()関数は、フォークのTableの参照をとって、先ほど追加したleft, rightをindexとするmutexをlock()するようにしました。 またunwrap()がでてきましたが、詳しい説明はされていませんでした。

さて、こうして得たロックを_left, _rightというvariable bindingに代入しています。 アンダーバー_をつけると、このvariable bindingは未使用であるとの印になり、 コンパイラの警告を抑制できると書いてありました。

そしてロック解除は、スコープを抜けて_left, _rightが破棄されるとき自動でおこなわれるようです。 C++でいうデストラクタの処理ですね。

main()内に入っていきます。

let table = Arc::new(Table { forks: vec![
    Mutex::new(()),
    Mutex::new(()),
    Mutex::new(()),
    Mutex::new(()),
    Mutex::new(()),
]});

Table構造体のインスタンスtableをつくりました。 ‘arc’は’atomic reference count’の略で、tableを複数スレッドで扱うため、 Arcとしてつくっているようです。 tableを共有するごとに参照カウンタが増え、スレッドを抜けると減る、という仕組みです。

let philosophers = vec![
    Philosopher::new("Judith Butler", 0, 1),
    Philosopher::new("Gilles Deleuze", 1, 2),
    Philosopher::new("Karl Marx", 2, 3),
    Philosopher::new("Emma Goldman", 3, 4),
    Philosopher::new("Michel Foucault", 0, 4),
];

Philosopher::new()にフォークのindexも加えて渡すようにしました。 ここで注意したいのが、最後のMichel Foucaultに渡すindexが、 4, 0ではなく0, 4になっていることです。 もし4, 0にすると、冒頭のデッドロックが起きてしまいます。

Learn Rust

前回扱うつもりで飛ばしてしまった、overview的なチュートリアル”Dining Philosophers” を扱います。

Dining Philosophers

並列計算に関する問題です。かのDijkstraの提示した問題をもとにした有名な話ですが、 設定を確認しておきます。

In ancient times, a wealthy philanthropist endowed a College to accommodate five eminent philosophers. Each philosopher had a room in which they could engage in their professional activity of thinking; there was also a common dining room, furnished with a circular table, surrounded by five chairs, each labelled by the name of the philosopher who was to sit in it. They sat anticlockwise around the table. To the left of each philosopher there was laid a golden fork, and in the centre stood a large bowl of spaghetti, which was constantly replenished. A philosopher was expected to spend most of their time thinking; but when they felt hungry, they went to the dining room, sat down in their own chair, picked up their own fork on their left, and plunged it into the spaghetti. But such is the tangled nature of spaghetti that a second fork is required to carry it to the mouth. The philosopher therefore had also to pick up the fork on their right. When they were finished they would put down both their forks, get up from their chair, and continue thinking. Of course, a fork can be used by only one philosopher at a time. If the other philosopher wants it, they just have to wait until the fork is available again. — C.A.R.Hoare Communicating Sequential Process June 21, 2004

テーブルを5人の哲学者が囲んでいます。 各人の左にはフォークが一つずつ、合計5本置いてあります。 彼らはこれを一本使って、テーブル中央におかれたスパゲッティ皿からフォークを使って手元に運び、 さらにもう一本で口に運びます。 哲学者は満腹になったらフォークをおき、部屋に戻って思索に耽ります。 もちろんそれぞれのフォークはひとりずつしか使えないので、 使おうとしたフォークが別の哲学者に使われていた場合、 フォークがまた使えるようになるまで待たなくてはなりません。

哲学者が食事を続けられるようにするためにはどうすればいいでしょうか。 単純なアルゴリズムとして、次が考えられます。

1. 哲学者が左にあるフォークを取る。
2. 続いて右にあるフォークを取る。
3. 食事をする。
4. 終わったら2本のフォークを置く。

このアルゴリズムはちゃんと動くでしょうか？ 例えば次のような場合を考えてみましょう。

1. 哲学者1が食事を始める。彼は左にあるフォークを取る。
2. 哲学者2が食事を始める。彼は左にあるフォークを取る。
3. 哲学者3が食事を始める。彼は左にあるフォークを取る。
4. 哲学者4が食事を始める。彼は左にあるフォークを取る。
5. 哲学者5が食事を始める。彼は左にあるフォークを取る。
6. …？誰もが右側のフォークを求めて待ち続けるようになってしまいました。

この問題の解決策はいくつかあります。たとえばWikipedia を見てください。

このチュートリアルでは独自の解放をとっているようです。 まずは問題をモデル化していきます。

struct Philosopher {
    name: String,
}

impl Philosopher {
    fn new(name: &str) -> Philosopher {
        Philosopher {
            name: name.to_string(),
        }
    }
}

fn main() {
    let p1 = Philosopher::new("Baruch Spinoza");
    let p2 = Philosopher::new("Gilles Deleuze");
    let p3 = Philosopher::new("Karl Marx");
    let p4 = Philosopher::new("Friedrich Nietzsche");
    let p5 = Philosopher::new("Michel Foucault");
}

哲学者を表す構造体を作っているようです。 structとimplがありますが、structはメンバ変数だけ、 implはメンバ関数を定義しています。 このように、構造と定義を別々に書くことができるということでしょうか？

ともかく、Philosopher構造体は、String型のnameメンバと new()メンバ関数をもっていることがわかります。

C++に引っ張られてメンバ関数と言ってしまいましたが、new()は’associated function’と呼ぶようです。 staticメンバ関数のようなものでしょうか。 new()関数は&strつまり文字列の参照を受け取り、 to_string()によってそのコピーを取り、nameに代入しています。 newという名前は構造体の新しいインスタンスを作るときによく使われるそうです。といっても、Pythonのように名前が限定されているわけではないようです。あくまで習慣というわけですね。

Stringを直接受け取らないのは、 呼び出し元でto_string()を呼ばなくていいようにするためだそうです。

この関数でも、returnは使わずexpressionを最後に書いて戻り値としていますね。

そしてmain()でnew()を呼び、哲学者を5人登場させています。 構造体のassociated functionにアクセスするときは::を使うようです。

基礎となる構造ができたので、実際の動作を付け加えていきます。

まずは哲学者に食事をさせるところからです。

use std::thread;

struct Philosopher {
    name: String,
}

impl Philosopher {
    fn new(name: &str) -> Philosopher {
        Philosopher {
            name: name.to_string(),
        }
    }

    fn eat(&self) {
        println!("{} is eating.", self.name);

        thread::sleep_ms(1000);

        println!("{} is done eating.", self.name);
    }
}

fn main() {
    let philosophers = vec![
        Philosopher::new("Judith Butler"),
        Philosopher::new("Gilles Deleuze"),
        Philosopher::new("Karl Marx"),
        Philosopher::new("Emma Goldman"),
        Philosopher::new("Michel Foucault"),
    ];

    for p in &philosophers {
        p.eat();
    }
}

まずmain()を見てみると、哲学者たちをvec!で作ることにしました。 vec!はmacroの一つで、Vec<T>という型のvectorを作るようです。 おそらく<T>はC++のtemplateのようなものでしょうね。 このvectorをforループで走査し、pに参照を代入しています。

Philosopher構造体に新たにeat()関数をつくりました。 Rustではassociated functionでなく、インスタンスに紐付いたmethodを作る場合、 selfの参照を明示的に受け取るようにするようです。 eat()関数のなかでは、selfを通してnameにアクセスしています。

さらに、eat()に時間をかけて実際に食べているようにするために、 thread::sleep_ms()関数を使いました。 これを使うためには、use std::thread;としてincludeする必要があるようです。

このコードはまだシングルスレッドです。 つまり哲学者たちはひとりずつしか食事ができません。 マルチスレッドにしてみましょう。

let philosophers = vec![
    // 略
];

let handles: Vec<_> = philosophers.into_iter().map(|p| {
    thread::spawn(move || {
        p.eat();
    })
}).collect();

for h in handles {
    h.join.unwrap();
}

handlesというvariable bindingをつくっています。 新しく作ったスレッドを扱うハンドルという意味だそうです。

少しずつ見ていきます。

philosophers.into_iter().map(|p| {

into_iter()関数は、哲学者のownershipをとるイテレータを生成します。 さらに各イテレータに対してmap()関数でclosureを渡し、呼び出しているようです。

thread::spawn(move || {
    p.eat();
})

ここでスレッドが作られ、並列に実行されます。 thread::spawn()関数はclosureを一つとり、新しいスレッドをつくってそれを実行するそうです。 ここではmoveというアノテーションを書いています。 これによって、キャプチャした値、すなわちpのownershipがclosure内に移動するようです。

ここでもthread::spawn()にセミコロン;をつけず、expressionとして戻り値を返しています。

}).collect();

最後にcollect()を呼んでいます。 この関数はmap()の結果をまとめ、’collection of some kind’を作りますが、 どんな型にまとめるかの情報が必要になります。 それがhandlesを定義するときに型注釈として書いたVec<_>というわけです。 collect()の戻り値をvectorに指定するが、その内部の型はRustの型推論で決めよ、ということらしいです。

forループも変わっています。 操作するのはスレッドを扱うhandlesになり、ループ内部ではそれをjoin()しています。 unwrap()については現時点ではよくわかりません。

ともかく、これでマルチスレッドができました。 実行してみると、例えば以下のような出力になり、並列に実行されていることが確認できます。

Judith Butler is eating.
Gilles Deleuze is eating.
Karl Marx is eating.
Emma Goldman is eating.
Michel Foucault is eating.
Judith Butler is done eating.
Gilles Deleuze is done eating.
Karl Marx is done eating.
Emma Goldman is done eating.
Michel Foucault is done eating.

さて、フォークをモデル化するのを忘れていました。 新しいstructを追加します。

use std::sync::Mutec;

struct Table {
    forks: Vec<Mutex<()>>,
}

フォークをmutexとみなし、それが置いてあるTableをつくりました。 Mutexには内部の型を指定するようですが、今回は内部の値を使用するわけではないので、単に空tuple()としています。

このTableを組み込みましょう。

順に見ていきます。

まずstd::sync::Arcもincludeします。 std::sync内のものを複数includeするときはこんな書き方もできるんですね。

struct Philosopher {
    name: String,
    left: usize,
    right: usize,
}

Philosopher構造体に二つのフィールドを追加しました。 left, rightがそれぞれフォークを表します。 型がusizeとなっているのは、フォークのvectorのindexを受け取るためのようです。

    fn new(name: &str, left: usize, right: usize) -> Philosopher {
        Philosopher {
            name: name.to_string(),
            left: left,
            right: right,
        }
    }

Philosopher::new()も書き直します。使用するフォークのindexをとるようにしました。

    fn eat(&self, table: &Table) {
        let _left = table.forks[self.left].lock().unwrap();
        let _right = table.forks[self.right].lock().unwrap();

        println!("{} is eating.", self.name);

        thread::sleep_ms(1000);

        println!("{} is done eating.", self.name);
    }

eat()関数は、フォークのTableの参照をとって、先ほど追加したleft, rightをindexとするmutexをlock()するようにしました。 またunwrap()がでてきましたが、詳しい説明はされていませんでした。

さて、こうして得たロックを_left, _rightというvariable bindingに代入しています。 アンダーバー_をつけると、このvariable bindingは未使用であるとの印になり、 コンパイラの警告を抑制できると書いてありました。

そしてロック解除は、スコープを抜けて_left, _rightが破棄されるとき自動でおこなわれるようです。 C++でいうデストラクタの処理ですね。

main()内に入っていきます。

let table = Arc::new(Table { forks: vec![
    Mutex::new(()),
    Mutex::new(()),
    Mutex::new(()),
    Mutex::new(()),
    Mutex::new(()),
]});

Table構造体のインスタンスtableをつくりました。 ‘arc’は’atomic reference count’の略で、tableを複数スレッドで扱うため、 Arcとしてつくっているようです。 tableを共有するごとに参照カウンタが増え、スレッドを抜けると減る、という仕組みです。

let philosophers = vec![
    Philosopher::new("Judith Butler", 0, 1),
    Philosopher::new("Gilles Deleuze", 1, 2),
    Philosopher::new("Karl Marx", 2, 3),
    Philosopher::new("Emma Goldman", 3, 4),
    Philosopher::new("Michel Foucault", 0, 4),
];

Philosopher::new()にフォークのindexも加えて渡すようにしました。 ここで注意したいのが、最後のMichel Foucaultに渡すindexが、 4, 0ではなく0, 4になっていることです。 もし4, 0にすると、冒頭のデッドロックが起きてしまいます。

let handles: Vec<_> = philosophers.into_iter().map(|p| {
    let table = table.clone();

    thread::spawn(move || {
        p.eat(&table);
    })
}).collect();

最後に、map()に渡すclosure内でtableをclone()しています。 Arc<T>型のインスタンスに対してclone()すると、参照カウンタが増えるとのことです。

これで解決です。哲学者たちはデッドロックに陥らず、食事を続けられるようになりました。 ちょっと工夫するだけで簡単に問題解決しちゃいました。

let handles: Vec<_> = philosophers.into_iter().map(|p| {
    let table = table.clone();

    thread::spawn(move || {
        p.eat(&table);
    })
}).collect();

最後に、map()に渡すclosure内でtableをclone()しています。 Arc<T>型のインスタンスに対してclone()すると、参照カウンタが増えるとのことです。

これで解決です。哲学者たちはデッドロックに陥らず、食事を続けられるようになりました。