檜山正幸のキマイラ飼育記 このページをアンテナに追加 RSSフィード Twitter

キマイラ・サイトは http://www.chimaira.org/です。
トラックバック/コメントは日付を気にせずにどうぞ。
連絡は hiyama{at}chimaira{dot}org へ。
蒸し返し歓迎!
このブログの更新は、Twitterアカウント @m_hiyama で通知されます。
Follow @m_hiyama
ところで、アーカイブってけっこう便利ですよ。

2015-11-30 (月)

お手軽で実用的なジェネリックスへの道は遠い

| 09:23 | お手軽で実用的なジェネリックスへの道は遠いを含むブックマーク

TypeScriptジェネリックス:可能性が見えると不満がつのる」において、クラス定義や関数定義に型パラメータを渡せるだけでは、ジェネリック・プログラミングは難しいと述べました。そのときの例題はリストの総和だったのですが、より簡単な累乗(ベキ乗、power)計算を例にしてもう一度問題点を説明します。C++ジェネリックスについても触れ、比較してみます。

内容:

  1. TypeScriptの痒いジェネリック
  2. さすがC++、だが型パラメータ制約が書けない
  3. 帯に短しタスキに長しな現状

TypeScriptの痒いジェネリック

次は通常のTypeScriptコードです*1。特に問題なくコンパイル・実行できます。

type T = number;

function power(x: T, n: number) : T
{
    var result: T = 1;
    for (var i: number = 0; i < n; i++) {
	result *= x;
    }
    return result;
}

numberの型別名として使っていたTを型パラメータに変更すると、コンパイルできなくなります。

//type T = number;

function power<T>(x: T, n: number) : T
{
    var result: T = 1; // 定数1を、T型変数resultに代入できない
    for (var i: number = 0; i < n; i++) {
	result *= x;  // 演算子 *= は、T型変数resultとxには使えない
    }
    return result;
}

定数「1」、掛け算して代入する演算子「*=」の意味が固定されていて、一般化することができないのです。一般化しようとするなら、演算子ではなくて名前を持つメソッドにするしかありません。定数や演算子(または同等な関数)は、個々のインスタンスに存在するというより、型Tに付属するのが自然だと(僕には)思えるので、次のように書きたいところです。

function power<T>(x: T, n: number) : T
{
    var result: T = T.one;
    for (var i: number = 0; i < n; i++) {
	T.mul_accum(result, x);
    }
    return result;
}

こんな書き方は、コンパイラに全く相手にされません。定数と“掛け算して代入”演算子を、インスタンスのメソッドに持たせるならまだ脈があります。

function power<T>(x: T, n: number) : T
{
    var result: T = x.one();
    for (var i: number = 0; i < n; i++) {
	result.mul_accum(x);
    }
    return result;
}

ウーン、x.one() て気持ち悪い、ヤダなー、でもしょうがない。

このままでは、x.oneやresult.mul_accumの存在をコンパイラが認識できないので、型Tのインスタンスにoneやmul_accumというメソッドが存在することを教えてやる必要があります。one, mul_accumを持つインターフェイスを作って、型Tがそのインターフェイスの実装だと明示します(使うキーワードはimplementsじゃなくてextends)。

interface MonoidalState {
    one() : MonoidalState;
    mul_accum(x: MonoidalState) : MonoidalState;
}

function power<T extends MonoidalState>(x: T, n: number) : T
{
    var result: T = <T>x.one();
    for (var i: number = 0; i < n; i++) {
	result.mul_accum(x);
    }
    return result;
}

var result: T = <T>x.one(); の行の <T> はキャスト(TypeScriptでは型アサーションと呼ぶ)です。このキャストを付けないと、コンパイラは「T型の変数に x.one() が代入できない」と言ってエラーになります。x.one() の型がinterface MonoidalStateであるのは分かりますが、だからといって型Tそのものと互換性があるとは限らないからです。

余談になりますが、上記のような問題が出るのは、interfaceの名前と隠蔽ソート(thisのデータ型)を区別してないせいです。次のように書ければ、キャストのような回避手段は不要でしょう。

interface MonoidalState {
    this: T; // this(状態)のデータ型をTとする
    one() : T;
    mul_accum(x: T) : T;
}

最後に、ジェネリック関数powerに渡すデータを作って、実際に累乗の計算をしてみます。

class NumPair implements MonoidalState {
    fst: number;
    snd: number;

    constructor(x: number, y: number) {
	this.fst = x;
	this.snd = y;
    }

    one() : NumPair {
	return new NumPair(1, 1);
    }

    mul_accum(np: NumPair) : NumPair {
	this.fst *= np.fst;
	this.snd *= np.snd;
	return this;
    }

    toString() {
	return "(" + this.fst + ", " + this.snd + ")"
    }
}

var np = new NumPair(2.1, 2.1);
console.log("power<NumPair>(np, 3) = " + power<NumPair>(np, 3));

次のような出力になります(なんか誤差が出てます)。

power(np, 3) = (9.261000000000001, 9.261000000000001)

