Don't Repeat Yourself

Don't Repeat Yourself (DRY) is a principle of software development aimed at reducing repetition of all kinds. -- wikipedia

Multimap を Rust でも使う(と、クレートの選び方)

先日仕事で、Rust を使用してとあるアプリケーションを作っていたところ、Guava の Multimap のようなデータ構造がほしいと思う場面がありました。

Guava の Multimap というのは、Java のライブラリ Guava に存在する HashMap の value 側がリストやベクタなどの複数要素を格納できる構造になっている Map です。具体的には下記のようなシグネチャなのですが、値側の実体はベクタとして管理される(つまり実質、HashMap<String, List<String>>)というものです。詳しいチュートリアルはこちらにあり、下記では Java コードをこの記事より引用させていただいております。

String key = "a-key";
Multimap<String, String> map = ArrayListMultimap.create();

map.put(key, "firstValue");
map.put(key, "secondValue");

// この時点で、{key, ["firstValue", "secondValue"]} という感じのマップができあがっている。

assertEquals(2, map.size());

Rust ではクレートを探すとだいたいのものはすでに誰かが作ってくれています。ということで、探してみました。「multimap」という名前では複数件該当しましたが、下記のクレートがよさそうに感じました。

github.com

この記事は Multimap の紹介ではあるものの、クレートを普段どう選んでいるかを少しメモしておく記事にもしておきたいと思っています。参考になれば幸いです。

私的クレートの選び方

さて、クレートを選ぶときに少し迷うのが、「ではこのクレートの評判はどうなのか」という点でしょう。クレートの評判を決める基準は今のところほぼないと思いますが、私は次のような点を見ながら使用を検討するテーブルにあげるかどうかを決めています。

  • GitHub のスター数
  • crates.io でのダウンロード数
  • どういう人(たち)が作っているか
  • README や doc を読んで使い方がイメージできるか

GitHub のスター数は少し迷う水準でした。24スターだったためです。スターはたしかに安心材料あるいは不安材料になり得ます。Rust を使っているときは、個人的には100件以上のスターがついていると少し安心できる感があります。

一方で、crates.io でのダウンロード数はかなりの数がありますね。2021年3月26日時点では 3,528,280 件のダウンロードが確認できます。GitHub のスターこそ少ないものの、かなり幅広いユーザーに使われてきた「枯れた」クレートなのだと判断できました。

Rust ではこのように、GitHub のスター数は多くはないものの、Rust ユーザーにはかなり多く使われているクレートが存在するように思います。

今回は確認しませんでしたが、作者を見に行くこともあります。私は、Organization で管理されているクレートはより優先して使いたいと思います。会社単位や組織単位で管理されているクレートは、長続きしそうな感じがするからです。作者を確認しに行く気持ちは、食料品をスーパーで買うときに、生産者の顔が見えると安心感を覚えるあれに近いと思います。

doc を読んで使い方がイメージできないものは、詰まったときにいろいろ困ってしまいます。他に代替のクレートが存在した場合には、doc に example がなく使い方がイメージできないものは切ってしまうことがあります。

README などを読む限りでは、私が使いたいと思っていた機能がおおよそ揃っていそうで使いたかったので、最後の決め手として実装を読んで判断しようと思いました。詳しくは書きませんが、実装を読んだ限り非常にシンプルに HashMap をラップした実装で、これなら安心して使えそうと思い使用の判断に至りました。

みなさんはどう選んでいますか?

Multimap を使ってみる

ようやく本題に入るわけですが、Multimap を使ってみましょう。実際にアプリケーションに書いたコードはお見せできませんが、別の例で使い方を見ていきたいと思います。

ベクタから MultiMap を作る

今回の題材は通貨間の価格を記録するものとします。USD/JPY や JPY/USD の値を保持しているベクタが存在しており、そのベクタは順不同で CurrencyRate というデータをもっているものとします。最終的には、通貨ペア CurrencyPair をキーとし、値にレート CurrencyRate.rate のベクタをもつ MultiMap が生成されることを想定しています。

コードは次のようになります。

#![allow(dead_code)]

use chrono::{DateTime, Utc};
use multimap::MultiMap;

#[derive(PartialEq, Eq, Hash)]
enum CurrencyKind {
    Usd,
    Jpy,
}

#[derive(PartialEq, Eq, Hash)]
struct CurrencyPair {
    base: CurrencyKind,
    quote: CurrencyKind,
}

impl CurrencyPair {
    fn usd_jpy() -> CurrencyPair {
        CurrencyPair {
            base: CurrencyKind::Usd,
            quote: CurrencyKind::Jpy,
        }
    }

    fn jpy_usd() -> CurrencyPair {
        CurrencyPair {
            base: CurrencyKind::Jpy,
            quote: CurrencyKind::Usd,
        }
    }
}

struct CurrencyRate {
    currency_pair: CurrencyPair,
    rate: f64,
    datetime: DateTime<Utc>,
}

impl CurrencyRate {
    fn usd_jpy(rate: f64) -> CurrencyRate {
        CurrencyRate {
            currency_pair: CurrencyPair::usd_jpy(),
            rate,
            datetime: Utc::now(),
        }
    }

    fn jpy_usd(rate: f64) -> CurrencyRate {
        CurrencyRate {
            currency_pair: CurrencyPair::jpy_usd(),
            rate,
            datetime: Utc::now(),
        }
    }
}

fn main() {
    let mixed_currency_rate_chart = vec![
        CurrencyRate::usd_jpy(106.0),
        CurrencyRate::usd_jpy(106.3),
        CurrencyRate::jpy_usd(0.0092),
        CurrencyRate::jpy_usd(0.0095),
        CurrencyRate::usd_jpy(106.4),
        CurrencyRate::jpy_usd(0.0093),
    ];

    let currency_rate_map: MultiMap<CurrencyPair, f64> = mixed_currency_rate_chart
        .into_iter()
        .map(|elem| (elem.currency_pair, elem.rate))
        .collect();

    let usd_jpy = currency_rate_map.get_vec(&CurrencyPair::usd_jpy()).unwrap();
    assert_eq!(*usd_jpy, vec![106.0, 106.3, 106.4]);

    let jpy_usd = currency_rate_map.get_vec(&CurrencyPair::jpy_usd()).unwrap();
    assert_eq!(*jpy_usd, vec![0.0092, 0.0095, 0.0093]);
}

最終的には、

  • CurrencyPair { base: CurrencyKind::Usd, quote: CurrencyKind::Jpy } というキーに対しては [106.0, 106.3, 106.4] が入っている。
  • CurrencyPair { base: CurrencyKind::Jpy, quote: CurrencyKind::Usd } というキーに対しては [0.0092, 0.0095, 0.0093] が入っている。

という結果が得られます。

要素を追加する

要素を追加するにはマップの変数束縛を可変にし、insert メソッドを呼び出すことで可能です。値側の配列に値が追加されます。

// 先ほどの例から main 関数部分だけを抜き出した

fn main() {
    let mixed_currency_rate_chart = vec![
        CurrencyRate::usd_jpy(106.0),
        CurrencyRate::usd_jpy(106.3),
        CurrencyRate::jpy_usd(0.0092),
        CurrencyRate::jpy_usd(0.0095),
        CurrencyRate::usd_jpy(106.4),
        CurrencyRate::jpy_usd(0.0093),
    ];

    let mut currency_rate_map: MultiMap<CurrencyPair, f64> = mixed_currency_rate_chart
        .into_iter()
        .map(|elem| (elem.currency_pair, elem.rate))
        .collect();

    let usd_jpy = currency_rate_map.get_vec(&CurrencyPair::usd_jpy()).unwrap();
    assert_eq!(*usd_jpy, vec![106.0, 106.3, 106.4]);

    let jpy_usd = currency_rate_map.get_vec(&CurrencyPair::jpy_usd()).unwrap();
    assert_eq!(*jpy_usd, vec![0.0092, 0.0095, 0.0093]);

    // insert をしてみる
    currency_rate_map.insert(CurrencyPair::usd_jpy(), 110.0);
    let new_usd_jpy = currency_rate_map.get_vec(&CurrencyPair::usd_jpy()).unwrap();
    // 110.0 という値をベクタに追加できていることがわかる
    assert_eq!(*new_usd_jpy, vec![106.0, 106.3, 106.4, 110.0]);
}

insert_many_from_slice メソッドを呼び出すとスライスをごそっと追加することもできます。

fn main() {
    let mixed_currency_rate_chart = vec![
        CurrencyRate::usd_jpy(106.0),
        CurrencyRate::usd_jpy(106.3),
        CurrencyRate::jpy_usd(0.0092),
        CurrencyRate::jpy_usd(0.0095),
        CurrencyRate::usd_jpy(106.4),
        CurrencyRate::jpy_usd(0.0093),
    ];

    let mut currency_rate_map: MultiMap<CurrencyPair, f64> = mixed_currency_rate_chart
        .into_iter()
        .map(|elem| (elem.currency_pair, elem.rate))
        .collect();

    let usd_jpy = currency_rate_map.get_vec(&CurrencyPair::usd_jpy()).unwrap();
    assert_eq!(*usd_jpy, vec![106.0, 106.3, 106.4]);

    let jpy_usd = currency_rate_map.get_vec(&CurrencyPair::jpy_usd()).unwrap();
    assert_eq!(*jpy_usd, vec![0.0092, 0.0095, 0.0093]);

    // スライスをごそっと追加する
    currency_rate_map
        .insert_many_from_slice(CurrencyPair::usd_jpy(), &[110.0, 110.2, 110.3, 110.4]);
    let new_usd_jpy = currency_rate_map.get_vec(&CurrencyPair::usd_jpy()).unwrap();

    // スライスで追加した分が末尾に増えている
    assert_eq!(
        *new_usd_jpy,
        vec![106.0, 106.3, 106.4, 110.0, 110.2, 110.3, 110.4]
    );
}

要素を取得する

get をすると、キーに該当する配列から最初の値への参照だけを取得することができます。ここは少し注意が必要かもしれません。

fn main() {
    let mixed_currency_rate_chart = vec![
        CurrencyRate::usd_jpy(106.0),
        CurrencyRate::usd_jpy(106.3),
        CurrencyRate::jpy_usd(0.0092),
        CurrencyRate::jpy_usd(0.0095),
        CurrencyRate::usd_jpy(106.4),
        CurrencyRate::jpy_usd(0.0093),
    ];

    let currency_rate_map: MultiMap<CurrencyPair, f64> = mixed_currency_rate_chart
        .into_iter()
        .map(|elem| (elem.currency_pair, elem.rate))
        .collect();

    let usd_jpy = currency_rate_map.get(&CurrencyPair::usd_jpy()).unwrap();
    // キーに対応する値のベクタの先頭を取得する
    assert_eq!(*usd_jpy, 106.0);
}

MultiMap を使用する場合、キーで値のベクタを全部引けると嬉しいはずです。これは先ほどから紹介しておりますが、get_vec というメソッドで取得できます。

fn main() {
    let mixed_currency_rate_chart = vec![
        CurrencyRate::usd_jpy(106.0),
        CurrencyRate::usd_jpy(106.3),
        CurrencyRate::jpy_usd(0.0092),
        CurrencyRate::jpy_usd(0.0095),
        CurrencyRate::usd_jpy(106.4),
        CurrencyRate::jpy_usd(0.0093),
    ];

    let currency_rate_map: MultiMap<CurrencyPair, f64> = mixed_currency_rate_chart
        .into_iter()
        .map(|elem| (elem.currency_pair, elem.rate))
        .collect();

    let usd_jpy = currency_rate_map.get_vec(&CurrencyPair::usd_jpy()).unwrap();
    assert_eq!(*usd_jpy, vec![106.0, 106.3, 106.4]);
}

可変な参照を取得したい場合には、HashMap と同様に get_mut がある他、get_vec_mut もあります。

Entry → orInsert

HashMap にある entryor_insert のベクタ版も存在します。これは、値が1つもなかったらデフォルト値を設定する操作をするメソッドです。

