Rustで型の多相再帰はできない
OCamlやHaskellに比べると、Rustは多相再帰ができない場合がほとんどである。以下にその詳細を説明する。
多相再帰
異なる型引数による再帰呼び出しを多相再帰 (polymorphic recursion) という。多相再帰はPurely Functinoal Data Structuresで紹介されているようなデータ構造でよく出てくる。例えば、完全二分木はOCamlとHaskellではそれぞれ以下のように書ける。
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); }
多相再帰ができない理由
OCamlやHaskellはパラメーター多相性を実行時に解決している(ジェネリックス)のに対し、Rustはパラメーター多相性をコンパイル時に解決する(テンプレート)。
上の例では、 Sep<u32>
ができたことにより、Rustは Sep<u32>
のための専用のコードを生成しようとする。ところが、この型は内部に Sep<(u32, u32)>
を持ちうるため、これに関係するコードの生成が必要になる。さらにその内部では Sep<((u32, u32), (u32, u32))>
が必要になる。この繰り返しになってしまうためコンパイルができない。
OCamlやHaskellなら、 int sep
専用ではなく 'a sep
用の汎用のコードを生成して終わりなので、特に困ることはない。
幽霊型も使用不可能
OCamlやHaskellの内部表現を真似て、 T
を Box
にくるんでもコンパイルエラーはなくならない。
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::Pred
は Z
だから、これ以上必要なものはない。
生存期間に関する多相再帰は可能
ここまでで言及したのは、型に関する多相再帰である。生存期間は型とは異なり、コンパイル時には型消去されるだけなので、実行時に無限に多くの生存期間が生じうることに全く問題はない。
むしろ、普通に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() {}
において、 list
と tail
の生存期間は明らかに異なる。