ジェネリクス勉強会補足

2017-06-24

κeenです。本日ジェネリクス勉強会で発表したのですがいくつか拾いきれないコメントがあったのでここでお返事書きます

発表スライドはこちら

ジェネリクスの実装はポインタ方式とテンプレート方式だけじゃないよ

もちろんです。基本的な手法を大別しただけで、私の発表中にもポインタ方式でも最適化がありえるとの指摘がありましたし、ジェネリクス勉強会中でも.NETの実装の話も出てました。勉強会全体を見ているならここで私がフォローするまでもないかと思いますが、念のため拾っておきます。

クロージャの件が分からない

クロージャの型は関数型じゃないの？
無名関数は関数に名前がないだけで型はあるんじゃないの？
なんで(Iteratorのmapとかの)返り値に関数型がでてくるの

Rustの挙動を知らないとちょっと分かりづらかったですね。それとあとで見返したら私も発表中一箇所嘘いってました。詳しいことをコード例を出しながら説明していきます

Rustのクロージャの型は匿名化された型

Rustのクロージャ3種を作って理解する | κeenのHappy Hacκing BlogやRustのゼロコスト抽象化 | κeenのHappy Hacκing Blog で若干説明しましたが、Rustではクロージャリテラル毎に型が作られます。

let mut x = 0;
let mut counter = || { x += 1; x}

こう書いたときにコンパイラは裏で以下のようなコードを生成します。（Rustを知らない人への説明のため、FnOnceの存在や実際は参照でキャプチャするなどを無視した疑似コードです）

struct AnonymousClosure{x: i32}
impl FnMut<()> for AnonymousClosure {
    extern "rust-call" fn call_mut(&mut self, (): ()) -> i32 {
        self.x += 1;
        x
    }
}
let mut x = 0;
let mut counter = AnnonymousClosure{x: x}

要点は

クロージャ自体はただのキャプチャしたデータの集まり
関数本体は、メソッドとして定義される。 Rustは静的ディスパッチをする ので 関数ポインタはデータには含まれない。コンパイラが解決する。
- 私が1つ嘘を言っていたというのはここです。関数ポインタもデータに含まれるって言っちゃってました。
- クロージャだけど関数ポインタを使わないんですね
1クロージャリテラルにつき1型を生成することでクロージャリテラル毎の関数本体を出し分けている
キャプチャした変数をまとめた構造体自体はポインタ型になっていない

ということで

クロージャ自体の型は関数型ではなくて、関数っぽい振舞いをするトレイト(ここではFnMut)を実装しているだけのただの無名型です。
無名関数だから型が無名という説明は確かにちょっとおかしかったですね。

クロージャを返したい

ここから「なんで(Iteratorのmapとかの)返り値に関数型がでてくるの」へのお返事。

説明の例として遅延評価するイテレータへのマップを書きたいと思います。引数にはイテレータとクロージャを取ります。実際には適用する訳ではないのでマップするイテレータとクロージャの組を返せばよさそうですね。ここで思い出して欲しいのはクロージャはただのFnMutを実装している構造体なのでした。なのでこう書くのですが、

fn map<I, B, F>(i: I, f: F) -> (I, F)
where
  I: Iterator,
  F: FnMut(I::Item) -> B,
{
  (I, F)
}

実際にクロージャを渡したときには

fn map(i: SomeIter, f: AnnonymousClosure) -> (SomeIter, AnnonymousClosure)
{
  (i, f)
}

のようになります。ここでも、クロージャデータにはポインタが挟まってないことに注意して下さい。そして型名が分かるのでクロージャを呼び出すときにはその関数が 静的ディスパッチされます

返り値にクロージャの型を書く = クロージャの関数本体が静的ディスパッチされる = 速い

ということが伝わりますでしょうか。なのでRustではできるかぎり返り値にクロージャの型を書きたいのです。

で、このパターンだと引数で受け取ったものを返り値で返すだけなので関数を呼んだときに得られた名前を書くだけです。たとえクロージャが匿名型であっても書くことができます。

返り値にだけ書きたい

ところが返り値にだけクロージャの型を書こうとすると、ダメです。先程のmap関数を関数の中で使ってみましょう。

fn inc<I>(i: I) -> ???
where
  I: Iterator<Item = i32>,
{
  map(i, |x| x + 1)
}

