コンテンツにスキップ

「ジェネリックプログラミング」の版間の差分

出典: フリー百科事典『ウィキペディア(Wikipedia)』
削除された内容 追加された内容
Poshnegev (会話) による ID:86696849 の版を取り消し 英語版の記事en:Generic programmingの無断転載と思われる記述をすべてリバート。著作権の侵害。Wikipedia:翻訳のガイドライン, Wikipedia:ウィキペディア内でのコピー
タグ: 取り消し
Poshnegev (会話 | 投稿記録)
英語版の無断転載と言うなら、この記事全部がそれに当たります。歴史節も出典付きです。今後無茶なリバートはしないようにお願い申し上げます。
1行目: 1行目:
{{プログラミング・パラダイム}}
{{著作権問題調査依頼|date=2021-02}}
'''ジェネリック'''(総称あるいは汎用)'''プログラミング'''({{lang-en-short|generic programming}})は、具体的なデータ型に直接依存しない、抽象的かつ汎用的なコード記述可能にする[[プログラミング (コンピュータ)|コンピュータプログラミング]]手法である。
'''ジェネリックプログラミング'''({{lang-en-short|generic programming}})は、特定の[[データ型]]に依存しない汎用的な[[アルゴリズム]]実現する[[プログラミング]]手法である。アルゴリズムで扱われるデータ型の特定は、型パラメータで決定される。この手法は[[アルゴリズム]]と[[データ構造]]の機能的な分離を促進する。


== 概要 ==
== 概要 ==
6行目: 6行目:


