ジェネリックプログラミング
ジェネリック(総称あるいは汎用)プログラミング(英: generic programming)は、具体的なデータ型に直接依存しない、抽象的かつ汎用的なコード記述を可能にするコンピュータプログラミング手法である。
概要
編集特徴
編集template<typename T>
class LinkedList {
public:
// 双方向連結リストのノード。
class Node {
friend class LinkedList;
public:
T value;
private:
Node* prev;
Node* next;
private:
Node() : value(), prev(), next() {}
explicit Node(const T& value, Node* prev = NULL, Node* next = NULL) : value(value), prev(prev), next(next) {}
~Node() {}
public:
Node* getPrev() { return this->prev; }
Node* getNext() { return this->next; }
};
private:
Node dummy;
public:
LinkedList() : dummy() {
this->dummy.prev = &this->dummy;
this->dummy.next = &this->dummy;
}
~LinkedList() { this->clear(); }
size_t getSize() const { /* ... */ }
Node* getHead() { return this->dummy.next; }
Node* getTail() { return this->dummy.prev; }
Node* getSentinel() { return &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);
if (node->prev) { node->prev->next = node->next; }
if (node->next) { node->next->prev = node->prev; }
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;
T
とする双方向連結リストの定義例である。typen
ame T
はテンプレートによる抽象化の対象となる型の名前︵プレースホルダー︶を表す。そしてこの定義されたクラステンプレートのインスタンス化、すなわち型パラメータT
に具象型を与えることによって生成されるクラス型は、T
について実際に指定した具象型のリストとして扱われる。これらの﹁T型のコンテナ﹂を一般にジェネリクス (generics) と呼び、ジェネリックプログラミングの代表的なテクニックである。プログラミング言語によって制約は様々だが、このテクニックは、継承関係やシグネチャといった制約条件 (constraint) を維持する限り、内包するT
にあらゆるデータ型を指定可能なクラスの定義を可能にする。これはジェネリックプログラミングの典型であり、一部の言語[要説明]ではこの形式のみを実装する。ただし、概念としてのジェネリックプログラミングはジェネリクスに限定されない。
オブジェクト指向プログラミング言語は、サブタイプ︵派生型︶でスーパータイプ︵基底型︶の振る舞い︵アルゴリズム︶をオーバーライドすることによる動的なポリモーフィズム︵多態性︶を備えており、動的な多態性もまたスーパータイプによる抽象化とサブタイプによる具象化[2]を実現するものだが、ジェネリクスは静的な多態性による抽象化と具象化を実現するという点で設計を異にする。
ジェネリックプログラミングのもう一つの応用例として、型に依存しないスワップ関数の例を示す。
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!"
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では、List
のようなコレクションに格納できる要素型はObject
のみであったため、要素取り出しの際には実際のサブクラス型への適切なキャストが必要だった。それに対し、ジェネリクスは静的な型付けについての利点を持ちながら動的な型付けの利点を完全ではないが得られる方法である。
Adaのジェネリクス
編集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;
利点と制限
編集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;
C++のテンプレート
編集C++のテンプレートは関数テンプレート、クラステンプレートをサポートするほか、C++14では変数テンプレートもサポートするようになった。C++のテンプレートは特に静的なダック・タイピングを可能にする点で強力であり、JavaやC#のジェネリクスと比べて柔軟性が高い一方、テンプレート引数に関する制約条件を明示的にコード上で記述できないことからコンパイルエラーメッセージが難解になりやすい。テンプレートはC++言語仕様の複雑化の要因にもなっている。
C++のStandard Template Library (STL) はテンプレートによる汎用的なアルゴリズムとデータ構造を提供する。
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のジェネリクス
編集List
<I
nteger
>
は正しいのに対して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
, Str
ing
>>
は有効な型である。
ワイルドカード
編集List
<?>
は無名のオブジェクト型を持つリストを表す。引数としてList<?>
を取るようなメソッドは任意の型のリストを取ることができる。リストからの読み出しはObject
型のオブジェクトを返し、そしてnullではない要素をリストへ書き込むことはパラメーター型が任意ではないために許されない。
ジェネリック要素の制約を指定するために、ジェネリック型が境界クラスのサブクラス︵クラスの拡張とインターフェイスの実装のいずれか︶であることを示すキーワードextends
を使用できる。そしてLi
st
<? extends Number
>
は与えられたリストがNu
mber
クラスを拡張するオブジェクトを保持することを意味する。従って、リストが何の要素の型を保持しているのかがわからないためにnullではない要素の書き込みが許されないのに対し、リストから要素を読むとNumber
が返るだろう。
ジェネリック要素の下限を指定するために、ジェネリック型が境界クラスのスーパークラスであることを示すキーワードsuper
が使用される。そしてList
<? super Number
>
はList
<N
umber
>
やList
<Object
>
でありえる。リストに正しい型を保存することが保証されるため任意のNumber
型の要素をリストに追加できるのに対し、リストからの読み出しではObject
型のオブジェクトを返す。
制約
編集new T[size];
経由のようにメソッドが型引数T
を持っていた場合はプログラマはその型の新しい配列を生成することができない。しかし、この制約はJavaのリフレクションのメカニズムを利用して回避することが可能である。クラスT
のインスタンスが利用可能な場合、T
に対応するClass
オブジェクトのオブジェクトから1つを得て、新しい配列を生成するためにjava.lang.reflect.Array.newInst
ance(Class, int)
を使うことができる。もう1つのJavaのジェネリクスの実装上の制約は、<?>
以外に、型パラメーターの型でジェネリッククラスの配列を生成することが不可能であるということだ。これは言語の配列の取り扱い方法に起因するものであり、タイプセーフを維持するために、明示的にキャストしなくともコンパイラが警告を出さないことを全てのコードで保証する必要があるからである。
Haskellのジェネリックプログラミング
編集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
編集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
編集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のジェネリックプログラミング
編集List<List<Diction
ary<int, int>>>
のような型は有効である。
●C#︵および一般の.NET︶は、キーワードwhere
を使用することで、値型/参照型、デフォルトコンストラクタの存在、親クラス、実装するインターフェイスなどでジェネリック型を制約することができる。
●共変性と反変性をサポートしている。C# 4.0以降ではout修飾子またはin修飾子により、型パラメータを共変または反変にすることができる。これによって、ジェネリック型の代入と使用の柔軟性が向上する。
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;
}
この例ではFirstIndexOfMax
メソッドの型パラメータT
に対して、IComparable<T>
インターフェイスを実装していなければならないという制約を指定している。このことにより、IComparable<T>
インターフェイスのメンバであるCompareTo
メソッドが利用可能になっている。
C++/CLIは.NETのジェネリクスとC++のテンプレート両方をサポートする。ただしこれらの間に互換性はない。
その他の言語のジェネリックプログラミング機能
編集脚注
編集- ^ Stanley B. Lippman. “Pure C++:Generic Programming Under .NET”. マイクロソフト・MSDNマガジン. 2008年12月28日閲覧。[リンク切れ]
- ^ 統一モデリング言語 (UML) の用語では、それぞれ汎化 (generalization) および特化 (specialization) と呼ぶ。
- ^ Verilog by Example, Section The Rest for Reference. Blaine C. Readler, Full Arc Press, 2011. ISBN 978-0-9834973-0-1