こうすると型はこう解決されます。

sturct AnnonymousClosure;
impl FnMut<(i32,)> for AnonymousClosure {
    extern "rust-call" fn call_mut(&mut self, (x,): (i32,)) -> i32 {
        x + 1
    }
}

fn inc(i: SomeItr) -> (SomeItr, AnnonymousClosure)
{
  map(i, AnnonymousClosure::new())
}

返り値にだけ匿名型が出てきました。先程のようにパラメータで受け取ってそのまま返すということができません。なのでここで、返り値も匿名化する存在型が必要になるのです。

ここまでくれば以下のコードにも存在型が必要な理由が分かりますでしょうか。

fn do_later() -> impl Future<Item = (), Err = Error> {
    do_something()
        // ここでクロージャが出てきた
        .and_then(|()| do_another_thing())
        // 本来の`and_then`の返り値は
        // `AndThen<Self, B, F>`だが
        // `F`の型が匿名化されていて書けない
}

存在型って、forallでできるよ

マジレスなのかただ知識を披露してるのかよく分からなかったのですが、いちおうお返事書いておきます。

どの意味で「forall」でできるよと言っているのかよく分からなかったのですが、Coqの実装を見ていっているのなら見当違いです。 Coqの実装はこの辺が参考になりますかね。 Coqで「任意のxについて…」「あるxが存在して…」を扱う - きくらげ観察日記。

これをRustで書くとこうなるでしょうか。Rustにはトレイトをパラメータで受け取る手段がないのでひとまず量化する一階の述語をFn() -> ()トレイトにしておきます。

struct FnExists<F: Fn() -> ()>(f: F)

これは命題論理としては正しいのですが、型パラメータを取るので目的である匿名化を実現できていません。

2017-06-25 追記: よく考えたらCoqの実装とは異なりました。Coqに忠実にするならこうでしょうか。

struct FnExists(for<F: Fn() -> ()> f: F)

これもダメです。Fの実際のサイズが分からないのでコンパイルできません。これを実現できている言語ではポインタを使って実現しているのかと思います。 Rustでも説明の通りトレイトオブジェクトがあれば可能です。しかしながらオーバーヘッドがかかるので避けたいという話でした。「型システムに表現能力がある」と「値レベルでのパフォーマンスを犠牲にしない表現能力がある」は別の話です。

/追記

もう1つは、CPS変換の可能性もあります。この辺が参考になりますかね。データ型のCPS変換について - Just $ A sandbox。

直観論理でも以下が成り立ちます。

\[ {}^\exists x P(x) \to \lnot ^\forall x \lnot P(x) \]

因みに逆は直観論理では成り立ちません（直感的な説明をすると存在しないことを否定しても実際の値を構成できないからです）。

これは確かに正しいです。「Trトレイトを実装した型」という存在型は以下の疑似コードで書けるでしょう。

trait Tr{}
fn exists() -> FnOnce<A>(FnOnce<T: Tr>(t: T) -> A) -> A {
  let tr = SomeTr::new();
  forall <A> move |cont: FnOnce<T: Tr>(t: T) -> A| -> A { cont(tr) }
}

ですがまあ、これは実際には無理です。 1つにはRustには型の高ランク多相がありません。ジェネリクスだけです。もしランクの概念を知らずにforallで書けると主張しているならそれは的外れです。ランクの概念を知った上で高ランク多相を入れろという主張なら理解はできますが、無理です。引数に渡す関数や返り値で返す関数、要はデータとして扱う関数はジェネリクスにできません。スライドの中でRustはテンプレート方式と説明しましたが、ジェネリクスはテンプレートであって実際のデータではないので値として扱えないのです。なのでRustのコンパイル方式を大きく変えるなどしないと実現できないでしょう。

それにもう1つ、ランクとは関係なしにクリティカルな理由があります。上で説明した通り、クロージャの実際の型は匿名データ型になります。なので返り値に型として書くことができません。冷静になって考えれば返り値のクロージャの型を書かないようにするための存在型のために返り値にクロージャの型を書くのは土台無理です。

さて、私の知識では全称型で存在型を構成する手法はこれくらいですがもし上記以外の構成方法が存在して、私が明後日な返事をしているなら連絡下さい。