ポリモーフィズム

歴史

アドホック多相およびパラメータ多相という分類は、クリストファー・ストレイチーが1967年に講義ノートとして著したFundamental Concepts in Programming Languagesで初めて導入された。
このストレイチーの分類はPeter WegnerとLuca Cardelliが1985年に発表した論文のなかで拡張され、部分型や継承を説明するために包含多相という分類が導入された。 なお部分型付けや継承の実装自体は1967年に登場したSimulaから既に存在していた。

アドホック多相

関数や演算子の多重定義のように、同じ名前で型の異なる引数に適用できて、その振る舞いは引数の型によって違うような関数の多相性のことをアドホック多相という。「ad hoc（その場しのぎの）」という用語は悪い意味で使われているのではなく、単にこの種の多相性が型システムの基本的な機能ではないという事実を指して使われている。次のC++での例では、Add関数は呼び出し側からは様々な型に対して総称的に動作するかのように見えるが、コンパイラから見ればこれらは全く別個の2つの関数である。
#include <iostream>#include <string>int Add(int x, int y) {
    return x + y;}std::string Add(const std::string& s1, const std::string& s2) {
    return s1 + s2;}int main() {
    std::cout << Add(1, 2) << std::endl; // "3" が出力される。
    std::cout << Add("Hello, ", "World!") << std::endl; // "Hello, World!" が出力される。}
動的型付け言語では、実行されるべき正しい関数が実行時まで決定できない可能性があるという点で、状況はより複雑になりうる。
暗黙の型変換も型強制多相（coercion polymorphism）としてアドホック多相の一形態と定義される。

パラメータ多相

パラメータ多相を使うと、値の型に関係なく均一に値を扱うことで、関数やデータ型を総称的に記述できるようになる。パラメータ多相は言語の静的な型安全性を保ちながら表現力を向上させる手法のひとつである。
パラメータ多相の概念は関数とデータ型の両方に適用される。異なる型の値に対して評価、適用可能な関数のことを多相な関数という。総称化された型とみなすことができるデータ型（例えば任意の型の要素を持てるリスト）は多相なデータ型という。
パラメータ多相性は関数型プログラミングの分野では至るところに現れるため、しばしば単に「多相性」と言われることがある。次のHaskellの例ではパラメータ化されたリストと2つのパラメータ多相な関数を示す。
data List a = Nil | Cons a (List a)length :: List a -> Integerlength Nil         = 0length (Cons x xs) = 1 + length xsmap :: (a -> b) -> List a -> List bmap f Nil         = Nilmap f (Cons x xs) = Cons (f x) (map f xs)
パラメータ多相は様々なオブジェクト指向言語でも利用できる。例えばC++やD言語のテンプレート、JavaやC#のジェネリクスなどである。
class List<T> {
    class Node<T> {
        T elem;
        Node<T> next;
    }
    Node<T> head;
    int GetLength() { ... }}List<B> Map(Func<A, B> f, List<A> xs) {
    ...}
ジャン＝イヴ・ジラールとJohn C. Reynoldsは、それぞれ独立に、パラメータ多相の概念をラムダ計算の拡張（System Fとか多相ラムダ計算と呼ばれる）として形式的に発展させた。

部分型付け

いくつかのプログラミング言語では、特定の多相性の状況において使用できる型の範囲を制限するために部分型付け（部分型多相とも呼ばれる）を採用している。そういった言語で部分型付けを使用すると、ある型Tのオブジェクトを受け取る関数は、Tの部分型である型Sのオブジェクトを渡された場合でも正しく動作する（リスコフの置換原則）。この型の関係性はしばしばS <: Tと表記される。一般的に部分型多相は動的に解決される（後述）。
次のJavaの例ではAnimalの部分型としてCatとDogを用意する。メソッドletsHear()はAnimal型の引数を受け取るが、その部分型の引数を渡しても問題なく動作する。
abstract class Animal {
    abstract String talk();}class Cat extends Animal {
    String talk() {
        return "Meow!";
    }}class Dog extends Animal {
    String talk() {
        return "Woof!";
    }}class Test {
    static void letsHear(final Animal a) {
        System.out.println(a.talk());
    }
    public static void main(String[] args) {
        letsHear(new Cat());
        letsHear(new Dog());
    }}
オブジェクト指向言語はサブクラス化（継承）によって部分型多相を提供する。典型的な実装では、各クラスはそれぞれ仮想関数テーブル（vtable）と呼ばれる関数のテーブルを持ち、各オブジェクトは自らのクラスのvtableへのポインタを持つ。多相なメソッドを呼出すときには、このvtableを参照する。
多くのオブジェクト指向言語では、仮想関数の呼出しに1番目の引数（thisオブジェクト）の vtable だけを参照する単一ディスパッチを採用している。つまりその他の引数の実行時の型は仮想関数の呼び出しに全く無関係である。一方でCommon Lisp Object Systemなどでは、メソッドの呼出しが全ての引数に対して多相的となる多重ディスパッチを採用している。

静的ポリモーフィズムと動的ポリモーフィズム

ポリモーフィズムは実装がいつ選択されるかによって、静的（コンパイル時）か動的（実行時、典型的には仮想関数などを通して）かに区別できる。これはそれぞれ静的ディスパッチと動的ディスパッチとして知られ、さらにこれらに対応するポリモーフィズムはそれぞれ静的ポリモーフィズムと動的ポリモーフィズムと呼ばれる。
動的ディスパッチのオーバーヘッドが無いため、静的ポリモーフィズムはより高速に実行できるが、追加的なコンパイラの補助を必要とする。静的ポリモーフィズムではコンパイラやソースコード解析ツール、プログラマの目視による、より広範な静的解析（特に最適化）が可能となる。動的ポリモーフィズムはより柔軟だが速度はより遅くなる。例えば動的ディスパッチではダック・タイピングが可能で、動的にリンクされたライブラリはオブジェクトの型を知らなくても動作できるだろう。
典型的にはアドホック多相とパラメータ多相は静的ポリモーフィズムとして動作し、部分型多相は動的ポリモーフィズムとして動作する。しかし、奇妙に再帰したテンプレートパターンのような洗練されたテンプレートメタプログラミングを通して、部分型多相で静的ポリモーフィズムを実現することも可能である。