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

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

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

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

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

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

テンプレートの特殊化

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

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

長所と短所

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

これら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言語の再帰テンプレートは通常の実行時再帰とほぼ同じように書ける。これは典型的なコンパイル時の関数テンプレートに見られる。

エイリアスパラメーター

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

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

Javaのジェネリクス

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

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

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

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

ワイルドカード

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

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

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

制約

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

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

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

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

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

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

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

EqとShowの導出インスタンスへのサポートは、それらのメソッドである==と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のもう１つの拡張だ。この拡張は下記の特徴がある。

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

• 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のジェネリクスは、コンパイラによるジェネリクス型から非ジェネリクス型へのコンバートとしてではなく、実行時に実装される。このことにより、ジェネリクス型に関するあらゆる情報はメタデータとして保存される。

• 型情報を削除せず、CLRの内部でジェネリクスが構築されるため（そしてコンパイラ上では全く構築しないため）、キャストや動的チェックの実行からくるパフォーマンスヒットがない。また、プログラマーはリフレクションを通じてジェネリック情報にアクセスできる。
• *型情報を削除しないので、Javaでは不可能なジェネリック型の配列の生成が可能。
• .NETはジェネリック型の引数として値型（基本型、ユーザ定義型のどちらも）を利用できる。その場合、JITコンパイラは特殊化のためにネイティブコードの新しいインスタンスを作成する。このことによりボックス化をする必要がなくなり、パフォーマンスが向上する。
• Javaと同様、ジェネリック型引数がそれら自身のジェネリック型であるようにできる。つまり、List>>のような型は有効である。
• C#（および一般の.NET）は、キーワードwhereを使用することで、値型/参照型、コンストラクタの存在、親クラス、実装するインターフェイスなどでジェネリック型を制約することができる。