fn main() {
    let mixed_currency_rate_chart = vec![
        CurrencyRate::usd_jpy(106.0),
        CurrencyRate::usd_jpy(106.3),
        CurrencyRate::jpy_usd(0.0092),
        CurrencyRate::jpy_usd(0.0095),
        CurrencyRate::usd_jpy(106.4),
        CurrencyRate::jpy_usd(0.0093),
    ];

    let mut currency_rate_map: MultiMap<CurrencyPair, f64> = mixed_currency_rate_chart
        .into_iter()
        .map(|elem| (elem.currency_pair, elem.rate))
        .collect();

    let usd_jpy = currency_rate_map.get_vec(&CurrencyPair::usd_jpy()).unwrap();
    assert_eq!(*usd_jpy, vec![106.0, 106.3, 106.4]);

    currency_rate_map
        .entry(CurrencyPair::usd_jpy())
        .or_insert_vec(vec![0.0, 999.9]);

    // 今回はすでに値が入っており、0と999.9が入ることはない。
    let usd_jpy = currency_rate_map.get_vec(&CurrencyPair::usd_jpy()).unwrap();
    assert_eq!(*usd_jpy, vec![106.0, 106.3, 106.4]);
}

なぜイテレータから、いろいろ複雑そうな Multimap にスッと復元できるのか

下記のコードは見慣れない方もいたかもしれません。

let base_currency_rate: MultiMap<CurrencyKind, f64> = mixed_currency_chart
        .into_iter()
        .map(|elem| (elem.base_currency_kind, elem.rate))
        .collect();

なぜ Vec からイテレータを取り出し、それを MultiMap に的確に collect できるのでしょうか?

その答えは FromIterator というトレイトにあります*1MultiMap 用に用意された実装の中で、MultiMap への詰め直し作業を行っています。

impl<K, V, S> FromIterator<(K, V)> for MultiMap<K, V, S>
    where K: Eq + Hash,
          S: BuildHasher + Default
{
    fn from_iter<T: IntoIterator<Item = (K, V)>>(iterable: T) -> MultiMap<K, V, S> {
        let iter = iterable.into_iter();
        let hint = iter.size_hint().0;

        let mut multimap = MultiMap::with_capacity_and_hasher(hint, S::default());
        for (k, v) in iter {
            multimap.insert(k, v);
        }

        multimap
    }
}

MultiMapinsert メソッドは、通常の HashMapinsert メソッドとは異なります。Entry::OccupiedEntry::Vacant を用いて判定を行う点は共通していますが*2、その後は get_vec_mutinsert_vec といった MultiMap 固有のメソッドを呼び出しています。

    pub fn insert(&mut self, k: K, v: V) {
        match self.entry(k) {
            Entry::Occupied(mut entry) => {
                entry.get_vec_mut().push(v);
            }
            Entry::Vacant(entry) => {
                entry.insert_vec(vec![v]);
            }
        }
    }

これにより、下記のコードから MultiMap がきれいに生成できています。

let base_currency_rate: MultiMap<CurrencyKind, f64> = mixed_currency_chart
        .into_iter()
        .map(|elem| (elem.base_currency_kind, elem.rate))
        .collect();

ちなみに Vec から一度イテレータを取り出して map してキーと値のタプルを作り、それを collect するという技法は、Rust の標準ライブラリに用意されている HashMap でも使うことができます。

この記法を応用すると、読み取りさせたいだけの HashMap に可変性を与えることなくマップを生成できます。下記は HashMapFromIterator<(K, V)> が実装されていることを利用した HashMap 生成のコードです。

let map: HashMap<i32, &str> = vec![(1, "one"), (2, "two"), (3, "three")].into_iter().collect();

まとめ

  • MultiMap を使うと、値にベクタをもつ構造をシンプルに表現できる上、挿入などの操作も大変楽に行える。

*1:FromIterator トレイトのドキュメント→https://doc.rust-lang.org/std/iter/trait.FromIterator.html

*2:この記事が詳しいです→RustのHashMapはentryが便利 https://keens.github.io/blog/2020/05/23/rustnohashmaphaentrygabenri/ 。ただし、この Entry は MultiMap 向けに独自に実装されているものです。

Vec::retain の最適化

先日 rustc に上がっていた PR にこんなものがありました。Vec::retain を最適化したという PR です。他の PR の様子なども見る限り、以前からここは取り組まれていたようですが、この度ようやく修正が入り、Vec::retain が高速化しました。

github.com

実際どのくらい高速化したかと言うと、ベンチマークを見る限りではほとんど倍になっていたケースもあるくらいには速くなっていました。その他でもパフォーマンスが微妙に高くなっていたりと、だいたいのケースで高速化しているように見えました。

この PR では、

  • swap の廃止
  • truncate の廃止

の2つが行われています。truncate の方は、実装の修正の関係で新実装の設計に合わなくなったためについでに削除されたように読めましたが、swap は明確な意図をもって削除されています。この swap の削除の話が、調べてみると意外に奥が深く、読みがいがあったのでそれを紹介しようと思って記事を書いています。

なお、これは免責事項になりますが、筆者は普段高レイヤー言語を扱うことが多く、ポインタの操作やメモリ管理の定石などに詳しいわけではありません。記事には誤りがある可能性があるので、何か誤りがありましたらご連絡ください。

今回この記事では、まず Vec::retain とは何で、旧実装がどのようなアルゴリズムのもと retain を行っていたかを解説します。また、その過程で swaptruncate といった関数を実装レベルで見ていきます。その後、新実装の解説を行い、新実装でどのような最適化が行われたために速度が向上したかについて説明する予定です。

ちなみに、コードリーディングの過程のメモは Zenn のスクラップにて公開済みです。このブログの記事は、スクラップの再編成をしたものになります。

Vec::retain とは

Vec::retain とは、条件に合うベクタ内の要素のみを残す処理を行う便利関数です。たとえば、1〜4の数列を入れてあった際に、偶数のみ残すというフィルタリングを行うことができます。Iteratorfilter に近い関数ではあります。

fn main() {
    let mut vec = vec![1, 2, 3, 4];
    vec.retain(|&x| x % 2 == 0);
    assert_eq!(vec, [2, 4]);
}

フィルタと違うポイントとしては、元の配列を破壊しながら要素を残すので、ミュータブルな関数になります。シグネチャは下記のようになっています。

    pub fn retain<F>(&mut self, mut f: F)
    where
        F: FnMut(&T) -> bool,

旧実装のアルゴリズム

旧実装の問題点の整理

この実装の問題点は Vec::swap という関数にありました。Vec::swap 関数の中では std::ptr::copystd::ptr::copy_nonoverlapping という処理が走ります。copy の方は、C の memmove に相当します。また、copy_nonoverlapping の方は memcpy に相当します。memmove はある特定の条件を満たしてしまうとパフォーマンスが落ちることがあるようです。

旧実装では、Vec::swap は削除した要素の個数回呼び出されてしまうことになります。つまり、std::ptr::copy が削除した個数回分呼ばれてしまいます。str::ptr::copy_nonoverlapping は個数×2回呼ばれてしまいます。後ほど説明しますが、新実装ではここを削ることにしたようです。

旧実装を見ていく

では、これまでの実装はどのようになっていたのでしょうか?1.50 時点のソースコードを貼り付けます。

    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn retain<F>(&mut self, mut f: F)
    where
        F: FnMut(&T) -> bool,
    {
        let len = self.len();
        let mut del = 0;
        {
            let v = &mut **self;

            for i in 0..len {
                if !f(&v[i]) {
                    del += 1;
                } else if del > 0 {
                    v.swap(i - del, i);
                }
            }
        }
        if del > 0 {
            self.truncate(len - del);
        }
    }

ここで単純なベクタを例にとってどのようなアルゴリズムになっているのかを見ていきます。

たとえば、[1, 2, 3, 4] というベクタがあった際に、偶数のみを残すという retain を行うものとします。retain(|x| x % 2 == 0) という関数を書くものとします。この結果残る要素は、[2, 4] となるはずです。ミュータブルなので、元の配列の状況が破壊的に変化する点に注意が必要です。

この際行われる処理をまとめると、下記のようになります。

  • i = 0 でループ
    1. 1 は 1 % 2 == 0 を満たさないので、del + 1 される。この時点で del = 1
    2. 配列自体に変化なし。
  • i = 1 でループ
    1. 2 は 2 % 2 == 0 を満たすので、次の del > 0 の判定に移る。
    2. del = 1 より、これは満たされる。
    3. この時点で、i - del = 1 - 1 = 0 番目と、i = 1 番目の要素が swap される。
    4. 配列は [2, 1, 3, 4] となる。
  • i = 2 でループ(配列 = [2, 1, 3, 4])
    1. 3 は 3 % 2 == 0 を満たさないので、del + 1 される。この時点で del = 1 + 1 = 2
    2. 配列自体に変化なし。
  • i = 3 でループ(配列 = [2, 1, 3, 4])
    1. 4 は 4 % 2 == 0 を満たすので、次の del > 0 の判定に移る。
    2. del = 2 より、これは満たされる。
    3. この時点で、i - del = 3 - 2 = 1 番目と、i = 3 番目の要素が swap される。
    4. 配列は [2, 4, 3, 1] となる。
  • 次のループはないので、ループを抜ける。
  • del > 0 より、不要になった分を truncate する。

swap は2回、truncate は1回呼び出されていることがわかります。swap は削除する際に呼び出されるので、削除する要素が増えるとその分、swap が呼び出される回数も増えることになります。100個削除するなら、100回 swap が呼ばれることになります。まず、この点を抑えておく必要があります。

では、次に swaptruncate がどのような処理を行っているかについて見ていきましょう。

Vec::swap の内部実装

まず、Vec::swap 関数が何をしているかについて見ます。コードが示すとおりで、指定されたインデックスの要素同士を入れ替えます。

fn main() {
    let mut v = ["a", "b", "c", "d"];
    v.swap(1, 3);
    assert!(v == ["a", "d", "c", "b"]);
}

Vec::swap の内部実装は下記のようになっています。2つのインデックスに紐づく要素の可変なポインタを取得しておき、それを std::ptr::swap に投げ込みます。処理の本体は std::ptr::swap に任されています。

    #[stable(feature = "rust1", since = "1.0.0")]
    #[inline]
    pub fn swap(&mut self, a: usize, b: usize) {
        // Can't take two mutable loans from one vector, so instead just cast
        // them to their raw pointers to do the swap.
        let pa: *mut T = &mut self[a];
        let pb: *mut T = &mut self[b];
        // SAFETY: `pa` and `pb` have been created from safe mutable references and refer
        // to elements in the slice and therefore are guaranteed to be valid and aligned.
        // Note that accessing the elements behind `a` and `b` is checked and will
        // panic when out of bounds.
        unsafe {
            ptr::swap(pa, pb);
        }
    }

std::ptr::swap の実装は下記のようになっています。MaybeUninit という、初期化されていないかもしれない型を使って tmp を用意した後、x, y の入れ替え処理をします。

#[inline]
#[stable(feature = "rust1", since = "1.0.0")]
pub unsafe fn swap<T>(x: *mut T, y: *mut T) {
    // Give ourselves some scratch space to work with.
    // We do not have to worry about drops: `MaybeUninit` does nothing when dropped.
    let mut tmp = MaybeUninit::<T>::uninit();

    // Perform the swap
    // SAFETY: the caller must guarantee that `x` and `y` are
    // valid for writes and properly aligned. `tmp` cannot be
    // overlapping either `x` or `y` because `tmp` was just allocated
    // on the stack as a separate allocated object.
    unsafe {
        copy_nonoverlapping(x, tmp.as_mut_ptr(), 1);
        copy(y, x, 1); // `x` and `y` may overlap
        copy_nonoverlapping(tmp.as_ptr(), y, 1);
    }
}

さて、ここで copy_nonoverlappingcopy という関数が出てきました。ドキュメントを読んでみると、次のような処理をすることがわかります。

  • copy_nonoverlapping: 重なりあわないメモリ領域同士をコピーする。memcpy と同じ。
  • copy: 重なる可能性があるメモリ領域同士をコピーする。memmove と同じ。重なり合わない場合は、実質的な動作は memcpy とおなじになる。

重要なケースは copy の方です。memmove は、コピー元とコピー先のメモリ領域自体に重なりがある場合、処理速度が低下することがあるそうです*1。これは重なっている領域分のコピーを1ビットずつ走らせることに由来します*2

