ジェネリックプログラミング

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

ジェネリック(総称あるいは汎用)プログラミング (generic programming)はデータ形式に依存しないコンピュータプログラミング方式である。

概要[編集]

ジェネリックプログラミングはデータ型でコードをインスタンス化するのか、あるいはデータ型をパラメータとして渡すかということにかかわらず、同じソースコードを利用できる[1]。ジェネリックプログラミングは言語により異なる形で実装されている。ジェネリックプログラミングの機能は70年代にCLUAdaのような言語に搭載され、次にBETAC++DEiffelJava、その後DECTrellis/Owl言語などの数多くのオブジェクトベース(object-based)およびオブジェクト指向(object-oriented)言語に採用された。

1995年の書籍デザインパターンの共著者は(Ada、Eiffel、Java、C#の)ジェネリクスや、(C++の)テンプレートとしても知られるパラメータ化された型(parameterized types)としてジェネリクスについて触れている。これらは、型を指定することなく、型を定義できるようにする(型は使用する時点で引数として与えられる)。このテクニック(特にデリゲーションを組み合わせるとき)は非常に強力であるが、同時に「動的に、高度にパラメーター化されたソフトウェアはより静的なソフトウェアよりも理解しづらい」とその著者は忠告している(Gang of Four 1995:21)。

特徴[編集]

オブジェクトのコンテナを作成する際は、たとえデータ形式が異なるだけで事実上同一のコードであったとしても、データ形式毎にそれぞれ実装するのが一般的である。ジェネリックプログラミングによりC++で言うところのテンプレートクラスを定義できることがジェネリックプログラミングの利点の一例として挙げられる。

template<typename T> 
class List 
{ 
   /* クラスの中身 */
};
 
List<Animal> list_of_animals;
List<Car> list_of_cars;

上記のTはインスタンス化する型を表す。そしてこの定義によって生成する型は指定した型Tのリストとして扱われる。これらの「T型のコンテナ」を一般にジェネリクス (generics)と呼び、ジェネリックプログラミングの代表的なテクニックである。このテクニックは、サブタイプやシグネチャといった契約を維持する限り、異なるデータ型を含めたクラスの定義を可能にする(サブクラスでアルゴリズムをオーバーライドする多態と混同しないこと)。上記はジェネリックプログラミングの典型であり、一部の言語ではこの形式のみを実装するが、コンセプトとしてのジェネリックプログラミングはジェネリクスに限定されない。ジェネリックプログラミングのもう一つの応用例として、型に依存しないスワップ関数の例を示す。

template<typename T>
void Swap(T & a, T & b) //"&"により参照としてパラメーターを渡している。
{
   T temp = b;
   b = a;
   a = temp;
}
 
string hello = "world!", world = "Hello, ";
Swap( world, hello );
cout << hello << world << endl; //出力は"Hello, world!"

上記の例で使用したC++のtemplate文は、プログラマーや言語の開発者たちにこの概念を普及させたジェネリックプログラミングの例といわれている。この構文はジェネリックプログラミングの全ての概念をサポートする。またD言語はC++のテンプレートをベースに構文を単純化した完全なジェネリックの機能を提供する。JavaはJ2SE 5.0よりC++の文法に近いジェネリックプログラミングの機能を提供しており、ジェネリックス(「T型のコンテナ」)という、ジェネリックプログラミングのサブセットを実装する。

C# 2.0、Chrome 1.5Visual Basic .NET 2005は、Microsoft .NET Framework 2.0がサポートするジェネリクスを利用するための構文が追加された。MLファミリーはパラメトリックな多態 (parametric polymorphism)とファンクタと呼ばれるジェネリックモジュールを利用してのジェネリックプログラミングを推奨する。Haskellのタイプクラスのメカニズムもまたジェネリックプログラミングをサポートする。

Objective-Cにあるような動的型付けを使い、必要に応じて注意深くコーディング規約を守れば、ジェネリックプログラミングのテクニックを使う必要がなくなる。全てのオブジェクトを包括する汎用型があるためである。Javaもまたそうであるが、キャストが必要なので静的な型付けの統一性を乱してしまう。それに対し、ジェネリクスは静的な型付けについての利点を持ちながら動的な型付けの利点を完全ではないが得られる唯一の方法である。

Adaのジェネリクス[編集]

Adaには1977年~1980年の設計当初から汎用体 (generics)が存在する。標準ライブラリでも多くのサービスを実装するために汎用体を用いている。Ada2005では1998年に規格化されたC++のStandard Template Library(STL)の影響を受けた広範な汎用コンテナが標準ライブラリとして追加された。

汎用体 (generic unit)とは、0または複数の汎用体仮パラメータ(generic formal parameters)を採るプログラム単位(パッケージまたは副プログラム)である。

汎用体仮パラメータとしては、オブジェクト(変数・定数)、データ型、副プログラム、パッケージ,さらには他の汎用体のインスタンスさえ指定することができる。汎用体仮パラメータのデータ型としては、離散 (dicscrete)型、浮動小数点数型、固定小数点数型、アクセス(ポインタ)型などを用いることができる。

汎用体をインスタンス化する際、プログラマは全ての仮パラメータに対応する実パラメータを指定する必要があるが、プログラマが明示的に全ての実パラメータを指定しなくても済むよう,仮パラメータにはデフォルトを指定することもできる。インスタンス化してしまえば,汎用体のインスタンスは、汎用体ではない通常のプログラム単位であるかのように振舞う。インスタンス化は実行時、例えばループの中などで行うことも可能である。

Adaの例[編集]

汎用体パッケージの仕様部

generic
   Max_Size : Natural; -- 汎用体仮オブジェクトの例
   type Element_Type is private; -- 汎用体仮データ型の例;  この例では制限型でなければ任意のデータ型が該当
package Stacks is
   type Size_Type is range 0 .. Max_Size;
   type Stack is limited private;
   procedure Create (S : out Stack;
                     Initial_Size : in Size_Type := Max_Size);
   procedure Push (Into : in out Stack; Element : in Element_Type);
   procedure Pop (From : in out Stack; Element : out Element_Type);
   Overflow : exception;
   Underflow : exception;
private
   subtype Index_Type is Size_Type range 1 .. Max_Size;
   type Vector is array (Index_Type range <>) of Element_Type;
   type Stack (Allocated_Size : Size_Type := 0) is record
      Top : Index_Type;
      Storage : Vector (1 .. Allocated_Size);
   end record;
end Stacks;

汎用体パッケージのインスタンス化

type Bookmark_Type is new Natural;
-- 編集中のテキストドキュメント内の場所を記録する
 
package Bookmark_Stacks is new Stacks (Max_Size => 20,
                                       Element_Type => Bookmark_Type);
-- ドキュメント中の記録された場所にユーザがジャンプできるようにする

汎用体パッケージインスタンスの利用

type Document_Type is record
   Contents : Ada.Strings.Unbounded.Unbounded_String;
   Bookmarks : Bookmark_Stacks.Stack;
end record;
 
procedure Edit (Document_Name : in String) is
   Document : Document_Type;
begin
   -- ブックマークのスタックを初期化
   Bookmark_Stacks.Create (S => Document.Bookmarks, Initial_Size => 10);
   -- この時点でDocument_Nameファイルを開いたり、読み込んだりが可能
end Edit;

利点と制限[編集]

Adaの言語構文では、汎用体仮パラメータとして何を許容するか、精密に制約条件を課することができる。例えば実パラメータとしてはモジュラー型(任意の上限で巡回する符号なし整数型)のみを許容するように,仮パラメータとして指定することも可能である。さらには汎用体仮パラメータ間に一定の制約があるように規制することも可能である。例えば、

generic
   type Index_Type is (<>); -- 離散型(discrete type)のみを許容
   type Element_Type is private; -- 制限型(limited type)以外の任意データ型
   type Array_Type is array (Index_Type range <>) of Element_Type;

この例でArray_Typeには、Element_Typeに対応する特定のデータ型を要素とし、Index_Typeに対応する特定の離散型の部分型を添字とする配列型でなければならないという制約を課している。プログラマがこの汎用体をインスタンス化する際には、同制約を満足する配列型を実パラメタとして渡さなければならない。

構文の複雑さに難はあるものの、精密な制約が表現できることで、汎用体仮パラメータの全ては仕様部として完全に定義される。このため、コンパイラは汎用体本体がなくても汎用体をインスタンス化することができる(もちろん本体がないとリンクはできない)。

C++と異なってAdaでは暗黙的な特化による汎用体のインスタンス化を許さないため、全ての汎用体は明示的にインスタンス化することが必要である。この規則により以下のような結果が生じる。

  • コンパイラは共有ジェネリクス (shared generics)を実装できる。すなわち、ある汎用体のオブジェクトコードは全インスタンスで共有できる(もちろんプログラマが副プログラムのインライン化を要求しない限り)。さらなる結果として、
    • コードが肥大化する可能性がない(コードの肥大化はC++では一般的であり後述のように特別な配慮が求められる)。
    • インスタンス化の都度に新たなオブジェクトコードを生成することは不要であるため、コンパイル時のみならず、実行時に汎用体をインスタンス化することができる。
    • 汎用体仮オブジェクトに対応する実オブジェクトは、たとえ同実オブジェクトが静的である(コンパイル時に値が確定する)としても、汎用体本体中では常に静的ではないものとみなされる。詳細についてはWikibookのGeneric formal objectsを参照。
  • ある汎用体の全インスタンスは全く同一であるため、他人の作成したプログラムをレビューしたり、理解することが容易である。配慮すべき「特別な場合」はないのだから。
  • 全てのインスタンス化は明示的であり、プログラムの理解が困難となるような暗黙的なインスタンス化はない。
  • Adaでは特化を許容しないためテンプレートメタプログラミングはできない。
    ただし仮パラメータに精密な制約を課することができるため、例えば、スワップ副プログラムを仮パラメータとして、ソートを目的とした汎用体の挙動をスワップ対象に応じて変化させたり、離散型の規定演算である大小判定を用いてMaxを実装するなど、特化の利点とされる目的の一部は他の方法により達成することができる。

C++のテンプレート[編集]

テンプレートは特に多重継承演算子多重定義を組み合わせた場合にパワフルである。C++のStandard Template Library (STL)はテンプレートで作られたフレームワークを提供する。

C++のテンプレートはまた、実行時ではなくコンパイル時にコードの一部を事前評価する方法であるテンプレートメタプログラミングにも利用できる。C++のテンプレートはチューリング完全である。ただし、コンパイラによる制限があり、少なくとも規格上では再帰の深さは16段階までしか保障されていない。再帰の制限が無ければコンパイル処理が永遠に終了しないコードを記述することができ、それをコードから判断することはコンパイラには不可能だからである。(停止性問題を参照)

技術概要[編集]

関数テンプレートとクラステンプレートの2種類のテンプレートがある。関数テンプレートは普通の関数のように動作するが、型に依存することなく多様な引数を受け入れられる。例えば、C++ STLには、xyのどちらか大きいほうを返すmax(x, y)の関数テンプレートがある。max()はこのように実装できるだろう。

template <typename T>
T max(T x, T y)
{
    if (x < y)
        return y;
    else
        return x;
}

このテンプレートは関数のように呼び出せる。

cout << max(3, 7);   // 7を出力

コンパイラは引数を評価してこれが max(int, int) の呼び出しであることを決定し、型Tint である関数のバージョンをインスタンス化する。

引数xyが整数や文字列、あるいは"x < y"と表現することに意味のあるそれ以外の型(正確に言えばoperator<を指定するあらゆる型)のとき、これは機能する。これは利用可能な型のセットに何らかの共通の継承がある必要がなく、これは実際には静的なダック・タイピング(duck typing)である。もしプログラムがカスタムデータ型を定義するならば、max()で利用可能にするために必要なことはその型の<の意味を定義するために演算子を多重定義するということだけである。この例だけでは小さな利点にしか見えないかもしれないが、STLのような総合ライブラリの中では、わずかな演算子を定義するだけで新しいデータ型に対して幅広い機能を得られるのだ。単純に<を定義することだけで、標準のsort()stable_sort()binary_search()といったアルゴリズムを型に利用でき、またsetやヒープや連想配列等々の内部データ構造に利用できる。

C++のテンプレートは完全にコンパイル時点でタイプセーフである。例えば、複素数には狭義の順序 (strict order) がないので標準形式のcomplex<演算子を定義しない。従ってmax(x, y)関数にxyとしてcomplex型を指定した場合、コンパイルエラーとなる。同様に、<をあてにする他のテンプレートはcomplexデータに適用できない。ただ、コンパイラは歴史的にやや難解で役に立たないエラーメッセージをこの種のエラーに対して生成する。目的によっては手法とコーディング規約にこだわることでこの問題を軽減できるかもしれない。

2つ目のテンプレートの種類であるクラステンプレートは同じコンセプトをクラスに拡張する。クラステンプレートはよくジェネリックコンテナを作るのに利用される。例えば、STLには連結リストコンテナがある。整数の連結リストを作るためにはlist<int>と書く。文字列のリストはlist<string>である。listはたとえどんな型が<>の間に指定されても動作する共通の関数セットを持っている。

テンプレートの特殊化[編集]

テンプレートの特殊化 (template specialization)はC++のテンプレートの強力な機能だ。インスタンス化されるであろうパラメーター化された型(parameterized type)に特化した特徴を備えた新しい実装ができる。テンプレートの特殊化は、特定の形式に最適化できるようにすることと、コード肥大化の削減に役立てるという2つの目的がある。

例としてsort()テンプレート関数について考える。このような関数の動作は第一にコンテナの特定位置の2つの値を入れ替えまたは交換することだ。値が多い場合(各要素を格納するためにメモリを消費するという点で)、オブジェクトへのポインタのリストを先に構築し、それらのポインタをソートして、最終的なソートされたシーケンスを構築するのが多くの場合で高速だ。値が非常に少なければ単純に必要に応じて値をスワップで置き換えるのが通常は最も速い。しかしさらにパラメーター化された型がポインター型である場合はポインタの配列を構築する必要がない。テンプレートの特殊化はテンプレートの作者に複数の異なる実装を記述できるようにし、パラメーター化された型が各実装で利用されるべき特徴を指定できるようにする。

長所と短所[編集]

max()関数のようなテンプレートのユーザーの一部は(古いC言語の)関数形式のプリプロセッサマクロを活用していた。例えば次のようなmax()マクロがある。

#define max(a, b) ((a) < (b) ? (b) : (a))

これら2つのマクロとテンプレートはコンパイル時間を長くする。マクロは常にインラインとして展開される。テンプレートもコンパイラが適切と判断すればインライン関数として展開される。従って、関数形式のマクロと関数テンプレートは共に実行時のオーバーヘッドがない。

しかしテンプレートは次のような目的でマクロより重要であると一般的に考えられている。まずテンプレートはタイプセーフである。そしてテンプレートは関数形式のマクロを濫用したコードにある一般的なエラーの一部を回避する。恐らく最も重要なのは、テンプレートはマクロよりも大きなコードに対して効果があるようにするために設計されたということだ。

テンプレートには主に3つの欠点がある。コンパイラのサポート、貧弱なエラーメッセージ、コードの肥大化だ。

歴史的に多くのコンパイラがテンプレートについて非常に貧弱なサポートしかなく、そのためテンプレートを使うことで移植性を損なった。C++について考慮していないリンカを利用するとき、あるいは共有ライブラリの境界を越えてテンプレートを使おうとしたときも十分な対応がなされていなかった。今ではかなりしっかりしており、標準テンプレートをサポートし、また、新しいC++の標準であるC++0xはこれらの問題をさらに解決していることが期待されている。

ほとんど全てのコンパイラは、テンプレートを使ったコードにエラーを検出したときに、混乱した、長い、そして役に立たないエラーメッセージを出力する。これはテンプレートを使った開発を難しくしている。

テンプレートの使用はコンパイラが余分なコード(テンプレートのインスタンス化)を生成する原因となりうるので、見境なくテンプレートを利用すると過剰に大きな実行ファイルを出力してしまう。しかしながら一部のケースでは、うまくテンプレートの特殊化を利用することで、そのようなコードの肥大化を劇的に減らすことができる。またテンプレートによって生じる余分なインスタンス化はデバッガが素直にテンプレートを扱うことを困難にする原因ともなりうる。例えばソースコードのテンプレートの中にブレークポイントをセットする場合、実際のインスタンスの中の望ましい場所にセットすることに失敗するかもしれないし、そのテンプレートによってインスタンス化された全ての場所にブレークポイントを設置しなければならないかもしれない。

D言語のテンプレート[編集]

D言語はC++のものを発展させたテンプレートをサポートする。大半のC++テンプレートの表現はD言語でもそのまま利用できる。それに加え、D言語は一部の一般的なケースを合理化する機能をいくつか追加する。

最もはっきりとした違いは一部のシンタックスの変更である。D言語はテンプレートの定義で山形カッコ< >の代わりに丸カッコ( )を使用する。またテンプレートのインスタンス化でも山形カッコの代わりに!( )構文(感嘆符を前に付けた丸カッコ)を使う。従って、D言語のa!(b)はC++のa<b>と等価である。この変更は、テンプレート構文の構文解析を容易にするためになされた(山形カッコは比較演算子との区別がつきにくく、構文解析器が複雑化しがちであった)。

Static-if[編集]

D言語はコンパイル時に条件をチェックするstatic if構文を提供する。これはC++の#if#endifのプリプロセッサマクロに少し似ている。static ifはテンプレート引数や、それらを使用したコンパイル時関数実行の結果を含めた全てのコンパイル時の値にアクセスできるというのがその主要な違いである。従ってC++でテンプレートの特殊化を必要とする多くの状況でも、D言語では特殊化の必要なく容易に書ける。D言語の再帰テンプレートは通常の実行時再帰とほぼ同じように書ける。これは典型的なコンパイル時の関数テンプレートに見られる。

template Factorial(ulong n) {
    static if (n <= 1)
        const Factorial = 1u;
    else
        const Factorial = n * Factorial!(n - 1);
}

エイリアスパラメーター[編集]

D言語のテンプレートはまたエイリアスパラメーターを受け入れることができる。エイリアスパラメーターはC++のtypedefと似ているが、テンプレートパラメーターを置き換えることもできる。これは今後利用可能なC++0x仕様に追加されるであろう、C++のテンプレートのテンプレート引数にある機能の拡張版である。エイリアスパラメーターは、テンプレート、関数、型、その他のコンパイル時のシンボルを指定できる。これは例えばテンプレート関数の中に関数をプログラマーが挿入できるようにする。

template wrapper(alias Fn) {
    // "extern(C)"インターフェイスでD言語の関数をラップする
    extern(C) void wrapper() {
        Fn();
    }
}

この種のテンプレートはC言語APIとD言語のコードを接続するときに使いやすいだろう。仮想のC言語APIが関数ポインタを要求する場合、このようにテンプレートを利用できる。

void foo() {
    // ...
}
 
some_c_function(&wrapper!(foo));

Javaのジェネリクス[編集]

2004年、J2SE5.0の一部としてJavaにジェネリクスが追加された。C++のテンプレートとは違い、Javaコードのジェネリクスはジェネリッククラスの1つのコンパイルされたバージョンだけを生成する。ジェネリックJavaクラスは型パラメータとしてオブジェクト型だけを利用できる(基本型は許されない)。従ってList<Integer>は正しいのに対してList<int>は正しくない。

Javaではジェネリクスはコンパイル時に型の正しさをチェックする。そしてジェネリック型情報は型削除(type erasure)と呼ばれるプロセスを通じて除去され、親クラスの型情報だけが保持される。例えば、List<Integer>は全てのオブジェクトを保有できる非ジェネリックの(生の)Listに変換されるだろう。しかしながら、コンパイル時のチェックにより、コードが未チェックのコンパイルエラーを生成しない限り、型が正しいようにコードの出力が保証される。

このプロセスの典型的な副作用はジェネリック型の情報を実行時に参照できないことだ。従って、実行時には、List<Integer>List<String>が同じListクラスであることを示す。この副作用を緩和するひとつの方法はCollectionの宣言を修飾するJavaのCollections.checkedList(List<E>,Class<E>)メソッドを利用して、実行時に型付けされたCollectionの不正利用(例えば不適切な型の挿入)をチェックすることによるものである。これは旧式のコードとジェネリクスを利用するコードを共存運用したい場合の状況で役立つ。

C++やC#のように、Javaはネストされたジェネリック型ができる。従ってList<Map<Integer, String>>は有効な型だ。

ワイルドカード[編集]

Javaのジェネリック型パラメーターは特定のクラスに制限されない。与えられたジェネリックオブジェクトが持っているかもしれないパラメーターの型の境界を指定するためにJavaではワイルドカードを使用できる。例えば、List<?>は無名のオブジェクト型を持つリストを表す。引数としてlistを取るようなメソッドは任意の型のリストを取ることができる。リストからの読み出しはObject型のオブジェクトを返し、そしてnullではない要素をリストへ書き込むことはパラメーター型が任意ではないために許されない。

ジェネリック要素の制約を指定するために、ジェネリック型が境界クラスのサブクラス(クラスの拡張とインターフェイスの実装のいずれか)であることを示すキーワードextendsを使用できる。そしてList<? extends Number>は与えられたリストがNumberクラスを拡張するオブジェクトを保持することを意味する。従って、リストが何の要素の型を保持しているのかがわからないためにnullではない要素の書き込みが許されないのに対し、リストから要素を読むとNumberが返るだろう。

ジェネリック要素の下限を指定するために、ジェネリック型が境界クラスのスーパークラスであることを示すキーワードsuperが使用される。そしてList<? super Number>List<Number>List<Object>でありえる。リストに正しい型を保存することが保障されるため任意のNumber型の要素をリストに追加できるのに対し、リストから読み出しではObject型のオブジェクトを返す。

制約[編集]

Javaのジェネリクスの実装上の制約により、配列のコンポーネントの型が何であるべきかを特定する方法がないために、ジェネリック型の配列を作成することは不可能である。従ってnew T[size];経由のようにメソッドが型引数Tを持っていた場合はプログラマはその型の新しい配列を生成することが出来ない。(この制約はJavaのリフレクションのメカニズムを利用して回避することが可能だ。クラスTのインスタンスが利用可能な場合、Tに対応するClassオブジェクトのオブジェクトから1つを得て、新しい配列を生成するためにjava.lang.reflect.Array.newInstance(Class,int)を使うことができる。) もう1つのJavaのジェネリクスの実装上の制約は、 <?>以外に、型パラメーターの型でジェネリッククラスの配列を生成することが不可能であるということだ。これは言語の配列の取り扱い方法に起因するものであり、明示的にキャストしなくともコンパイラが警告を出さないことを全てのコードで保障する必要がタイプセーフを維持するためにあるからである。

Haskellのジェネリックプログラミング[編集]

Haskell言語にはパラメータ化された型(parameterized types)、パラメータ的多態(parametric polymorphism)、そしてJavaのジェネリクスやC++のテンプレートの両方に似たプログラミングのスタイルをサポートする型クラス(type classes)がある。Haskellプログラムではこれらの構文を様々なところで利用しており、避けることはかなり難しい。Haskellはまた、さらなるジェネリック性と、多態が提供する以上の再利用性を目指すようにプログラマーと言語開発者を奮起させる、さらに独特なジェネリックプログラミングの機能がある。

Haskellの6つの事前定義された型クラス(同一性を比較できるEqという型と、値を文字列に変換できるShowという型を含む)は導出インスタンス(derived instances)をサポートしている特別なプロパティを持つ。プログラマーが新しい型を定義するということは、クラスのインスタンスを宣言するときに、普通であれば必要なクラスメソッドの実装を提供することなく、この型がこれらの特別型クラスのインスタンスとなることを明示できるということである。全ての必要なメソッドは型の構造に基づいて導出(つまり自動的に生成)される。

例として、下記の2分木型の宣言はこれがEqShowのクラスのインスタンスになることを示している。

data BinTree a = Leaf a | Node (BinTree a) a (Bintree a)
      deriving (Eq, Show)

Tがそれらの演算子を自分でサポートしているのであれば、任意の型のBinTree T形式のために比較関数(==)と文字列表現関数(show)が自動的に定義される。

EqShowの導出インスタンスへのサポートは、それらのメソッドである==showを、パラメーター的な多態関数とは質的に異なるジェネリックにする。これらの"関数"(より正確には型でインデックス付けられた(type-indexed)関数のファミリー)はたくさんの異なる型の値を受け入れることができ、各引数の型によってそれらは異なる動作をするが、新しい型へのサポートを追加するためにわずかな作業が必要とされる。Ralf Hinze氏(2004)は、あるプログラミングテクニックによりユーザー定義型のクラスに対して同様の結果を達成できることを示した。彼以外の多くの研究者はこれと、Haskellの流れとは違う種類のジェネリック性やHaskellの拡張(下記参照)に対する取り組みを提案していた。

PolyP[編集]

PolyPはHaskellに対する最初のジェネリックプログラミング言語拡張であった。PolyPではジェネリック関数はpolytypicと呼ばれた。通常データ型のパターンファンクタの構造によって構造的な導出を通じて定義できるpolytypic関数のような特別な構文を言語に導入した。PolyPでの通常データ型はHaskellのデータ型のサブセットである。通常データ型tは* → *の種類でなければならず、もしaが定義における表面的な型の引数である場合は、tに対する全ての再帰呼び出しはt a形式でなければならない。これらの制約は、異なる形式の再帰呼び出しである入れ子のデータタイプと同様に、上位に種類付けされたデータ型を規定する。

PolyPの展開された関数はここに例として示される。

   flatten :: Regular d => d a -> [a]
   flatten = cata fl
   
   polytypic fl :: f a [a] -> [a]
     case f of
       g+h -> either fl fl
       g*h -> \(x,y) -> fl x ++ fl y
       () -> \x -> []
       Par -> \x -> [x]
       Rec -> \x -> x
       d@g -> concat . flatten . pmap fl
       Con t -> \x -> []
   
   cata :: Regular d => (FunctorOf d a b -> b) -> d a -> b

ジェネリックHaskell[編集]

ジェネリックHaskellはユトレヒト大学で開発されたHaskellのもう1つの拡張だ。この拡張は下記の特徴がある。

  • Type-indexed valuesは様々なHaskell型のコンストラクタ(ユニット、基本型、合計、積、ユーザー定義型のコンストラクタ)に渡ってインデックス付けられた値として定義される。さらにコンストラクタケースを使って特定のコンストラクタに対してtype-indexed valuesの動作を指定することもでき、デフォルトケースを使ったもう一つの中で1つのジェネリック定義を再利用することもできる。

type-indexed valueの結果は任意の型に特殊化され得る。

  • Kind-indexed types*k → kの両方のケースを与えることで定義された種別に対してインデックス付けられた型である。インスタンスは種別にkind-indexed typeを適用することで得られる。
  • ジェネリック定義は型もしくは種別にそれらを適用することで利用できる。これはジェネリックアプリケーションと呼ばれる。どの種類のジェネリック定義が適用されたかに依存して結果は型か値になる。
  • Generic abstractionはジェネリック定義が(与えられた種別の)型パラメーターの抽象化で定義されることを可能にする。
  • Type-indexed typesは型コンストラクタに対してインデックス付けられた型である。これらは型がもっとジェネリック値に取り入るために利用できる。type-indexed typesの結果は任意の型に特殊化され得る。

ジェネリックHaskellの比較関数の一例として。

   type Eq {[ * ]} t1 t2 = t1 -> t2 -> Bool
   type Eq {[ k -> l ]} t1 t2 = forall u1 u2. Eq {[ k ]} u1 u2 -> Eq {[ l ]} (t1 u1) (t2 u2)
   
   eq {| t :: k |} :: Eq {[ k ]} t t
   eq {| Unit |} _ _ = True
   eq {| :+: |} eqA eqB (Inl a1) (Inl a2) = eqA a1 a2
   eq {| :+: |} eqA eqB (Inr b1) (Inr b2) = eqB b1 b2
   eq {| :+: |} eqA eqB _ _ = False
   eq {| :*: |} eqA eqB (a1 :*: b1) (a2 :*: b2) = eqA a1 a2 && eqB b1 b2
   eq {| Int |} = (==)
   eq {| Char |} = (==)
   eq {| Bool |} = (==)

「決まり文句を捨てる」アプローチ[編集]

決まり文句を捨てるアプローチ(Scrap your boilerplate approach)は簡易的なジェネリックプログラミングのHaskellに対するアプローチである (Lämmel and Peyton Jones, 2003)。このアプローチはHaskellのGHC>=6.0の実装でサポートされる。このアプローチを使うことで、ジェネリックな読み込み、ジェネリックな明示、ジェネリックな比較(つまりgread、gshow、geq)と同様に、横断スキーム(例えばいつでもどこでも)のようなジェネリック関数をプログラマーは記述できる。このアプローチはタイプセーフなキャストとコンストラクタアプリケーションの実行のための一部の基本要素に基づいている。

C#と.NETのジェネリックプログラミング[編集]

C#(およびその他の.NET言語)のジェネリクスは.NET Framework 2.0の一部として2005年11月に追加された。Javaと似てはいるが、.NETのジェネリクスは、コンパイラによるジェネリクス型から非ジェネリクス型へのコンバートとしてではなく、実行時に実装される。このことにより、ジェネリクス型に関するあらゆる情報はメタデータとして保存される。

.NETジェネリクスの機能

  • 型情報を削除せず、CLRの内部でジェネリクスが構築されるため(そしてコンパイラ上では全く構築しないため)、キャストや動的チェックの実行からくるパフォーマンスヒットがない。また、プログラマーはリフレクションを通じてジェネリック情報にアクセスできる。
    • 型情報を削除しないので、Javaでは不可能なジェネリック型の配列の生成が可能。
  • .NETはジェネリック型の引数として値型(基本型、ユーザ定義型のどちらも)を利用できる。その場合、JITコンパイラは特殊化のためにネイティブコードの新しいインスタンスを作成する。このことによりボックス化をする必要がなくなり、パフォーマンスが向上する。
  • Javaと同様、ジェネリック型引数がそれら自身のジェネリック型であるようにできる。つまり、List<List<Dictionary<int, int>>>のような型は有効である。
  • C#(および一般の.NET)は、キーワードwhereを使用することで、値型/参照型、デフォルトコンストラクタの存在、親クラス、実装するインターフェイスなどでジェネリック型を制約することができる。
  • 共変性と反変性をサポートしている。out修飾子またはin修飾子により、型パラメータを共変または反変にすることができる。これによって、ジェネリック型の代入と使用の柔軟性が向上する。
int MaxIndex<T>(List<T> list) where T: IComparable<T>
{
    if (list.Count == 0)
        return -1;
    int index = 0;
    for (int i = 1; i < list.Count; ++i)
        if (list[index].CompareTo(list[i]) < 0)
            index = i;
    return index;
}

この例ではMaxIndexメソッドの型パラメータTに対して、IComparable<T>インタフェースを実装していなければならないという制約をおいている。このことにより、IComparable<T>インタフェースのメンバであるCompareToメソッドが利用可能になっている。

その他の言語のジェネリックプログラミング機能[編集]

数多くの関数型言語はパラメータ化された型(parameterized types)とパラメータ化された多態(parametric polymorphism)の形で小規模なジェネリックプログラミングをサポートする。さらに標準MLとOCamlはクラステンプレートとAdaのジェネリックパッケージに似たファンクタを提供する。

Verilogのモジュールは1つ以上のパラメタを取ることができる。パラメタの実際の値は、そのモジュールを実体化する際に与えられる。一例としてジェネリックなレジスタアレイがあり、アレイの幅がパラメタで与えられている。そのようなアレイをジェネリックなワイヤベクトルと組み合わせることにより、単一のモジュール実装を用いて任意のビット幅を持つジェネリックなバッファやメモリを作ることができる。[2]

脚注[編集]

  1. ^ Stanley B. Lippman. “Pure C++:Generic Programming Under .NET”. マイクロソフトMSDNマガジン. 2008年12月28日閲覧。
  2. ^ Verilog by Example, Section The Rest for Reference. Blaine C. Readler, Full Arc Press, 2011. ISBN 978-0-9834973-0-1

関連項目[編集]