Rustで型の多相再帰はできない

OCamlHaskellに比べると、Rustは多相再帰ができない場合がほとんどである。以下にその詳細を説明する。

多相再帰

異なる型引数による再帰呼び出しを多相再帰 (polymorphic recursion) という。多相再帰はPurely Functinoal Data Structuresで紹介されているようなデータ構造でよく出てくる。例えば、完全二分木はOCamlHaskellではそれぞれ以下のように書ける。

type 'a sep = Nil | Cons of ('a * 'a) sep
data Sep a = Nil | Cons (Sep (a, a))

これがlistの定義と異なることがわかるだろうか。listでは 'a list の定義に 'a list という形の型のみを用いる。ここでは 'a sep の定義に ('a * 'a) sep を用いている。これが多相再帰である。

Rustにおける型の多相再帰

同じものをRustで書こうとすると次のようになる。

enum Sep<T> {
    Nil,
    Cons(T, Box<Sep<(T, T)>>),
}

fn main() {
    let x = Sep::Nil::<u32>;
}

しかしこれはコンパイルが通らない。例えばコンパイラが無限ループに陥りkillされる。

再帰型だけではなく再帰関数についても同じことが起こる。以下のコードはやはり再帰制限に引っかかる。

fn f<T>(n: u32, x: T) {
    if n > 0 {
        f::<Option<T>>(n-1, Some(x));
    }
}

fn main() {
    f(1, true);
}

多相再帰ができない理由

OCamlHaskellはパラメーター多相性を実行時に解決している(ジェネリックス)のに対し、Rustはパラメーター多相性をコンパイル時に解決する(テンプレート)。

上の例では、 Sep<u32> ができたことにより、Rustは Sep<u32> のための専用のコードを生成しようとする。ところが、この型は内部に Sep<(u32, u32)> を持ちうるため、これに関係するコードの生成が必要になる。さらにその内部では Sep<((u32, u32), (u32, u32))> が必要になる。この繰り返しになってしまうためコンパイルができない。

OCamlHaskellなら、 int sep 専用ではなく 'a sep 用の汎用のコードを生成して終わりなので、特に困ることはない。

幽霊型も使用不可能

OCamlHaskellの内部表現を真似て、 TBox にくるんでもコンパイルエラーはなくならない。

enum Sep<T> {
    Nil,
    Cons(Box<T>, Box<Sep<(T, T)>>),
}

fn main() {
    let x = Sep::Nil::<u32>;
}

完全に型情報を捨てて Any にしてしまえば、もちろんコンパイルは通る。

use std::any::Any;

enum Sep {
    Nil,
    Cons(Box<Any>, Box<Sep>),
}

fn main() {
    let x = Sep::Nil::<u32>;
}

これだと心許ないので、幽霊型をつけてみると、コンパイルは失敗する。

struct BoxAny<T> {
    val: Box<std::any::Any>,
    _phantom: std::marker::PhantomData<T>,
}

enum Sep<T> {
    Nil,
    Cons(BoxAny<T>, BoxAny<Sep<(T, T)>>),
}

fn main() {
    let x = Sep::Nil::<u32>;
}

結局、幽霊型の場合も、幽霊型引数の違いごとに別々にコード生成をしなくてはならないため、無限コード生成を回避することはできない。

多相再帰自体が禁止されているわけではない

実際は、多相再帰自体は禁止されているわけではない。無限にたくさんの型が発生しない限りは、多相再帰があっても問題ない。

人工的な例だが、次のようなプログラムは動作する。

use std::marker::PhantomData;

struct Z;
struct S<X>(PhantomData<X>);

trait Nat {
    type Pred : Nat;
    fn to_u32() -> u32;
}

impl Nat for Z {
    type Pred = Z;
    fn to_u32() -> u32 { 0 }
}
impl<X:Nat> Nat for S<X> {
    type Pred = X;
    fn to_u32() -> u32 { X::to_u32() + 1 }
}

fn f<X:Nat>() -> u32 {
    if(X::to_u32() == 0) {
        1
    } else {
        f::<X::Pred>() * 2
    }
}

fn main() {
    println!("{}", f::<S<S<S<Z>>>>());
}

ここで f<S<S<S<Z>>>> を生成しようとすると f<S<S<Z>>> が必要になる。これにはさらに f<S<Z>> が必要になる。さらに f<Z> が必要になる。しかし Z::PredZ だから、これ以上必要なものはない。

生存期間に関する多相再帰は可能

ここまでで言及したのは、型に関する多相再帰である。生存期間は型とは異なり、コンパイル時には型消去されるだけなので、実行時に無限に多くの生存期間が生じうることに全く問題はない。

むしろ、普通にRustコードを書いていると、生存期間に関する多相再帰が発生していると考えてよいだろう。例えば、

enum List<X> {
    Nil,
    Cons(X, Box<List<X>>),
}

fn length<'a, X>(list: &'a List<X>) -> u32 {
    match list {
        &List::Nil => 0,
        &List::Cons(_, ref tail) => length(tail) + 1,
    }
}

fn main() {}

において、 listtail の生存期間は明らかに異なる。

まとめ

  • Rustでは、多相再帰そのものが禁止されているわけではない。
  • 生存期間に関する多相再帰は全く問題がないどころか、頻繁に使われている。
  • 型に関する多相再帰の多くは、無限に多くの型を生成してしまうために、失敗する。
  • 幽霊型でも同じ問題が起きる。