それでは、最後に合計で何回 memcpymemmove が走っているのかを見てみましょう。先ほど書いた処理の流れの、swap を copycopy_nonoverlapping に読み替えてみます。

  • i = 0 でループ
    1. 1 は 1 % 2 == 0 を満たさないので、del + 1 される。この時点で del = 1
    2. 配列自体に変化なし。
  • i = 1 でループ
    1. 2 は 2 % 2 == 0 を満たすので、次の del > 0 の判定に移る。
    2. del = 1 より、これは満たされる。
    3. この時点で、i - del = 1 - 1 = 0 番目と、i = 1 番目の要素が swap される。copy は1回、copy_nonoverlapping は2回走る。
    4. 配列は [2, 1, 3, 4] となる。
  • i = 2 でループ(配列 = [2, 1, 3, 4])
    1. 3 は 3 % 2 == 0 を満たさないので、del + 1 される。この時点で del = 1 + 1 = 2
    2. 配列自体に変化なし。
  • i = 3 でループ(配列 = [2, 1, 3, 4])
    1. 4 は 4 % 2 == 0 を満たすので、次の del > 0 の判定に移る。
    2. del = 2 より、これは満たされる。
    3. この時点で、i - del = 3 - 2 = 1 番目と、i = 3 番目の要素が swap される。copy は1回、copy_nonoverlapping は2回走る。
    4. 配列は [2, 4, 3, 1] となる。
  • 次のループはないので、ループを抜ける。
  • del > 0 より、不要になった分を truncate する。

つまり、copy は2回走り、copy_nonoverlapping は4回走っていることがわかります。

Vec::truncate の内部実装

truncate 関数は指定した長さの配列に現在の配列を直すというものです。[1, 2, 3, 4]の配列に対して、truncate(2) をすると、左から2要素を残して他はカットするイメージです。

内部実装は下記のようになっています。指定した長さ以降の配列の要素のスライスを一時的に確保しておき、ベクタの長さを指定の長さに削ったあと、一時的に確保したスライスのメモリ領域を解放する処理を行っているようです。

    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn truncate(&mut self, len: usize) {
        // This is safe because:
        //
        // * the slice passed to `drop_in_place` is valid; the `len > self.len`
        //   case avoids creating an invalid slice, and
        // * the `len` of the vector is shrunk before calling `drop_in_place`,
        //   such that no value will be dropped twice in case `drop_in_place`
        //   were to panic once (if it panics twice, the program aborts).
        unsafe {
            if len > self.len {
                return;
            }
            let remaining_len = self.len - len;
            let s = ptr::slice_from_raw_parts_mut(self.as_mut_ptr().add(len), remaining_len);
            self.len = len;
            ptr::drop_in_place(s);
        }
    }

truncate には drop_in_place が使用されているという点がポイントだと思います。これによって、truncate によって残らなかった領域のメモリリークを防いでいます。

新実装のアルゴリズム

新実装の狙いと方針

新実装では、先ほど説明した swap 関数内で呼び出される copycopy_nonoverlapping の回数削減が行われます。とくに劇的に削減されるのは copy の呼び出し回数です。これが、不要だった要素の個数に関係なく1回に削減されています。

これは、メモリの重なりが多かった場合というワーストケースに劇的に効くのはもちろん、特段そうしたワーストケースでない実装においても copy の回数を純粋に減らせることにつながるため、大幅な速度アップが期待できます。実際、ベンチマークでも大幅な速度アップが見込めていそうな結果が出ています。

大まかな方針としては

  • retain 判定の結果、不要となった要素を swap しながら truncate の範囲外に追いやるという手法ではなく、スワップはするものの不要だった要素は都度 drop しておくことにした。
  • swap の際には swap 関数は呼び出さず、copy_nonoverlapping を呼び出すようにした。不要な要素は drop されるので、メモリが重ならないことを保証できるためこれを使用できると思われる。
  • copy は全体の retain 判定がすべて終了した後、後述する構造体の drop のタイミングに一度だけ行う。

新実装を見ていく

新実装をまずは貼ります。

    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn retain<F>(&mut self, mut f: F)
    where
        F: FnMut(&T) -> bool,
    {
        let original_len = self.len();
        // Avoid double drop if the drop guard is not executed,
        // since we may make some holes during the process.
        unsafe { self.set_len(0) };

        // Vec: [Kept, Kept, Hole, Hole, Hole, Hole, Unchecked, Unchecked]
        //      |<-              processed len   ->| ^- next to check
        //                  |<-  deleted cnt     ->|
        //      |<-              original_len                          ->|
        // Kept: Elements which predicate returns true on.
        // Hole: Moved or dropped element slot.
        // Unchecked: Unchecked valid elements.
        //
        // This drop guard will be invoked when predicate or `drop` of element panicked.
        // It shifts unchecked elements to cover holes and `set_len` to the correct length.
        // In cases when predicate and `drop` never panick, it will be optimized out.
        struct BackshiftOnDrop<'a, T, A: Allocator> {
            v: &'a mut Vec<T, A>,
            processed_len: usize,
            deleted_cnt: usize,
            original_len: usize,
        }

        impl<T, A: Allocator> Drop for BackshiftOnDrop<'_, T, A> {
            fn drop(&mut self) {
                if self.deleted_cnt > 0 {
                    // SAFETY: Trailing unchecked items must be valid since we never touch them.
                    unsafe {
                        ptr::copy(
                            self.v.as_ptr().add(self.processed_len),
                            self.v.as_mut_ptr().add(self.processed_len - self.deleted_cnt),
                            self.original_len - self.processed_len,
                        );
                    }
                }
                // SAFETY: After filling holes, all items are in contiguous memory.
                unsafe {
                    self.v.set_len(self.original_len - self.deleted_cnt);
                }
            }
        }

        let mut g = BackshiftOnDrop { v: self, processed_len: 0, deleted_cnt: 0, original_len };

        while g.processed_len < original_len {
            // SAFETY: Unchecked element must be valid.
            let cur = unsafe { &mut *g.v.as_mut_ptr().add(g.processed_len) };
            if !f(cur) {
                // Advance early to avoid double drop if `drop_in_place` panicked.
                g.processed_len += 1;
                g.deleted_cnt += 1;
                // SAFETY: We never touch this element again after dropped.
                unsafe { ptr::drop_in_place(cur) };
                // We already advanced the counter.
                continue;
            }
            if g.deleted_cnt > 0 {
                // SAFETY: `deleted_cnt` > 0, so the hole slot must not overlap with current element.
                // We use copy for move, and never touch this element again.
                unsafe {
                    let hole_slot = g.v.as_mut_ptr().add(g.processed_len - g.deleted_cnt);
                    ptr::copy_nonoverlapping(cur, hole_slot, 1);
                }
            }
            g.processed_len += 1;
        }

        // All item are processed. This can be optimized to `set_len` by LLVM.
        drop(g);
    }

大幅に実装量は増えていますが、まず構造体が追加されたことと、その構造体に対する Drop トレイとの実装が追加されたために行数が増えています。この構造体は今回の新実装の中核を担っています。

大雑把なアルゴリズムは下記のようになります。

  1. BackshiftOnDrop を作る。
  2. 1で作った構造体の processed_lenoriginal_len (元の配列の長さ) をこえるまでは、ループ処理を回し続ける。
    1. retain の条件に一致しない場合は、その要素を drop しておく。
    2. 要素を削除したカウンタが0より大きければ、削除分を反映した配列の状態を move しておく。
  3. 1を drop する。drop 時に後処理として、下記2つが走る。
    1. 要素を削除したカウンタが0より大きければ、処理した分を copy する。
    2. ベクタ自身の持つサイズを現状のものに調整する。

BackshiftOnDrop は3つのフィールドを持ちます。

  • processed_len: 現在の retain の条件の判定がどこまで進められたかを記録する。
  • deleted_cnt: 不要判定され削除(= drop)された要素の個数を記録する。
  • original_len: もともとのベクタの長さを保持する。

また、コメントにもある通り、ベクタの走査中には次のようなステータスを1つ1つの要素に概念的に適用します。これらの用語は後々アルゴリズムの説明の際に用いられます。一方で、実装には現れてきません。

  • Kept: retain 判定の結果、保持されることが決定された状態の要素を指す。
  • Hole: retain 判定の結果、drop された状態の要素を指す。
  • Unchecked: まだ走査されていない状態の要素を指す。

この実装を、再度 [1, 2, 3, 4] というベクタに対して偶数を retain するという例に対して適用してみましょう。

まず、今回からポインタに対する操作に変わるため、便宜的にアドレスを決定しておきます。下記の決め事はあくまで説明のための例であり、実際の実行環境とは異なる状態になっている可能性があります。

address 0x7ffe4d8f54a0 0x7ffe4d8f54a4 0x7ffe4d8f54a8 0x7ffe4d8f54ac
index 0 1 2 3
value 1i32 2i32 3i32 4i32

これらを元にコードをなぞって見ていくと、下記のような手順で処理が進んでいくことがわかります。

  1. 最初の g を作る。processed_len = 0, deleted_cnt = 0, original_len = 4, 配列: [1, 2, 3, 4]
  2. 1回目の while (processed_len = 0 < original_len = 4), 配列 [1 (Unchecked), 2 (Unchecked), 3 (Unchecked), 4 (Unchecked)]
    1. cur を作る。cur = g.v.as_mut_ptr().add(0) = 0x7ffe4d8f54a0
    2. cur の示す先の値は1i32なので、最初の if ブロックの条件を満たす。processed_len = 1, deleted_cnt = 1 となる。また、curdrop される。配列は [(Hole), 2 (Unchecked), 3 (Unchecked), 4 (Unchecked)] になっているはず。
    3. 次のループに飛ぶ。
  3. 2回目の while (processed_len = 1 < original_len = 4, deleted_cnt = 1), 配列: [(Hole), 2 (Unchecked), 3(Unchecked), 4 (Unchecked)]
    1. cur を作る。cur = g.v.as_mut_ptr().add(1) = 0x7ffe4d8f54a4
    2. cur の示す先の値は 2i32 なので、最初の if ブロックの条件は満たさない。次。
    3. deleted_cnt = 1 より、条件を満たす。
      1. hole_slotg.v.as_mut_ptr().add(1 - 1) = g.v.as_mut_ptr().add(0) = 0x7ffe4d8f54a0(さっき drop したところ)。
      2. curhole_slotcopy_nonoverlapping する。つまり、[2 (Kept), (Hole), 3 (Unchecked), 4 (Unchecked)] となっているはず。
    4. processed_len = 2
  4. 3回目の while (processed_len = 2 < original_len = 4, deleted_cnt = 1), 配列: [2 (Kept), (Hole), 3 (Unchecked), 4 (Unchecked)]
    1. cur を作る。cur = g.v.as_mut_ptr().add(2) = 0x7ffe4d8f54a8
    2. cur の示す先の値は3i32なので、最初の if ブロックの条件を満たす。processed_len = 3, deleted_cnt = 2 となる。また、curdrop される。配列は [2 (Kept), (Hole), (Hole), 4 (Unchecked)] になっているはず。
    3. 次のループに飛ぶ。
  5. 4回目の while (processed_len = 3 < original_len = 4, deleted_cnt = 2), 配列: [2 (Kept), (Hole), (Hole), 4 (Unchecked)]
    1. cur を作る。cur = g.v.as_mut_ptr().add(3) = 0x7ffe4d8f54ac
    2. cur の示す先の値は 4i32 なので、最初の if ブロックの条件は満たさない。次。
    3. deleted_cnt = 2 より、条件を満たす。
      1. hole_slotg.v.as_mut_ptr().add(3 - 2) = g.v.as_mut_ptr().add(1) = 0x7ffe4d8f54a4
      2. curhole_slotcopy_nonoverlapping する。つまり、[2 (Kept), 4 (Kept), (Hole), (Hole)] となっているはず。
    4. processed_len = 4
  6. 5回目のループは条件を満たさずできない。
  7. drop 処理を行う。配列の状態は、[2 (Kept), 4 (Kept), (Hole), (Hole)]
    1. processed_len = 4, deleted_cnt = 2
    2. 終わった時点でのメモリの状態は、0x7ffe4d8f54a0 = 2, 0x7ffe4d8f54a4 =4, 0x7ffe4d8f54a8 = Hole, 0x7ffe4d8f54ac = Hole
    3. copy(g.v.as_ptr().add(4) = 0x7ffe4d8f54b0, g.v.as_mut_ptr().add(2) = 0x7ffe4d8f54a8, 0) が実行される。ただし、count に 0 が入っているので、実質何もしない*3
    4. Vec の len は2がセットされる。[2, 4] が len に含まれることになった。すでに drop 済みなので、不要と判断された要素のメモリ領域がメモリリークすることはない。

