ジェネリックプログラミング
ジェネリック(総称あるいは汎用)プログラミング(generic programming)は、具体的なデータ型に直接依存しない、抽象的かつ汎用的なコード記述を可能にするコンピュータプログラミング手法である。
ジェネリックプログラミングはデータ型でコードをインスタンス化するのか、あるいはデータ型をパラメータとして渡すかということにかかわらず、同じソースコードを利用できる。ジェネリックプログラミングは言語により異なる形で実装されている。ジェネリックプログラミングの機能は1970年代にCLUやAdaのような言語に搭載され、次にBETA、C++、D、Eiffel、Java、その後DECのTrellis/Owl言語などの数多くのオブジェクトベース (object-based) およびオブジェクト指向 (object-oriented) 言語に採用された。
1995年の書籍デザインパターン2019年3月の共著者2019年3月は(Ada、Eiffel、Java、C#の)ジェネリクスや、(C++の)テンプレートとしても知られるパラメータ化された型 (parameterized types) としてジェネリクスについて触れている。これらは、型を指定することなく、型を定義できるようにする(型は使用する時点で引数として与えられる)。このテクニック(特にデリゲーションを組み合わせるとき)は非常に強力である。
ジェネリックプログラミングの特徴は、型を抽象化してコードの再利用性を向上させつつ、静的型付け言語の持つ型安全性を維持できることである。
ジェネリックプログラミングを用いない場合、例えば伝統的なC言語やPascalのような従来の静的型付け言語において、ソートなどのアルゴリズムや連結リストのようなデータ構造(オブジェクトのコンテナ)を記述する際は、たとえ対象となる要素のデータ型が異なるだけで事実上同一のコードであったとしても、具体的なデータ型ごとにそれぞれ実装しなければならない。整数型のリスト、倍精度浮動小数点数型のリスト、文字列型のリスト、ユーザー定義構造体のリスト、……といった具合である。もしジェネリックプログラミングをサポートしない言語で汎用的なコードを記述して再利用しようと思えば、メモリ空間効率や型安全性などを犠牲にしなければならなくなる(共用体や汎用ポインタ型とキャストを駆使するなど)。一方、C++の関数テンプレートやクラステンプレートのように、ジェネリックプログラミングを用いることで、抽象化された型について一度だけ記述したアルゴリズムやデータ構造をさまざまな具象データ型に適用して、コードを型安全に再利用できるようになる。これがジェネリックプログラミングの利点の一例として挙げられる。
以下にC++の例を示す。
上記は要素型をTとする双方向連結リストの定義例である。typename Tはテンプレートによる抽象化の対象となる型の名前(プレースホルダー)を表す。そしてこの定義されたクラステンプレートのインスタンス化、すなわち型パラメータTに具象型を与えることによって生成されるクラス型は、Tについて実際に指定した具象型のリストとして扱われる。これらの「T型のコンテナ」を一般にジェネリクス (generics) と呼び、ジェネリックプログラミングの代表的なテクニックである。プログラミング言語によって制約は様々だが、このテクニックは、継承関係やシグネチャといった制約条件 (constraint) を維持する限り、内包するTにあらゆるデータ型を指定可能なクラスの定義を可能にする。これはジェネリックプログラミングの典型であり、一部の言語ではこの形式のみを実装する。ただし、概念としてのジェネリックプログラミングはジェネリクスに限定されない。
オブジェクト指向プログラミング言語は、サブタイプ(派生型)でスーパータイプ(基底型)の振る舞い(アルゴリズム)をオーバーライドすることによる動的なポリモーフィズム(多態性)を備えており、動的な多態性もまたスーパータイプによる抽象化とサブタイプによる具象化を実現するものだが、ジェネリクスは静的な多態性による抽象化と具象化を実現するという点で設計を異にする。
ジェネリックプログラミングのもう一つの応用例として、型に依存しないスワップ関数の例を示す。
上記の例で使用したC++のtemplate文は、プログラマーや言語の開発者たちにこの概念を普及させたジェネリックプログラミングの例といわれている。この構文はジェネリックプログラミングの全ての概念に対応する。また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では、java/utilのようなコレクションに格納できる要素型はjava/langのみであったため、要素取り出しの際には実際のサブクラス型への適切なキャストが必要だった。それに対し、ジェネリクスは静的な型付けについての利点を持ちながら動的な型付けの利点を完全ではないが得られる方法である。
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では暗黙的な特化による汎用体のインスタンス化を許さないため、全ての汎用体は明示的にインスタンス化することが必要である。この規則により以下のような結果が生じる。
コンパイラは共有ジェネリクス (shared generics) を実装できる。すなわち、ある汎用体のオブジェクトコードは全インスタンスで共有できる(もちろんプログラマが副プログラムのインライン化を要求しない限り)。さらなる結果として、
コードが肥大化する可能性がない(コードの肥大化はC++では一般的であり後述のように特別な配慮が求められる)。
インスタンス化の都度に新たなオブジェクトコードを生成することは不要であるため、コンパイル時のみならず、実行時に汎用体をインスタンス化することができる。
汎用体仮オブジェクトに対応する実オブジェクトは、たとえ同実オブジェクトが静的である(コンパイル時に値が確定する)としても、汎用体本体中では常に静的ではないものとみなされる。詳細についてはWikibookのGeneric formal objectsを参照。
ある汎用体の全インスタンスは全く同一であるため、他人の作成したプログラムをレビューしたり、理解することが容易である。配慮すべき「特別な場合」はないのだから。
全てのインスタンス化は明示的であり、プログラムの理解が困難となるような暗黙的なインスタンス化はない。
Adaでは特化を許容しないためテンプレートメタプログラミングはできない。
ただし仮パラメータに精密な制約を課することができるため、例えば、スワップ副プログラムを仮パラメータとして、ソートを目的とした汎用体の挙動をスワップ対象に応じて変化させたり、離散型の規定演算である大小判定を用いてMaxを実装するなど、特化の利点とされる目的の一部は他の方法により、達成することができる。
C++のテンプレートは関数テンプレート、クラステンプレートをサポートするほか、C++14では変数テンプレートもサポートするようになった。C++のテンプレートは特に静的なダック・タイピングを可能にする点で強力であり、JavaやC#のジェネリクスと比べて柔軟性が高い一方、テンプレート引数に関する制約条件を明示的にコード上で記述できないことからコンパイルエラーメッセージが難解になりやすい。テンプレートはC++言語仕様の複雑化の要因にもなっている。
C++のStandard Template Library (STL) はテンプレートによる汎用的なアルゴリズムとデータ構造を提供する。
D言語はC++のものを発展させたテンプレートをサポートする。大半のC++テンプレートの表現はD言語でもそのまま利用できる。それに加え、D言語は一部の一般的なケースを合理化する機能をいくつか追加する。
最もはっきりとした違いは一部のシンタックスの変更である。D言語はテンプレートの定義で山形カッコ< >の代わりに丸カッコ( )を使用する。またテンプレートのインスタンス化でも山形カッコの代わりに!( )構文(感嘆符を前に付けた丸カッコ)を使う。従って、D言語のa!(b)はC++のa<b>と等価である。この変更は、テンプレート構文の構文解析を容易にするためになされた(山形カッコは比較演算子との区別がつきにくく、構文解析器が複雑化しがちであった)。
D言語はコンパイル時に条件をチェックするstatic if構文を提供する。これはC++の#ifと#endifのプリプロセッサマクロに少し似ている。static ifはテンプレート引数や、それらを使用したコンパイル時関数実行の結果を含めた全てのコンパイル時の値にアクセスできるというのがその主要な違いである。従ってC++でテンプレートの特殊化を必要とする多くの状況でも、D言語では特殊化の必要なく容易に書ける。D言語の再帰テンプレートは通常の実行時再帰とほぼ同じように書ける。これは典型的なコンパイル時の関数テンプレートに見られる。
D言語のテンプレートはまたエイリアスパラメーターを受け入れることができる。エイリアスパラメーターはC++のtypedefと似ているが、テンプレートパラメーターを置き換えることもできる。これは今後利用可能なC++0x仕様に追加されるであろう、C++のテンプレートのテンプレート引数にある機能の拡張版である。エイリアスパラメーターは、テンプレート、関数、型、その他のコンパイル時のシンボルを指定できる。これは例えばテンプレート関数の中に関数をプログラマーが挿入できるようにする。
この種のテンプレートはC言語APIとD言語のコードを接続するときに使いやすいだろう。仮想のC言語APIが関数ポインタを要求する場合、このようにテンプレートを利用できる。
2004年、J2SE 5.0の一部としてJavaにジェネリクスが追加された。C++のテンプレートとは違い、Javaコードのジェネリクスはジェネリッククラスの1つのコンパイルされたバージョンだけを生成する。ジェネリックJavaクラスは型パラメータとしてオブジェクト型だけを利用できる(基本型は許されない)。従ってjava/util<java/lang>は正しいのに対してjava/util<int>は正しくない。
Javaではジェネリクスはコンパイル時に型の正しさをチェックする。そしてジェネリック型情報は型消去 (type erasure) と呼ばれるプロセスを通じて除去され、親クラスの型情報だけが保持される。例えば、java/util<java/lang>は全てのオブジェクトを保有できる非ジェネリックの(生の)java/utilに変換されるだろう。しかしながら、コンパイル時のチェックにより、コードが未チェックのコンパイルエラーを生成しない限り、型が正しいようにコードの出力が保証される。
このプロセスの典型的な副作用はジェネリック型の情報を実行時に参照できないことである。従って、実行時には、java/util<java/lang>とjava/util<java/lang>が同じjava/utilクラスであることを示す。この副作用を緩和するひとつの方法はjava/utilの宣言を修飾するJavaのCollections.checkedList(List<E>, Class<E>)メソッドを利用して、実行時に型付けされたjava/utilの不正利用(例えば不適切な型の挿入)をチェックすることによるものである。これは旧式のコードとジェネリクスを利用するコードを共存運用したい場合の状況で役立つ。
C++やC#のように、Javaはネストされたジェネリック型を定義できる。従って、例えばjava/util<java/util<java/lang, java/lang>>は有効な型である。
Javaのジェネリック型パラメーターは特定のクラスに制限されない。与えられたジェネリックオブジェクトが持っているかもしれないパラメーターの型の境界を指定するためにJavaではワイルドカードを使用できる。例えば、java/util<?>は無名のオブジェクト型を持つリストを表す。引数としてList<?>を取るようなメソッドは任意の型のリストを取ることができる。リストからの読み出しはjava/lang型のオブジェクトを返し、そしてnullではない要素をリストへ書き込むことはパラメーター型が任意ではないために許されない。
ジェネリック要素の制約を指定するために、ジェネリック型が境界クラスのサブクラス(クラスの拡張とインターフェイスの実装のいずれか)であることを示すキーワードextendsを使用できる。そしてjava/util<? extends java/lang>は与えられたリストがjava/langクラスを拡張するオブジェクトを保持することを意味する。従って、リストが何の要素の型を保持しているのかがわからないためにnullではない要素の書き込みが許されないのに対し、リストから要素を読むとjava/langが返るだろう。
ジェネリック要素の下限を指定するために、ジェネリック型が境界クラスのスーパークラスであることを示すキーワードsuperが使用される。そしてjava/util<? super java/lang>はjava/util<java/lang>やjava/util<java/lang>でありえる。リストに正しい型を保存することが保証されるため任意のjava/lang型の要素をリストに追加できるのに対し、リストからの読み出しではjava/lang型のオブジェクトを返す。
Javaのジェネリクスの実装上の制約により、配列のコンポーネントの型が何であるべきかを特定する方法がないために、ジェネリック型の配列を作成することは不可能である。従ってnew T[size];経由のようにメソッドが型引数Tを持っていた場合はプログラマはその型の新しい配列を生成することができない。しかし、この制約はJavaのリフレクションのメカニズムを利用して回避することが可能である。クラスTのインスタンスが利用可能な場合、Tに対応するjava/langオブジェクトのオブジェクトから1つを得て、新しい配列を生成するためにjava.lang.reflect.Array.newInstance(Class, int)を使うことができる。もう1つのJavaのジェネリクスの実装上の制約は、<?>以外に、型パラメーターの型でジェネリッククラスの配列を生成することが不可能であるということだ。これは言語の配列の取り扱い方法に起因するものであり、タイプセーフを維持するために、明示的にキャストしなくともコンパイラが警告を出さないことを全てのコードで保証する必要があるからである。
Haskell言語にはパラメータ化された型 (parameterized types)、パラメータ多相 (parametric polymorphism)、そしてJavaのジェネリクスやC++のテンプレートの両方に似たプログラミングのスタイルをサポートする型クラス (type classes) がある。Haskellプログラムではこれらの構文を様々なところで利用しており、避けることはかなり難しい。Haskellはまた、さらなるジェネリック性と、多態が提供する以上の再利用性を目指すようにプログラマーと言語開発者を奮起させる、さらに独特なジェネリックプログラミングの機能がある。
Haskellの6つの事前定義された型クラス(同一性を比較できるEqという型と、値を文字列に変換できるShowという型を含む)は導出インスタンス (derived instances) をサポートしている特別なプロパティを持つ。プログラマーが新しい型を定義するということは、クラスのインスタンスを宣言するときに、普通であれば必要なクラスメソッドの実装を提供することなく、この型がこれらの特別型クラスのインスタンスとなることを明示できるということである。全ての必要なメソッドは型の構造に基づいて導出(つまり自動的に生成)される。
例として、下記の二分木型の宣言はこれがEqとShowのクラスのインスタンスになることを示している。
<pre>
data BinTree a = Leaf a | Node (BinTree a) a (Bintree a)
deriving (Eq, Show)
</pre>
Tがそれらの演算子を自分でサポートしているのであれば、任意の型のBinTree T形式のために比較関数 (==) と文字列表現関数 (show) が自動的に定義される。
EqとShowの導出インスタンスへのサポートは、それらのメソッドである==とshowを、パラメーター的な多態関数とは質的に異なるジェネリックにする。これらの"関数"(より正確には型でインデックス付けられた (type-indexed) 関数のファミリー)はたくさんの異なる型の値を受け入れることができ、各引数の型によってそれらは異なる動作をするが、新しい型へのサポートを追加するためにわずかな作業が必要とされる。Ralf Hinze氏 (2004) は、あるプログラミングテクニックによりユーザー定義型のクラスに対して同様の結果を達成できることを示した。彼以外の多くの研究者はこれと、Haskellの流れとは違う種類のジェネリック性やHaskellの拡張(下記参照)に対する取り組みを提案していた。
PolyPはHaskellに対する最初のジェネリックプログラミング言語拡張であった。PolyPではジェネリック関数はpolytypicと呼ばれた。通常データ型のパターンファンクタの構造によって構造的な導出を通じて定義できるpolytypic関数のような特別な構文を言語に導入した。PolyPでの通常データ型はHaskellのデータ型のサブセットである。通常データ型tは* → *の種類でなければならず、もしaが定義における表面的な型の引数である場合は、tに対する全ての再帰呼び出しはt a形式でなければならない。これらの制約は、異なる形式の再帰呼び出しである入れ子のデータタイプと同様に、上位に種類付けされたデータ型を規定する。
PolyPの展開された関数はここに例として示される。
<pre>
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
</pre>
ジェネリック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の比較関数の一例として。
<pre>
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  :: Eq {[ k ]} t t
eq  _ _ = 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  = (==)
eq  = (==)
eq  = (==)
</pre>
決まり文句を捨てるアプローチ (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ジェネリクスの機能
型情報を削除せず、CLRの内部でジェネリクスが構築されるため(そしてコンパイラ上では全く構築しないため)、キャストや動的チェックの実行からくるパフォーマンスヒットがない。また、プログラマーはリフレクションを通じてジェネリック情報にアクセスできる。
型情報を削除しないので、Javaでは不可能なジェネリック型の配列の生成が可能。
ジェネリック型の引数として参照型だけでなく値型(組み込みの基本型、およびユーザー定義型の両方)も利用できる。値型の場合、JITコンパイラは特殊化のためにネイティブコードの新しいインスタンスを作成する。このことによりボックス化をする必要がなくなり、パフォーマンスが向上する。
Javaと同様、ジェネリック型引数がそれら自身のジェネリック型であるようにできる。つまり、List>>のような型は有効である。
C#(および一般の.NET)は、キーワードwhereを使用することで、値型/参照型、デフォルトコンストラクタの存在、親クラス、実装するインターフェイスなどでジェネリック型を制約することができる。
共変性と反変性をサポートしている。C# 4.0以降ではout修飾子またはin修飾子により、型パラメータを共変または反変にすることができる。これによって、ジェネリック型の代入と使用の柔軟性が向上する。
この例ではFirstIndexOfMaxメソッドの型パラメータTに対して、IComparable<T>インターフェイスを実装していなければならないという制約を指定している。このことにより、IComparable<T>インターフェイスのメンバであるCompareToメソッドが利用可能になっている。
C++/CLIは.NETのジェネリクスとC++のテンプレート両方をサポートする。ただしこれらの間に互換性はない。