ジェネリックプログラミング
ジェネリック（総称あるいは汎用）プログラミング（）はデータ形式に依存しないコンピュータプログラミング方式である。
ジェネリックプログラミングはデータ型でコードをインスタンス化するのか、あるいはデータ型をパラメータとして渡すかということにかかわらず、同じソースコードを利用できる。ジェネリックプログラミングは言語により異なる形で実装されている。ジェネリックプログラミングの機能は70年代にCLUやAdaのような言語に搭載され、次にBETA、C++、D、Eiffel、Java、その後DECのTrellis/Owl言語などの数多くのオブジェクトベース (object-based) およびオブジェクト指向 (object-oriented) 言語に採用された。
1995年の書籍デザインパターンの共著者は（Ada、Eiffel、Java、C#の）ジェネリクスや、（C++の）テンプレートとしても知られるパラメータ化された型 (parameterized types) としてジェネリクスについて触れている。これらは、型を指定することなく、型を定義できるようにする（型は使用する時点で引数として与えられる）。このテクニック（特にデリゲーションを組み合わせるとき）は非常に強力である。
オブジェクトのコンテナを作成する際は、たとえデータ形式が異なるだけで事実上同一のコードであったとしても、データ形式毎にそれぞれ実装するのが一般的である。ジェネリックプログラミングによりC++で言うところのテンプレートクラスを定義できることがジェネリックプログラミングの利点の一例として挙げられる。
上記のTはインスタンス化する型を表す。そしてこの定義によって生成する型は指定した型Tのリストとして扱われる。これらの「T型のコンテナ」を一般にジェネリクス (generics) と呼び、ジェネリックプログラミングの代表的なテクニックである。このテクニックは、サブタイプやシグネチャといった契約を維持する限り、異なるデータ型を含めたクラスの定義を可能にする。サブクラスでアルゴリズムをオーバーライドする多態と設計が異なる。前者はジェネリックプログラミングの典型であり、一部の言語ではこの形式のみを実装する。概念としてのジェネリックプログラミングはジェネリクスに限定されない。ジェネリックプログラミングのもう一つの応用例として、型に依存しないスワップ関数の例を示す。
上記の例で使用したC++のcodice_1文は、プログラマーや言語の開発者たちにこの概念を普及させたジェネリックプログラミングの例といわれている。この構文はジェネリックプログラミングの全ての概念に対応する。またD言語はC++のテンプレートを基に構文を単純化した完全なジェネリックの機能を提供する。JavaはJ2SE 5.0よりC++の文法に近いジェネリックプログラミングの機能を提供しており、ジェネリクス（「T型のコンテナ」）という、ジェネリックプログラミングの部分集合を実装する。
C# 2.0、Chrome 1.5、Visual Basic .NET 2005 (VB 8.0) では、Microsoft .NET Framework 2.0がサポートするジェネリクスを利用するための構文が追加された。MLファミリーはパラメトリックな多態 (parametric polymorphism) とファンクタと呼ばれるジェネリックモジュールを利用してのジェネリックプログラミングを推奨する。Haskellのタイプクラスのメカニズムもまたジェネリックプログラミングに対応する。
Objective-Cにあるような動的型付けを使い、必要に応じて注意深くコーディング規約を守れば、ジェネリックプログラミングの技術を使う必要がなくなる。全てのオブジェクトを包括する汎用型があるためである。Javaもまたそうであるが、キャストが必要なので静的な型付けの統一性を乱してしまう。それに対し、ジェネリクスは静的な型付けについての利点を持ちながら動的な型付けの利点を完全ではないが得られる方法である。
Adaには1977年～1980年の設計当初から汎用体 (generics) が存在する。標準ライブラリでも多くのサービスを実装するために汎用体を用いている。Ada2005では1998年に規格化されたC++のStandard Template Library (STL) の影響を受けた広範な汎用コンテナが標準ライブラリとして追加された。
汎用体 (generic unit) とは、0または複数の汎用体仮パラメータ (generic formal parameters) を採るプログラム単位（パッケージまたは副プログラム）である。
汎用体仮パラメータとしては、オブジェクト（変数・定数）、データ型、副プログラム、パッケージ，さらには他の汎用体のインスタンスさえ指定することができる。汎用体仮パラメータのデータ型としては、離散 (discrete) 型、浮動小数点数型、固定小数点数型、アクセス（ポインタ）型などを用いることができる。
汎用体をインスタンス化する際、プログラマは全ての仮パラメータに対応する実パラメータを指定する必要があるが、プログラマが明示的に全ての実パラメータを指定しなくても済むよう，仮パラメータにはデフォルトを指定することもできる。インスタンス化してしまえば，汎用体のインスタンスは、汎用体ではない通常のプログラム単位であるかのように振舞う。インスタンス化は実行時、例えばループの中などで行うことも可能である。
汎用体パッケージの仕様部
汎用体パッケージのインスタンス化
汎用体パッケージインスタンスの利用
Adaの言語構文では、汎用体仮パラメータとして何を許容するか、精密に制約条件を課することができる。例えば実パラメータとしてはモジュラー型（任意の上限で巡回する符号なし整数型）のみを許容するように、仮パラメータとして指定することも可能である。さらには汎用体仮パラメータ間に一定の制約があるように規制することも可能である。例えば、
この例でArray_Typeには、Element_Typeに対応する特定のデータ型を要素とし、Index_Typeに対応する特定の離散型の部分型を添字とする配列型でなければならないという制約を課している。プログラマがこの汎用体をインスタンス化する際には、同制約を満足する配列型を実パラメタとして渡さなければならない。
構文の複雑さに難はあるものの、精密な制約が表現できることで、汎用体仮パラメータの全ては仕様部として完全に定義される。このため、コンパイラは汎用体本体がなくても汎用体をインスタンス化することができる（もちろん本体がないとリンクはできない）。
C++と異なってAdaでは暗黙的な特化による汎用体のインスタンス化を許さないため、全ての汎用体は明示的にインスタンス化することが必要である。この規則により以下のような結果が生じる。"テンプレート"は特に多重継承と演算子の多重定義を組み合わせた場合に強力である。C++のStandard Template Library (STL) はテンプレートで作られた枠組みを提供する。
C++のテンプレートはまた、実行時ではなくコンパイル時にコードの一部を事前評価する方法であるテンプレートメタプログラミングにも利用できる。C++のテンプレートはチューリング完全である。ただし、コンパイラによる制限がある。規格上は再帰の深さは参考 (informative) で実装量 (implementation quantities) であり、C++2011の案 (N3797) では1024を最小として例示している。再帰の制限が無ければコンパイル処理が永遠に終了しないコードを記述することができ、それをコードから判断することはコンパイラには不可能だからである。停止性問題を参照。
関数テンプレートとクラステンプレートの2種類のテンプレートがある。関数テンプレートは普通の関数のように動作するが、型に依存することなく多様な引数を受け入れられる。例えば、C++ STLには、"x"と"y"のどちらか大きいほうを返すcodice_2の関数テンプレートがある。codice_3はこのように実装できるだろう。
このテンプレートは関数のように呼び出せる。
コンパイラは引数を評価してこれがcodice_4の呼び出しであることを決定し、型codice_5がcodice_6である関数のバージョンを"インスタンス化"する。
引数codice_7とcodice_8が整数や文字列、あるいは"codice_9"と表現することに意味のあるそれ以外の型（正確に言えばcodice_10を指定するあらゆる型）のとき、これは機能する。これは利用可能な型のセットに何らかの共通の継承がある必要がなく、これは実際には静的なダック・タイピング (duck typing) である。もしプログラムがカスタムデータ型を定義するならば、codice_3で利用可能にするために必要なことはその型のcodice_12の意味を定義するために演算子を多重定義するということだけである。この例だけでは小さな利点にしか見えないかもしれないが、STLのような総合ライブラリの中では、わずかな演算子を定義するだけで新しいデータ型に対して幅広い機能を得られるのだ。単純にcodice_12を定義することだけで、標準のcodice_14やcodice_15、codice_16といったアルゴリズムを型に利用でき、またcodice_17やヒープや連想配列等々の内部データ構造に利用できる。
C++のテンプレートは完全にコンパイル時点でタイプセーフである。例えば、複素数には狭義の順序 (strict order) がないので標準形式のcodice_18はcodice_12演算子を定義しない。従ってcodice_2関数に"x"と"y"としてcodice_18型を指定した場合、コンパイルエラーとなる。同様に、codice_12をあてにする他のテンプレートはcodice_18データに適用できない。ただ、コンパイラは歴史的にやや難解で役に立たないエラーメッセージをこの種のエラーに対して生成する。目的によっては手法とコーディング規約にこだわることでこの問題を軽減できるかもしれない。
2つ目のテンプレートの種類であるクラステンプレートは同じコンセプトをクラスに拡張する。クラステンプレートはよくジェネリックコンテナを作るのに利用される。例えば、STLには連結リストコンテナがある。整数の連結リストを作るためにはcodice_24と書く。文字列のリストはcodice_25である。codice_26はたとえどんな型がcodice_12とcodice_28の間に指定されても動作する共通の関数セットを持っている。
テンプレートの特殊化 (template specialization) はC++のテンプレートの強力な機能である。インスタンス化されるであろうパラメーター化された型 (parameterized type) に特化した特徴を備えた新しい実装ができる。テンプレートの特殊化は、特定の形式に最適化できるようにすることと、コード肥大化の削減に役立てるという2つの目的がある。
例としてcodice_14テンプレート関数について考える。このような関数の動作は第一にコンテナの特定位置の2つの値を入れ替えまたは交換することだ。値が多い場合（各要素を格納するためにメモリを消費するという点で）、オブジェクトへのポインタのリストを先に構築し、それらのポインタをソートして、最終的なソートされたシーケンスを構築するのが多くの場合で高速だ。値が非常に少なければ単純に必要に応じて値をスワップで置き換えるのが最も速い。しかしさらにパラメーター化された型がポインター型である場合はポインタの配列を構築する必要がない。テンプレートの特殊化はテンプレートの作者に複数の異なる実装を記述できるようにし、パラメーター化された型が各実装で利用されるべき特徴を指定できるようにする。
codice_3関数のようなテンプレートのユーザーの一部は（古いC言語の）関数形式のプリプロセッサマクロを活用していた。例えば次のようなcodice_3マクロがある。
これら2つのマクロとテンプレートはコンパイル時間を長くする。マクロは常にインラインとして展開される。テンプレートもコンパイラが適切と判断すればインライン関数として展開される。従って、関数形式のマクロと関数テンプレートは共に実行時のオーバーヘッドがない。
しかしテンプレートは次のような目的でマクロより重要であると一般的に考えられている。まずテンプレートはタイプセーフである。そしてテンプレートは関数形式のマクロを濫用したコードにある一般的なエラーの一部を回避する。恐らく最も重要なのは、テンプレートはマクロよりも大きなコードに対して効果があるようにするために設計されたということだ。
テンプレートには主に3つの欠点がある。コンパイラのサポート、貧弱なエラーメッセージ、コードの肥大化だ。
歴史的に多くのコンパイラがテンプレートについて非常に貧弱なサポートしかなく、そのためテンプレートを使うことで移植性を損なった。C++について考慮していないリンカを利用するとき、あるいは共有ライブラリの境界を越えてテンプレートを使おうとしたときも十分な対応がなされていなかった。今ではかなりしっかりしており、標準テンプレートをサポートし、また、新しいC++の標準であるC++0xはこれらの問題をさらに解決していることが期待されている。
ほとんど全てのコンパイラは、テンプレートを使ったコードにエラーを検出したときに、混乱した、長い、そして役に立たないエラーメッセージを出力する。これはテンプレートを使った開発を難しくしている。
テンプレートの使用はコンパイラが余分なコード（テンプレートの"インスタンス化"）を生成する原因となりうるので、見境なくテンプレートを利用すると過剰に大きな実行ファイルを出力してしまう。しかしながら一部のケースでは、うまくテンプレートの特殊化を利用することで、そのようなコードの肥大化を劇的に減らすことができる。またテンプレートによって生じる余分なインスタンス化はデバッガが素直にテンプレートを扱うことを困難にする原因ともなりうる。例えばソースコードのテンプレートの中にブレークポイントをセットする場合、実際のインスタンスの中の望ましい場所にセットすることに失敗するかもしれないし、そのテンプレートによってインスタンス化された全ての場所にブレークポイントを設置しなければならないかもしれない。
D言語はC++のものを発展させたテンプレートをサポートする。大半のC++テンプレートの表現はD言語でもそのまま利用できる。それに加え、D言語は一部の一般的なケースを合理化する機能をいくつか追加する。
最もはっきりとした違いは一部のシンタックスの変更である。D言語はテンプレートの定義で山形カッコcodice_32の代わりに丸カッコcodice_33を使用する。またテンプレートのインスタンス化でも山形カッコの代わりにcodice_34構文（感嘆符を前に付けた丸カッコ）を使う。従って、D言語のcodice_35はC++のcodice_36と等価である。この変更は、テンプレート構文の構文解析を容易にするためになされた（山形カッコは比較演算子との区別がつきにくく、構文解析器が複雑化しがちであった）。
D言語はコンパイル時に条件をチェックするcodice_37構文を提供する。これはC++のcodice_38とcodice_39のプリプロセッサマクロに少し似ている。codice_37はテンプレート引数や、それらを使用したコンパイル時関数実行の結果を含めた全てのコンパイル時の値にアクセスできるというのがその主要な違いである。従ってC++でテンプレートの特殊化を必要とする多くの状況でも、D言語では特殊化の必要なく容易に書ける。D言語の再帰テンプレートは通常の実行時再帰とほぼ同じように書ける。これは典型的なコンパイル時の関数テンプレートに見られる。
D言語のテンプレートはまたエイリアスパラメーターを受け入れることができる。エイリアスパラメーターはC++のcodice_41と似ているが、テンプレートパラメーターを置き換えることもできる。これは今後利用可能なC++0x仕様に追加されるであろう、C++のテンプレートのテンプレート引数にある機能の拡張版である。エイリアスパラメーターは、テンプレート、関数、型、その他のコンパイル時のシンボルを指定できる。これは例えばテンプレート関数の中に関数をプログラマーが"挿入"できるようにする。
この種のテンプレートはC言語APIとD言語のコードを接続するときに使いやすいだろう。仮想のC言語APIが関数ポインタを要求する場合、このようにテンプレートを利用できる。
2004年、J2SE5.0の一部としてJavaにジェネリクスが追加された。C++のテンプレートとは違い、Javaコードのジェネリクスはジェネリッククラスの１つのコンパイルされたバージョンだけを生成する。ジェネリックJavaクラスは型パラメータとしてオブジェクト型だけを利用できる（基本型は許されない）。従ってcodice_42は正しいのに対してcodice_43は正しくない。
Javaではジェネリクスはコンパイル時に型の正しさをチェックする。そしてジェネリック型情報は型削除 (type erasure) と呼ばれるプロセスを通じて除去され、親クラスの型情報だけが保持される。例えば、codice_42は全てのオブジェクトを保有できる非ジェネリックの（生の）codice_45に変換されるだろう。しかしながら、コンパイル時のチェックにより、コードが未チェックのコンパイルエラーを生成しない限り、型が正しいようにコードの出力が保証される。
このプロセスの典型的な副作用はジェネリック型の情報を実行時に参照できないことだ。従って、実行時には、codice_42とcodice_42が同じcodice_45クラスであることを示す。この副作用を緩和するひとつの方法はの宣言を修飾するJavaのcodice_45メソッドを利用して、実行時に型付けされたの不正利用（例えば不適切な型の挿入）をチェックすることによるものである。これは旧式のコードとジェネリクスを利用するコードを共存運用したい場合の状況で役立つ。
C++やC#のように、Javaはネストされたジェネリック型ができる。従ってcodice_50は有効な型だ。
Javaのジェネリック型パラメーターは特定のクラスに制限されない。与えられたジェネリックオブジェクトが持っているかもしれないパラメーターの型の境界を指定するためにJavaでは"ワイルドカード"を使用できる。例えば、codice_51は無名のオブジェクト型を持つリストを表す。引数としてlistを取るようなメソッドは任意の型のリストを取ることができる。リストからの読み出しはcodice_45型のオブジェクトを返し、そしてnullではない要素をリストへ書き込むことはパラメーター型が任意ではないために許されない。
ジェネリック要素の制約を指定するために、ジェネリック型が境界クラスのサブクラス（クラスの拡張とインターフェイスの実装のいずれか）であることを示すキーワードcodice_53を使用できる。そしてcodice_54は与えられたリストがcodice_45クラスを拡張するオブジェクトを保持することを意味する。従って、リストが何の要素の型を保持しているのかがわからないためにnullではない要素の書き込みが許されないのに対し、リストから要素を読むとが返るだろう。
ジェネリック要素の下限を指定するために、ジェネリック型が境界クラスのスーパークラスであることを示すキーワードcodice_56が使用される。そしてcodice_57はcodice_42やcodice_42でありえる。リストに正しい型を保存することが保障されるため任意のcodice_45型の要素をリストに追加できるのに対し、リストから読み出しではcodice_45型のオブジェクトを返す。
Javaのジェネリクスの実装上の制約により、配列のコンポーネントの型が何であるべきかを特定する方法がないために、ジェネリック型の配列を作成することは不可能である。従ってcodice_62経由のようにメソッドが型引数Tを持っていた場合はプログラマはその型の新しい配列を生成することが出来ない。（この制約はJavaのリフレクションのメカニズムを利用して回避することが可能だ。クラスcodice_5のインスタンスが利用可能な場合、codice_5に対応するcodice_45オブジェクトのオブジェクトから１つを得て、新しい配列を生成するためにcodice_45を使うことができる。）もう１つのJavaのジェネリクスの実装上の制約は、codice_51以外に、型パラメーターの型でジェネリッククラスの配列を生成することが不可能であるということだ。これは言語の配列の取り扱い方法に起因するものであり、明示的にキャストしなくともコンパイラが警告を出さないことを全てのコードで保障する必要がタイプセーフを維持するためにあるからである。
Haskell言語にはパラメータ化された型 (parameterized types)、パラメータ的多態 (parametric polymorphism)、そしてJavaのジェネリクスやC++のテンプレートの両方に似たプログラミングのスタイルをサポートする型クラス (type classes) がある。Haskellプログラムではこれらの構文を様々なところで利用しており、避けることはかなり難しい。Haskellはまた、さらなるジェネリック性と、多態が提供する以上の再利用性を目指すようにプログラマーと言語開発者を奮起させる、さらに独特なジェネリックプログラミングの機能がある。
Haskellの6つの事前定義された型クラス（同一性を比較できるcodice_68という型と、値を文字列に変換できるcodice_69という型を含む）は"導出インスタンス" (derived instances) をサポートしている特別なプロパティを持つ。プログラマーが新しい型を定義するということは、クラスのインスタンスを宣言するときに、普通であれば必要なクラスメソッドの実装を提供することなく、この型がこれらの特別型クラスのインスタンスとなることを明示できるということである。全ての必要なメソッドは型の構造に基づいて導出（つまり自動的に生成）される。
例として、下記の２分木型の宣言はこれがcodice_68とcodice_69のクラスのインスタンスになることを示している。
codice_5がそれらの演算子を自分でサポートしているのであれば、任意の型のcodice_73形式のために比較関数 (codice_74) と文字列表現関数 (codice_75) が自動的に定義される。
codice_68とcodice_69の導出インスタンスへのサポートは、それらのメソッドであるcodice_74とcodice_75を、パラメーター的な多態関数とは質的に異なるジェネリックにする。これらの"関数"（より正確には型でインデックス付けられた (type-indexed) 関数のファミリー）はたくさんの異なる型の値を受け入れることができ、各引数の型によってそれらは異なる動作をするが、新しい型へのサポートを追加するためにわずかな作業が必要とされる。Ralf Hinze氏 (2004) は、あるプログラミングテクニックによりユーザー定義型のクラスに対して同様の結果を達成できることを示した。彼以外の多くの研究者はこれと、Haskellの流れとは違う種類のジェネリック性やHaskellの拡張（下記参照）に対する取り組みを提案していた。
PolyPはHaskellに対する最初のジェネリックプログラミング言語拡張であった。PolyPではジェネリック関数は"polytypic"と呼ばれた。通常データ型のパターンファンクタの構造によって構造的な導出を通じて定義できるpolytypic関数のような特別な構文を言語に導入した。PolyPでの通常データ型はHaskellのデータ型のサブセットである。通常データ型tは"* → *"の種類でなければならず、もし"a"が定義における表面的な型の引数である場合は、"t"に対する全ての再帰呼び出しは"t a"形式でなければならない。これらの制約は、異なる形式の再帰呼び出しである入れ子のデータタイプと同様に、上位に種類付けされたデータ型を規定する。
PolyPの展開された関数はここに例として示される。
ジェネリック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言語）のジェネリクスは.NET Framework 2.0の一部として2005年11月に追加された。Javaと似てはいるが、.NETのジェネリクスは、コンパイラによるジェネリクス型から非ジェネリクス型へのコンバートとしてではなく、実行時に実装される。このことにより、ジェネリクス型に関するあらゆる情報はメタデータとして保存される。
.NETジェネリクスの機能
この例ではMaxIndexメソッドの型パラメータTに対して、IComparableインタフェースを実装していなければならないという制約をおいている。このことにより、IComparableインタフェースのメンバであるCompareToメソッドが利用可能になっている。
数多くの関数型言語はパラメータ化された型 (parameterized types) とパラメータ化された多態 (parametric polymorphism) の形で小規模なジェネリックプログラミングをサポートする。さらに標準MLとOCamlはクラステンプレートとAdaのジェネリックパッケージに似たファンクタを提供する。
Verilogのモジュールは1つ以上のパラメタを取ることができる。パラメタの実際の値は、そのモジュールを実体化する際に与えられる。一例としてジェネリックなアレイがあり、アレイの幅がパラメタで与えられている。そのようなアレイをジェネリックなワイヤベクトルと組み合わせることにより、単一のモジュール実装を用いて任意のビット幅を持つジェネリックなバッファやメモリを作ることができる。