重要なポイントは、copy の回数が減っている点です。最後の 7-2 でしか copy は走らなくなっています。今回の場合は、不要だった要素数が2個しかないので実質 1/2 ですが、仮に不要だった要素が100個だった場合であっても、1回しかコピーは走りません。ということは、コピーの回数は 1/100 ということになります。これは劇的な改善だと思われます。

また、copy_nonoverlapping も2回に減っています。

したがって、コピー操作全般の回数が、旧実装(6回)と比較すると半分(新実装では3回)に減っていることがわかります。不要な要素の多さによっては減る回数がさらに増える可能性があることもわかりました。

まとめ

  • Vec::retain の実装が最適化された。
  • swap を行いながら不要になった要素を範囲外に寄せておき、最後に範囲外の要素を全部 drop するという戦略を取らなくした。
  • 不要な要素を発見したら都度 drop しておき、メモリ領域同士が重ならないことを保証しながらスワップ操作をできるようにした。こうすることで、memcpy を安心して走らせることができるし、memmove の速度低下の可能性も下げられるようになった。

Rust の Vec は実はこうしたポインタ操作の宝庫です。筆者のように、普段高レイヤー言語を触っていて参照もポインタもほぼ馴染みがない、というエンジニアにとって、Rust の Vec は絶好の教材だと思います。他の実装も読んでみて、どういった操作をしているのか知りたくなってきました。

*1:これは Rust でもそうなのかをベンチを取ってみる必要がありそうです。それは後日で。

*2:記事を参考にしただけなので、最近の実装がどうなのかまでは調べていません: https://fd0.hatenablog.jp/entry/20071222/p1

*3:例が悪く、processed_len と deleted_cnt が非対称になる例を見せるべきだった可能性はある。

Rust でステートマシンを扱えるライブラリを書いてみた

TL; DR

  • Rust でステートマシンをいい感じに扱えるようにするライブラリを書いてみた。
  • とくに他の言語のライブラリを調査したわけではないので、もう少しいいアイディアがあるかもしれない。

何を作ったか

Rust でマクロや他のライブラリを一切使わずにステートマシンを実装できるライブラリを作り、crates.io に公開してみました。

https://crates.io/crates/statemachine-rs

ドキュメントはこちらにあります。

docs.rs

リポジトリはこちらです。

github.com

何ができるのか

詳しくは README に記載しておりますので、使用してみたい場合はぜひご覧ください。

Rust には enum(Rust では代数的データ型になっています)という大変素晴らしい概念が利用できます。ステートマシンにもこれを利用しないわけにはいきませんよね。このライブラリは、enum 等を使用したステートマシンの実装のお手伝いをします。

下記のサンプルでは、ボタンの切り替えを行ってみています。

まず初期設定を StateMachineBuilder というビルダーを使って行えるように実装してあります。

State として ButtonState を用意し、Input として Input という enum を定義します。下記では On/Off という状態を、Press という入力を使って切り替えられるようにしています。

Input に対して State がどのように変化するのかは、クロージャーで定義します。transition 関数の引数は StateInput のタプルになっています。ここで、状態と入力のパターンマッチングを行い、状態遷移を定義します。

use statemachine_rs::machine::{builder::StateMachineBuilder, StateMachine};

#[derive(Clone, Debug, PartialEq)]
enum ButtonState {
    On,
    Off,
}

enum Input {
    Press,
}

fn main() {
    let sm = StateMachineBuilder::start()
        .initial_state(ButtonState::Off)
        .transition(|state, input| match (state, input) {
            (ButtonState::On, Input::Press) => ButtonState::Off,
            (ButtonState::Off, Input::Press) => ButtonState::On,
        })
        .build()
        .unwrap();

    assert_eq!(ButtonState::Off, sm.current_state());
    sm.consume(Input::Press);
    assert_eq!(ButtonState::On, sm.current_state());
}

状態を進める際には consume という関数が生えており、この consume に入力を渡すと状態遷移が行われます。consumeStateMachine トレイトの関数です。consume 以外にも、現在の状態の取得や状態のリセットなどを行える関数を用意してあります。また、StateMachine トレイトは pub なため、自身で構造体とその実装を定義してオリジナルのステートマシンを用意することもできます。

pub trait StateMachine<State, Input> {
    fn current_state(&self) -> State;

    fn consume(&self, input: Input) -> State;

    fn reset(&self) -> State;

    fn set(&self, new_state: State);
}

実装して迷っているポイント

今回 Rust ではじめて OSS のライブラリを作ってみたので、慣習がわかっていない部分があります。

実装の都合で Stateenum に対しては現在 Clone が要求されます。現在、標準で提供しているのは BasicStateMachine という構造体です。これは StateClone を要求しています。実装側を見ていただくとわかるのですが、どうしても clone が必要と思われる箇所が出てくるためです。

/// The basic state machine implementation.
/// It holds `initial_state`, `current_state`, `transition` function.
pub struct BasicStateMachine<State, Input, Transition>
where
    Transition: Fn(&State, Input) -> State,
    State: Clone,
{
    /// `initial_state` is literally an initial state of the state machine.
    /// The field isn't updated the whole life of its state machine.
    /// That is, it always returns its initial state of its machine.
    initial_state: State,
    /// `current_state` is the current state of the state machine.
    /// It transit to the next state via `transition`.
    current_state: RefCell<StateWrapper<State>>,
    /// `transition` is the definition of state transition.
    /// See an example of [`StateMachine::consume()`], you can grasp how
    /// to define the transition.
    transition: Transition,
    _maker: PhantomData<Input>,
}

もし StateClone を要求するのが、大きなパフォーマンス劣化を招く原因になりうるのだとしたら、この Clone の制約を外せるように実装を調整する必要があるのかなと思っています。が、正直これをどう上手に調整したらよいかの想像がついていません。このあたりのワークアラウンドは結構迷ってます…。

もし何かアイディアがある方がいらっしゃいましたら、お気軽に Issue を立てたり、PR を投げたりなどよろしくお願いします😃

また、BasicStateMachineRefCell を使用していることからもわかるようにスレッドセーフではありません。スレッドセーフな StateMachine 実装は、今後時間を見つけて追加する予定です。

はじめてのクレート公開の感想

cargo package からの cargo publish をするだけでクレートを公開できてしまうのは、正直かなり便利ですね。Scala のときは sonatype だったか、どこかの外部サービスに一度ユーザー登録をして、JIRA をうんたらかんたら…といった作業が必要だった(勘違いしてるかも)と記憶しているのですが、crates.io は GitHub の ID さえあればアカウントを作成でき、サイト上でアクセスキーを生成してあとはローカルから cargo publish を打つだけ、という非常にスムーズな構成になっていました。

OSS の公開に際しての悩みの種といえばドキュメントですが、ドキュメントは crates.io に登録した時点で自動的に URL を用意してくれ、そちらに cargo doc の結果をホストしてくれます。今回私が作ったクレートのドキュメントはこちらにありますが、これを見たときに「ああ、クレートを公開しちゃったよ…すごい…」という気持ちになりました。いたれりつくせり。

ドキュメントを書くのはかなり骨の折れる作業で、主にサンプルコードの用意の部分で結構手間取りました。ただ、サンプルコードを用意しておくと、cargo test したタイミングで doc test が走り、コメント内のコードのコンパイルが通るかや assertion が通るかを自動でチェックしてくれます。ドキュメントのメンテ漏れに気づけるようになるので、この仕組みは非常に素晴らしいです。ちなみに他の言語での経験だと Python でも同じことができますね。

クレートの使い勝手については、自分が普段 Rust コードを書く際には問題ないなというレベルで公開してしまっているため、他の方がどう感じるかが結構気になっています。というわけで、ドッグフーディングしてくださる方、よろしくお願いします。Issue や PR お待ちしております!

Rust を始めるための資料集

かとじゅんさんのお誘いで、私塾匠真堂にて登壇させていただき、Rust に関する話をさせていただきました。ありがとうございました。

今回のセッションを通じて Rust を始めたくなった方向けに、Rust をはじめるための資料をいくつかリストアップしてます。よかったらどうぞ。

プログラミング言語の学習方法について

みなさんは新しいプログラミング言語を学ぶ際、どのように学びますか?

私は、軽く制御構文やデータ型の作り方などを学んだ後は、すぐにアプリケーションを作ってみて、詰まったらリファレンスを参照するといった学び方をしていることが多いです。

逆に、リファレンスをまず眺めて、文法をしっかり把握した後にアプリケーションを作ってみるという方もいるかもしれません。

いずれにせよ、

  • リファレンスを眺める。
  • アプリケーションを何かしら作ってみる。

の2つを、多くのプログラマは新しいプログラミング言語を習得する際にやっているのではないでしょうか?ということで、この2つについて、私の知る限りで資料を列挙したいと思います。

各資料の紹介時には、どういったシチュエーションで使用できるか、どのような特徴をもった資料かを簡単に補足説明しました。

Rust についてまず概観を掴む

Rust がどのような言語なのかについて、まず概略でいいから掴みたいという方向けにおすすめできる記事です。(他にもいい記事があるので、思い出し次第追加します)

  • 最速で知る! プログラミング言語Rustの基本機能とメモリ管理【第二言語としてのRust】: 少し古めの記事ではあるのですが、この頃から Rust のコンセプトは大きくは変わっていません。Rust がどのような言語かについて簡単に触れた後、所有権などを図を用いて説明しており大変わかりやすいです。
  • Rust は何が新しいのか: これは少々突っ込んだ話側かもしれませんが、Rust の「新しさ」について解説された記事です。Rust ではムーブセマンティクスと呼ばれる概念を使ってメモリ管理をしているわけですが、そのムーブセマンティクスは C++ から輸入され、Rust 向けにアレンジされた概念です。C++ におけるムーブセマンティクスの利点とペイン、そしてそれらを Rust がどう解決したかについて簡潔にまとまっています。
  • プログラミング言語 Rust のご紹介: これは私が以前発表した資料ですが、Rust の2020年時点での現状や言語機能、日本でのコミュニティ活動をまとめてみたものです。
  • Rust入門ガイド (sapporo.rs) - Qiita: sapporo.rs という勉強会で発表されたプレゼンのようですが、Rust の特徴が非常に簡潔にまとまっていてよいです。どういう用途に使用できそうか、という話まで込みで書かれており、Rust を使うイメージがわかない場合には読まれるとよいかと思います。

文法を学ぶ

2021年現在では、下記がおすすめできるかなと思っています。

  • Rust の最初のステップ: Microsoft社が提供する Rust の入門講座で、文法を1から学んで最終的にはちょっとした CLI アプリを作るところまで到達します。Rust を書き始める際に必要な項目がコンパクトにまとまっており、一番最初に取り組むチュートリアルとしておすすめできます。
  • Tour of Rust [一部邦訳]: これは現時点で最初の一歩におすすめできる資料かなと思います。Go 言語には A Tour of Go という、Go を始める際にうってつけな教材があります。それの Rust 版です。Rust の文法を1ページ1ページ解説しつつ、横で Playground を使ってコードを実際に実行して挙動を確かめるところまでセットでできます。まずこれを軽く通してみて、簡単に文法の概観を掴むとよいのではないかと思います。
  • Rust by Example: 文法の細かい解説というよりは、サンプルスクリプトを通じて Rust を学んでいける資料に仕上がっています。細かい解説はいいから、とりあえずサクサク写経しつつ概観を掴んで実際にアプリケーションを作って学んでいきたい、という方におすすめできるかなと思います。
  • とほほの Rust 入門: あのとほほさんの Rust 入門です。非常に簡潔に Rust の文法が網羅されており、サクサク Rust の文法を見ていく場合に適しているように思います。
  • Rustlings [未邦訳]: コンパイルエラーになる Rust コードのコンパイルを通るようにしていく問題集です。Rust のコンパイルエラーを直していく過程で、さまざまな Rust の文法について学んでいくことができるように設計されています。Rust にちょっと慣れてきたくらいでやってみるといいかもしれません。
  • AtCoder と Rust で始める!競技プログラミング入門(Rust 版 APG4b): 競技プログラミングを Rust でやりたい方向けに書かれた資料だとは思いますが、Rust の基本的な文法がよく解説されています。その章の文法を学んだ後に、AtCoder の問題を解いてみるという形式になっており、非常に導入がスムーズに感じます。
  • Rust入門: この本も日本語で書かれた Rust 入門に適した本で、Rust の概要をサクッと学んでみたい方にオススメです。各概念について完結にまとめられていて、必要に応じて概念図も用意されており、実用的なドキュメントになっていると思います。