演算子記号をメソッド名に書き換えて、いちおう何とかなりましたが、数値(number)型には使えなくなってしまいました。これは萎える。例えば、成分が何であってもいいような行列計算のパッケージを書くとか、このレベルのジェネリックスでは辛すぎます

さすがC++、だが型パラメータ制約が書けない

同じことをC++11でやってみましょう。使ったコンパイラは、tdm-gccです。

$ alias g++
alias g++='x86_64-w64-mingw32-g++ -std=c++11'

$ g++ --version
x86_64-w64-mingw32-g++.exe (tdm64-1) 5.1.0
Copyright (C) 2015 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

スタートはこれ(↓)です。

#include <iostream>

using T = double;

T power(T x, unsigned int n) {
  T result = 1;
  for (unsigned int i = 0; i < n; i++) {
    result *= x;
  }
  return result;
}

TypeScriptの場合と同じです。型別名だったTを型パラメータにしてみます。関数本体は一字一句直さなくていい点はラクチンでいいですね。

#include <iostream>

//using T = double;
template <typename T>
T power(T x, unsigned int n) {
  T result = 1;
  for (unsigned int i = 0; i < n; i++) {
    result *= x;
  }
  return result;
}

警告もなしにコンパイルできます。「えっ、ほんとにこれでいいの?」という感じ。次のようにはからうことを想定しているのでしょう。

  1. T result = 1; は、定数1からT型のインスタンスを生成する手段があるなら、それでなんとかする。
  2. result *= x; は、T型の変数と値に対する演算子 *= が定義されているなら、それでなんとかする。

なんとかなりそうなデータを用意してあげれば、実際になんとかなります。

class NumPair {
public:
  double fst;
  double snd;

  NumPair(double x, double y) : fst(x), snd(y) {}
  NumPair(double x) : fst(x), snd(x) {}

  NumPair& operator*=(NumPair rhs) {
    fst *= rhs.fst;
    snd *= rhs.snd;
    return *this;
  }
};
std::ostream& operator<<(std::ostream &out, NumPair np) {
  return out << "(" << np.fst << ", " << np.snd << ")";
}

int main()
{
  NumPair np = 2.1;
  std::cout << "power<NumPair>(np, 3) = " << power<NumPair>(np, 3) << std::endl;
  return 0;
}

これ(↑)もTypeScriptのときと同じで、結果も同様です。

$ g++ cpp-generics.cpp

$ ./a.exe
power<NumPair>(np, 3) = (9.261, 9.261)

$

TypeScriptと決定的に違うのは、power関数は一字一句変えずにそのまま汎用化できたことです。素晴らしい。初期化の多様な解釈や演算子オーバーロードの威力です。これなら実用的に使えます。

しかし気になることもあります。power関数定義時の型Tには、定数1で初期化できること、*=演算子が在ることが要求されますが、その保証はどこにもありません。保証がない状況でもコンパイルが通るということは、楽観的あるいは性善説に基づく想定をしているわけです。TypeScriptコンパイラが未知の型Tのメソッドの存在を疑ってかかる態度とは対照的です。

一時、C++の型パラメータに関する制約を書くために、「コンセプト」と呼ばれる型クラスに似たメカニズムが提案されていたようです。コンセプトは結局見送りになって、今のC++には入っていません。

楽観的な態度も悪くはないのですが、ジェネリックな関数やクラスに渡す型パラメータに関する要件を明示的に書き下したいときもあります。安全性が増すし、意図や前提が形になりますからね。

帯に短しタスキに長しな現状

C++にコンセプト(型クラス相当機能)がないのは残念ですが、それによって実用性が極端に落ちるわけではないでしょう。一方、TypeScriptに演算子オーバーロードが欠けているのは用途によっては致命的な欠点です。そうはいっても、C++ってお手軽じゃないしなー。

最近のプログラミング言語ジェネリックス機能を持っているものが多いですが、言語の進化に伴って後から付けたものがほとんどで、最初からジェネリックスありきで設計したものって、(少なくともメジャーどころでは)ないんじゃないの*2ジェネリックスと演算子オーバーロードと型クラスを中核にしたプログラミング言語が出てきたら面白いのにね。

*1:n乗するのに掛け算をn回します。工夫すれば掛け算の数は減らせます。例えば、中間の結果を利用すれば、8乗なら3回の掛け算で済みます。

*2[追記]今回話題にしたTypeScriptは最初からジェネリックスが付いてますが、これはJavaScriptがもとで、それが進化してジェネリックスも付いた、という感じ。メイヤー先生のEiffelは最初からジェネリックスあったかな。D言語やRustもジェネリックス付き。関数型言語は型パラメータを扱えるのが多いし、Haskellの型クラスは最強そうですが、利用者は多くないでしょう。Coqの型クラスもなかなかのもんですが、利用者は(略。[/追記]

kmizushimakmizushima 2015/12/01 11:39 Scalaには演算子オーバーロードもジェネエリクスも型クラスもあります。

m-hiyamam-hiyama 2015/12/01 14:43 kmizushimaさん、
あ、Scalaか、なるほど。視界にありませんでした。今後は意識します。