Rustの FnBox について、動機・仕組み・問題点を説明する。

`FnBox` の動機

以前の記事では、「「クロージャを boxせずに返したい」という欲求は人類の四大欲求のひとつと言われている。」と書いたが、出所の異なるクロージャを同じ型で扱う必要がある場合は無理せず Box に入れるべきである。

例えば、非同期処理など、継続渡し形式で何らかの処理をする場合は、一般に生のクロージャでは使い勝手が悪い。おもちゃ的な例として、フィボナッチ数列の計算を継続渡し形式で行うことを考える。以下のように書くとうまくいかない。

fn fib_cont<T, F: Fn(u32) -> T>(n: u32, continuation: F) -> T {
    if n <= 1 {
        continuation(n)
    } else {
        fib_cont(n - 1, |a| {
            fib_cont(n - 2, |b| {
                continuation(a + b)
            })
        })
    }
}

fn main() {
    fib_cont(13, |a| {
        println!("{}", a);
    });
}

そこで、生のクロージャではなく、トレイトオブジェクトを渡すようにする。動的ディスパッチになってしまうが、異なるクロージャを同じ型で渡せるようになる。

fn fib_cont<'a, T>(n: u32, continuation: Box<Fn(u32) -> T + 'a>) -> T {
    if n <= 1 {
        continuation(n)
    } else {
        fib_cont(n - 1, Box::new(|a| {
            fib_cont(n - 2, Box::new(|b| {
                continuation(a + b)
            }))
        }))
    }
}

fn main() {
    fib_cont(13, Box::new(|a| {
        println!("{}", a);
    }));
}

ここで Fn を使ったが、場合によっては FnMut や FnOnce をインターフェースとして使いたい場合もある。 Fn/FnMut/FnOnce は以下のような違いがある。

Fn は所有権や書き込み権限がない参照に対しても呼ぶことができる。その代わり、キャプチャーした変数に書き込めないし、仮にmoveキャプチャーでもその変数を外に動かすことはできない。
FnMut は所有権がなくても呼べるが、 mut である必要はある。キャプチャーした変数には書き込めるが、仮にmoveキャプチャーでもその変数を外に動かすことはできない。
FnOnce は所有権があるときに1回だけ呼べる。その代わり、キャプチャーした変数には書き込めるし、moveキャプチャーならキャプチャーした変数を外に動かすことができる。

実践的な例ではないが、先ほどのフィボナッチ数列の例を FnOnce で書き直してみる。

fn fib_cont<'a, T>(n: u32, continuation: Box<FnOnce(u32) -> T + 'a>) -> T {
    if n <= 1 {
        continuation(n)
    } else {
        fib_cont(n - 1, Box::new(move |a| {
            fib_cont(n - 2, Box::new(move |b| {
                continuation(a + b)
            }))
        }))
    }
}

fn main() {
    fib_cont(13, Box::new(|a| {
        println!("{}", a);
    }));
}

ところがこのプログラムは現在のRustではエラーになる。これは FnOnce の定義を見るとわかる。

pub trait FnOnce<Args> {
    type Output;
    extern "rust-call" fn call_once(self, args: Args) -> Self::Output;
}

この call_once メソッドは Self 型の引数をとるにも関わらず、 Self: Sized を要求していない。以前の記事で指摘したように、このことは実は許されているのであった。また、オブジェクト安全性の条件も実は満たされているため、 FnOnce(u32) -> T の対応するトレイトオブジェクト自体は実際に存在することになる。

しかし実際に FnOnce(u32) -> T を呼ぶためには、このオブジェクトをムーブで渡す必要がある。しかしムーブで渡すにはその型が Sized である必要があるから、うまくいかない。つまりオブジェクトを生成する時点では問題にはならないが、実際にメソッドを呼ぶ段階で問題が発生することになる。

`FnBox` の仕組み

std::ops で定義されている Fn, FnMut, FnOnce とは異なり、 FnBox は単なるユーザー定義のトレイトである。 (extern "rust-call" と丸括弧記法を採用しているという特殊性はあるものの)

そしてその定義は以下のようになっている。