これまでは TRPL を薦めてきましたし、実際私も TRPL の第1版の日本語訳で入門しました。今でも TRPL は第一のリファレンスに使えます。一方で、国内海外問わず、TRPL がまずまずハードだという声も聞きます。近年 Rust ユーザーの増加により、入門用のドキュメントだんだん種類が増えてきました。これから学ばれる方の他の言語での習熟度や、これまで取り組んできた領域によってどの資料が合うかは変わってきます。上のリストのものをいくつか試してみて、ご自身にあうと思うものを選ばれるとよいと思います。

何かアプリケーションを実装してみる

Rust では本当にさまざまなものが作れます。また、それらの作り方について解説したチュートリアルがかなりの数存在しており、最初に取り掛かる際におすすめできそうなものをご紹介します。Rust らしい書き方を学ぶには、やはりこうしたチュートリアルのコードを写経してみるのがいいのではないでしょうか。

あるいは、ここで紹介したチュートリアルではなくて、何か別の言語向けに書かれたチュートリアルを Rust に直してみるのもいいトレーニングかもしれません。実際、私も LSH という小さな C で書かれたシェルを Rust に直してみるなどの遊びをしてみました。

ちょっと突っ込んだ話を知りたい

  • The Rust Programming Language: 通称 TRPL。Rust を使う際のバイブル的な存在です。が、すべてをこなすとハードな仕上がりになっている(と個人的には思う)ので、発展的な話題は一旦見切ってアプリケーションの実装に移るといいかもしれません。Rust を書いている最中に何度も立ち返ることになるドキュメントでもあります。Rust だけでなく、コンピュータ一般に関する細かい解説も載っており、読むだけでも勉強になるドキュメントに仕上がっています。
  • Learn Rust With Entirely Too Many Linked Lists [未邦訳]: Rust で LinkedList を実装しながら、LinkedList のように再帰的な構造をもつデータ構造を Rust ではどう扱ったらよいかについて学ぶことができます。また、所有権や unsafe 、スマートポインタの扱い方などのワークアラウンドについても確認することができます。
  • Rust Language Cheat Sheet [未邦訳]: Rust のチートシートではあるものの一歩踏み込んだ話題にも触れていて、たとえば「ムーブが起きた際には、一体裏側では何が起きているの?」などといった細かい話を図付きで確認することができます。メモリレイアウトがどうなっているかは、やはり図で示されるととても理解しやすいです。
  • Rust Cookbook [未邦訳]: Rust は標準ライブラリが薄く作られています。これには理由があるのですが、クレート(ライブラリ)探しを少々がんばる必要があります。「シングルトンを Rust でやりたい」「データベースにつなぎたい」「日付を扱いたい」といったユースケースごとに、どのようなクレート(ライブラリ)を使用したらいいかを教えてくれる本です。
  • The Rustnomicon: Rust には、生ポインタを扱えるようにする unsafe という機能があります。この unsafe を扱う際には数々の危険行為が存在するわけですがそれらについていろいろ教えてくれる本です。Rust でシステムプログラミングをする際には、この本を一読しておくことをおすすめします。
  • The Rust Reference: Rust を構成する各機能について、入門書以上のことが書いてあります。ある機能について、どういうことができるのかなどをより深く知りたくなった場合、この本を参照することがままあります。
  • Rust API ガイドライン: たとえば変数名や関数名はどうつけたらよいのかといった話や、ドキュメントの書き方、どのように関数の引数をデザインしたらよいか、型のよい使い方などが書かれています。

コミュニティの力を借りる

Rust を一人で学んでいると、どうしてもわからないことが出てくると思います。私もそうでした。

Rust には、現在日本の Slack グループがあります。ここで質問してみるのはいかがでしょうか。#beginner や #code というチャンネルがあり、多くの方が質問をしています。

rust-jp.herokuapp.com

もし英語のコミュニケーションに抵抗のない方であれば、

  • Reddit: クレート(ライブラリ)の作者や Rust 言語の設計者本人からの回答を得られることがたまにあります。日本語で2次情報に当たり続けるより確度の高い情報を得られる可能性があります。
  • ユーザーフォーラムで質問する: こちらも同様に英語圏の詳しい人が答えてくれます。

仲間を見つける

勉強会が都内を中心にいくつか開催されています。COVID-19 の関係で現在はオンライン開催が多くなっていますが、2020年中ですと、下記のような勉強会が開催されていました。

また、日本向けの Rust カンファレンスである Rust.Tokyo というものを毎年11月頃に開催予定しております。2020年は RustFest Global という形で開催しました。2021年は再び Rust.Tokyo として開催していきたいと思っています。

Webサイト(2020年のままです🙇‍♀️) rust.tokyo

Twitter アカウント twitter.com

CPUエミュレータをRustで自作する

この記事は Rust Advent Calendar 2020 ならびに CyberAgent Developers Advent Calendar 25日目の記事です。

今年のはじめの頃になりますが、『CPUの創り方』という本に載っている TD4 という CPU を実装してみました。TD4 は「とりあえず動作するだけの4bit CPU」の略です。この本に載っている CPU エミュレータを実際に実装してみました。ただし、本書には GUI が載っていましたが、それは省略しました。

CPUの創りかた

CPUの創りかた

  • 作者:渡波 郁
  • 発売日: 2003/10/01
  • メディア: 単行本(ソフトカバー)

「最近話題の RISC-V などの CPU エミュレータを作ってみたいものの、いきなり作るにはハードルが高い。何か簡単なもので素振りをして CPU の動作の仕組みをまずは知りたい」という方にはかなりオススメできる教材だと思います。私自身、TD4 のエミュレータを実装してみて CPU の動作原理やコンセプトがわかり、その後製作中の RISC-V エミュレータに生きているように思います。

今回私が実装したものは下記です。だいたい1日くらいで実装できました:

この記事では、まず CPU の動作原理について TD4 を通じて簡単に解説し、Rust による実装例を見ていきます。また実装したインタプリタについても簡単に解説を加える予定です。

f:id:yuk1tyd:20201225203217p:plain
加算を行う処理を動かしてみた図

今回の記事では Rust を用いた実装になっていますが、Rust 以外の言語でもまったく問題なく実装できる内容だと思っています。たとえば PythonJava 、Go のようなアプリケーション向けの言語であっても問題なく実装できるはずです。Rust のシステムプログラミング言語としての側面を利用した実装箇所は今回はないためです*1

このブログでは恒例行事になっていますが、すべての解説を盛り込んだためかなりのボリュームになっています。お好きなところをかいつまんでお読みください。

リポジトリ

github.com

方針

今回のエミュレーションの方針は、クロックごとのレジスタ内の値を再現することとしました。本書を読むと、実際は CPU を論理回路から作り上げて再現することも可能なのですが、今回は命令を書いてそれを読み込ませるとレジスタに値を読み込んで計算などを行ってくれるという部分を再現することとしました。

予備知識

TD4 のような小さな題材であっても、基本的なアイディアは実際の CPU とそう相違ないはずです。TD4 を元に、CPU に関しての予備知識を少し書いておきたいと思います。

fetch-decode-execute サイクル

CPU は、fetch-decode-execute というステップを踏みながら計算を実行します*2

  1. fetch: メモリ上からプログラムを読み出すフェーズ。
  2. decode: 取り出した命令を元に内部的にどういった処理に対応するかを紐付け、行う計算を確定するフェーズ。
  3. execute: 2で確定した計算を実際に実行するフェーズ。

このサイクルをプログラムが終了するまで実行し続けます。

今回の TD4 エミュレータも同様にこのサイクルを実行して計算を行うように実装しました。

ROM

TD4 では ROM (Read-Only Memory) と呼ばれる領域にプログラムを書き出し、そこからプログラムを1行1行読み取って計算処理を行います。

Rust ではたとえば下記のようにして表現されており、ここにプログラムの内容(今回はバイナリ表現)が入っています。

pub struct Rom {
    pub memory_array: Vec<u8>, // ここに [00000000, 00010000, 11100001] のような形でプログラムが入っている。
}

現在どの番地のプログラムを読み出しているかについては、プログラムカウンタ(pc)と呼ばれるフラグによって管理されます。先ほどの fetch-decode-execute サイクルが1サイクル終了するとプログラムカウンタが足され、次のプログラムを読み出し、ということを ROM の配列が終了するまで行うことになります。

プログラムは「オペレーションコード」と「イミディエイトデータ」と呼ばれる領域に分けて書かれています。

たとえば、00000001 という値があったときには、TD4 は 0000 をオペレーションコード、0001 をイミディエイトデータとして解釈します。ちなみにオペレーションコード 0000 は TD4 では A レジスタ(このあと説明します)の値とイミディエイトデータの ADD 命令を意味します。

レジスタ

一言で言うなら CPU における記録領域のようなものです。

TD4 では A レジスタと B レジスタという2つのレジスタが用意されています。このレジスタに計算途中の内容を出し入れしながら、計算処理を次々行っていきます。

I/O ポート

これは CPU に対して入力を与えたり、あるいは演算の結果を出力するために使用するポートです。TD4 の場合は CPU から直接 I/O が出るという構成を取っているようです。これは規模の小さい CPU で多く採用されている方式だそうです。

TD4 の命令

TD4 では加算命令(add)、レジスタの値の転送命令(mov)、入出力ポートのやりとり(in, out)、ジャンプ命令(jmp, jnc)の4つの動作が組み込まれています。

実際の CPU になってくると、これらに四則演算が追加されたり、浮動小数点演算が追加されたりと高機能になっていきます。

こうした命令はプログラム側に書かれており、CPU の役割は命令を解釈し計算処理を実行していくことにあたります。

CPU エミュレータの実装

それでは CPU エミュレータの実装の紹介に移っていきましょう。

データ構造を用意する

CPU エミュレータを作り始めた際によかった手順としては、まずデータ構造を用意し、その後に一気にそれらを紐付けていくという方法でした*3

最初に命令を表現する enum を用意しました。OpCode という enum です。なお num_derive という便利なトレイトを今回は使用しています。

use num_derive::FromPrimitive;

#[derive(Debug, PartialEq, FromPrimitive)]
pub enum Opcode {
    AddA = 0b0000,
    AddB = 0b0101,
    MovA = 0b0011,
    MovB = 0b0111,
    MovA2B = 0b0001,
    MovB2A = 0b0100,
    Jmp = 0b1111,
    Jnc = 0b1110,
    InA = 0b0010,
    InB = 0b0110,
    OutB = 0b1001,
    OutIm = 0b1011,
}

各命令の詳しい内容は省略しますが、TD4 では12個の命令を実装すればいったん動くようにできています。ということで、enum を12個用意しました。

また、レジスタも用意します。レジスタは A レジスタ、B レジスタ以外に、キャリーフラグとプログラムカウンタを持っています。

#[derive(Clone)]
pub struct Register {
    register_a: u8, // register a
    register_b: u8, // register b
    carry_flag: u8, // carry flag
    pc: u8,         // program counter
}

I/O ポートも用意します。TD4 では入力と出力をもっているので、それらを用意します。

pub struct Port {
    input: u8,
    output: u8,
}

ROM も用意します。これは先ほどもご紹介しましたがもう一度ここに貼っておきます。プログラムの内容そのものを保持しています。

pub struct Rom {
    pub memory_array: Vec<u8>,
}

エントリポイント

今回のプログラムのエントリポイントとして重要なのは CpuEmulator という構造体です。これが実質エミュレータの構造を表現しています。ここに、先ほども説明した fetch-decode-execute サイクルを表現していくとスムーズでした。

まず CPU エミュレータ自体は下記のような構造体です*4

pub struct CpuEmulator {
    register: RefCell<Register>,
    port: RefCell<Port>,
    rom: RefCell<Rom>,
}

まず fetch です。ここでは現状のプログラムカウンタの値を確認し、プログラムカウンタに該当するプログラムを ROM から読み取ります。

(...)
    fn fetch(&self) -> u8 {
        let pc = self.register.borrow().pc();
        if self.rom.borrow().size() <= pc {
            return 0;
        }

        let code = self.rom.borrow().read(pc);

        code
    }
(...)

次は decode です。ここでバイナリ形式になっているオペレーションコードを解読して、先ほども紹介した内部表現(enum Opcode)に変換をかけます。

