読者です 読者をやめる 読者になる 読者になる

Rust で Generic な数値型を作る

ちまたで話題(?) の Rust 言語。昨年末くらいから「日本語情報が全然無い、先駆者になるチャンス!」とか思いながらのろのろしてたら、先日の0.1版発表で一気に知名度が上がってしまい(´・ω・`)としているgifnksmです。
0.1リリースでいろいろ変わりましたね。tag が enum になったり、alt で列挙型の値で分岐するときに末尾にどっと(.) をつけなくてもよくなったり。実装する予定の機能(Proposals · graydon/rust Wiki · GitHub) もまだまだたくさんあり、今後にますます期待です。
さてさて、そんなRust言語で、 Generic な整数型を作ってみました。
なぜ作ったかと言いますと、以下のようなコードを普通にコンパイルした場合、

fn add<T>(a: T, b: T) -> T { a + b }

以下のようなエラーでコンパイルが通らなくなってしまうからです。

main.rs:17:29: 17:34 error: binary operation + cannot be applied to type `'a`
main.rs:17 fn add<T>(a: T, b: T) -> T { a + b }

T型には + 演算子が定義されてねーよ!というエラーです。C++やDのTemplateとは違い、Rust は Generics によってポリモーフィズムを実現していますので、Generic 関数を呼び出した時点では無く、書いた時点で関数本体がコンパイルされ、コンパイルエラーになっているようです。
では、どうするか。Genericな数値を表すインターフェースを書いてやって、そのインターフェースに対する各数値型の実装を書いてやればよさそうです。関数を呼び出す側ではTではなくGenericな数値型を指定してやります。具体的には、以下の通り。

use std;
import std::io;

// Generic な数値型の定義
iface num<T> {
    fn val() -> T;
    fn zero() -> num<T>;
    fn add(++num<T>) -> num<T>;
    fn sub(++num<T>) -> num<T>;
}

// 実装 (uint)
impl of num<uint> for uint {
    fn val() -> uint { self }
    fn zero() -> num<uint> { 0u as (num<uint>) }
    fn add(a: num<uint>) -> num<uint> {
        (self + a.val()) as (num<uint>)
    }
    fn sub(a: num<uint>) -> num<uint> {
        (self - a.val()) as (num<uint>)
    }
}

// 実装 (int)
impl of num<int> for int {
    fn val() -> int { self }
    fn zero() -> num<int> { 0 as (num<int>) }
    fn add(a: num<int>) -> num<int> {
        (self + a.val()) as (num<int>)
    }
    fn sub(a: num<int>) -> num<int> {
        (self - a.val()) as (num<int>)
    }
}

// Generic な数値型を使った関数 (要素数が0の時は死ぬ)
fn sum<T>(vals: [num<T>]) -> num<T> {
    vec::foldl(vals[0].zero(), vals) { |s, t| s.add(t) }
}

fn main() {
    // [int] の和を求める
    std::io::println(#fmt("%d", sum(vec::map([1, 2, 3]) { |v| v as (num<int>) }).val()));
    // [uint] の和を求める
    std::io::println(#fmt("%u", sum(vec::map([1u, 2u, 3u]) { |v| v as (num<uint>) }).val()));
}

addで引数にとる数値型が自分と同じ型であることを保証するために、Tを型パラメータとしてnumに追加しています。また、num<T>型の"0"を取得する方法がわからなかったので、配列の0番目の要素に対して.zero()を呼び出すという格好悪い実装になっています(これは、ifaceが定数を持てるようになれば解決する、かも?)
上記のように、自分で実装したら不格好になりました。Language ProposalProposals for interfacesのOperator overloadingの節によれば、

iface num {
    fn +(self, self) -> self;
    fn -(self, self) -> self;
    /* etc */
}

のようなnumが組み込み型に対して定義されるようになるらしいので、ユーザー側でわざわざ不格好な定義をしなくてもよくなるかもしれません。
しかし、ユーザーが後付けで型に対する操作を追加できたり、限られたスコープでオープンクラス的に操作を追加できるあたり、Haskellの型クラスを思い出させます。後発言語なだけあって、インターフェースの仕様が洗練されてて良い感じだなー、と思います。
システムプログラミング言語、Rustの今後に期待ですね!!

2012/9/27 追記

最近の Rust では、コアライブラリにNumトレイトが標準で組み込まれています (以下は、2012/9/27 時点での incoming ブランチから持ってきた定義です)

trait Num {
    // FIXME: Trait composition. (#2616)
    pure fn add(other: &self) -> self;
    pure fn sub(other: &self) -> self;
    pure fn mul(other: &self) -> self;
    pure fn div(other: &self) -> self;
    pure fn modulo(other: &self) -> self;
    pure fn neg() -> self;

    pure fn to_int() -> int;
    static pure fn from_int(n: int) -> self;
}

こんな感じ実装&使用できます。

// bigint::add などは別途定義しておく
impl BigInt : Num {
  pure fn add(other: &BigInt) -> BigInt { bigint::add(&self, other) } 
  pure fn sub(other: &BigInt) -> BigInt { bigint::sub(&self, other) } 
  ...
  static pure fn from_int(n: int) -> BigInt { bigint::from_int(n) }
}

fn factorial(n: uint) {
  let mut prod: BigInt = from_int(1);
  for uint::range(2, n + 1) |i| {
    prod *= from_int(i); // 左辺の prod から型推論可能
  }
}

Num トレイトを実装した型については、演算子もオーバーロードされたものが使われます。Rustの演算子オーバーロードは core::opsAddトレイトなど、各演算子毎に定義されたオーバーロード用トレイトを実装するのが本来のやり方ですが、どうやらNumトレイトは特別扱いされているようです。

fn main() {
  let n: BigInt = from_int(1);
  let m = n + from_int(2);
  let k = n * m - from_int(10);
}