pub trait FnBox<A> {
    type Output;

    fn call_box(self: Box<Self>, args: A) -> Self::Output;
}

self が Box<Self> 型をとれることは以前の記事で説明してある。

さて、このトレイトの定義は FnOnce とほぼ同じである。唯一の違いは、 call_once の self が Self なのに対して、 call_box の self が Box<Self> であるという点である。したがってこの2つのトレイトは、 Self: Sized である限り、相互に実装可能である。実際、 FnBox は全ての FnOnce に対して実装されている。 (もちろん逆はない。一貫性条件に反するからである。)

impl<A, F> FnBox<A> for F where F: FnOnce<A> { ... }

ここで重要なのは、 Box<FnOnce> と Box<FnBox> の違いである。以前の記事で説明したvtableの構造によると、これらのfatポインタの指すvtableは以下の構造を持つことになる。

Box<FnOnce> のfatポインタの指す先には、
- 0番目: Drop Glue
- 1番目: 元の型のバイト数
- 2番目: 元の型のアラインメント
- 3番目: call_once へのポインタ
Box<FnBox> のfatポインタの指す先には、
- 0番目: Drop Glue
- 1番目: 元の型のバイト数
- 2番目: 元の型のアラインメント
- 3番目: call_box へのポインタ

さて、このfatポインタが判明している状態で、クロージャを呼ぶことを考える。 call_once を呼ぶことを考えると、これはほぼ不可能であると考えられる。例えば f64 と u64 は通常同じバイト数、同じアラインメントを持つが、 f64 と u64 をそれぞれ第1引数に持つ関数は格納先のレジスタが異なるかもしれない。これはvtableだけからは区別できない。

一方 call_box は FnMut::call_mut や Fn::call と同じように簡単である。第1引数はthinポインタなので、fatポインタの0番目をそのまま渡せばよい。

最後に、 FnBox は FnOnce を実装していないが、 Box<FnBox> は FnOnce を実装している。

impl<'a, A, R> FnOnce<A> for Box<FnBox<A, Output = R> + 'a> { ... }

言語処理系は FnBox を特別扱いしないが、上のように FnOnce を実装しているため通常の関数呼び出し構文が利用可能になっている。

結局、 FnOnce から出発して、 FnBox を経由して FnOnce に戻ってきたことになる。このように、 FnBox は適切なvtableを提供するための中間表現であると言える。

`FnBox` の使い方

FnBox の使い方は簡単で、 Box<FnOnce> として使いたい場所を Box<FnBox> に変えるだけでよい。ただし、以下の2点に注意する必要がある。

機能ゲートで守られているので、nightlyコンパイラを使い、冒頭で #![feature(fnbox)] を宣言する必要がある。
preludeには入っていないので、 use std::boxed::FnBox; する必要がある。

#![feature(fnbox)]

use std::boxed::FnBox;

fn fib_cont<'a, T>(n: u32, continuation: Box<FnOnce(u32) -> T + 'a>) -> T {
    if n <= 1 {
        continuation(n)
    } else {
        fib_cont(n - 1, Box::new(move |a| {
            fib_cont(n - 2, Box::new(move |b| {
                continuation(a + b)
            }))
        }))
    }
}

fn main() {
    fib_cont(13, Box::new(|a| {
        println!("{}", a);
    }));
}

安定化していない理由

FnBox は以上のようによくできた仕組みだが、安定化されていない。追跡用のissueによると、これは主に次の2つの理由によるもののようだ。

「値渡しのself」に取って代わられる可能性がある。
トレイト実装の一貫性に引っかかる部分の解決ができていない。
高階トレイト境界とうまく相互作用しない。

「値渡しのself」

By-value-self (「値渡しのself」) とはまさに上で述べた FnOnce のような状況を指している。

現段階で有効な追跡issueが見当たらなかったので、現在は誰も動いていないようだが、意図されているのは次のような内容だと思われる: selfを値渡しするメソッドがあった場合は、vtableにはサイズが不明でも渡せるような別の関数へのポインタを入れておく。selfの値渡しメソッドの呼び出しが実際に発生した場合は、それがBoxの参照外しとセットだったら Sized でなくても許可するようにする。このようにして FnOnce に限らない一般のトレイトに対してもワークアラウンドなしにトレイトオブジェクトが動作するようにする。

