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

ジェネリックプログラミング（英: generic programming）は、コンピュータプログラミングのための手法またはスタイルの一つである。特定のデータ型に依存しないプログラム記述を目的にしており、これを型（type）の総称化（generic）と呼ぶ。静的な機能であり、総称化された型はコンパイル時に特有化（specific）決定される。クラス定義、モジュール定義、関数定義のコード記述箇所で任意の型が総称化され、クラスのインスタンス化、モジュールのメモリ展開化、関数呼び出しのコード記述箇所で特有化される。型差分の重複コードを削減できるのが主な利点である。プログラミング言語組込の機能名としては、ジェネリクス（generics）やテンプレート（template）などと呼ばれる。

このスタイルのルーツは、1973年の関数型言語「ML」のパラメトリック多相であり、1983年の「Ada」のジェネリクス、1986年の「Eiffel」のジェネリシティ、1986年の「C++」のテンプレート導入を経て、1989年に計算機科学者デビッド・マッサーとアレクサンダー・ステパノフの両人が、正式にジェネリックプログラミングの名義で確立した。以降、SML・Haskell・Scala・Java・C#・D・Delphi・VB.net・F#・Rust・TypeScript・Python・Swiftなどの多数の言語仕様に採用されている。

特徴

ジェネリックとは、データ型を任意の抽象記号にしたソースコード記述をプログラマに許可し、コンパイラが一定の指定構文に従い、抽象記号箇所に適切なデータ型を自動的に当てはめて、中間表現コードを生成する仕組みを意味する。端的に言うとコンパイラによる型安全が保証されたパラメータ付きマクロと考えてもよい。その最大の利点は、対象データ型の部分だけが異なる重複コードをひとまとめにできる差分プログラミング的な効用である。例としてはdouble atof(char* c) int atoi(char* c) long atol(char* c)といった返り値の型が違うだけのコードをその型を総称化したT ato<T>(char* c)にまとめられる。ジェネリックの実装には標準方式、後付けジェネリック方式、テンプレートメタ方式、関数型言語方式の四つがあり、特有化インスタンス・型安全・型キャストの各性質に微妙な違いがある。

ジェネリッククラス

ジェネリッククラスは、その任意のメンバ変数の型、メンバ関数の引数/返り値の型、メンバ関数内のローカル変数の型を総称化できるクラス定義である。総称化された型は一般的に型パラメータ（type parameter）と呼ばれる。プレースホルダ（place holder）とも呼ばれる。型パラメータの宣言は<T> [T, U] template<typename T>のように大抵は角括弧が用いられてクラス名の隣に付記される。ジェネリッククラスのインスタンス化は、スペシフィックインスタンス化と呼ばれる。スペシフィックインスタンス化ではコンストラクタの隣に<int> [int]のように当てはめ型（applying type）を付記する。ここでは最も構文が平易なC#を例にする。

    public class GenTest<T> {
        private T mT;
        public GenTest(T pT) {
            mT = pT;
        }
    }

    GenTest<int> g1 = new GenTest<int>(1);  // int型でスペシフィックインスタンス化

ジェネリック関数

ジェネリック関数は、その引数/返り値の型、ローカル変数の型を総称化できる関数定義である。型パラメータの宣言は<T, U> [T] template<typename T>のように大抵は角括弧が用いられて関数名の隣に付記される。ジェネリック関数の呼び出しは、スペシフィックコールと呼ばれる。スペシフィックコールでは、引数が総称化対象ならば型推論によって関数呼び出し記述の実引数値がそのまま当てはめ型の指定になる。返り値とローカル変数が総称化対象ならば関数名の隣に<int> [int]のように当てはめ型を付記する。ここではジェネリック関数が最も多用されるC++を例にする。

template <typename T>
T max(T x, T y) {
  return x < y ? y : x;
}

std::cout << max(3, 7);  // int型でmaxをスペシフィックコール

パラメータ制約

制約（constraint）とは、型パラメータに当てはめられる型を、指定した型の派生型に限定する機能を指す。指定したクラスのサブクラスに限定する機能とも言い換えられる。型パラメータはその指定した型またはクラスで記号修飾されて宣言される。制約方式は、スーパークラスを指定してその派生クラスグループに限定するものと、値型/参照型/ポインタ型/数値型/実数型/配列型/構造体型/モジュール型/クラス型/インターフェース型/といったデータ性質を指定してそれに限定するものの二通りがある。型パラメータに当てはめる型が制約（constraint）外ならコンパイルエラーになる。これによって不正な当てはめ型を静的にチェックできるようになる。

イテレータ