(...)
    fn decode(&self, data: u8) -> Result<(Opcode, u8), EmulatorErr> {
        let op = data >> 4;
        let im = data & 0x0f;

        if let Some(opcode) = FromPrimitive::from_u8(op) {
            match opcode {
                Opcode::AddA
                | Opcode::AddB
                | Opcode::MovA
                | Opcode::MovB
                | Opcode::MovA2B
                | Opcode::MovB2A
                | Opcode::Jmp
                | Opcode::Jnc
                | Opcode::OutIm => Ok((opcode, im)),
                Opcode::InA | Opcode::InB | Opcode::OutB => Ok((opcode, 0)),
            }
        } else {
            // never comes
            Err(EmulatorErr::new("No match for opcode"))
        }
    }
(...)

最後は exec です。先ほどの decode の結果をもとに、その Opcode に対応した関数を実行させます。

(...)
    pub fn exec(&self) -> Result<(), EmulatorErr> {
        loop {
            let data = self.fetch();
            let (opcode, im) = self.decode(data)?;

            match opcode {
                Opcode::MovA => self.mov_a(im),
                Opcode::MovB => self.mov_b(im),
                Opcode::AddA => self.add_a(im),
                Opcode::AddB => self.add_b(im),
                Opcode::MovA2B => self.mov_a2b(),
                Opcode::MovB2A => self.mov_b2a(),
                Opcode::Jmp => self.jmp(im),
                Opcode::Jnc => self.jnc(im),
                Opcode::InA => self.in_a(),
                Opcode::InB => self.in_b(),
                Opcode::OutB => self.out_b(),
                Opcode::OutIm => self.out_im(im),
            };

            // To prevent infinite loop
            if opcode != Opcode::Jmp && opcode != Opcode::Jnc {
                self.register.borrow_mut().incr_pc();
            }

            if self.does_halt() {
                return Ok(());
            }
        }
    }
(...)

細々とした各関数の実行内容については、こちらのコードをご覧いただくと、各々の命令がどういった処理を行っているかについて概略を掴むことができるかと思います。

実行自体は、CpuEmulator::withCpuEmulator の構造体を生成したあとに exec() 関数を呼び出すことによって行われます。program という箇所に、たとえば [00110011, 00000001] のようなバイナリが入ってきて、これを解釈して計算処理が走るというのが、このエミュレータの大まかな構造です。

(...)
    let rom = Rom::new(program);
    let register = Register::new();
    let port = Port::new(0b0000, 0b0000);
    let emulator = CpuEmulator::with(register, port, rom);
    match emulator.exec() {
        Ok(_) => (),
        Err(err) => panic!("{:?}", err),
    }
(...)

命令コンパイラの実装

さてここからは、本などには載っていない独自コンテンツになります。命令をアセンブラのように書くと、中でコンパイルして CPU エミュレータ用のプログラムに変え、シームレスに計算処理まで紐付けられる実装を追加してみました。

設計

今回の TD4 エミュレータは、バイナリを渡す必要があります。これでも十分楽しめるのですが、せっかくなのでアセンブラのような書き味の形式のファイルを用意して、それを読み込むとコンパイルが走ってバイナリ表現に変えてくれる形式にしてみたら、より使いやすいエミュレータになるのではないかと思いました。

具体的には、下記のようなファイルを読み込ませると、中で加算処理を行い加算結果を返してくれるというようなものです(コメント部分は実際のファイルには入れられません)。

mov A 0001 // 0001 という値を A レジスタに転送する
add A 0001 // A レジスタの値と 0001 を加算する
mov B A // A レジスタの値を B レジスタに転送する
out B // B レジスタの内容を出力する

このファイルを sasm(simple assembly の略のつもり)という拡張子に変えたテキストファイルにして保存しておき、TD4 エミュレータに読ませると、あとは中で任意の計算処理を走らせるようにしました。

なお、出来としてはおもちゃレベルのもので、エラーハンドリングなども結構雑に作ってあります。意図しない構文を入れると普通に落ちると思います。

パース部分の実装

よくあるコンパイラのパーサーのデザインだと思いますが、下記のような構造体を用意しました。私は 9cc を作ったことがあるのですが、それを一部真似しました。

pub struct Parser {
    pos: usize, // 今どの番地を読んでいるのかを保持する
    source: Vec<String>, // ファイルから読み込んだ内容を文字列で保持する
}

このアセンブラの内容はとてもシンプルなので、空白部分 split をかければ、欲しい内容は一通り抽出できてしまいます。たとえば

mov A 0001

この場合ですと、空白で split をかけると、mov, A, 0001 という文字列が取得できます。TD4 の場合、命令がとても単純なので、たとえば mov の後ろには必ず A か B という文字列が来ているはず、といった感じでシンプルに条件分岐をしながらパースしていくと、一通り命令をパースして解釈できるようになります。

mov の場合のパースの実装例は、たとえば下記のようになっています。パース関数はこちらにあります。

