クロージャを boxせずに 返したい: Rustのconservative_impl_traitとimplementation leak

Rust

概要: 「クロージャを boxせずに 返したい」という欲求は人類の四大欲求のひとつと言われている。 conservative_impl_trait という機能を使うことでこれをスパッと解決できるが、これは単なる構文糖衣にとどまらずRustの型システムに食い込むこともあってかまだ安定版入りしていない。なぜこの機能が必要で、なぜこの機能が問題かを説明する。

クロージャをboxせずに返したい話

Rustではクロージャに異なる型がつく

OCamlやHaskellのような言語では、外の環境を引き継ぐ無名関数 (クロージャ) を次のように作ることができるのであった。

let mult_curry x = fun y -> x * y

この関数は x を受け取り、「y を受けとってx * yを返す関数」を返す。この「y を受けとって x * y を返す関数」は、 y というデータを引き連れている。そして、この関数には int -> int という型がつく。

今度は恒等関数を考える。これはどのようなデータも引き連れていない。この関数にも int -> int という型がつく。つまり、OCamlでは、引き連れているデータに関係なく、引数・戻り値型が同じ関数には同じ型がつくことになる。これはHaskellでも同様である。

C++やRustではそのようにはならない。作成したクロージャごとに異なる型がつく。ただし、それらの型は Fn(...) -> ... というトレイトを通じて統一的に扱える、というわけである。

ここから先の話は、クロージャに限らず一般のトレイトに関しても正しい。わかりやすさのためにクロージャを中心に説明する。

Rustでクロージャに同じ型をつける方法

クロージャに同じ型をつけるには、trait objectの概念をつかう。trait objectは仮想関数テーブルを引き連れているので、元の型がわからなくても動的に正しい関数を呼び出すことができる。

例えば、関数fを受け取り、これを2回適用する別の関数を返すには、次のように書くことができる。

fn twice(f: Box<Fn(u32) -> u32>) -> Box<Fn(u32) -> u32> {
    Box::new(move |x| f(f(x)))
}

このように書いていけば、生存期間や所有権の問題は残るが、かなりOCamlやHaskellに近い形で高階関数を書ける。ただし、trait objectはものによって大きさが異なるため、必ずポインタに包まなければならないし、動的ディスパッチになるため性能劣化が予想される。

静的ディスパッチでクロージャを受け取る

trait objectを使わずにクロージャを受け渡しする方法はあるが、引数と戻り値では方法が異なる。

クロージャを引数にする場合、次のように関数を多相にすればよい。

fn apply_twice<F: Fn(u32) -> u32>(f: F, x: u32) -> u32 {
  f(f(x))
}

こうすれば、クロージャの型に応じて、実際には別々の関数の実体を与えることができるため、呼び出し元がどのようなクロージャを用意しても正しく受け渡しができる。

静的ディスパッチでクロージャを返す

一方、クロージャを返すのは難しい。クロージャを受け取るときは、クロージャの型を決めるのは呼び出し元だから、全称型に相当する <> を使えばよかったが、クロージャを返すときは、クロージャの型を決めるのは自分自身だから、存在型に相当する機能が必要になる。

現在できる方法は、クロージャ型に名前をつけてしまうことである。例えば、先ほどの関数 twice を静的ディスパッチで実装すると次のようになる。

#![feature(unboxed_closures, fn_traits)]

struct Twice<F: Fn(u32) -> u32>(F);

impl<F: Fn(u32) -> u32> FnOnce<(u32,)> for Twice<F> {
    type Output = u32;
    extern "rust-call" fn call_once(self, args: (u32,)) -> Self::Output {
        self.call(args)
    }
}
impl<F: Fn(u32) -> u32> FnMut<(u32,)> for Twice<F> {
    extern "rust-call" fn call_mut(&mut self, args: (u32,)) -> Self::Output {
        self.call(args)
    }
}
impl<F: Fn(u32) -> u32> Fn<(u32,)> for Twice<F> {
    extern "rust-call" fn call(&self, args: (u32,)) -> Self::Output {
        self.0(self.0(args.0))
    }
}

fn twice<F: Fn(u32) -> u32>(f: F) -> Twice<F> {
    Twice(f)
}

この方法の問題点は2つある:

  • クロージャ用トレイトの内部仕様はまだ確定していないため、stableでは使えない。(この問題はクロージャ特有であり、一般のトレイトには関係ない)
  • 上のコードを見ればわかる通り、この方法で書こうとすると骨が折れる。

conservative_impl_trait はこの2つ目の問題を解決する。ついでに1つ目の問題も解決されるが、 conservative_impl_trait 自身もunstableなため現状ではこの恩恵はない。

conservative_impl_trait の利点

impl Trait と存在型

conservative_impl_trait は impl Trait とよばれる構文を提供することからこの名がついている。この構文は実質的に存在型といえる。例えば、

impl Iterator<Item=u32> == 「Iterator<Item=u32> を実装する型 T があり、その型 T」

ということになる。