イテレータは反復子とも邦訳され、ジェネリック化されたコレクションクラス（Array、List、Set、Mapなど）の収納要素を取り出す機能である。

共変性と反変性

共変性（covariance）とは、当てはめ型の継承関係をそのままジェネリッククラスの継承関係にシフトさせる機能を指している。反変性（contravariance）は、当てはめ型の継承関係を逆にしてシフトさせる。ここでList<T>をジェネリックラスとし、猫クラスを動物クラスのサブクラスとすると、共変性ではList<猫>はList<動物>のサブクラスになる。反変性ではList<動物>はList<猫>のサブクラスになる。

来歴

マッサーとステパノフは1989年の著作でジェネリックプログラミングをこのように定義している。

ジェネリックプログラミングは定型コードの抽象化に焦点を当てている。それは異なるデータ表現を結合する総称化アルゴリズムを獲得して、ソフトウェアの拡張を促進する。

このパラダイムの原点は、1973年公開の関数型言語「ML」のパラメトリック多相に求めることができる。これは型理論（型付きラムダ計算）に沿って、型の合成体としての型を扱うための仕組みであった。合成内の直積や直和といった構造パターンはデータ構築子で定義され、その構造パターン内の型要素を抽象代数（型変数）にしてその特有化は型構築子で定義される。型構築子に適用する型引数を変えることで一つの構造パターンを軸にした多様な型が生成される。その型付け値は引数として関数に適用され、パターンマッチングで抽象代数部分をその都度特定した。型構築子の考え方は、そのまま配列/構造体/データコンテナ/モジュールに応用できるものであった。しかしパラメトリック多相では型構築子の内部は総称化されるが、型構築子そのものを総称化するのは型付きラムダ計算理論の枠外になるので関数の引数/返り値を直接抽象代数にすることは出来なかった。この解決策として、型構築子（type constrcutor）を総称化子（generics）に置き換えたことが、パラメトリック多相とジェネリックプログラミングの分水嶺になっている。総称化子は1983年公開の手続き型言語「Ada」で初めて実装された。総称化子はパッケージ（モジュール）内の任意要素のデータ型をそのまま抽象記号化できて型安全が保証されるマクロに似た仕組みになり、これはプログラミング目的に特化された機能と言えた。ステパノフのこのように述べている。

ジェネリックプログラミングはアルゴリズムとデータ構造を抽象化して分類する。このアイディアはクヌース（文芸的プログラミングなどの提唱者）由来であって型理論ではない。

Adaのジェネリクス

1983年公開のAdaは、最初からジェネリクスを言語仕様に組み込んだ手続き型言語であった。ここではオブジェクト指向が導入される1995年以前のAdaのジェネリクスを対象にする。Adaは、データと手続きをまとめたモジュールをパッケージと呼んでおり、それを総称化したジェネリックパッケージを扱っている。パッケージ定義の冒頭でメンバ定数、メンバ変数の型、メンバ手続きの引数/返り値の型、メンバパッケージなどを型パラメータで総称化宣言できる。型パラメータは制約（constraint）で修飾できる。型パラメータには未指定時のデフォルト型も指定できる。ジェネリックパッケージの定義は以下のようになる。

generic
   Max_Size : Natural; -- 総称化で用いられる形式値
   type Element_Type is private; -- Element_Typeをlimited型以外OKの制約で総称型に
package Stacks is    -- Stackをジェネリックパッケージ宣言
   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;

ジェネリックパッケージのスペシフィックインスタンス化は以下のようになる。

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);
end Edit;

型パラメータは制約（constraint）で修飾できる。データ型性質の上位概念が「制約」になり、離散型、実数型、配列型、パッケージ型、アクセス型（ポインタ）などで当てはめ型を制約できる。制約もまた総称化できるので、総称化されたデータ型性質で制約を課すこともできる。その例は以下のようになる。

generic
   type Index_Type is (<>); -- discrete型のみOK
   type Element_Type is private; -- limited型以外OK
   type Array_Type is array (Index_Type range <>) of Element_Type;

この例でArray_Typeには、Element_Type制約下のデータ型を要素とし、Index_Type制約下のデータ型を添字とする配列型であるという制約を課している。プログラマがこのジェネリックパッケージをスペシフィックインスタンス化するには、その制約を満たす配列型を型パラメータに当てはめねばならない。

Eiffelのジェネリシティ

1986年公開のEiffelは、最初からジェネリシティを言語仕様に組み込んだオブジェクト指向言語である。クラスに総称化を取り入れた最も初期の言語である。ジェネリッククラスの定義は以下のようになる。

class
    LIST [G]
            ...