(...)
    pub fn parse(&mut self) -> Result<Vec<Token>, EmulatorErr> {
        let mut result = Vec::new();

        loop {
            let op = self.source.get(self.pos);

            if op.is_none() {
                break;
            }

            let op = op.unwrap();

            if op == "mov" {
                self.pos += 1;
                let lhs = self
                    .source
                    .get(self.pos)
                    .ok_or_else(|| EmulatorErr::new("Failed to parse mov left hand side value"))?;

                self.pos += 1;
                let rhs = self
                    .source
                    .get(self.pos)
                    .ok_or_else(|| EmulatorErr::new("Failed to parse mov right hand side value"))?;

                let token = if lhs == "B" && rhs == "A" {
                    Token::MovBA
                } else if lhs == "A" && rhs == "B" {
                    Token::MovAB
                } else {
                    Token::Mov(
                        Register::from(lhs.to_string()),
                        self.from_binary_to_decimal(rhs)?,
                    )
                };

                result.push(token);
            }
(...)

最終的な結果は Token と呼ばれる enum に詰めて返しています。この enum は Opcode とは別物にしてあって、下記のような定義にしました。

pub enum Register {
    A,
    B,
}

pub enum Token {
    Mov(Register, u8),
    MovAB,
    MovBA,
    Add(Register, u8),
    Jmp(u8),
    Jnc(u8),
    In(Register),
    OutIm(u8),
    OutB,
}

そしてこの Token は、のちのコンパイルフェーズで一旦バイナリ表現に変換されます。

コンパイル部分の実装

コンパイル部分の実装も行いました。

Token ごとに所定のバイナリに変換していきます。たとえば add A 0001 とあったら、まず A レジスタ値との加算命令をしめすバイナリ 0000 とイミディエイトデータ 0001 をくっつけるイメージです。

(...)
    pub fn compile(&self, tokens: Vec<Token>) -> Result<Vec<u8>, EmulatorErr> {
        if tokens.is_empty() {
            return Err(EmulatorErr::new(
                "Failed to start to compile because token list is empty.",
            ));
        }

        let mut result = Vec::new();

        for token in tokens {
            let program = match token {
                Token::Mov(Register::A, im) => self.gen_bin_code(0b0011, im),
                Token::Mov(Register::B, im) => self.gen_bin_code(0b0111, im),
                Token::MovAB => self.gen_bin_code_with_zero_padding(0b0001),
                Token::MovBA => self.gen_bin_code_with_zero_padding(0b0100),
                Token::Add(Register::A, im) => self.gen_bin_code(0b0000, im),
                Token::Add(Register::B, im) => self.gen_bin_code(0b0101, im),
                Token::Jmp(im) => self.gen_bin_code(0b1111, im),
                Token::Jnc(im) => self.gen_bin_code(0b1110, im),
                Token::In(Register::A) => self.gen_bin_code_with_zero_padding(0b0010),
                Token::In(Register::B) => self.gen_bin_code_with_zero_padding(0b0110),
                Token::OutB => self.gen_bin_code_with_zero_padding(0b1001),
                Token::OutIm(im) => self.gen_bin_code(0b1011, im),
            };
            result.push(program);
        }

        Ok(result)
    }
(...)

あとは gen_bin_code などの関数が、指定のバイナリを生成して返すというイメージです。イミディエイトデータを受け取らない命令も TD4 にはあるのですが、その場合は 0000 で詰めればよいことに仕様上なっているので、それ用の関数も用意しました。

やってみた感想

コンピュータの内部については、これを実装してみるまでは全然知らない状態でした。何がどこから読み込まれて計算処理が行われるのかについて、あまり理解できていませんでした。

まず、CPU エミュレータを実装してみたことによって fetch-decode-execute サイクルに関して知ることができ、「このようにしてコンピュータは動いているのか!」と身を持って理解できたように思います。

コンパイラのフェーズは、単に空白を split しただけですし、登場してくる文字列もパターンがかなり定まりきったものを使っただけなので、そこまで難しいことはしていないのですが、自分で1からこうしたコンパイラインタプリタを作るのは楽しいですね。

ちょっとやってみたいなと思ったものの、実力が足りずにできなかったなと思っているものは、今回用意したアセンブラを吐くプログラミング言語を自分で設計して、そのコンパイラを実装してみるというものです。まだまだプログラミング言語そのものに対する理解や、文法の設計経験などが足りないため難しいです。が、いつか取り組めたらいいなと思いました。

次は RISC-V のエミュレータにもチャレンジしてみています。命令数ははるかに多いですし、考慮しなければならない内容やコードベースもこの TD4 エミュレータと比較すると比ではないくらいに多いのですが、がんばって作りきろうと思っています。

*1:パターンマッチがあると、命令のデコード周りをきれいに実装できるかな、というくらいですかね。

*2:fetch-decode-execute cycle: https://www.bbc.co.uk/bitesize/guides/z2342hv/revision/5

*3:ちょっと記憶がなく、そこからしっかり始めたかはもう覚えていませんが。

*4:今思うとここは RefCell である必要はなく、おとなしく &mut にするべき箇所だったかもなと思っています。

Rustでもモナドは実装できるのか?(再)

この記事は言語実装Advent Calendar 2020 25日目の記事です。

モナドに関する話題が言語実装アドベントカレンダーの範疇に入るのかわかっていませんが*1プログラミング言語がお好きな方はきっとモナドもお好きだろう…ということで、Rust におけるモナドの扱いについて記事にしたいと思います。

この記事では、Rust を使って

  • モナドを実装してみる。
  • do 記法を実装してみる。

ところまでやってみました。後半で、GATs と呼ばれる Rust の nightly に入った機能に関して少し細く説明を加えています。

なおこの記事では、モナドとは何かという話はあまり触れていません。

さらに執筆時間*2と記事の都合上、Rust 言語の細かい文法に関する解説もとくに行っていません🙇‍♀️ 登場してくる文法には、適宜注釈でコメントをできるかぎり付与するようにしましたが、不十分かもしれません。

今回の記事は、ずいぶん前に登壇した内容のアップデートです。この発表以降にさらに Rust の言語機能にアップデートがあり、その内容を使ってモナドを実装してみるという記事です。

Rust でもモナドは実装できるのか? - Speaker Deck

前提知識

解説を加えてしまうと記事の長さがとても大変なことになってしまうので今回は省かせていただきますが、いくつか詳しく解説された記事があるのでそちらをリンクさせていただきます。

高階カインド型

まず高階カインド型そのものについては、Scala による説明ですが、下記の記事が直感的でわかりやすいです。

qiita.com

また、なぜ高階カインド型が必要とされるのかについては、この記事がわかりやすいです。

keens.github.io

モナド

モナドというのはいくつか説明の仕方があるかとは思いますが、

ubiteku.oinker.me

個人的にはこの記事の説明が丁寧でわかりやすいかなと思いました。

従来のエミュレーション方法

従来のやり方では、HKT<T> と呼ばれる高階カインド型を表現するトレイトを用意し、HKT トレイトに関連型を2つ(高階を示すものと、高階の中身の型を示すもの)用意すれば、完全ではないものの近い形でエミュレーションできました。たとえば、従来のやり方ではモナドは下記のようにエミュレーションできます。

trait HKT<T> {
    type C;
    type H;
}

trait Functor<U>: HKT<U> {
    fn map<F>(self, f: F) -> Self::H
    where
        F: Fn(Self::C) -> U;
}

trait Monad<U>: Functor<U> {
    fn pure(self, m: U) -> Self::H;
    fn bind<F>(self, f: F) -> Self::H
    where
        F: Fn(Self::C) -> Self::H;
}

単純なデータ構造を例にとって、実装をしてみます。たとえば Id モナド*3を実装してみると、

struct Id<T>(T);

// 高階カインドに関するエミュレーションをここで行う。
impl<T, U> HKT<U> for Id<T> {
    type C = T;
    type H = Id<U>;
}

// ファンクタを定義する
impl<T, U> Functor<U> for Id<T> {
    fn map<F>(self, f: F) -> Self::H
    where
        F: Fn(Self::C) -> U,
    {
        Id(f(self.0))
    }
}

// モナドを定義する
impl<T, U> Monad<U> for Id<T> {
    fn pure(self, m: U) -> Id<U> {
        Id(m)
    }

    fn bind<F>(self, f: F) -> Id<U>
    where
        F: Fn(T) -> Id<U>,
    {
        f(self.0)
    }
}

といった形で、一応型パズルは解け、実際に動かしてみるときちんとそれらしい動きをしていることがわかります。残りは発表資料をご覧ください。

Generic Associated Types を用いたエミュレーション(new!)

ここからが本題です。

Rust nightly 1.50 から入った Generic Associated Types(解説は後ほど)という機能を使うと、従来の HKT トレイトを使う場合と比べ、かなり実装をきれいにすることができます。

1つ1つ型クラスを定義していきます。

型クラスを定義する

Functor を用意する

まずは Functor を用意します。Functor は変換処理の一般化です。

この FunctorFunctor の型パラメータとなる A を関連型 *4 でもたせ、高階カインド型そのものを Lifted<B> という形でもたせます。LiftedFunctor を実装してある必要があるという制約も付与しています。ここに後ほど具体的な型が入ってくることになります。

pub trait Functor {
    type A;
    type Lifted<B>: Functor;

    fn map<F, B>(self, f: F) -> Self::Lifted<B>
    where
        F: FnMut(Self::A) -> B;
}

そして、Lifted<B> の部分に、いわゆる Generic Associated Types(GATs)が使用されています。GATs については後ほど解説します。現在の stable Rust においては、このように Lifted という関連型に型パラメータを付与することはできません。

Pointed を用意する

続いて Pointed を用意します。Pointedpure 関数の一般化です。この関数は、元の型をモナドの文脈の型に変換する機能を持ちます。

PointedFunctor のトレイト境界をもちます。実装先が、Functor も実装してある必要があります。

pub trait Pointed: Functor {
    fn pure(t: Self::A) -> Self::Lifted<Self::A>;
}

Applicative を用意する

続いて Applicative を用意します。Applicative は関数適用の一般化です。apply という関数を持ちます。トレイト境界に Pointed を持ちます。

pub trait Applicative: Pointed {
    fn apply<F, B, C>(self, b: Self::Lifted<B>, f: F) -> Self::Lifted<C>
    where
        F: FnMut(Self::A, B) -> C;
}

Monad を用意する

最後に Monad を用意します。Monad は手続きの結合の一般化です。bind という関数を持ちます。トレイト境界に Applicative を持ちます。

pub trait Monad: Applicative {
    fn bind<B, F>(self, f: F) -> Self::Lifted<B>
    where
        F: FnMut(Self::A) -> Self::Lifted<B>;
}

いくつか型を実装していく

ここまで用意できたところで、実際にいくつか型を実装していきましょう。まずは最も単純な例として、先ほどもご紹介した Id モナドを実装してみます。

pub struct Id<M>(pub M);

impl<A> Monad for Id<A> {
    fn bind<B, F>(self, mut f: F) -> Id<B>
    where
        F: FnMut(A) -> Id<B>,
    {
        f(self.0)
    }
}

impl<A> Pointed for Id<A> {
    fn pure(t: A) -> Id<A> {
        Id(t)
    }
}

impl<A> Applicative for Id<A> {
    fn apply<F, B, C>(self, b: Id<B>, mut f: F) -> Id<C>
    where
        F: FnMut(A, B) -> C,
    {
        Id(f(self.0, b.0))
    }
}

impl<A> Functor for Id<A> {
    type A = A;
    type Lifted<B> = Id<B>;

    fn map<F, B>(self, mut f: F) -> Id<B>
    where
        F: FnMut(A) -> B,
    {
        Id(f(self.0))
    }
}

また、Rust にすでに存在する OptionResult も、一応今回用意したモナドにすることができます。*5

まずは Option モナドを用意してみます。

impl<A> Monad for Option<A> {
    fn bind<B, F>(self, mut f: F) -> Option<B>
    where
        F: FnMut(A) -> Option<B>,
    {
        self.and_then(f)
    }
}

impl<A> Pointed for Option<A> {
    fn pure(t: A) -> Option<A> {
        Some(t)
    }
}

impl<A> Applicative for Option<A> {
    fn apply<F, B, C>(self, b: Option<B>, mut f: F) -> Option<C>
    where
        F: FnMut(A, B) -> C,
    {
        let a = self?;
        let b = b?;
        Some(f(a, b))
    }
}

impl<A> Functor for Option<A> {
    type A = A;
    type Lifted<B> = Option<B>;

    fn map<F, B>(self, mut f: F) -> Option<B>
    where
        F: FnMut(A) -> B,
    {
        self.map(f)
    }
}

また、Result モナドは今回は Ok 側にバイアスをもたせた形で用意してみました。

impl<A, E> Monad for Result<A, E> {
    fn bind<B, F>(self, f: F) -> Result<B, E>
    where
        F: FnMut(A) -> Result<B, E>,
    {
        self.and_then(f)
    }
}

impl<A, E> Pointed for Result<A, E> {
    fn pure(t: A) -> Result<A, E> {
        Ok(t)
    }
}

impl<A, E> Applicative for Result<A, E> {
    fn apply<F, B, C>(self, b: Result<B, E>, mut f: F) -> Result<C, E>
    where
        F: FnMut(A, B) -> C,
    {
        let a = self?;
        let b = b?;
        Ok(f(a, b))
    }
}

impl<A, E> Functor for Result<A, E> {
    type A = A;
    type Lifted<B> = Result<B, E>;

    fn map<F, B>(self, mut f: F) -> Result<B, E>
    where
        F: FnMut(A) -> B,
    {
        self.map(f)
    }
}

現状実装できないもの

ただし、関数型プログラミングにおいて利用する道具が完全に実装できるというわけではありません。たとえば、

  • いわゆる flattenjoin の処理はコンパイル時にコンパイラがパニックを出して落ちる(バグの可能性がある)。
  • traverse を実装しようとするとうまくコンパイルが通らない*6

といった内容が、この記事にて報告されていました

do 記法

Haskell には do 記法、Scala には for-yield と呼ばれる構文があり、これらを用いることで次のように bind(あるいは flatMap)がいくつも重なってしまう現象を回避できたりします。

// Rust による例
Option::pure(...).bind(|o| return_option_function(o).bind(|p| return_option_function(p))

モナドの真骨頂は、こうした do 記法や for-yield などとともに利用するところにあると思うのですが、Rust にはそうした専用の構文はありません。

そこで、Rust のマクロという機能を用いて do 記法を実装しました。do は Rust においては予約語になっており使用できないので、monad-do から取って mdo というマクロを作りました。

macro_rules! mdo {
    ($i:ident <- $e:expr; $($t:tt)*) => {
        $e.bind(move |$i| mdo!($($t)*))
    };
    ($e:expr; $($t:tt)*) => {
        $e.bind(move |()| mdo!($($t)*))
    };
    (ret $e:expr) => {
        $e
    };
}

少し Rust のマクロに関して補足を入れておくと、

  • $i, $e, $t: マクロ内における変数。
  • $(...)**: 0回以上の繰り返しを意味します。
  • :ident: これはいわゆる識別子がやってくることを示します。
  • :expr: これはいわゆる式がやってくることを示します。
  • :tt: 何か単一のトークン木がやってくることを示します。

内部で軽い構文解析を行い、<- の前後を解析して式なのか識別子なのか、それ以降に続く別のトークン木なのかを見分けます。その後、取り出せた式と識別子を使ってモナドに紐づけて実装されている(はずの) bind を呼び出し、残ったトークン木を更に再帰的に mdo! マクロにかける、ということをしています。また、結果は ret と書いた後ろの式を返します。

これを用いることで、

mdo! {
    a <- {何かモナドを作る};
    b <- {何かモナドを作る};
    ret result(a +b) // 何か結果を返す
}

といった記法が可能になります。

実際 Rust でこれを使用してみると、下記のように記述可能になり、テストを通すことができました。

mod test_do {
    use crate::data::option::*;
    use crate::{applicative::Applicative, functor::Functor, functor::Pointed, monad::Monad};

    #[test]
    fn test_do_notation() {
        let actual = mdo!{
            x <- Option::pure(1);
            y <- Option::pure(2);
            ret Option::pure(x + y) // Some(3) が返るはず
        };
        assert_eq!(actual, Some(3));
    }
}

便利ですね。

Generic Associated Types(GATs)とは何か

ここからは言語実装やプログラミング言語全般の話というより Rust 特有の事情の話になってしまい大変恐縮なのですが、GATs が一体何なのか、どういう使い道があるのかについて RFC を読みながら簡単にまとめておきたいと思います。

github.com

GATs というのは先ほども軽く触れたとおり、関連型に何かしらの型パラメータ(AT みたいなもの)をもたせることができる機能です。Rust にいわゆる高階カインド型を導入するための機能です。

Rust の場合は、他の言語でもあるような型パラメータ以外にもライフタイム注釈*7をこの位置に入れることができます。つまり、型パラメータの位置に入るのは A というような型情報と、もうひとつは 'a というライフタイム注釈が来ることになります。GATs はこれら2つを関連型で扱えるようにするための機能です。

下記は RFC から拝借してきたコードですが、ライフタイムに関しては次のような記述が GATs で行えるようになります。これは Rust を書いていると多々直面する内容で、ユーザーが求めていた機能でもありました。

trait StreamingIterator {
   type Item<'a>;
}

impl<T> StreamingIterator for StreamIterMut<T> {
    type Item<'a> = &'a mut [T];
    ...
}

また、型パラメータを関連型にもたせる側では、たとえば下記のような記述が GATs を用いて行えるようになります。Rust には RcBox などのスマートポインタがいくつか存在しますが、これらは型パラメータを引数に取ります。そうしたポインタを関連型の具象実装側を切り替えることで切り替えたい場合に、GATs が役に立ちます。

trait PointerFamily {
    type Pointer<T>: Deref<Target = T>;
    fn new<T>(value: T) -> Self::Pointer<T>;
}

struct ArcFamily;

impl PointerFamily for ArcFamily {
    type Pointer<T> = Arc<T>;
    fn new<T>(value: T) -> Self::Pointer<T> {
        Arc::new(value)
    }
}

struct RcFamily;

impl PointerFamily for RcFamily {
    type Pointer<T> = Rc<T>;
    fn new<T>(value: T) -> Self::Pointer<T> {
        Rc::new(value)
    }
}

struct Foo<P: PointerFamily> {
    bar: P::Pointer<String>,
}

RFC によると、GATs が入ったからと言ってモナドを完全に実装できるようになるというわけではないと注意書きがなされています。私がモナドを実装することに関してそこまで深い知識があるわけではないので、一体どういったポイントが足りなくてそうなっているのかは今後の探求の課題だなと思いました。

リポジトリ

まだいろいろ実験中ですが、リポジトリはこちらにあります。

github.com

参考文献

*1:カレンダーに登録してみたものの、プログラミング言語そのものに関わりそうな話題としての持ちネタがこれくらいしかありませんでした🙏

*2:12/24に書き始めたのが間違いだった。もう少し時間を取るべきでしたね。

*3:恒等モナド。単に 1i32 のような値をモナド文脈の中に持ち込める存在です。これを用いるとたとえば、Id(1).map(|i| i + 1) = Id(2) のような計算を行うことができます。

*4:Rust ではトレイト内部に type という他の言語でも見られるような型エイリアスをつけることができます。これは関連型と呼ばれ、Rust を書いていると何度も登場してくる概念になります。高階カインド型のエミュレーションは、この関連型を用いて行うことになります。後ほど解説しますが、現状の stable Rust ではこの関連型に型パラメータを付与することはできません。が、nightly で型パラメータを付与することが可能になり、より関連型の一般化をしやすくなりました。

*5:Rust では実際のところ、これらの型は Iterator として一般化されているのであまりやる意味はないのですが…

*6:ただ、これは直せそうな気がしました。関連型のうちどれを使用すればいいかをきちんと明示的に書いてあげる必要があるかも?

*7:Rust にはダングリングポインタを防止するための仕組みとしてライフタイムという概念が存在します。このライフタイムというのは、ユーザーがライフタイム注釈を個別に指定してライフタイムを明示的に書くこともできるようになっています。ライフタイム注釈というのは 'a というようにシングルクオートで始まる形で、通常の型情報と同じ位置(<> 内)に入れて書きます。

RustFest Global を開催しました

この記事は Rust Advent Calendar 2020 その3の4日目の記事です。今日は Rust に関する話ではあるのですが、技術的な話ではない記事になってしまうことをお許しください。

1ヶ月ほど経ってしまいましたが、Rust の全世界的なカンファレンス RustFest Global を、11/7〜11/8で開催しました。スピーカーとして参加してくださった皆さん、また RustFest Global に遊びに来てくださった皆さん、ありがとうございました。

今日はその RustFest Global に関する話を書きたいと思います。ちなみに多分この記事を Google 翻訳にかけて読まれる海外の方も多いと思うので、先に書きます。英語にするので少しお待ち下さい!

For non Japanese speakers: I'm going to jot down my thoughts regarding RustFest Global. Unfortunately, there is no English version right now. I'm planning to translate this post into English soon. Please gimme a moment!

RustFest Global とは?

f:id:yuk1tyd:20201204143538p:plain
RustFest Global

rustfest.global

ヨーロッパの RustFest チームの声掛けで始まった、複数のタイムゾーンにまたがる Rust カンファレンス

たしか夏前だったと思いますが、RustFest チームからの声掛けで、今回 Rust.Tokyo のチームもこのカンファレンスの運営に参加することになりました。

RustFest チームというのはヨーロッパ圏の Rust カンファレンスを開くチームで、ヨーロッパで毎年カンファレンスを開催しています。前回はバルセロナだったと思います。実は去年の Rust.Tokyo にて、Rust コアチームの Florian Gilcher 氏が基調講演を行ってくれましたが、彼も RustFest チームの主催者の一人でした。現在は卒業生のようです。

Rust.Tokyo は今年は中止の判断をしていた

私たち Rust.Tokyo のチームは、今年は Rust.Tokyo を実施しないという判断をしていました。理由はご多分に漏れずコロナウィルスです。中止の判断をした4月時点では、コロナウィルスがいつ収まりを見せるか、あるいはどのように今後感染拡大していくのかがまったく見えない状態でした。周りのカンファレンスも中止の判断をしているところが多かったというのもあります。

rust.tokyo

しかし一方で、2020年になって Rust はさらに広まりを見せ、私自身も本を共著で出版させてもらうなど盛り上がりを感じていました。そのような状況でカンファレンスを今年は開けないというのは、少し歯がゆい思いがありました。

そんななかでの RustFest チームからの声掛けということもあり、Rust.Tokyo としてもぜひ、ということで運営に参加することになりました。

ラテンアメリカのチームも一緒に運営をすることに

Rust.Tokyo 以外には、日本のユーザーの方は本当にあまり馴染みがないかもしれませんが、Rust LATAM というラテンアメリカのチームも運営に参加することになりました。彼らはアルゼンチンなどに済んでいるようです。日本の真裏、12時間の時差です。

開催まで

毎週ヨーロッパとラテンアメリカと一緒にミーティング

開催までは、毎週ヨーロッパとラテンアメリカ、ならびに日本のチームが Zoom で集まってミーティングを行いました。

グローバル規模で会議をすることになって大変だったのは時差の問題です。JST では1時開始のミーティングでした。ラテンアメリカチームが入ってきて、JST で19時スタート(ラテンアメリカは朝の7時スタート)のミーティングも追加され、隔週で時間帯をラテンアメリカと交代しながら行いました。

私は普段は英語はそれなりに聞けるのですが*1、夜中の1時に第二外国語を聞くのはなかなかハードでした笑。でも、毎週のミーティングは楽しかったです :)

翻訳チームの結成

今回のカンファレンスは「グローバルである」ことにとてもこだわっていました。つまり、Rust.Tokyo は日本だけでなくアジア太平洋地域(APAC)の担当をすることが期待されていました。

本来であればアジアの様々な国の言葉に英語の文章をローカライズして提供するべきだったのですが、参加者の人口比やツテの問題などを考慮して、韓国語と中国語(簡体字繁体字)の翻訳ができる方を募集しました。

韓国語については Enwei Jin さん、中国語の簡体字については Xidorn Quan さん、繁体字については Rust.Tokyo にも参加してくれた Cheng You Bai さんと Kan-Ru Chen さんが担当してくださいました。

改めてお礼をさせてください!本当にありがとうございました。Thank you for the translation team! I appreciate your swift & professional work.

翻訳チームとは基本的にすべて英語でやりとりをしました。英語は世界の標準語になっていますね。

翻訳チームには、主に RustFest のアカウントで告知される内容の翻訳と、CfP に際してサイトに掲載された文章を翻訳していただきました。たとえばこのような感じに。

全然話が逸れますが、個人的には、実際に翻訳されてあがってきた文章を見ながら「この言語ではこういう言い方をするんだ〜」というのを知ることができてとてもおもしろかったです。私は韓国系のドラマや YouTuber を見るのが好きで、韓国語を少しだけ勉強しているというのもあり、韓国語はとくに勉強になりました。できれば英語の字幕なしでそうした番組や YouTube の動画を観られるようになりたい…。

発表が英語でなかった場合の事前字幕付け

発表者が英語話者でない場合も想定していました。その場合には事前にプレゼンテーションを録画してもらい、その録画内容に字幕をつけることで対応という形になりました。

結果、日本から参加してくださったスピーカーの方は日本語でお話いただきました。ほかは、すべて英語のセッションとなりました。

字幕自体はプロの翻訳の会社に依頼してつけてもらいました。できあがった成果物について、スピーカーが話している内容と字幕の表示される内容があっているか、また字幕が表示されるタイミングは正しいかを確認しました。

準備

準備のほとんどは RustFest チームが行ってくれました。改めて本当にありがとうございました。

  • スピーカーの募集
  • スポンサーの募集
  • アーティストの募集
  • スケッチノーターの募集
  • 使用するツールの手配
  • 翻訳業者の手配

などを行っていました。

日本のカンファレンスと圧倒的に違うと感じたのは、アーティストの募集とスケッチノーターの募集でした。アーティストによる演奏があるカンファレンスは、日本ではまったく見ませんね。海外系のカンファレンスだと結構見るのでわりと一般的だと思います。アメリカの Rust のカンファレンスの RustConf は演奏していたような気がします。

スケッチノートというのは、日本でもカンファレンスに参加した方がボランティアで SNS などに流してくださるのを見ることはあるかもしれません。一方で、このように公式に募集しているカンファレンスは、私の知っている範囲が狭いだけかもしれませんが、カンファレンスサイドが公式に募集しているのは日本ではあまり見ないように思います。

ヨーロッパ圏というか欧米圏は、このようにアートも含めて「場」を設計するところに力を注いでいるところがとても見習うべきポイントだなと個人的には思いました。神は細部に宿る、のかもしれません。

(日本におけるアートの立ち位置は、今回のイベントのように(ヨーロッパのような)積極的に「場」に入れ込んでいくという立ち位置では必ずしもないように思います。日常にアートがそこまで入り込んでいないという感じがあります。東京には美術館は多いんですけどね。カンファレンスや人が集まった際、ふとした瞬間にアートを入れようとはならないのだと思います。私だけかもしれませんが、「何かこう、気合いをいれて楽しむもの」という印象が強いかもしれません。なので、カンファレンスとアートを融合させようという発想にそもそも至りません。ヨーロッパ圏とアジア圏のアートの考え方やアートへの接し方の違いはとても興味がわきました。)

あつ森のグッズ

同じく RustFest 主催者の Pillar さんがあつ森用のグッズを作ってくれたので、記念にもらって撮影してみました。

めっちゃかわいいのである。

当日

チャットルームのモデレータ

私は主にチャットルームのモデレータをしていました。Code of Conduct に反する発言をする人がいないかを監視していました。

途中で「資本主義とはなんたるか、あなたはどう思うか」というコメントが始まって、テックイベントで政治的発言は大丈夫なのかな…と思う場面もありましたが、スピーカーの方が機転を利かせて「あとは DM しよ!」と言ってくれていて内心かなりホッとする出来事がありました笑。

結局まあまあ見てしまった

20時間にも及ぶカンファレンスでしたが、日本時間であれば、開始からラテンアメリカの途中までは見られるタイムスケジュールでした。どのセッションもおもしろく、ところどころ休憩を取りながらすべてのブロックを一通り見ることができました。

次々に日が昇っていく

運営のチャットルームがあったんですが、APAC が終わったくらいで日が昇ってくる写真がヨーロッパから投稿されるなど、ワイワイ楽しくやっていました。

日本は日本から開始すると一番早く日がのぼっている国で、ヨーロッパが次に日が昇り、ラテンアメリカが最後に日が昇るという感じでした。実はラテンアメリカの方は APAC のセッションの方の最初の方は見てくれていて、最初のプレゼンテーションの前には「gambatte!」というコメントをくれてとてもほっこりしました。

難しいと感じたこと

英語の壁

日本向けのカンファレンスではないので仕方がありませんが、やはり英語のセッションのときは如実にTwitterやチャットルームのリアクションが減ってしまったように思いました。英語、大変ですよね。私もネイティブスピーカーというわけではないので、英語を使う際は少し頭を切り替えないといけません。

日本に住んでいると、英語を使う機会がそもそもありませんよね。英語を見ない・聞かない・話さない日が大半だと思います。自分から注意深く英語のコンテンツを見るようにしないと、なかなか触れる機会がないと思います。これは、地政学的な要因や文化的な要因が絡んでいて、致し方ない問題だと思います。

英語の壁の突破策は、やはり同時通訳なのでしょう。ScalaMatsuri などでは同時通訳で日本語→英語訳、あるいは英語→日本語訳が聞けたりしますが、そうした施策はやはり有用なのだなあと思いました。こうした同時通訳の用意などは、今回感じた「完全なローカライゼーション」への課題感にもつながっていきます。

すべての人が楽しめるカンファレンスにするために、言語の障壁はできる限り取り払わなければならないというのは、去年の Rust.Tokyo でも感じたことでした。

「完全な」ローカライゼーション

ローカライゼーションというのは難しいですね。日本語訳を用意することはもちろんローカライゼーションの一つではあるのですが、それだけでは足りないことがあります。

たとえば最近あがっていた記事でおもしろかったものなのですが、海外サイトのローカライゼーションだけでも、これだけ気にしなければならないことが出てきます。デザインだけでなく、よく使われる言葉やキャッチコピーに変えるなどの対応も必要になってきます。

zenn.dev

ツールに関するローカライゼーションなどもあるでしょう。たとえばメッセージングアプリに関して言えば、海外では WhatsApp が大半ですが日本では LINE が大半といった具合にです。日本では使い慣れないツールを使う必要が出てくると、どうしても操作に慣れなくてストレスが…といったこともあるかもしれません。

要するに、言語の翻訳だけではなく文化の翻訳も本来は行う必要がある、ということです。

しかし、こうしたローカライゼーションは完全対応しようとすると、費用と人がより多く必要になります。限られた資源の中で適切なローカライゼーションを優先順位をつけて行っていく必要があるというのが現実です。的確なローカライゼーション施策を打つのはとても難しいのだなあと思いました。

来年以降

RustFest Project 始動

まだ詳細は未定の部分が多いですが、RustFest Project が始動します。

これは、たとえば今はコミュニティが存在しない国や地域で新しくコミュニティを立ち上げたい!となった際に、RustFest Project がいろいろノウハウや資金面でコミュニティの立ち上げや運営を援助できる仕組みです。

blog.rustfest.eu

予算の使途などをオープンに管理するために下記のページで今後予算状況や何に使用したかなどを知ることができます。ならびに、金銭的なコントリビューションをこのページから応募することもできます。

opencollective.com

技術とコミュニティは密接な関係にあります。その技術が、いい形で普及するかどうか、また発展するかどうかはコミュニティの力にかかっています。こうした、 Rust がコミュニティを大切にする姿勢は、Rust の好きなところのひとつでもあります。

遊びに行きたい

コロナ終わってたら来年の RustFest と Rust LATAM に遊びに行きたいです!

*1:ただ、子どものころ英語を使う環境にいただけなので、大人の使う単語は正直わからん!となることは多いです。あとはアメリカ英語がわかりません。