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

ジェネリック（総称あるいは汎用）プログラミング（）は、具体的なデータ型に直接依存しない、抽象的かつ汎用的なコード記述を可能にするコンピュータプログラミング手法である。
概要.
ジェネリックプログラミングはデータ型でコードをインスタンス化するのか、あるいはデータ型をパラメータとして渡すかということにかかわらず、同じソースコードを利用できる。ジェネリックプログラミングは言語により異なる形で実装されている。ジェネリックプログラミングの機能は1970年代にCLUやAdaのような言語に搭載され、次にBETA、C++、D、Eiffel、Java、その後DECのTrellis/Owl言語などの数多くのオブジェクトベース (object-based) およびオブジェクト指向 (object-oriented) 言語に採用された。
1995年の書籍デザインパターンの共著者は（Ada、Eiffel、Java、C#の）ジェネリクスや、（C++の）テンプレートとしても知られるパラメータ化された型 (parameterized types) としてジェネリクスについて触れている。これらは、型を指定することなく、型を定義できるようにする（型は使用する時点で引数として与えられる）。このテクニック（特にデリゲーションを組み合わせるとき）は非常に強力である。
特徴.
ジェネリックプログラミングの特徴は、型を抽象化してコードの再利用性を向上させつつ、静的型付け言語の持つ型安全性を維持できることである。
ジェネリックプログラミングを用いない場合、例えば伝統的なC言語やPascalのような従来の静的型付け言語において、ソートなどのアルゴリズムや連結リストのようなデータ構造（オブジェクトのコンテナ）を記述する際は、たとえ対象となる要素のデータ型が異なるだけで事実上同一のコードであったとしても、具体的なデータ型ごとにそれぞれ実装しなければならない。整数型のリスト、倍精度浮動小数点数型のリスト、文字列型のリスト、ユーザー定義構造体のリスト、……といった具合である。もしジェネリックプログラミングをサポートしない言語で汎用的なコードを記述して再利用しようと思えば、メモリ空間効率や型安全性などを犠牲にしなければならなくなる（共用体や汎用ポインタ型とキャストを駆使するなど）。一方、C++の関数テンプレートやクラステンプレートのように、ジェネリックプログラミングを用いることで、抽象化された型について一度だけ記述したアルゴリズムやデータ構造をさまざまな具象データ型に適用して、コードを型安全に再利用できるようになる。これがジェネリックプログラミングの利点の一例として挙げられる。
以下にC++の例を示す。
template<typename T>
class LinkedList {
public:
 // 双方向連結リストのノード。
 class Node {
 friend class LinkedList;
 public:
 T value;
 private:
 Node* prev;
 Node* next;
 private:
 public:
private:
 Node dummy;
public:
 LinkedList() : dummy() {
 this->dummy.prev = &this->dummy;
 this->dummy.next = &this->dummy;
 static Node* insertBefore(Node* node, const T& value) {
 assert(node);
 assert(node->prev);
 Node* temp = new Node(value, node->prev, node);
 node->prev->next = temp;
 node->prev = temp;
 return temp;
 static Node* insertAfter(Node* node, const T& value) {
 assert(node);
 assert(node->next);
 Node* temp = new Node(value, node, node->next);
 node->next->prev = temp;
 node->next = temp;
 return temp;
 static void remove(Node*& node) {
 assert(node);
 delete node;
 node = NULL;
 void clear() {
 for (Node* current = this->getHead(); current != this->getSentinel(); ) {
 Node* temp = current;
 current = current->next;
 delete temp;
 this->dummy.prev = &this->dummy;
 this->dummy.next = &this->dummy;
};
LinkedList<int> list_of_integers;
LinkedList<Animal> list_of_animals;
LinkedList<Car> list_of_cars;
上記は要素型をcodice_1とする双方向連結リストの定義例である。codice_2はテンプレートによる抽象化の対象となる型の名前（プレースホルダー）を表す。そしてこの定義されたクラステンプレートのインスタンス化、すなわち型パラメータcodice_1に具象型を与えることによって生成されるクラス型は、codice_1について実際に指定した具象型のリストとして扱われる。これらの「T型のコンテナ」を一般にジェネリクス (generics) と呼び、ジェネリックプログラミングの代表的なテクニックである。プログラミング言語によって制約は様々だが、このテクニックは、継承関係やシグネチャといった制約条件 (constraint) を維持する限り、内包するcodice_1にあらゆるデータ型を指定可能なクラスの定義を可能にする。これはジェネリックプログラミングの典型であり、一部の言語ではこの形式のみを実装する。ただし、概念としてのジェネリックプログラミングはジェネリクスに限定されない。
オブジェクト指向プログラミング言語は、サブタイプ（派生型）でスーパータイプ（基底型）の振る舞い（アルゴリズム）をオーバーライドすることによる動的なポリモーフィズム（多態性）を備えており、動的な多態性もまたスーパータイプによる抽象化とサブタイプによる具象化を実現するものだが、ジェネリクスは静的な多態性による抽象化と具象化を実現するという点で設計を異にする。
ジェネリックプログラミングのもう一つの応用例として、型に依存しないスワップ関数の例を示す。
template<typename T>
void Swap(T& a, T& b) // "&"により参照としてパラメーターを渡している。
 T temp = b;
 b = a;
 a = temp;
using namespace std;
string s1 = "world!", s2 = "Hello, ";
Swap(s1, s2);
cout « s1 « s2 « endl; // 出力は"Hello, world!"
上記の例で使用したC++のcodice_6文は、プログラマーや言語の開発者たちにこの概念を普及させたジェネリックプログラミングの例といわれている。この構文はジェネリックプログラミングの全ての概念に対応する。またD言語はC++のテンプレートを基に構文を単純化した完全なジェネリックの機能を提供する。JavaはJ2SE 5.0よりC++の文法に近いジェネリックプログラミングの機能を提供しており、ジェネリクス（「T型のコンテナ」）という、ジェネリックプログラミングの部分集合を実装する。
C# 2.0、Visual Basic .NET 2005 (VB 8.0) では、Microsoft .NET Framework 2.0がサポートするジェネリクスを利用するための構文が追加された。MLファミリーは (parametric polymorphism) とファンクタと呼ばれるジェネリックモジュールを利用してのジェネリックプログラミングを推奨する。Haskellのタイプクラスのメカニズムもまたジェネリックプログラミングに対応する。
Objective-Cにあるような動的型付けを使い、必要に応じて注意深くコーディング規約を守れば、ジェネリックプログラミングの技術を使う必要がなくなる。全てのオブジェクトを包括する汎用型があるためである。Javaもまたそうであるが、キャストが必要なので静的な型付けの統一性を乱してしまう。例えば、ジェネリクスをサポートしていなかった時代のJavaでは、のようなコレクションに格納できる要素型はのみであったため、要素取り出しの際には実際のサブクラス型への適切なキャストが必要だった。それに対し、ジェネリクスは静的な型付けについての利点を持ちながら動的な型付けの利点を完全ではないが得られる方法である。
Adaのジェネリクス.
Adaには1977年-1980年の設計当初から汎用体 (generics) が存在する。標準ライブラリでも多くのサービスを実装するために汎用体を用いている。Ada2005では1998年に規格化されたC++のStandard Template Library (STL) の影響を受けた広範な汎用コンテナが標準ライブラリとして追加された。
汎用体 (generic unit) とは、0または複数の汎用体仮パラメータ (generic formal parameters) を採るプログラム単位（パッケージまたは副プログラム）である。
汎用体仮パラメータとしては、オブジェクト（変数・定数）、データ型、副プログラム、パッケージ，さらには他の汎用体のインスタンスさえ指定することができる。汎用体仮パラメータのデータ型としては、離散 (discrete) 型、浮動小数点数型、固定小数点数型、アクセス（ポインタ）型などを用いることができる。
汎用体をインスタンス化する際、プログラマは全ての仮パラメータに対応する実パラメータを指定する必要があるが、プログラマが明示的に全ての実パラメータを指定しなくても済むよう，仮パラメータにはデフォルトを指定することもできる。インスタンス化してしまえば，汎用体のインスタンスは、汎用体ではない通常のプログラム単位であるかのように振舞う。インスタンス化は実行時、例えばループの中などで行うことも可能である。
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では暗黙的な特化による汎用体のインスタンス化を許さないため、全ての汎用体は明示的にインスタンス化することが必要である。この規則により以下のような結果が生じる。
C++のテンプレート.
C++のテンプレートは関数テンプレート、クラステンプレートをサポートするほか、C++14では変数テンプレートもサポートするようになった。C++のテンプレートは特に静的なダック・タイピングを可能にする点で強力であり、JavaやC#のジェネリクスと比べて柔軟性が高い一方、テンプレート引数に関する制約条件を明示的にコード上で記述できないことからコンパイルエラーメッセージが難解になりやすい。テンプレートはC++言語仕様の複雑化の要因にもなっている。
C++のStandard Template Library (STL) はテンプレートによる汎用的なアルゴリズムとデータ構造を提供する。
D言語のテンプレート.
D言語はC++のものを発展させたテンプレートをサポートする。大半のC++テンプレートの表現はD言語でもそのまま利用できる。それに加え、D言語は一部の一般的なケースを合理化する機能をいくつか追加する。
最もはっきりとした違いは一部のシンタックスの変更である。D言語はテンプレートの定義で山形カッコcodice_7の代わりに丸カッコcodice_8を使用する。またテンプレートのインスタンス化でも山形カッコの代わりにcodice_9構文（感嘆符を前に付けた丸カッコ）を使う。従って、D言語のcodice_10はC++のcodice_11と等価である。この変更は、テンプレート構文の構文解析を容易にするためになされた（山形カッコは比較演算子との区別がつきにくく、構文解析器が複雑化しがちであった）。
Static-if.
D言語はコンパイル時に条件をチェックするcodice_12構文を提供する。これはC++のcodice_13とcodice_14のプリプロセッサマクロに少し似ている。codice_12はテンプレート引数や、それらを使用したコンパイル時関数実行の結果を含めた全てのコンパイル時の値にアクセスできるというのがその主要な違いである。従ってC++でテンプレートの特殊化を必要とする多くの状況でも、D言語では特殊化の必要なく容易に書ける。D言語の再帰テンプレートは通常の実行時再帰とほぼ同じように書ける。これは典型的なコンパイル時の関数テンプレートに見られる。
template Factorial(ulong n) {
 static if (n <= 1)
 const Factorial = 1u;
 else
 const Factorial = n * Factorial!(n - 1);
エイリアスパラメーター.
D言語のテンプレートはまたエイリアスパラメーターを受け入れることができる。エイリアスパラメーターはC++のcodice_16と似ているが、テンプレートパラメーターを置き換えることもできる。これは今後利用可能な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年、J2SE 5.0の一部としてJavaにジェネリクスが追加された。C++のテンプレートとは違い、Javaコードのジェネリクスはジェネリッククラスの1つのコンパイルされたバージョンだけを生成する。ジェネリックJavaクラスは型パラメータとしてオブジェクト型だけを利用できる（基本型は許されない）。従ってcodice_17は正しいのに対してcodice_18は正しくない。
Javaではジェネリクスはコンパイル時に型の正しさをチェックする。そしてジェネリック型情報は型消去 (type erasure) と呼ばれるプロセスを通じて除去され、親クラスの型情報だけが保持される。例えば、codice_17は全てのオブジェクトを保有できる非ジェネリックの（生の）に変換されるだろう。しかしながら、コンパイル時のチェックにより、コードが未チェックのコンパイルエラーを生成しない限り、型が正しいようにコードの出力が保証される。
このプロセスの典型的な副作用はジェネリック型の情報を実行時に参照できないことである。従って、実行時には、codice_17とcodice_17が同じクラスであることを示す。この副作用を緩和するひとつの方法はの宣言を修飾するJavaのメソッドを利用して、実行時に型付けされたの不正利用（例えば不適切な型の挿入）をチェックすることによるものである。これは旧式のコードとジェネリクスを利用するコードを共存運用したい場合の状況で役立つ。
C++やC#のように、Javaはネストされたジェネリック型を定義できる。従って、例えばcodice_22は有効な型である。
ワイルドカード.
Javaのジェネリック型パラメーターは特定のクラスに制限されない。与えられたジェネリックオブジェクトが持っているかもしれないパラメーターの型の境界を指定するためにJavaではワイルドカードを使用できる。例えば、codice_23は無名のオブジェクト型を持つリストを表す。引数としてcodice_24を取るようなメソッドは任意の型のリストを取ることができる。リストからの読み出しは型のオブジェクトを返し、そしてnullではない要素をリストへ書き込むことはパラメーター型が任意ではないために許されない。
ジェネリック要素の制約を指定するために、ジェネリック型が境界クラスのサブクラス（クラスの拡張とインターフェイスの実装のいずれか）であることを示すキーワードcodice_25を使用できる。そしてcodice_26は与えられたリストがクラスを拡張するオブジェクトを保持することを意味する。従って、リストが何の要素の型を保持しているのかがわからないためにnullではない要素の書き込みが許されないのに対し、リストから要素を読むとが返るだろう。
ジェネリック要素の下限を指定するために、ジェネリック型が境界クラスのスーパークラスであることを示すキーワードcodice_27が使用される。そしてcodice_28はcodice_17やcodice_17でありえる。リストに正しい型を保存することが保証されるため任意の型の要素をリストに追加できるのに対し、リストからの読み出しでは型のオブジェクトを返す。
制約.
Javaのジェネリクスの実装上の制約により、配列のコンポーネントの型が何であるべきかを特定する方法がないために、ジェネリック型の配列を作成することは不可能である。従ってcodice_31経由のようにメソッドが型引数codice_1を持っていた場合はプログラマはその型の新しい配列を生成することができない。しかし、この制約はJavaのリフレクションのメカニズムを利用して回避することが可能である。クラスcodice_1のインスタンスが利用可能な場合、codice_1に対応するオブジェクトのオブジェクトから1つを得て、新しい配列を生成するためにを使うことができる。もう１つのJavaのジェネリクスの実装上の制約は、codice_23以外に、型パラメーターの型でジェネリッククラスの配列を生成することが不可能であるということだ。これは言語の配列の取り扱い方法に起因するものであり、タイプセーフを維持するために、明示的にキャストしなくともコンパイラが警告を出さないことを全てのコードで保証する必要があるからである。
Haskellのジェネリックプログラミング.
Haskell言語にはパラメータ化された型 (parameterized types)、パラメータ多相 (parametric polymorphism)、そしてJavaのジェネリクスやC++のテンプレートの両方に似たプログラミングのスタイルをサポートする型クラス (type classes) がある。Haskellプログラムではこれらの構文を様々なところで利用しており、避けることはかなり難しい。Haskellはまた、さらなるジェネリック性と、多態が提供する以上の再利用性を目指すようにプログラマーと言語開発者を奮起させる、さらに独特なジェネリックプログラミングの機能がある。
Haskellの6つの事前定義された型クラス（同一性を比較できるcodice_36という型と、値を文字列に変換できるcodice_37という型を含む）は"導出インスタンス" (derived instances) をサポートしている特別なプロパティを持つ。プログラマーが新しい型を定義するということは、クラスのインスタンスを宣言するときに、普通であれば必要なクラスメソッドの実装を提供することなく、この型がこれらの特別型クラスのインスタンスとなることを明示できるということである。全ての必要なメソッドは型の構造に基づいて導出（つまり自動的に生成）される。
例として、下記の二分木型の宣言はこれがcodice_36とcodice_37のクラスのインスタンスになることを示している。
codice_1がそれらの演算子を自分でサポートしているのであれば、任意の型のcodice_41形式のために比較関数 (codice_42) と文字列表現関数 (codice_43) が自動的に定義される。
codice_36とcodice_37の導出インスタンスへのサポートは、それらのメソッドであるcodice_42とcodice_43を、パラメーター的な多態関数とは質的に異なるジェネリックにする。これらの"関数"（より正確には型でインデックス付けられた (type-indexed) 関数のファミリー）はたくさんの異なる型の値を受け入れることができ、各引数の型によってそれらは異なる動作をするが、新しい型へのサポートを追加するためにわずかな作業が必要とされる。Ralf Hinze氏 (2004) は、あるプログラミングテクニックによりユーザー定義型のクラスに対して同様の結果を達成できることを示した。彼以外の多くの研究者はこれと、Haskellの流れとは違う種類のジェネリック性やHaskellの拡張（下記参照）に対する取り組みを提案していた。
PolyP.
PolyPはHaskellに対する最初のジェネリックプログラミング言語拡張であった。PolyPではジェネリック関数は"polytypic"と呼ばれた。通常データ型のパターンファンクタの構造によって構造的な導出を通じて定義できるpolytypic関数のような特別な構文を言語に導入した。PolyPでの通常データ型はHaskellのデータ型のサブセットである。通常データ型tは"* → *"の種類でなければならず、もし"a"が定義における表面的な型の引数である場合は、"t"に対する全ての再帰呼び出しは"t a"形式でなければならない。これらの制約は、異なる形式の再帰呼び出しである入れ子のデータタイプと同様に、上位に種類付けされたデータ型を規定する。
PolyPの展開された関数はここに例として示される。
ジェネリックHaskell.
ジェネリックHaskellはユトレヒト大学で開発されたHaskellのもう１つの拡張だ。この拡張は下記の特徴がある。
type-indexed valueの結果は任意の型に特殊化され得る。
ジェネリックHaskellの比較関数の一例として。
「決まり文句を捨てる」アプローチ.
決まり文句を捨てるアプローチ (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ジェネリクスの機能
using System;
using System.Collections.Generic;
static int FirstIndexOfMax<T>(List<T> list) where T: IComparable<T>
 if (list.Count == 0) {
 return -1;
 int index = -1;
 for (int i = 0; i < list.Count; ++i) {
 if ((index == -1 && list[i] != null) ||
 (index >= 0 && list[index] != null && list[i] != null && list[index].CompareTo(list[i]) < 0)) {
 index = i;
 return index;
この例ではcodice_50メソッドの型パラメータcodice_1に対して、codice_52インターフェイスを実装していなければならないという制約を指定している。このことにより、codice_52インターフェイスのメンバであるcodice_54メソッドが利用可能になっている。
C++/CLIは.NETのジェネリクスとC++のテンプレート両方をサポートする。ただしこれらの間に互換性はない。
その他の言語のジェネリックプログラミング機能.
数多くの関数型言語はパラメータ化された型 (parameterized types) とパラメータ多相 (parametric polymorphism) の形で小規模なジェネリックプログラミングをサポートする。さらに標準MLとOCamlはクラステンプレートとAdaのジェネリックパッケージに似たファンクタを提供する。
Verilogのモジュールは1つ以上のパラメタを取ることができる。パラメタの実際の値は、そのモジュールを実体化する際に与えられる。一例としてジェネリックなアレイがあり、アレイの幅がパラメタで与えられている。そのようなアレイをジェネリックなワイヤベクトルと組み合わせることにより、単一のモジュール実装を用いて任意のビット幅を持つジェネリックなバッファやメモリを作ることができる。