feature   -- Access
    item: G
            -- The item currently pointed to by cursor
            ...
feature   -- Element change
    put (new_item: G)
            -- Add `new_item' at the end of the list
            ...

ジェネリッククラスのスペシフィックインスタンス化は以下のようになる。

    list_of_accounts: LIST [ACCOUNT]
            -- Account list

    list_of_deposits: LIST [DEPOSIT]
            -- Deposit list

ジェネリッククラスの型パラメータは制約（constraint）で修飾できる。

class
    SORTED_LIST [G -> COMPARABLE]

C++のテンプレート

→詳細は「テンプレート (プログラミング)」を参照

C++では1986年からテンプレート機能が導入された。C++のテンプレートは、ソースコード・トランスレータの仕組みに沿ったテンプレートメタプログラミング方式の機能だったので、AdaやEiffelのジェネリックとは微妙な違いがあった。C++はテンプレートクラスとテンプレート関数をサポートし、C++11からテンプレートエイリアス、C++14からテンプレート変数も加えられた。パラメータ制約はない。1993年から発表された標準テンプレートライブラリ (STL) は、ジェネリックプログラミングの普及に最も貢献している。テンプレートクラスは以下のようになる。ここでは双方向連結リストをテンプレートクラスにしている。その要素の型をTとしている。<typename T>はテンプレートクラスのプレースホルダ（型パラメータ）の宣言である。

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;

テンプレート関数は以下のようになる。ここではスワップ関数をテンプレートにしている。

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!"

関数型言語のジェネリック

Standard MLのファンクタ

Standard MLで1988年頃に採用されたテンプレートメタ方式のジェネリックプログラミングの機能名はファンクタ（functor）と呼ばれた。

Haskellの型クラス

1990年に初版公開されたHaskellでは、関数オーバーロードおよび特定の型付け値を扱うための関数モジュールを、型推論の枠組み内で実装できるようにするためにジェネリックプログラミングが取り入れられた。静的な関数型言語のそれはパラメトリック多相と融合された型理論に沿ったものになり、Ada、Eiffel、C++などのジェネリックとは一線を画した方式になっている。Haskellのジェネリックの機能名は型クラス（type classes）と呼ばれ、型理論で言う文脈（context）と組み合わせられたものになっている。

型クラスは、総称型の値（型パラメータ）を引数/返り値/計算値として扱えるジェネリック関数群の関数の型（function type）と式内容（expressions）をそれぞれ定義できる構文である。型クラスの宣言名はそのまま文脈シンボルになって型構築子に付加できるものになる。型構築子＝値の型である。型構築子の定義構文で型クラス名を付加することがスペシフィックインスタンス化になり、型クラス構文で定義されたジェネリック関数群の関数の型と式内容の型パラメータ箇所にその型構築子を当てはめたものがコンパイル時に生成されることになる。加えてその型構築子のためのスペシフィック関数の式内容も個別定義できる。下記の例は二分木データ構造のパラメトリック多相化代数的データ型BinTreeの定義構文に、型クラスEq＆Showを付加して同時にスペシフィックインスタンス化している。なおパラメトリック多相化代数的データ型はこちらも「generalized algebraic datatype」と呼ばれているが、ジェネリックとは区別する必要がある。

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

Scalaのジェネリクス

2003年に初公開されたScalaの開発者である情報工学者マーティン・オーダスキーは、型理論と関数型プログラミングを専攻分野にしていたのでそのジェネリクスにバリアンスと型境界を取り入れている。バリアンスは圏論の共変関手と反変関手由来のものであり、ジェネリッククラス/トレイトの共変性と反変性の機能である。型境界は型理論の境界的量化子（bounded quantifier）由来のものであり、パラメータ制約を上限型境界と下限型境界に派生させた機能である。

Javaのジェネリクス

Javaでは、2004年のJ2SE 5.0からジェネリクス機能が導入された。それまでのJavaはジェネリックを堅牢性を損ねるものと見送っていたので大きな方針転換となったがその結果、旧バージョンとのバイトコード互換性維持を課せられた後付け実装方式を余儀なくされている。Javaは、ジェネリクスクラスとジェネリクスインターフェースとジェネリッククラスメソッド（=ジェネリック関数）をサポートしている。型パラメータには参照型（オブジェクト）のみ指定可能で、プリミティブ値は不可である。List<Integer>は可能だがList<int>は不可である。型パラメータはネスト可能である。型パラメータは、上限型境界（extends）と下限型境界（super）で修飾できる。

Javaのジェネリクスの特徴として、型パラメータに指定できるワイルドカード <?> がある。上限型境界と下限型境界で修飾できるワイルドカードは様々に応用される。ワイルドカードは型パラメータに当てはめられた型の判別を実行時まで遅延させる動的束縛型と同義である。旧バージョンとの互換性から、ランタイム時のジェネリクスインスタンスの型情報は、型パラメータ部分を省いたコンテナ部分だけが保持されている。これはコンパイル時のList<Integer>を、ランタイムシステム側はただのListと認識していることを意味する。その型パラメータ判別は、コンテナ要素の実行時型チェックによって代用されている。この仕組みは型消去（type erasure）と呼ばれている。これはジェネリックプログラミングの静的な解釈に便乗した実装方式であったが、共変反変バリアンスへの拡張を閉ざすことにもなった。ワイルドカードはその補填として用意されたものだったが、共変反変バリアンスとはまた違った性質での柔軟な拡張を可能にしている。ジェネリッククラスの例は以下のようになる。

List<String> v = new ArrayList<String>();
v.add("test");
Integer i = (Integer)v.get(0); // (type error)  compilation-time error

ジェネリックインターフェースは以下のようになる。

public interface List<E> { 
    void add(E x);
    Iterator<E> iterator();
}

public interface Iterator<E> { 
    E next();
    boolean hasNext();
}

C#のジェネリクス

C#も、Javaに倣った堅牢性方針からジェネリクスを見送っていたが、2005年のver2.0からジェネリクスを採用した。Javaのジェネリクスサポートはソースコードのコンパイル水準に留まり、Java仮想マシンのバイトコード水準の拡張まではなされなかった。それに対してC#は、Microsoft .NET Framework 2.0にも拡張を施してランタイムシステム水準からのジェネリクスサポートを整備した。これによってJavaでは出来なかった型パラメータへのプリミティブ値の適用、ジェネリクスが正確に反映されたインスタンスの型情報、ジェネリッククラスの共変性と反変性もサポートできるようになった。パラメータ制約とジェネリクスの入れ子のより自然な解釈も備わっている。C#のジェネリクスクラスは以下のようになる。

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++のテンプレート両方をサポートする。ただしこれらの間に互換性はない。

D言語のテンプレート

2006年に初公開されたD言語のテンプレート機能は、強力なテンプレートメタプログラミングの仕様を備えている。Dの言語仕様自体が、静的コンパイルと通常コンパイルの二段階のコード生成が前提という大きな特徴を備えている。従来のテンプレート機能がプレースホルダ（型パラメータ）に型を当てはめるだけなのに対して、Dのテンプレート機能は値とエイリアスパラメータも当てはめることができる。値とエイリアスパラメータが当てはめられたテンプレート記述は静的コンパイルの対象になり、柔軟なジェネリックコード生成を可能している。静的コンパイルは通常コンパイル前に行われるもので、テンプレート記述ソースをインタプリタ的に解釈していく機能と考えてもよい。値とエイリアスパラメータが用いられるテンプレート記述ソースではstatic-ifによる条件分岐と、静的コンパイル対象関数の再帰による反復処理も可能になっている。エイリアスパラメータは()付記で関数名になり、.付記で左辺がインスタンス名（変数名）右辺がメソッド名になる。エイリアスパラメータをゲッターにする静的コンパイル対象無名変数はヴォルデモート型と呼ばれる。静的コンパイル対象関数はtemplateの接頭キーワードで定義される。通常コンパイルのジェネリッククラスとジェネリック関数のプレースホルダ（型パラメータ）宣言は( )を用いる。D言語では一つの( )併記が通常関数で、二つの( )併記がジェネリック関数と見なされる。最初の( )がプレースホルダである。この書式はD言語のテンプレート重視方針の象徴でもある。スペシフィックインスタンス化では!( )を用いる。例としてC++のa<b>は、D言語ではa!(b)になる。

静的コンパイル対象関数の例。

template Factorial(ulong n) {
    static if (n <= 1)
        const Factorial = 1u;
    else
        const Factorial = n * Factorial!(n - 1);
}

エイリアスパラメータの例。

template wrapper(alias Fn) {
    // "extern(C)"インターフェイスでD言語の関数をラップする
    extern(C) void wrapper() {
        Fn();
    }
}

静的コンパイル対象関数は参照化して普通の関数からも使用できる。これは事実上の定数を扱っているのと同義になり実行速度向上に繋がる。ただしその分のコンパイル時間は増える。通常コンパイルで機械コードに落とし込む前に、静的コンパイルで出来ることは全部やっておこうというのがD言語の理念である。

void foo() {
    // ...
}

some_c_function(&wrapper!(foo));

関連項目

• テンプレートメタプログラミング
• ポリモーフィズム