1995年の書籍[[デザインパターン (ソフトウェア)|デザインパターン]]{{Full|date=2019年3月}}の共著者{{誰|date=2019年3月}}は(Ada、Eiffel、Java、[[C Sharp|C#]]の)ジェネリクスや、(C++の)[[テンプレート (プログラミング)|テンプレート]]としても知られるパラメータ化された型 (parameterized types) としてジェネリクスについて触れている。これらは、型を指定することなく、型を定義できるようにする(型は使用する時点で引数として与えられる)。このテクニック(特に[[デリゲート (プログラミング)|デリゲーション]]を組み合わせるとき)は非常に強力である。
1995年の書籍[[デザインパターン (ソフトウェア)|デザインパターン]]{{Full|date=2019年3月}}の共著者{{誰|date=2019年3月}}は(Ada、Eiffel、Java、[[C Sharp|C#]]の)ジェネリクスや、(C++の)[[テンプレート (プログラミング)|テンプレート]]としても知られるパラメータ化された型 (parameterized types) としてジェネリクスについて触れている。これらは、型を指定することなく、型を定義できるようにする(型は使用する時点で引数として与えられる)。このテクニック(特に[[デリゲート (プログラミング)|デリゲーション]]を組み合わせるとき)は非常に強力である。

== 歴史 ==
ジェネリックプログラミングは、計算機科学者{{仮リンク|デビッド・マッサー|en|David Musser|label=}}と{{仮リンク|アレクサンダー・ステパノフ|en|Alexander Stepanov|label=}}の1989年著書で確立されている。
定型プログラムの抽象化に焦点を当てているジェネリックプログラミングは、多様なデータ表現を結合させる汎用性の獲得によって従来アルゴリズムの効率性を高めて、ソフトウェアの多様性を促進させる<ref>{{cite book|url=http://stepanovpapers.com/genprog.pdf|title=Generic Programming|author1=Musser, David R.|author2=Stepanov, Alexander A.}}</ref>。
このパラダイムは、[[アルゴリズム]]と[[データ構造]]の機能的な分離によってプログラムの汎用性と再利用性を高めることを提唱しており<ref>{{Cite_web|url=http://msdn.microsoft.com/msdnmag/issues/05/04/PureC/|title=Pure C++:Generic Programming Under .NET|author=Stanley B. Lippman|publisher=[[マイクロソフト]]・[[MSDN]]マガジン|accessdate=2008-12-28|deadlinkdate=2019-03}}</ref>、[[抽象代数学|抽象代数]]理論との類似性も見られる<ref>{{cite book|author1=Alexander Stepanov|author2=Paul McJones|title=Elements of Programming|publisher=Addison-Wesley Professional|date=19 June 2009|isbn=978-0-321-63537-2}}</ref>。このパラダイムのルーツは、計算機科学者[[クリストファー・ストレイチー]]の1967年著書にある{{仮リンク|パラメトリック多相|en|Parametric polymorphism}}であり、こちらは「[[ML (プログラミング言語)|ML]]」などの[[関数型プログラミング|関数型言語]]で1970年代から実践されている。このパラダイムに相当する機能は、1970年代以降の「[[Scheme]]」「[[CLU]]」「[[Ada]]」「[[Eiffel]]」がジェネリクスなどの名称ですでに導入していた<ref>{{cite journal|year=1987|title=A library of generic algorithms in Ada|journal=Proceedings of the 1987 Annual ACM SIGAda International Conference on Ada|pages=216–225|doi=10.1145/317500.317529|isbn=0897912438|author1=Musser, David R.|author2=Stepanov, Alexander A.|citeseerx=10.1.1.588.7431|s2cid=795406}}</ref>。マッサーとステパノフによる形式化は言わば後付け理論であったが、[[オブジェクト指向プログラミング]]への応用を促進させた<ref>{{cite book|url=http://www.cse.chalmers.se/~patrikj/poly/afp98/genprogintro.pdf|title=Generic Programming – an Introduction|author1=Roland Backhouse|author2=Patrik Jansson|author3=Johan Jeuring|author4=Lambert Meertens|year=1999}}</ref>。[[ポリモーフィズム]]理論でのジェネリックプログラミングは、パラメトリック多相とはやや異なるポリタイピック (多相型) の方で説明され、[[圏論]]との親和性も認識された。

ジェネリックプログラミングは「[[C++]]」では、やや性質を変えた[[テンプレートメタプログラミング|テンプレート・メタプログラミング]]になり、[[標準テンプレートライブラリ]] (STL) として実装された<ref>Alexander Stepanov and Meng Lee: The Standard Template Library. HP Laboratories Technical Report 95-11(R.1), 14 November 1995</ref>。[[イテレータ|イテレーション]]の方法論もここで確立されている<ref>Matthew H. Austern: Generic programming and the STL: using and extending the C++ Standard Template Library. Addison-Wesley Longman Publishing Co., Inc. Boston, MA, USA 1998</ref>。ステパノフはこのように述べている。
ジェネリックプログラミングは、アルゴリズムとデータ構造の抽象化と分類体系化を推し進める。このインスパイアは[[ドナルド・クヌース|クヌース]]([[文芸的プログラミング]])からであり、[[型理論]]ではない<ref>{{cite book|url=http://stepanovpapers.com/history%20of%20STL.pdf|title=Short History of STL|author=Stepanov, Alexander}}</ref>。その目標は、抽象化されたアルコリズムとデータ構造の体系的なカタログ化による進歩的なソフトウェア構築である<ref name="stroustrup20072">{{cite book|url=http://www.stroustrup.com/hopl-almost-final.pdf|title=Evolving a language in and for the real world: C++ 1991-2006|author=Stroustrup, Bjarne|doi=10.1145/1238844.1238848|s2cid=7518369}}</ref>。
また、[[イテレータ]]についてはこのように強調している。
イテレータの理論は、数学での[[環論]]や[[バナッハ空間]]のような、計算機科学の中枢になると信じる<ref>{{Cite web|title=STLport: An Interview with A. Stepanov|url=http://www.stlport.org/resources/StepanovUSA.html|website=www.stlport.org|accessdate=2021-09-26}}</ref>。
ジェネリックプログラミングは様々に応用されており、それと{{仮リンク|アドホック多相|en|Ad hoc polymorphism}}を融合した[[型クラス]]が「[[Haskell]]」に登場して<ref>{{cite web|url=https://www.microsoft.com/en-us/research/wp-content/uploads/2003/01/hmap.pdf|title=Scrap Your Boilerplate: A Practical Design Pattern for Generic Programming|publisher=Microsoft|access-date=16 October 2016|author1=Lämmel, Ralf|author2=Peyton Jones, Simon}}</ref>[[モナド (プログラミング)|モナド]]の実践手段にもされた。「[[Scala]]」は、{{仮リンク|サブタイプ多相|en|Subtyping polymorphism}}でアレンジした[[共変性と反変性 (計算機科学)|共変性と反変性]]を導入している。「[[D言語]]」は、{{仮リンク|多段階メタプログラミング|en|Multi-stage programming}}を[[C++]]のテンプレートに融合した強力な[[テンプレートメタプログラミング|テンプレート]]機能を導入している。


== 特徴 ==
== 特徴 ==
206行目: 217行目:
*Adaでは特化を許容しないため[[テンプレートメタプログラミング]]はできない。
*Adaでは特化を許容しないため[[テンプレートメタプログラミング]]はできない。
:ただし仮パラメータに精密な制約を課することができるため、例えば、スワップ副プログラムを仮パラメータとして、[[ソート]]を目的とした汎用体の挙動をスワップ対象に応じて変化させたり、離散型の規定演算である大小判定を用いてMaxを実装するなど、特化の利点とされる目的の一部は他の方法により、達成することができる。
:ただし仮パラメータに精密な制約を課することができるため、例えば、スワップ副プログラムを仮パラメータとして、[[ソート]]を目的とした汎用体の挙動をスワップ対象に応じて変化させたり、離散型の規定演算である大小判定を用いてMaxを実装するなど、特化の利点とされる目的の一部は他の方法により、達成することができる。

== 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++のテンプレート==
251行目: 285行目:


some_c_function(&wrapper!(foo));
some_c_function(&wrapper!(foo));
</syntaxhighlight>

== Scalaのジェネリクス ==
2003年公開のScalaは、ジェネリックプログラミングとサブタイピングを融合した最初の言語であり、[[ミックスイン]]も融合している。それをサポートする[[共変性と反変性 (計算機科学)|共変性と反変性]]、上限型境界と下限型境界、関連型の機能を初めて導入している。ただし上限型境界は型制約(constraint)と同じものなのでこれは初導入ではない。

以下のコード例は、いわゆる連結リストの作成であり、リスト要素を共変性にして、appendメソッドの引数に反変性と下限型境界<code>>:</code>を用いている。<syntaxhighlight lang="scala">
trait Node[+B] {
def append[D >: B](elem: D): Node[D]
}

case class ListNode[+B](h: B, t: Node[B]) extends Node[B] {
def append[D >: B](elem: D): ListNode[D] = ListNode(elem, this)
def first: B = h
def second: Node[B] = t
}

case class Null[+B]() extends Node[B] {
def append[D >: B](elem: D): ListNode[D] = ListNode(elem, this)
}
</syntaxhighlight>
</syntaxhighlight>


272行目: 325行目:
Javaのジェネリクスの実装上の制約により、配列のコンポーネントの型が何であるべきかを特定する方法がないために、ジェネリック型の配列を作成することは不可能である。従って<code><nowiki>new T[size];</nowiki></code>経由のようにメソッドが型引数<code>T</code>を持っていた場合はプログラマはその型の新しい配列を生成することができない。しかし、この制約はJavaの[[リフレクション (情報工学)|リフレクション]]のメカニズムを利用して回避することが可能である。クラス<code>T</code>のインスタンスが利用可能な場合、<code>T</code>に対応する{{Javadoc:SE|java/lang|Class}}オブジェクトのオブジェクトから1つを得て、新しい配列を生成するために{{Javadoc:SE|name=java.lang.reflect.Array.newInstance(Class, int)|java/lang/reflect|Array|newInstance-java.lang.Class-int-}}を使うことができる。もう1つのJavaのジェネリクスの実装上の制約は、<code>&lt;?&gt;</code>以外に、型パラメーターの型でジェネリッククラスの配列を生成することが不可能であるということだ。これは言語の配列の取り扱い方法に起因するものであり、タイプセーフを維持するために、明示的にキャストしなくともコンパイラが警告を出さないことを全てのコードで保証する必要があるからである。
Javaのジェネリクスの実装上の制約により、配列のコンポーネントの型が何であるべきかを特定する方法がないために、ジェネリック型の配列を作成することは不可能である。従って<code><nowiki>new T[size];</nowiki></code>経由のようにメソッドが型引数<code>T</code>を持っていた場合はプログラマはその型の新しい配列を生成することができない。しかし、この制約はJavaの[[リフレクション (情報工学)|リフレクション]]のメカニズムを利用して回避することが可能である。クラス<code>T</code>のインスタンスが利用可能な場合、<code>T</code>に対応する{{Javadoc:SE|java/lang|Class}}オブジェクトのオブジェクトから1つを得て、新しい配列を生成するために{{Javadoc:SE|name=java.lang.reflect.Array.newInstance(Class, int)|java/lang/reflect|Array|newInstance-java.lang.Class-int-}}を使うことができる。もう1つのJavaのジェネリクスの実装上の制約は、<code>&lt;?&gt;</code>以外に、型パラメーターの型でジェネリッククラスの配列を生成することが不可能であるということだ。これは言語の配列の取り扱い方法に起因するものであり、タイプセーフを維持するために、明示的にキャストしなくともコンパイラが警告を出さないことを全てのコードで保証する必要があるからである。


==Haskellのジェネリプログラミング==
==C#のジェネリク==
C#(およびその他の.NET言語)のジェネリクスは.NET Framework 2.0の一部として2005年11月に追加された。Javaと似てはいるが、.NETのジェネリクスは、コンパイラによるジェネリクス型から非ジェネリクス型へのコンバートとしてではなく、実行時に実装される。このことにより、ジェネリクス型に関するあらゆる情報はメタデータとして保存される。
[[Haskell]]言語にはパラメータ化された型 (parameterized types)、パラメータ多相 (parametric polymorphism)、そしてJavaのジェネリクスやC++のテンプレートの両方に似たプログラミングのスタイルをサポートする型クラス (type classes) がある。Haskellプログラムではこれらの構文を様々なところで利用しており、避けることはかなり難しい。Haskellはまた、さらなるジェネリック性と、多態が提供する以上の再利用性を目指すようにプログラマーと言語開発者を奮起させる、さらに独特なジェネリックプログラミングの機能がある。

.NETジェネリクスの機能
*型情報を削除せず、[[共通言語ランタイム|CLR]]の内部でジェネリクスが構築されるため(そしてコンパイラ上では全く構築しないため)、キャストや動的チェックの実行からくるパフォーマンスヒットがない。また、プログラマーはリフレクションを通じてジェネリック情報にアクセスできる。
**型情報を削除しないので、Javaでは不可能なジェネリック型の配列の生成が可能。
*ジェネリック型の引数として参照型だけでなく値型(組み込みの基本型、およびユーザー定義型の両方)も利用できる。値型の場合、JITコンパイラは特殊化のためにネイティブコードの新しいインスタンスを作成する。このことにより[[ボックス化]]をする必要がなくなり、パフォーマンスが向上する。
*Javaと同様、ジェネリック型引数がそれら自身のジェネリック型であるようにできる。つまり、<code><nowiki>List<List<Dictionary<int, int>>></nowiki></code>のような型は有効である。
*C#(および一般の.NET)は、キーワード<code>where</code>を使用することで、値型/参照型、デフォルトコンストラクタの存在、親クラス、実装するインターフェイスなどでジェネリック型を制約することができる。
*[[共変性と反変性 (計算機科学)|共変性と反変性]]をサポートしている。C# 4.0以降ではout修飾子またはin修飾子により、型パラメータを共変または反変にすることができる。これによって、ジェネリック型の代入と使用の柔軟性が向上する。

<syntaxhighlight lang="csharp">
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;
}
</syntaxhighlight>

この例では<code>FirstIndexOfMax</code>メソッドの型パラメータ<code>T</code>に対して、<code><nowiki>IComparable<T></nowiki></code>インターフェイスを実装していなければならないという制約を指定している。このことにより、<code><nowiki>IComparable<T></nowiki></code>インターフェイスのメンバである<code>CompareTo</code>メソッドが利用可能になっている。

[[C++/CLI]]は.NETのジェネリクスとC++のテンプレート両方をサポートする。ただしこれらの間に互換性はない。

==Haskellの型クラス==
[[Haskell]]には、{{仮リンク|パラメトリック多相|en|Parametric polymorphism}}と[[テンプレートメタプログラミング]]の特徴を合わせたような[[型クラス]] (type class) がある。ただしHaskellの型クラスの本質は、データ型に付与する{{仮リンク|制約(mathematics)|en|Constraint (mathematics)|label=制約}}としての{{仮リンク|アドホック多相|en|Ad hoc polymorphism}}である。

型クラスの定義はこう書式される。<code>Eq</code>が型クラス、<code>a</code>が総称化された型変数である。演算子<code>==</code>と<code>/=</code>も総称化されたままである。

<pre>
class Eq a where
(==), (/=) :: a -> a -> Bool
</pre>型クラスのインスタンス化はこう書式される。<code>Point</code>は2つの<code>Double</code>型(<code>x</code>, <code>y</code>)を持つ型である。<code>Eq</code>で<code>Point</code>が制約され、演算子<code>==</code>と<code>/=</code>が<code>Point</code>で詳細化される。インスタンス化とは即ち、型の制約および関数/演算子の詳細化である。

<pre>
instance Eq Point where
(Pt x y) == (Pt x' y') = x == x' && y == y'
</pre>型構築子(データ型)の定義と型クラスのインスタンス化のセット書式もある。<code>deriving</code>によって<code>Eq</code>が<code>Point</code>に付与され、<code>==</code>と<code>/=</code>も詳細化される。なお、<code>deriving</code>による関数/演算子の詳細化は他に説明を要するがここでは割愛する。

<pre>
data Point = Pt Double Double deriving Eq
</pre>関数の定義の中で型クラスによる制約を付与する書式もある。<code>=></code>がそうである。この関数<code>sum</code>は型クラス<code>Num</code>で制約されたデータ型の配列のみを引数にする。

<pre>
sum :: Num a => [a] -> a
</pre>ここまでの説明でHaskellの型クラスは、関数/演算子オーバーロードのための手段であることが推論されるようになる。このオーバーロードは非常に融通が利くので、[[モナド (プログラミング)|モナド]]の実践などで活躍する。

'''Haskellの型クラスの特徴'''


Haskellの6つの事前定義された型クラス(同一性を比較できる<code>Eq</code>という型と、値を文字列に変換できる<code>Show</code>という型を含む)は''導出インスタンス'' (derived instances) をサポートしている特別なプロパティを持つ。プログラマーが新しい型を定義するということは、クラスのインスタンスを宣言するときに、普通であれば必要なクラスメソッドの実装を提供することなく、この型がこれらの特別型クラスのインスタンスとなることを明示できるということである。全ての必要なメソッドは型の構造に基づいて導出(つまり自動的に生成)される。
Haskellの6つの事前定義された型クラス(同一性を比較できる<code>Eq</code>という型と、値を文字列に変換できる<code>Show</code>という型を含む)は''導出インスタンス'' (derived instances) をサポートしている特別なプロパティを持つ。プログラマーが新しい型を定義するということは、クラスのインスタンスを宣言するときに、普通であれば必要なクラスメソッドの実装を提供することなく、この型がこれらの特別型クラスのインスタンスとなることを明示できるということである。全ての必要なメソッドは型の構造に基づいて導出(つまり自動的に生成)される。
288行目: 398行目:
<code>Eq</code>と<code>Show</code>の導出インスタンスへのサポートは、それらのメソッドである<code>==</code>と<code>show</code>を、パラメーター的な多態関数とは質的に異なるジェネリックにする。これらの"関数"(より正確には型でインデックス付けられた (type-indexed) 関数のファミリー)はたくさんの異なる型の値を受け入れることができ、各引数の型によってそれらは異なる動作をするが、新しい型へのサポートを追加するためにわずかな作業が必要とされる。Ralf Hinze氏 (2004) は、あるプログラミングテクニックによりユーザー定義型のクラスに対して同様の結果を達成できることを示した。彼以外の多くの研究者はこれと、Haskellの流れとは違う種類のジェネリック性やHaskellの拡張(下記参照)に対する取り組みを提案していた。
<code>Eq</code>と<code>Show</code>の導出インスタンスへのサポートは、それらのメソッドである<code>==</code>と<code>show</code>を、パラメーター的な多態関数とは質的に異なるジェネリックにする。これらの"関数"(より正確には型でインデックス付けられた (type-indexed) 関数のファミリー)はたくさんの異なる型の値を受け入れることができ、各引数の型によってそれらは異なる動作をするが、新しい型へのサポートを追加するためにわずかな作業が必要とされる。Ralf Hinze氏 (2004) は、あるプログラミングテクニックによりユーザー定義型のクラスに対して同様の結果を達成できることを示した。彼以外の多くの研究者はこれと、Haskellの流れとは違う種類のジェネリック性やHaskellの拡張(下記参照)に対する取り組みを提案していた。


'''「決まり文句を捨てる」アプローチ'''
=== PolyP ===

決まり文句を捨てるアプローチ (Scrap your boilerplate approach) は簡易的なジェネリックプログラミングのHaskellに対するアプローチである (Lämmel and Peyton Jones, 2003)。このアプローチはHaskellのGHC>=6.0の実装でサポートされる。このアプローチを使うことで、ジェネリックな読み込み、ジェネリックな明示、ジェネリックな比較(つまりgread、gshow、geq)と同様に、横断スキーム(例えばいつでもどこでも)のようなジェネリック関数をプログラマーは記述できる。このアプローチはタイプセーフなキャストとコンストラクタアプリケーションの実行のための一部の基本要素に基づいている。

=== PolyPの多相型 ===
PolyPはHaskellに対する最初のジェネリックプログラミング言語拡張であった。PolyPではジェネリック関数は''polytypic''と呼ばれた。通常データ型のパターン[[ファンクタ]]の構造によって構造的な導出を通じて定義できるpolytypic関数のような特別な構文を言語に導入した。PolyPでの通常データ型はHaskellのデータ型のサブセットである。通常データ型tは''* → *''の種類でなければならず、もし''a''が定義における表面的な型の引数である場合は、''t''に対する全ての再帰呼び出しは''t a''形式でなければならない。これらの制約は、異なる形式の再帰呼び出しである入れ子のデータタイプと同様に、上位に種類付けされたデータ型を規定する。
PolyPはHaskellに対する最初のジェネリックプログラミング言語拡張であった。PolyPではジェネリック関数は''polytypic''と呼ばれた。通常データ型のパターン[[ファンクタ]]の構造によって構造的な導出を通じて定義できるpolytypic関数のような特別な構文を言語に導入した。PolyPでの通常データ型はHaskellのデータ型のサブセットである。通常データ型tは''* → *''の種類でなければならず、もし''a''が定義における表面的な型の引数である場合は、''t''に対する全ての再帰呼び出しは''t a''形式でなければならない。これらの制約は、異なる形式の再帰呼び出しである入れ子のデータタイプと同様に、上位に種類付けされたデータ型を規定する。


337行目: 451行目:
</pre>
</pre>


==その他の言語==
===「決まり文句を捨てる」アプローチ===

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

.NETジェネリクスの機能
*型情報を削除せず、[[共通言語ランタイム|CLR]]の内部でジェネリクスが構築されるため(そしてコンパイラ上では全く構築しないため)、キャストや動的チェックの実行からくるパフォーマンスヒットがない。また、プログラマーはリフレクションを通じてジェネリック情報にアクセスできる。
**型情報を削除しないので、Javaでは不可能なジェネリック型の配列の生成が可能。
*ジェネリック型の引数として参照型だけでなく値型(組み込みの基本型、およびユーザー定義型の両方)も利用できる。値型の場合、JITコンパイラは特殊化のためにネイティブコードの新しいインスタンスを作成する。このことにより[[ボックス化]]をする必要がなくなり、パフォーマンスが向上する。
*Javaと同様、ジェネリック型引数がそれら自身のジェネリック型であるようにできる。つまり、<code><nowiki>List<List<Dictionary<int, int>>></nowiki></code>のような型は有効である。
*C#(および一般の.NET)は、キーワード<code>where</code>を使用することで、値型/参照型、デフォルトコンストラクタの存在、親クラス、実装するインターフェイスなどでジェネリック型を制約することができる。
*[[共変性と反変性 (計算機科学)|共変性と反変性]]をサポートしている。C# 4.0以降ではout修飾子またはin修飾子により、型パラメータを共変または反変にすることができる。これによって、ジェネリック型の代入と使用の柔軟性が向上する。

<syntaxhighlight lang="csharp">
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;
}
</syntaxhighlight>

この例では<code>FirstIndexOfMax</code>メソッドの型パラメータ<code>T</code>に対して、<code><nowiki>IComparable<T></nowiki></code>インターフェイスを実装していなければならないという制約を指定している。このことにより、<code><nowiki>IComparable<T></nowiki></code>インターフェイスのメンバである<code>CompareTo</code>メソッドが利用可能になっている。

[[C++/CLI]]は.NETのジェネリクスとC++のテンプレート両方をサポートする。ただしこれらの間に互換性はない。

==その他の言語のジェネリックプログラミング機能==
数多くの関数型言語はパラメータ化された型 (parameterized types) とパラメータ多相 (parametric polymorphism) の形で小規模なジェネリックプログラミングをサポートする。さらに標準MLとOCamlはクラステンプレートとAdaのジェネリックパッケージに似たファンクタを提供する。
数多くの関数型言語はパラメータ化された型 (parameterized types) とパラメータ多相 (parametric polymorphism) の形で小規模なジェネリックプログラミングをサポートする。さらに標準MLとOCamlはクラステンプレートとAdaのジェネリックパッケージに似たファンクタを提供する。


385行目: 460行目:


== 関連項目 ==
== 関連項目 ==
* [[総称型]]
* [[イテレータ]]
* [[ポリモーフィズム]]
*[[ポリモーフィズム]]
* [[ダック・イピング]]
* [[テンプレートメプログラミング]]
*[[部分評価]]


{{Normdaten}}
{{Normdaten}}{{プログラミング言語の関連項目}}
{{DEFAULTSORT:しえねりつくふろくらみんく}}
{{DEFAULTSORT:しえねりつくふろくらみんく}}
[[Category:ソフトウェア工学]]
[[Category:ソフトウェア工学]]

2021年11月25日 (木) 04:27時点における版

ジェネリックプログラミング: generic programming)は、特定のデータ型に依存しない汎用的なアルゴリズムを実現するプログラミング手法である。アルゴリズムで扱われるデータ型の特定は、型パラメータで決定される。この手法はアルゴリズムデータ構造の機能的な分離を促進する。

概要

ジェネリックプログラミングはデータ型でコードをインスタンス化するのか、あるいはデータ型をパラメータとして渡すかということにかかわらず、同じソースコードを利用できる[1]。ジェネリックプログラミングは言語により異なる形で実装されている。ジェネリックプログラミングの機能は1970年代にCLUAdaのような言語に搭載され、次にBETAC++DEiffelJava、その後DECTrellis/Owl言語などの数多くのオブジェクトベース (object-based) およびオブジェクト指向 (object-oriented) 言語に採用された。

1995年の書籍デザインパターン[要文献特定詳細情報]の共著者[誰?]は(Ada、Eiffel、Java、C#の)ジェネリクスや、(C++の)テンプレートとしても知られるパラメータ化された型 (parameterized types) としてジェネリクスについて触れている。これらは、型を指定することなく、型を定義できるようにする(型は使用する時点で引数として与えられる)。このテクニック(特にデリゲーションを組み合わせるとき)は非常に強力である。

歴史

ジェネリックプログラミングは、計算機科学者デビッド・マッサー英語版アレクサンダー・ステパノフ英語版の1989年著書で確立されている。

定型プログラムの抽象化に焦点を当てているジェネリックプログラミングは、多様なデータ表現を結合させる汎用性の獲得によって従来アルゴリズムの効率性を高めて、ソフトウェアの多様性を促進させる[2]

このパラダイムは、アルゴリズムデータ構造の機能的な分離によってプログラムの汎用性と再利用性を高めることを提唱しており[3]抽象代数理論との類似性も見られる[4]。このパラダイムのルーツは、計算機科学者クリストファー・ストレイチーの1967年著書にあるパラメトリック多相英語版であり、こちらは「ML」などの関数型言語で1970年代から実践されている。このパラダイムに相当する機能は、1970年代以降の「Scheme」「CLU」「Ada」「Eiffel」がジェネリクスなどの名称ですでに導入していた[5]。マッサーとステパノフによる形式化は言わば後付け理論であったが、オブジェクト指向プログラミングへの応用を促進させた[6]ポリモーフィズム理論でのジェネリックプログラミングは、パラメトリック多相とはやや異なるポリタイピック (多相型) の方で説明され、圏論との親和性も認識された。

ジェネリックプログラミングは「C++」では、やや性質を変えたテンプレート・メタプログラミングになり、標準テンプレートライブラリ (STL) として実装された[7]イテレーションの方法論もここで確立されている[8]。ステパノフはこのように述べている。

ジェネリックプログラミングは、アルゴリズムとデータ構造の抽象化と分類体系化を推し進める。このインスパイアはクヌース文芸的プログラミング)からであり、型理論ではない[9]。その目標は、抽象化されたアルコリズムとデータ構造の体系的なカタログ化による進歩的なソフトウェア構築である[10]

また、イテレータについてはこのように強調している。

イテレータの理論は、数学での環論バナッハ空間のような、計算機科学の中枢になると信じる[11]

ジェネリックプログラミングは様々に応用されており、それとアドホック多相英語版を融合した型クラスが「Haskell」に登場して[12]モナドの実践手段にもされた。「Scala」は、サブタイプ多相英語版でアレンジした共変性と反変性を導入している。「D言語」は、多段階メタプログラミング英語版C++のテンプレートに融合した強力なテンプレート機能を導入している。

特徴

ジェネリックプログラミングの特徴は、型を抽象化してコードの再利用性を向上させつつ、静的型付け言語の持つ型安全性を維持できることである。

ジェネリックプログラミングを用いない場合、例えば伝統的なC言語Pascalのような従来の静的型付け言語において、ソートなどのアルゴリズムや連結リストのようなデータ構造(オブジェクトのコンテナ)を記述する際は、たとえ対象となる要素のデータ型が異なるだけで事実上同一のコードであったとしても、具体的なデータ型ごとにそれぞれ実装しなければならない。整数型のリスト、倍精度浮動小数点数型のリスト、文字列型のリスト、ユーザー定義構造体のリスト、……といった具合である。もしジェネリックプログラミングをサポートしない言語で汎用的なコードを記述して再利用しようと思えば、メモリ空間効率や型安全性などを犠牲にしなければならなくなる(共用体や汎用ポインタ型とキャストを駆使するなど)。一方、C++の関数テンプレートやクラステンプレートのように、ジェネリックプログラミングを用いることで、抽象化された型について一度だけ記述したアルゴリズムやデータ構造をさまざまな具象データ型に適用して、コードを型安全に再利用できるようになる。これがジェネリックプログラミングの利点の一例として挙げられる。

以下にC++の例を示す。

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とする双方向連結リストの定義例である。typename Tはテンプレートによる抽象化の対象となる型の名前(プレースホルダー)を表す。そしてこの定義されたクラステンプレートのインスタンス化、すなわち型パラメータTに具象型を与えることによって生成されるクラス型は、Tについて実際に指定した具象型のリストとして扱われる。これらの「T型のコンテナ」を一般にジェネリクス (generics) と呼び、ジェネリックプログラミングの代表的なテクニックである。プログラミング言語によって制約は様々だが、このテクニックは、継承関係やシグネチャといった制約条件 (constraint) を維持する限り、内包するTにあらゆるデータ型を指定可能なクラスの定義を可能にする。これはジェネリックプログラミングの典型であり、一部の言語[要説明]ではこの形式のみを実装する。ただし、概念としてのジェネリックプログラミングはジェネリクスに限定されない。

オブジェクト指向プログラミング言語は、サブタイプ(派生型)でスーパータイプ(基底型)の振る舞い(アルゴリズム)をオーバーライドすることによる動的なポリモーフィズム(多態性)を備えており、動的な多態性もまたスーパータイプによる抽象化とサブタイプによる具象化[13]を実現するものだが、ジェネリクスは静的な多態性による抽象化と具象化を実現するという点で設計を異にする。

ジェネリックプログラミングのもう一つの応用例として、型に依存しないスワップ関数の例を示す。

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

上記の例で使用した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では、Listのようなコレクションに格納できる要素型はObjectのみであったため、要素取り出しの際には実際のサブクラス型への適切なキャストが必要だった。それに対し、ジェネリクスは静的な型付けについての利点を持ちながら動的な型付けの利点を完全ではないが得られる方法である。

Adaのジェネリクス

Adaには1977年-1980年の設計当初から汎用体 (generics) が存在する。標準ライブラリでも多くのサービスを実装するために汎用体を用いている。Ada2005では1998年に規格化されたC++のStandard Template Library (STL) の影響を受けた広範な汎用コンテナが標準ライブラリとして追加された。

汎用体 (generic unit) とは、0または複数の汎用体仮パラメータ (generic formal parameters) を採るプログラム単位(パッケージまたは副プログラム)である。

汎用体仮パラメータとしては、オブジェクト(変数・定数)、データ型、副プログラム、パッケージ,さらには他の汎用体のインスタンスさえ指定することができる。汎用体仮パラメータのデータ型としては、離散 (discrete) 型、浮動小数点数型、固定小数点数型、アクセス(ポインタ)型などを用いることができる。

汎用体をインスタンス化する際、プログラマは全ての仮パラメータに対応する実パラメータを指定する必要があるが、プログラマが明示的に全ての実パラメータを指定しなくても済むよう,仮パラメータにはデフォルトを指定することもできる。インスタンス化してしまえば,汎用体のインスタンスは、汎用体ではない通常のプログラム単位であるかのように振舞う。インスタンス化は実行時、例えばループの中などで行うことも可能である。

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;

利点と制限

Adaの言語構文では、汎用体仮パラメータとして何を許容するか、精密に制約条件を課することができる。例えば実パラメータとしてはモジュラー型(任意の上限で巡回する符号なし整数型)のみを許容するように、仮パラメータとして指定することも可能である。さらには汎用体仮パラメータ間に一定の制約があるように規制することも可能である。例えば、

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;

この例でArray_Typeには、Element_Typeに対応する特定のデータ型を要素とし、Index_Typeに対応する特定の離散型の部分型を添字とする配列型でなければならないという制約を課している。プログラマがこの汎用体をインスタンス化する際には、同制約を満足する配列型を実パラメタとして渡さなければならない。

構文の複雑さに難はあるものの、精密な制約が表現できることで、汎用体仮パラメータの全ては仕様部として完全に定義される。このため、コンパイラは汎用体本体がなくても汎用体をインスタンス化することができる(もちろん本体がないとリンクはできない)。

C++と異なってAdaでは暗黙的な特化による汎用体のインスタンス化を許さないため、全ての汎用体は明示的にインスタンス化することが必要である。この規則により以下のような結果が生じる。

  • コンパイラは共有ジェネリクス (shared generics) を実装できる。すなわち、ある汎用体のオブジェクトコードは全インスタンスで共有できる(もちろんプログラマが副プログラムのインライン化を要求しない限り)。さらなる結果として、
    • コードが肥大化する可能性がない(コードの肥大化はC++では一般的であり後述のように特別な配慮が求められる)。
    • インスタンス化の都度に新たなオブジェクトコードを生成することは不要であるため、コンパイル時のみならず、実行時に汎用体をインスタンス化することができる。
    • 汎用体仮オブジェクトに対応する実オブジェクトは、たとえ同実オブジェクトが静的である(コンパイル時に値が確定する)としても、汎用体本体中では常に静的ではないものとみなされる。詳細についてはWikibookのGeneric formal objectsを参照。
  • ある汎用体の全インスタンスは全く同一であるため、他人の作成したプログラムをレビューしたり、理解することが容易である。配慮すべき「特別な場合」はないのだから。
  • 全てのインスタンス化は明示的であり、プログラムの理解が困難となるような暗黙的なインスタンス化はない。
  • Adaでは特化を許容しないためテンプレートメタプログラミングはできない。
ただし仮パラメータに精密な制約を課することができるため、例えば、スワップ副プログラムを仮パラメータとして、ソートを目的とした汎用体の挙動をスワップ対象に応じて変化させたり、離散型の規定演算である大小判定を用いてMaxを実装するなど、特化の利点とされる目的の一部は他の方法により、達成することができる。

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++のテンプレートは関数テンプレート、クラステンプレートをサポートするほか、C++14では変数テンプレートもサポートするようになった。C++のテンプレートは特に静的なダック・タイピングを可能にする点で強力であり、JavaやC#のジェネリクスと比べて柔軟性が高い一方、テンプレート引数に関する制約条件を明示的にコード上で記述できないことからコンパイルエラーメッセージが難解になりやすい。テンプレートはC++言語仕様の複雑化の要因にもなっている。

C++のStandard Template Library (STL) はテンプレートによる汎用的なアルゴリズムとデータ構造を提供する。

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

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

Scalaのジェネリクス

2003年公開のScalaは、ジェネリックプログラミングとサブタイピングを融合した最初の言語であり、ミックスインも融合している。それをサポートする共変性と反変性、上限型境界と下限型境界、関連型の機能を初めて導入している。ただし上限型境界は型制約(constraint)と同じものなのでこれは初導入ではない。

以下のコード例は、いわゆる連結リストの作成であり、リスト要素を共変性にして、appendメソッドの引数に反変性と下限型境界>:を用いている。

trait Node[+B] {
  def append[D >: B](elem: D): Node[D]
}

case class ListNode[+B](h: B, t: Node[B]) extends Node[B] {
  def append[D >: B](elem: D): ListNode[D] = ListNode(elem, this)
  def first: B = h
  def second: Node[B] = t
}

case class Null[+B]() extends Node[B] {
  def append[D >: B](elem: D): ListNode[D] = ListNode(elem, this)
}

Javaのジェネリクス

2004年、J2SE 5.0の一部としてJavaにジェネリクスが追加された。C++のテンプレートとは違い、Javaコードのジェネリクスはジェネリッククラスの1つのコンパイルされたバージョンだけを生成する。ジェネリックJavaクラスは型パラメータとしてオブジェクト型だけを利用できる(基本型は許されない)。従ってList<Integer>は正しいのに対して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, String>>は有効な型である。

ワイルドカード

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

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

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

制約

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

C#のジェネリクス

C#(およびその他の.NET言語)のジェネリクスは.NET Framework 2.0の一部として2005年11月に追加された。Javaと似てはいるが、.NETのジェネリクスは、コンパイラによるジェネリクス型から非ジェネリクス型へのコンバートとしてではなく、実行時に実装される。このことにより、ジェネリクス型に関するあらゆる情報はメタデータとして保存される。

.NETジェネリクスの機能

  • 型情報を削除せず、CLRの内部でジェネリクスが構築されるため(そしてコンパイラ上では全く構築しないため)、キャストや動的チェックの実行からくるパフォーマンスヒットがない。また、プログラマーはリフレクションを通じてジェネリック情報にアクセスできる。
    • 型情報を削除しないので、Javaでは不可能なジェネリック型の配列の生成が可能。
  • ジェネリック型の引数として参照型だけでなく値型(組み込みの基本型、およびユーザー定義型の両方)も利用できる。値型の場合、JITコンパイラは特殊化のためにネイティブコードの新しいインスタンスを作成する。このことによりボックス化をする必要がなくなり、パフォーマンスが向上する。
  • Javaと同様、ジェネリック型引数がそれら自身のジェネリック型であるようにできる。つまり、List<List<Dictionary<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++のテンプレート両方をサポートする。ただしこれらの間に互換性はない。

Haskellの型クラス

Haskellには、パラメトリック多相英語版テンプレートメタプログラミングの特徴を合わせたような型クラス (type class) がある。ただしHaskellの型クラスの本質は、データ型に付与する制約英語版としてのアドホック多相英語版である。

型クラスの定義はこう書式される。Eqが型クラス、aが総称化された型変数である。演算子==/=も総称化されたままである。

class Eq a where
  (==), (/=) :: a -> a -> Bool

型クラスのインスタンス化はこう書式される。Pointは2つのDouble型(x, y)を持つ型である。EqPointが制約され、演算子==/=Pointで詳細化される。インスタンス化とは即ち、型の制約および関数/演算子の詳細化である。

instance Eq Point where
  (Pt x y) == (Pt x' y') = x == x' && y == y'

型構築子(データ型)の定義と型クラスのインスタンス化のセット書式もある。derivingによってEqPointに付与され、==/=も詳細化される。なお、derivingによる関数/演算子の詳細化は他に説明を要するがここでは割愛する。

data Point = Pt Double Double deriving Eq

関数の定義の中で型クラスによる制約を付与する書式もある。=>がそうである。この関数sumは型クラスNumで制約されたデータ型の配列のみを引数にする。

sum :: Num a => [a] -> a

ここまでの説明でHaskellの型クラスは、関数/演算子オーバーロードのための手段であることが推論されるようになる。このオーバーロードは非常に融通が利くので、モナドの実践などで活躍する。

Haskellの型クラスの特徴

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

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

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

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

EqShowの導出インスタンスへのサポートは、それらのメソッドである==showを、パラメーター的な多態関数とは質的に異なるジェネリックにする。これらの"関数"(より正確には型でインデックス付けられた (type-indexed) 関数のファミリー)はたくさんの異なる型の値を受け入れることができ、各引数の型によってそれらは異なる動作をするが、新しい型へのサポートを追加するためにわずかな作業が必要とされる。Ralf Hinze氏 (2004) は、あるプログラミングテクニックによりユーザー定義型のクラスに対して同様の結果を達成できることを示した。彼以外の多くの研究者はこれと、Haskellの流れとは違う種類のジェネリック性やHaskellの拡張(下記参照)に対する取り組みを提案していた。

「決まり文句を捨てる」アプローチ

決まり文句を捨てるアプローチ (Scrap your boilerplate approach) は簡易的なジェネリックプログラミングのHaskellに対するアプローチである (Lämmel and Peyton Jones, 2003)。このアプローチはHaskellのGHC>=6.0の実装でサポートされる。このアプローチを使うことで、ジェネリックな読み込み、ジェネリックな明示、ジェネリックな比較(つまりgread、gshow、geq)と同様に、横断スキーム(例えばいつでもどこでも)のようなジェネリック関数をプログラマーは記述できる。このアプローチはタイプセーフなキャストとコンストラクタアプリケーションの実行のための一部の基本要素に基づいている。

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のもう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の比較関数の一例として。

   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 |} = (==)

その他の言語

数多くの関数型言語はパラメータ化された型 (parameterized types) とパラメータ多相 (parametric polymorphism) の形で小規模なジェネリックプログラミングをサポートする。さらに標準MLとOCamlはクラステンプレートとAdaのジェネリックパッケージに似たファンクタを提供する。

Verilogのモジュールは1つ以上のパラメタを取ることができる。パラメタの実際の値は、そのモジュールを実体化する際に与えられる。一例としてジェネリックなレジスタアレイがあり、アレイの幅がパラメタで与えられている。そのようなアレイをジェネリックなワイヤベクトルと組み合わせることにより、単一のモジュール実装を用いて任意のビット幅を持つジェネリックなバッファやメモリを作ることができる。[14]

脚注

  1. ^ Stanley B. Lippman. “Pure C++:Generic Programming Under .NET”. マイクロソフトMSDNマガジン. 2008年12月28日閲覧。
  2. ^ Musser, David R.; Stepanov, Alexander A.. Generic Programming. http://stepanovpapers.com/genprog.pdf 
  3. ^ Stanley B. Lippman. “Pure C++:Generic Programming Under .NET”. マイクロソフトMSDNマガジン. 2008年12月28日閲覧。
  4. ^ Alexander Stepanov; Paul McJones (19 June 2009). Elements of Programming. Addison-Wesley Professional. ISBN 978-0-321-63537-2 
  5. ^ Musser, David R.; Stepanov, Alexander A. (1987). “A library of generic algorithms in Ada”. Proceedings of the 1987 Annual ACM SIGAda International Conference on Ada: 216–225. doi:10.1145/317500.317529. ISBN 0897912438. 
  6. ^ Roland Backhouse; Patrik Jansson; Johan Jeuring; Lambert Meertens (1999). Generic Programming – an Introduction. http://www.cse.chalmers.se/~patrikj/poly/afp98/genprogintro.pdf 
  7. ^ Alexander Stepanov and Meng Lee: The Standard Template Library. HP Laboratories Technical Report 95-11(R.1), 14 November 1995
  8. ^ Matthew H. Austern: Generic programming and the STL: using and extending the C++ Standard Template Library. Addison-Wesley Longman Publishing Co., Inc. Boston, MA, USA 1998
  9. ^ Stepanov, Alexander. Short History of STL. http://stepanovpapers.com/history%20of%20STL.pdf 
  10. ^ Stroustrup, Bjarne. Evolving a language in and for the real world: C++ 1991-2006. doi:10.1145/1238844.1238848. http://www.stroustrup.com/hopl-almost-final.pdf 
  11. ^ STLport: An Interview with A. Stepanov”. www.stlport.org. 2021年9月26日閲覧。
  12. ^ Scrap Your Boilerplate: A Practical Design Pattern for Generic Programming”. Microsoft. 16 October 2016閲覧。
  13. ^ 統一モデリング言語 (UML) の用語では、それぞれ汎化 (generalization) および特化 (specialization) と呼ぶ。
  14. ^ Verilog by Example, Section The Rest for Reference. Blaine C. Readler, Full Arc Press, 2011. ISBN 978-0-9834973-0-1

関連項目