もしこの機能が本当に計画されているのであれば、 FnBox はやがて不要になり、廃止されることになる。これが安定化されていない第一の理由である。

ただし、2015年12月の時点で、値渡しのselfまでの一時的な措置として安定化させることが決定されているため、現在はこの理由は有効ではない。

トレイト実装の一貫性

Rustでは、複数のトレイト実装が非決定的に選択可能な状況を避けるための「一貫性(coherence)」規則を採用している。これはorphan ruleとoverlapping ruleからなる。

クロージャーの実装は難しい一貫性の問題を抱えている。というのもクロージャは Fn, FnMut, FnOnce と3段階に分けて提供されているため、ラッパーに対する Fn* 実装を提供するとほぼ必ず複数の経路での実装が存在することになってしまうのである。例えば、

impl<A, F: ?Sized> Fn<A> for Box<F> where F: Fn<A> { ... } // 実装A
impl<A, F: ?Sized> FnMut<A> for Box<F> where F: FnMut<A> { ... } // 実装B
impl<A, F: ?Sized> FnOnce<A> for Box<F> where F: FnOnce<A> { ... } // 実装C

という3種類のラッパーを提供するのはごく自然である。しかし3種類全てを提供すると、一貫性の問題が発生する。例えば F: Fn<A> だとして、 Box<F>: FnOnce<A> を解決したいとする。すると以下の3種類の経路の実装が選択可能である。

F: Fn<A> と実装Aから、 Box<F>: Fn<A> が提供される。このスーパートレイトとして Box<F>: FnOnce<A> が導出される。
F: Fn<A> のスーパートレイト F: FnMut<A> と実装Bから、 Box<F>: FnMut<A> が提供される。このスーパートレイトとして Box<F>: FnOnce<A> が導出される。
F: Fn<A> のスーパートレイト F: FnOnce<A> と実装Cから、 Box<F>: FnOnce<A> が提供される。

Rustはこれらの同一性を確かめる術は今のところないから、そもそも上記の実装A,B,Cの共存を認めていない。

これは FnBox に関係なく Fn, FnMut, FnOnce, ひいてはより一般のトレイト (Into など) に広く認められている問題である。ただ FnBox も同じ問題を抱えている。というのも、

impl<'a, A> FnOnce<A> for Box<FnBox<A> + 'a> { ... }
impl<A, F: ?Sized> FnOnce<A> for Box<F> where F: FnOnce<A> { ... }

がoverlapping ruleに引っかかるからである。

これは本来overlapしないが、何かのバグでそうなっているようだ。(例えば、 A 引数を削除した例を作って実験するとコンパイルが通る。)

高階トレイト境界との相互作用

また、 FnBox は高階トレイト境界に対してうまく動作しないという問題がある。

例えば Box<FnBox(&i32)> は Box<for<'a> FnBox(&'a i32)> の構文糖衣だが、このように高階トレイト境界を含んでいる場合は FnOnce が実装されないため、クロージャを呼び出すことができない。

これは一般に、高階の生存期間束縛を含む型に対するジェネリックな実装をうまく与える手段がないことに由来する。

まとめ

FnOnce をbox化して呼び出す手段は必要性は認識されているものの、安定的な実現はまだ得られていない。どうしても今必要なら、上に挙げた問題点を把握しつつ、 std::boxed::FnBox を使うのが望ましいだろう。

簡潔なQ

FnBoxについて

`FnBox` の動機

`FnBox` の仕組み

`FnBox` の使い方

安定化していない理由

「値渡しのself」

トレイト実装の一貫性

高階トレイト境界との相互作用

まとめ

FnBox の動機

FnBox の仕組み

FnBox の使い方

安定化していない理由

「値渡しのself」

トレイト実装の一貫性

高階トレイト境界との相互作用

まとめ

`FnBox` の動機

`FnBox` の仕組み

`FnBox` の使い方