この構文は2014年から提案されているようだが、このような型の扱いはかなり難しい。というのもRustでは型に関する多相性はコンパイル時に全て展開し尽くさなければならない (ただし、trait objectや Any など、動的に判定されるものは例外である) からである。

conservative_impl_trait は、この impl Trait 構文を使ってよい位置に強い制限をかけることで、あまり問題の起きない範囲内で存在型を実現しようというものである。具体的には、「関数(trait内を除く)の戻り値型の一部としてのみ、 impl Trait 構文を許容する」という制約をつける。

conservative_impl_trait を使ってクロージャを返す

実際に先ほどの例を conservative_impl_trait を使って書き換えると次のようになる。

#![feature(conservative_impl_trait)]

fn twice<F: Fn(u32) -> u32>(f: F) -> impl Fn(u32) -> u32 {
    move |x| f(f(x))
}

先ほどのとにかく骨が折れる方法に比べるとかなりスッキリしていて、 Twice<F> のような余計な型が出てこないために意味も読み取りやすくなっている。

conservative_impl_trait の仕組み

impl Trait は以下のように動作する。Rust HIRに型をつける際に、以下の処理が発生する。

  • 各 impl Trait を、その関数の生存期間・型引数全てで量化する。これは ∀x∃y を ∃f∀x に変換する処理に他ならないため、skolemizationと呼ばれる。
  • 各 impl Trait に固有のIDを割り振る。

impl Trait の実際の型は、関数の実装のコンパイルが終わった段階で確定する。これを、その impl Trait を使っている各部分に代入することで、 impl Trait が除去される。

この動作により、要するに上に挙げた3つめの twice が2つめの twice に変換される。

conservative_impl_trait の何が問題か

conservative_impl_trait の問題点は、おそらく「関数からのimplementation leak」に集約されると思われる。 conservative_impl_trait を導入すると、2種類の意味で、implementation leakが発生する。

そもそもRustの関数の型について

Rustは(おそらくコンパイル速度やコードの見通しの良さのために)、何でもは推論しない立場を取っている。とりわけこの思想が顕著なのが関数の型である。

HaskellやOCamlでは、

f x y = x + y / y

のように実装だけ書くと、関数の型が推論される。しかしRustでは、 fn で定義される関数の型は推論せず、全てを明記しなければならないようになっている。例えば、

fn f() -> _ {
  return 10u32 + 2;
}

のように書くことは許されない。

Lifetime elision、あるいはライフタイムの省略はこの制約に対する例外に見えるが、そうではない。lifetime elisionでは、lifetimeは関数宣言の型から補完されるのであり、関数の実装から推論されるわけではない。

そのため、Rustでは関数の実装を変更しても、他の部分のコンパイルには影響が及ばないようになっている。

conservative_impl_trait はこの性質を破る。このことをここではimplementation leak / 実装リークと呼ぶことにする。(一般的な用語ではない)

conservative_impl_trait による実装リークその1

その1は「同じ型宣言をもつ関数が異なる型を返す」というものである。これは impl Trait の本質であるから避けようはないし、これ自体は大きな問題にはならないと思われる。ただし、以下のような現象が発生する。

#![feature(conservative_impl_trait)]

fn f1() -> impl FnMut(u32) -> u32 {
    |x| x
}
fn f2() -> impl FnMut(u32) -> u32 {
    let mut y = 0;
    move |x| std::mem::replace(&mut y, x)
}

fn main() {
    let cl1 = f1();
    let cl2 = f2();
    println!("{}", std::mem::size_of_val(&cl1));
    println!("{}", std::mem::size_of_val(&cl2));
}

0
4

このように、 f1 と f2 は同じ型宣言を持つが、異なる大きさの値を返す。

conservative_impl_trait による実装リークその2

上記のように impl Trait は関数ごとに異なる型を割り当てるが、それ自体はあまり問題にはならない。その型についてわかっている情報が「 Trait を実装していること」に限定されているからである。

ところが、実際には impl Trait は Trait 以外のトレイトを実装することがある。まず何も言わなければ Sized が自動的に仮定される。これはそれほど問題にはならない。

もう1つの問題は、 Send や Sync が自動的に実装されることである。そしてこれは何と、関数の実装に依存して決まる。

以下がその例である。 Rc と Arc を impl AsRef で抽象化して返す2つの関数がある。型宣言は同じだが、片方は g に渡せるのに対しもう一方は g に渡すことができない。

#![feature(conservative_impl_trait)]

use std::rc::Rc;
use std::sync::Arc;
use std::convert::AsRef;

fn f1() -> impl AsRef<u32> {
    Rc::new(0)
}
fn f2() -> impl AsRef<u32> {
    Arc::new(0)
}

fn g<T:Send>(t: T) {}

fn main() {
    // g(f1()); // compile error
    g(f2());
}

まとめ

conservative_impl_trait は現在のRustに必須のデザインパターンを補う非常に有用な機能であると同時に、重要なabstraction boundaryのひとつを壊すという懸念がある。