コンセプトは滅びぬ！何度でもよみがえるさ！コンセプトの力こそC++erの夢だからだ！

C++

有名なあのセリフをいじってみたら、結構ハマっていたので、そのまま記事のタイトルにしました。過度な期待をされた方、ごめんなさい。ネタはタイトルだけです…

はじめに

これはC++11 Advent Calendar 2011の16日目の記事です。17日目の担当は、@yak_exさんです。Advent Calendarに参加するのは、これが初めてです。よろしくお願い致します。
この記事では、C++11の主要な機能の１つになるはずだった、コンセプトの入門的な紹介をします。皆さんもご存知のとおり、2009年７月のフランクフルト会議においてコンセプトは委員会草案から削除され、C++11ではコンセプトを使用できません。なので、ただ単に業務でC++11を使えるようになりたい方にとっては、コンセプトを勉強する価値はあまり無いかもしれません。ただ、コンセプトの概念を知ることによって、C++プログラミングの、更に一つ上の高みへとレベルアップできるのでは、と思います。
コンセプトは、C++におけるジェネリック・プログラミングを支える重要な概念であり、多くの（中毒的な）C++プログラマの夢によって、次の規格で必ずや復活するはず！ただ、C++の型システムにおける基礎に関わることなので、コンセプトが使えるようになるまでに、少なくとも５年単位の時間がかかりそうです。
この記事では、コンセプトが記載された最後の規格書ドラフトN2914の記述に基づいて説明します。詳細は、N2914の307頁から始まる14 Templates、386頁から始まる14.10 Concepts、408頁から始まる14.11 Constrained templatesを参照して下さい。

C++03のテンプレートにおける課題とは何か？

C++03のテンプレートの課題として以下のものが挙げられるかと思います：

  1. テンプレート定義時に、仮引数が備えるべきインタフェースが意識されないこと
  2. テンプレート実引数にヘンテコな型を渡しても、テンプレートが実体化されるまで、コンパイラのエラー検知が遅れること
  3. 冗長なエラーメッセージ

まず、テンプレートを定義する際は、テンプレート仮引数を使って記述していきますが、その記述の中には、その仮引数が特定のインタフェースを備えていることを前提としている場合がほとんどです。例えば、次のコードを考えてみましょう：

template< typename T >
void f( const T& t )
{
    t.g();
    t.h();
}

このテンプレート定義では、テンプレート仮引数Tが、メンバ関数としてg()、h()を備えていることを前提として書かれています。しかし、templateキーワードに続けて仮引数Tを宣言する際に、仮引数Tがそのようなインタフェースを備えていることを明示する手段がありません。

そのため、定義されたテンプレートを使うとき、前提となるインターフェースをもたない型をテンプレート実引数として渡しても、コンパイラが直ちにエラーを検出できないのです。コンパイラは不適切な型を渡されても、とりあえず何でも鵜呑みにして、渡された実引数に基づいてテンプレートを実体化します。その際に実引数の型が、テンプレート定義の中で使用されているインタフェースに適合しないことを知って、その段階で初めてエラー検出となるのです。例えば、次のコードを考えてみましょう：

class X
{
public:
    int g_() const {}
    void h( int i ) {}
};

int main()
{
    X x;
    f( x );

    return 0;
}

クラスXはメンバ関数としてg_()、h(int)を備えていますが、そのどちらもf()のテンプレート仮引数Tの前提となるインタフェースを備えていません。g_()は関数名が異なりますし、h(int)は引数の型（及び関数のconst指定）が一致しません。また、エラー検出がテンプレートの実体化まで遅れるため、実装に使用された全てのテンプレートが全ての実引数の列挙と共に、エラーメッセージに含まれることになります。不適切な型をテンプレート実引数として渡した際に（特に、STLにおいて）とても読みづらいエラーメッセージが出力される原因はこれだったのです。
以上を反省してみると、テンプレート引数に対して前提となる（インタフェースなどの）要件を、明示的に指定する枠組みが必要だと感じませんか？もし、そのようなことができたら、テンプレートを定義時に、仮引数が備えるべきインタフェースから逸脱する関数呼び出しがあったとしても、コンパイルエラーになるため嫌でもそれを意識するようになります。また、テンプレート実引数に不適切な型が渡されても、前提となる要件をその型が満足していなければ、コンパイラは直ちにエラーを検知できます。しかも、テンプレート実体化の前にエラーを検知できるので、エラーメッセージは短く、しかもエラー解決のために適切なものとなるに違いありません。
そのような「テンプレート引数に対して前提となる要件」のことを「コンセプト」といい、C++0xではコンセプトを強力にサポートする機能が提案されていたのです。コンセプトのサポートによって、ジェネリック・プログラミングに堅固な基礎づけが与えられ、新しい可能性のフロンティアを形成するはずでした。

コンセプトに関連する主要な概念

コンセプトをどのように使うのか、を説明する前に、主な登場人物を紹介します：

  • コンセプト
  • コンセプトマップ
  • constrained template

「コンセプト」とは、テンプレート引数に対する要件（使用できる関数、ネストした型など）をまとめたものです。粗っぽく言うと、コンセプトとは「型を記述するメタな型」であると考えることもできます。コンセプトによって、ジェネリック・プログラミングに（メタな）型安全の概念が導入されるのです。
「コンセプトマップ」とは、コンセプトと実在する型を関連づけるものです。コンセプトは、ただ定義しただけでは意味がありません。（コンセプトに適合する）実在する型を対応づけることによって、コンセプトは型を記述するメタな型となるのです。JavaやC#においてインタフェースが、定義されただけで他のクラスから実装されなければ、意味がないのと少しだけ状況が似ています。また、コンセプトマップの定義時に、関連付けられる型がコンセプト要件を満足できない場合は、コンパイルエラーになります。
最後の「constrained template」は、C++03のテンプレートを少しいじっただけで、テンプレート仮引数に対するコンセプト要件を明示的に指定するだけです。仮引数が、コンセプト要件で許可されていないもの（関数呼び出し、ネストした型など）を使用した場合は、コンパイルエラーになります。
当然、テンプレート実引数に、コンセプトに適合しない型が渡された場合も、コンパイルエラーになります。このように、コンセプトがもたらす型安全の考え方に基づいて、何重にもエラーチェックが行われます。このチェックをパスすれば、テンプレート実体化でエラーになることは、ほとんどありません。
constrained templateのこなれた訳語が思い付かなかった（制限テンプレート、束縛テンプレート…？）ので、草案そのままです。単語「constrain」は「制限する・束縛する」といった意味で、テンプレート引数をコンセプトに適合するものに制限する…、そのままです。なお、C++03のテンプレートは「unconstrained template」といい、従来どおり使用できます。その場合はコンセプトに基づくエラーチェックを行わず、コンパイラは従来どおり振る舞います。

C++0xのコンセプトは、どのように課題を解決するのか？

まず、次のコードを見て下さい：

#include <iostream>

concept C< typename T >
{
    int T::f() const;
    typename nested_type;
};

class X
{
public:
    int f() const { return 2011; }
};

concept_map C< X >
{
    typedef bool nested_type;
};

template< typename T > requires C< T >
void f( const T& t )
{
    int result = t.f();
    std::cout << result << std::endl;
}

int main()
{
    X x;
    f( x );

    return 0;
}

まず、コンセプトを定義します。キーワードconceptに続けて、コンセプト名C、テンプレート仮引数リスト< typename T >を並べ、その後にコンセプトの本体が続きます。C< typename T >は、型Tに対する要件としてのコンセプトCを表しています。コンセプトの本体では、関数T::f()（associated functionという）、型名nested_type（associated typeという）が指定されています。これにより、コンセプトCに適合する型Tは、メンバ関数f()、ネストした型nested_typeを備えなければなりません。
次に、コンセプトCに適合する型を定義します。クラスXは、メンバ関数f()をもっていますが、ネストした型nested_typeがありません。このままでは、この型はコンセプトCを満足しません。
そこで、コンセプトマップを定義します。コンセプトC< T >の型Tはテンプレート仮引数であり、コンセプトCは実在する型と関連付ける必要があること、及び型X（のシンタックス）をコンセプトCに適合させること、がその理由です。キーワードconcept_mapに続けて、定義済みのコンセプト名C、テンプレート実引数リスト< X >を並べ、その後にコンセプトマップの本体が続きます。C< X >は、型Xが上で定義したコンセプトCに適合することを表しています。コンセプトマップの本体では、typedefを使って型名nested_typeを宣言しており、クラスXの定義時に漏れていた型名を、補っています。コンセプト要件を１つでも満足できない場合（例えば、nested_typeをtypedefしなかった場合）はコンパイルエラーになります。なお、generic-programming.orgによると「model」という単語は（型がコンセプトを）満足するという意味の動詞として、また、コンセプト要件を満足する型のセットを意味する名詞として、使われるそうです。
そして、最終的な目的である型安全なテンプレート、constrained templateを記述します。C++03のテンプレートと異なるのは、template< typename T >の後にrequires C< T >が付加されただけです。キーワードrequiresと共に、C< T >は仮引数TがコンセプトCに適合することを指定しています。これにより、仮引数Tに対する実引数として、コンセプトCに適合する型を強制できます。また、コンセプトCが要求する（仮引数Tの）メンバ関数f()を使って、テンプレート定義が記述されています。なお、テンプレート定義の中で、コンセプトCで指定されていない関数呼び出しやネストした型を使用すると、コンパイルエラーになります。

次の２つのコードは、同じ意味になります（simple form）：

template< typename T > requires C< T >
void f( const T& t )
{
    int result = t.f();
    std::cout << result << std::endl;
}

template< C T > // コンセプトCに適合する仮引数T
void f( const T& t )
{
    int result = t.f();
    std::cout << result << std::endl;
}

requires節では、複数のコンセプト要件や、否定的なコンセプト要件（negative requirement）を記述できます：

template< typename T > requires C< T > && D< T >
void f( const T& t )
{
}

// コンセプトCに適合しない仮引数T
template< typename T > requires !C< T >
void f( const T& t )
{
}

なお、||演算子を使用することはできません。コンセプトが提案された初期には認められていました（requires C< T > || D< T >と書くと、排他的な選言が適用）が、この機能は後に削除されました。

コンセプトマップの必要性

先ほどの例では、コンセプトを満足するためには型Xに不足していた型名nested_typeを、コンセプトマップで補うだけでした。しかし、現実には実在する型が、コンセプト要件とはかけ離れたシグネチャの関数やネストした型をもっている場合も多いでしょう。テンプレートの既存テクニックとして、こういった型をラップする型を別に定義する方法がありますが、あまりスマートではありません。この問題を、言語の機能として本質的に解決するものが、コンセプトマップなのです。例えば、次のコードを考えてみましょう：

#include <iostream>

concept C< typename T >
{
    void print( const T& );
};

class X
{
public:
    int get() const { return 2011; }
};

concept_map C< X >
{
    void print( const X& x ) { std::cout << x.get() << std::endl; }
};

template< typename T > requires C< T >
void f( const T& t )
{
    print( t );
}

int main()
{
    X x;
    f( x );

    return 0;
}

このサンプルでは、大域関数print()を備える型を表すコンセプトC、及びメンバ関数get()をもつクラスXを定義しています。ここで、関数テンプレートf()の中で、コンセプトCに適合する型Tを引数として、大域関数print()を呼び出したいとします。この場合、存在しなかった大域関数print()をコンセプトマップ内で定義することで、型Xに関するシンタックスをコンセプトCに適合するように曲げているのです。そうして初めて、型XはコンセプトCの要件を満たすことができ、あたかも大域関数print()があるかのように振る舞うのです。
syntax adaptionと呼ばれているコンセプトマップのこの機能は、既存の型のシンタックスを変更することなく、コンセプトが要求するシンタックスに適合させます。また、generic-programming.orgでは、この機能をretroactive modelingと呼んでいます。コンセプトマップは、コンセプトと実在する型を関連付けるため、そして実在する型がコンセプトに適合するために不足している要件を（もしあれば）補うために存在します。
Bjarne Stroustrupも指摘しているとおり、syntax adaptionの機能は必須であり、コンセプトマップの必要性に疑う余地はありません。ただ、コンセプトに適合する型を定義する毎に、いちいちコンセプトマップを書くのは面倒です。本来意図された用途から逸脱しますが、この機能を更に拡張することで（constrained context限定で）C#の拡張メソッドと似たようなことができるかもしれません。

autoによる暗黙のコンセプト

特に、型定義によって何も加えなくてもコンセプトを満足する場合、コンセプトマップの本体は空になり、わざわざ書いていられません。そこで、コンセプト定義の際にキーワードautoを使うことで、何も加えなくてもこのコンセプトを満足する型に対して、自動的に適合するように指定できます。型が自動的にコンセプトに適合する場合は、コンセプトマップを使って、明示的にその型をコンセプトに関連づける必要がありません。例えば、次のコードを考えてみましょう：

auto concept C< typename T >
{
    int T::f();
    void T::g();
};

class X
{
public:
    int f() {}
    void g() {}
};

// コンセプトマップC< X >を定義する必要はない

template< typename T > requires C< T >
void f( T& t )
{
    t.f();
    t.g();
}

int main()
{
    X x;
    f( x );

    return 0;
}

キーワードconceptの前にある、キーワードautoに注意して下さい。これによって、メンバ関数int f()及びvoid g()を備える型は、自動的にコンセプトCに適合します。そのような型に対して、わざわざコンセプトマップを書く必要はありません。この機能は、必要になった時にコンパイラが、暗黙のコンセプトマップを定義することで実現されています。
autoが指定され、暗黙のコンセプトマップが自動的に生成されるコンセプトを「暗黙のコンセプト（implicit concept）」と呼ぶ一方、明示的にコンセプトマップを書く必要があるコンセプトは「明示的なコンセプト（explicit concept）」といいます。暗黙のコンセプトと明示的なコンセプトによって顕在化した言語思想の相違は、後々にコンセプトが委員会草案から削除される原因の１つになったと思われます。

concept map template

ところで、コンセプトマップはテンプレートにできます。キーワードtemplate、テンプレート仮引数リストに続けて、コンセプトマップを記述するだけです。concept map templateとsyntax adaptionを組み合せることで、コンセプトマップが持つ潜在的な力の一部を見ることができます。例えば、次のコードを考えてみましょう：

#include <vector>
#include <iostream>
#include <ios>

concept stack< typename T >
{
    typename value_type;

    void       push ( T&, const value_type& );
    void       pop  ( T& );
    value_type top  ( const T& );
    bool       empty( const T& );
};

template< typename T >
concept_map stack< std::vector< T > >
{
    typedef T value_type;

    void push ( std::vector< T >& v, const T& x ) { v.push_back( x ); }
    void pop  ( std::vector< T >& v )             { v.pop_back(); }
    T    top  ( const std::vector< T >& v )       { return v.back(); }
    bool empty( const std::vector< T >& v )       { return v.empty(); }
};

template< typename T > requires stack< T >
void f( T& t, T::value_type x )
{
    push( t, x ); push( t, x ); push( t, x );
    std::cout << std::boolalpha << empty( t ) << std::endl;

    pop( t ); pop( t ); pop( t );
    std::cout << std::boolalpha << empty( t ) << std::endl;
}

int main()
{
    std::vector< int > v;
    f( v, 2011 );

    return 0;
}

このサンプルでは、ネストした型value_type、及び大域関数push()、pop()、top()、empty()を備える型を表すコンセプトstackを定義しています。今回は、このコンセプトstackに、std::vector< T >を適合させたいとします。std::vector< T >の様々なテンプレート引数に対応するため、キーワードconcept_mapの前に、template< typename T >を置いてテンプレート化しています。更に、コンセプトマップの本体では、テンプレート仮引数Tを使ってstd::vector< T >のシンタックスを、コンセプトstackのそれに適合させています。これによって、任意の型Tに対してstd::vector< T >はコンセプトstackを満足し、関数テンプレートf()の第１引数として渡すことができるようになります。

複数のテンプレート引数をもつコンセプト

最初に定義したコンセプトC< T >は、単一の仮引数Tに対する要件を表していました。しかし、現実には複数の型に対してコンセプト要件を指定したいことも多くあります。そのような場合、複数の仮引数に対する要件として、コンセプトを定義します。例えば、次のコードを考えてみましょう：

#include <iostream>
#include <ios>

auto concept convertible< typename T, typename U >
{
    operator U( const T& );
    U::U( const U& ); // 返却値から一時オブジェクトをコピー初期化するため
}

template< typename U, typename T > requires convertible< T, U >
U convert( const T& t )
{
    return t;
}

int main()
{
    std::cout << std::fixed << convert< double >( 2011 ) << std::endl;
    // std::cout << convert< int* >( 2011.0 ) << std::endl; // エラー

    return 0;
}

このサンプルでは、引数型Tから引数型Uへの変換演算子を要件とする（暗黙の）コンセプトconvertibleを定義しています。コンセプトconvertibleの仮引数が< typename T, typename U >と複数であることに注意して下さい。コンセプト本体では、これらの仮引数を使って変換演算子を宣言しています。
そして、関数テンプレートconvert()では引数をそのまま返していますが、その際、返却値の型Uへと暗黙の変換が行われます。テンプレート仮引数が< typename U, typename T >と、順序が逆になっていることに注意して下さい。コンパイラに、関数の仮引数からテンプレート仮引数Tを推論させるためには、仮引数Tの宣言が右端にある必要があるのです。
main()では実際にconvert()を使って、int型の値をdouble型に変換しています。なお、double型からint*型への標準変換は無いため、コメントアウトした行を有効にすると、コンパイルエラーになります。

nested requirement

コンセプト定義の本体において、ある型が他のコンセプトに適合することを要件として含めたい場合があります。そのような場合は、nested requirementを使用します。例えば、次のコードを考えてみましょう：

#include <ostream>
#include <cstddef>
#include <iostream>

auto concept regular< typename T >
{
    T::T();
    T::~T();
    T::T( const T& );
    T& T::operator=( const T& );
    bool operator==( const T& a, const T& b );
    bool operator!=( const T& a, const T& b ) { return !( a == b ); }
};

concept iterator< typename T >
{
    requires regular< T >;

    typename value_type;
    typename difference_type;
    typename pointer;
    typename reference;

    reference operator*( T& );
    T& operator++( T& );
    T  operator++( T&, int );
    pointer operator->( const T& );

    // std::cout に出力するため
    std::ostream& operator<<( std::ostream&, reference );
    operator int( difference_type );
};

template< typename T >
concept_map iterator< T* >
{
    typedef T              value_type;
    typedef std::ptrdiff_t difference_type;
    typedef T*             pointer;
    typedef T&             reference;
};

template< typename T > requires iterator< T >
void f( T first, T last )
{
    for ( T i = first ; i != last ; ++i )
        std::cout << *i << std::endl;
}

int main()
{
    int ia[] = { 1, 2, 3, 4, 5 };
    f( ia, ia + 5 );

    return 0;
}

このサンプルでは、イテレータを表すコンセプトiteratorを定義しようとしています。まず、通常よく使われる型が適合している（暗黙の）コンセプトregularを定義します。このコンセプトに適合する型は、デフォルトコンストラクタ、デストラクタ、コピーコンストラクタ、コピー代入演算子、==演算子、!=演算子を備えています。!=演算子にはデフォルトの実装を与えており、必要になった時にコンパイラが使用します。
次に、コンセプトiteratorを定義しますが、１つ目のコンセプト要件にあるrequires節によって、他のコンセプトから追加的な要件をまるごと引き込んでいます。キーワードrequiresに続くregular< T >は、追加的な要件として型Tがコンセプトregularに適合することを表しています。結果として、コンセプトiteratorの定義内に、コンセプトregularの本体を（仮引数を実引数で置換して）そのまま移したような結果が得られます。
なお、コンセプトiteratorの本体では、イテレータ備えるべき型や関数を指定しています。その後でconcept map templateの、部分特殊化に似た構文によって、任意のポインタ型をコンセプトiteratorに適合させています。これによって、main()で確保したint配列をテンプレート関数f()に渡すことができます。

次の２つのコードは、同じ意味になります（simple form）：

concept D< typename T>
{
    C nested_type;
};

concept D< typename T>
{
    typename nested_type;
    requires C< nested_type >;
};

axiom

これまで扱ってきたコンセプト要件は、使用できる関数・ネストした型など、テンプレート仮引数のシンタックスに対するものでした。これとは対照的に、テンプレート引数のセマンティクスに係る要件を定めるものがaxiomです。「axiom」は、数学用語で「公理」と訳され、理論の枠組みを構築する際に基礎となる（その枠組みで常に真であるような）命題を意味します。axiomの記述方法が、数学における公理に似ているところから、この名前が付いたものと思われます。
コンセプト本体において、キーワードaxiomに続けて、axiom名、仮引数宣言を並べ、その後にaxiomの本体が続きます。axiomの本体では、当該コンセプトに満足させたいセマンティクス要件を（主に、==演算子を使って）記述します。例えば、次のコードを考えてみましょう：

auto concept copy_constructible< typename T >
{
    T::T( const T& );

    axiom copy_preservation( T x )
    {
        T( x ) == x;
    }
};

concept semigroup< typename Op, typename T > : copy_constructible< T >
{
    T operator()( Op, T, T );

    axiom associativity( Op op, T x, T y, T z )
    {
        op( x, op( y, z ) ) == op( op( x, y ), z );
    }
};

concept monoid< typename Op, typename T > : semigroup< Op, T >
{
    T identity_element( Op );

    axiom identity( Op op, T x )
    {
        op( x, identity_element( op ) ) == x;
        op( identity_element( op ), x ) == x;
    }
};

このサンプルでは、半群・モノイドを表すコンセプトsemigroup・monoidを定義しています。半群・モノイドについては、半群・モノイド [物理のかぎしっぽ]を参照して下さい。まず、コピーコンストラクト可能を表すコンセプトcopy_constructibleを定義しています。コピーコンストラクタをもつシンタックス要件に加えて、copy_preservation()では、コピー後の等値性というセマンティクス要件を指定しています。
次に、半群を表すコンセプトsemigroup< Op, T >を定義していますが、仮引数Opは半群上で定義される演算、仮引数Tは半群の元を表す型です。: copy_constructible< T >の部分はこの後すぐに解説しますので、今のところは無視して下さい。operator()は、Op(T, T)の構文で演算Opを適用するための、シンタックス要件です。加えて、associativity()によって、演算Opが結合律を満たすための、セマンティクス要件を指定しています。
最後に、モノイドを表すコンセプトmonoid< Op, T >を定義していますが、テンプレート仮引数の意味はコンセプトsemigroupのそれと同様です。うすうす感づいているとは思いますが、: semigroup< Op, T >の部分もとりあえず無視して下さい。identity_element()は、モノイドの単位元（恒等元）を返す大域関数です。そして、identity()によって、その単位元の振る舞いに対するセマンティクス要件を指定しています。

axiomでは、条件付きセマンティクス（conditional semantics）を、if文を使って記述できます。例えば、全順序を表すコンセプトtotal_orderを考えてみましょう：

concept total_order< typename Op, typename T >
{
    // Op(T, T)の構文で演算Opを適用するため
    bool operator()( Op, T, T );

    // 反対称律
    axiom antisymmetry( Op op, T x, T y )
    {
        if ( op( x, y ) && op( y, x ) )
            x == y;
    }

    // 遷移律
    axiom transitivity( Op op, T x, T y, T z )
    {
        if ( op( x, y ) && op( y, z ) )
            op( x, z ) == true;
    }

    // 「全」順序性（任意の２元に対して、順序が定義される）
    axiom totality( Op op, T x, T y )
    {
        ( op( x, y ) || op( y, x ) ) == true;
    }
};

テンプレート仮引数Opは順序関係を表す述語、仮引数Tは全順序集合の元を表す型です。各コンセプト要件については、コメントを参照して下さい。antisymmetry()とtransitivity()では、if文の条件が真である場合に限り、２つの式の等値性を記述しています。
コンセプト本体で、==演算子と!=演算子が宣言されていなければ、axiom内でこれらの演算子が暗黙的に宣言されます。また、axiomで２つの式の等値性を記述した場合、コンパイラがこれを最適化に活用することができます。ただし、最適化に活用され得ること以外は、axiomの記述は観測可能なプログラムの振る舞いに影響しません。セマンティクスに係るこれらの情報は、IDE等において最適化、検証、テスト、その他の解析・変換に使用されます。

concept refinement

concept refinementとは、クラスにおける継承に対応するものです。単語「refine」は「洗練する・精製する」といった意味で、例えば「oil refinery」は「製油所」と訳されます。コンセプトにおける「D refines B」は、クラスにおける「D inherits B」に対応しており、Dのことを「more refined concept」、Bのことを「less refined concept」といいます。
クラスDがクラスBを継承する場合に、クラスBのメンバを全て自動的に引き継ぐように、more refined conceptはless refined conceptの要件を全て自動的に引き継ぎます。また、コンセプトBの要件はコンセプトDのそれの部分集合になっているため、コンセプトDに適合する型は明示的にコンセプトマップを書かなくても、自動的にコンセプトBにも適合します。concept refinementによって、コンセプト間にis-a階層関係を導入することができるのです。例えば、次のコードを考えてみましょう：

#include <ostream>
#include <cstddef>
#include <iostream>

auto concept equality_comparable< typename T >
{
    bool operator==( const T& a, const T& b );
    bool operator!=( const T& a, const T& b ) { return !( a == b ); }

    axiom consistency( T a, T b )
    {
        ( a == b ) == !( a != b );
    }

    axiom reflexivity( T a ) { a == a; }

    axiom symmetry( T a, T b )
    {
        if ( a == b ) b == a;
    }

    axiom transitivity( T a, T b, T c )
    {
        if ( a == b && b == c ) a == c;
    }
};

auto concept less_than_comparable< typename T >
{
    bool operator< ( const T& a, const T& b );
    bool operator> ( const T& a, const T& b ) { return b < a; }
    bool operator<=( const T& a, const T& b ) { return !( b < a ); }
    bool operator>=( const T& a, const T& b ) { return !( a < b ); }

    axiom consistency( T a, T b )
    {
        ( a > b ) == ( b < a );
        ( a <= b ) == !( b < a );
        ( a >= b ) == !( a < b );
    }

    axiom irreflexivity( T a ) { ( a < a ) == false; }

    axiom antisymmetry( T a, T b )
    {
        if ( a < b )
            ( b < a ) == false;
    }

    axiom transitivity( T a, T b, T c )
    {
        if ( a < b && b < c )
            ( a < c ) == true;
    }

    axiom transitivity_of_equivalence( T a, T b, T c )
    {
        if ( !( a < b ) && !( b < a ) && !( b < c ) && !( c < b ) )
            ( !( a < c ) && !( c < a ) ) == true;
    }
};

auto concept regular< typename T >
{
    T::T();
    T::~T();
    T::T( const T& );
    T& T::operator=( const T& );

    requires equality_comparable< T >;
};

concept iterator< typename T >
{
    requires regular< T >;

    typename value_type;
    typename difference_type;
    typename pointer;
    typename reference;

    reference operator*( T& );
    T& operator++( T& );
    T  operator++( T&, int );
    pointer operator->( const T& );

    // std::cout に出力するため
    std::ostream& operator<<( std::ostream&, reference );
    operator int( difference_type );
};

concept forward_iterator< typename T > : iterator< T >
{
    axiom multi_pass( T a, T b )
    {
        if ( a == b ) *a == *b;
        if ( a == b ) ++a == ++b;
    }
};

concept bidirectional_iterator< typename T > : forward_iterator< T >
{
    T& operator--( T& );
    T  operator--( T&, int );
};

concept random_access_iterator< typename T > : bidirectional_iterator< T >
{
    T& operator+=( T&, difference_type );
    T  operator+ ( const T& t, difference_type n ) { T tmp( t ); tmp += n; return tmp; }
    T  operator+ ( difference_type n, const T& t ) { T tmp( t ); tmp += n; return tmp; }
    T& operator-=( T&, difference_type );
    T  operator- ( const T& t, difference_type n ) { T tmp( t ); tmp -= n; return tmp; }

    difference_type operator-( const T&, const T& );
    T& operator[]( const T& t, difference_type n );

    requires less_than_comparable< T >;
};

template< typename T >
concept_map random_access_iterator< T* >
{
    typedef T              value_type;
    typedef std::ptrdiff_t difference_type;
    typedef T*             pointer;
    typedef T&             reference;
};

template< typename T > requires iterator< T >
void f( T first, T last )
{
    for ( T i = first ; i != last ; ++i )
        std::cout << *i << std::endl;
}

template< typename T > requires random_access_iterator< T >
void g( T first, T last )
{
    std::cout << "size: " << last - first << std::endl;
}

int main()
{
    int ia[] = { 1, 2, 3, 4, 5 };
    f( ia, ia + 5 );
    g( ia, ia + 5 );

    return 0;
}

このサンプルでは、上で紹介したコンセプトiteratorを拡張して

random_access_iterator -> bidirectional_iterator -> forward_iterator

という、イテレータのis-a階層関係を定義しようとしています。最初に、equality_comparable、less_than_comparable、regularといった、よく使用されるコンセプトを記述します。equality_comparable、less_than_comparableのいくつかの演算子関数では、デフォルトの実装を与えており、必要になった時にコンパイラが使用します。そして、上で紹介したコンセプトiteratorを定義し、これをrefineして各アクセス特性に対応するイテレータコンセプトを記述します。
まずは、前進イテレータを表すコンセプトforward_iteratorです。キーワードconceptに続けて、コンセプト名forward_iterator、テンプレート仮引数リスト< typename T >を並べ（ここまでは、通常のコンセプト定義と同じ）、その後にコロン:、refineされるコンセプト名iterator、テンプレート実引数リスト< T >、そしてコンセプトforward_iteratorの本体が続きます。concept refinementの文法は、クラス継承のそれと似ています。: iterator< T >の部分に注目して下さい。
コンセプトforward_iteratorでは、追加のシンタックス要件はありません。multi_pass()により、コンテナの同じ地点を何度でも掃過するためのセマンティクス要件を、追加しています。両進イテレータを表すコンセプトbidirectional_iteratorでは、コンセプトforward_iteratorをrefineし、後退のためのシンタックス要件を追加しています。ランダムアクセスイテレータを表すコンセプトrandom_access_iteratorでは、コンセプトbidirectional_iteratorをrefineし、ランダムアクセスのためのシンタックス要件を追加しています。いくつかの演算子関数では、デフォルトの実装を与えており、必要になった時にコンパイラが使用します。
次に、concept map templateによって、任意のポインタ型をコンセプトrandom_access_iteratorに適合させています。任意のポインタ型をコンセプトiteratorに適合させるconcept map templateが定義されていないことに注意して下さい。random_access_iteratorに適合する型は、コンセプトマップを書かなくても、自動的にbidirectional_iterator、forward_iterator、iteratorに適合するのです。最後に、関数テンプレートf()、g()を記述していますが、テンプレート仮引数Tに対するコンセプト要件が、２つの関数で異なることに注意して下さい。それぞれの関数は、コンセプト要件で指定されたインタフェースを使って実装されており、main()では確保したint配列を渡しています。
concept refinementは、他のコンセプト要件をまるごと引き込むという点でnested requirementに似ています。しかし、nested requirementはコンセプト間にis-a階層関係を導入することはなく、自動的に引き込んだコンセプトに適合することもありません。

言語が提供するコンセプト

コンセプトでは表現できないテンプレート要件に対応するため、各翻訳単位の始めに暗黙で定義されるコンセプトがあります。これらは暗黙のコンセプトであり、コンセプトマップはコンパイラが暗黙で定義します。詳細は、N2914の404頁から始まる14.10.4 Support conceptsを参照して下さい。

namespace std
{
    concept Returnable<typename T> { }
    concept PointeeType<typename T> { }
    concept MemberPointeeType<typename T> { }
    concept ReferentType<typename T> { }
    concept VariableType<typename T> { }
    concept ObjectType<typename T> see below;
    concept ValueType<typename T> see below;
    concept ClassType<typename T> see below;
    concept Class<typename T> see below;
    concept PolymorphicClass<typename T> see below;
    concept Union<typename T> see below;
    concept TrivialType<typename T> see below;
    concept StandardLayoutType<typename T> see below;
    concept LiteralType<typename T> see below;
    concept ScalarType<typename T> see below;
    concept ArithmeticType<typename T> see below;
    concept NonTypeTemplateParameterType<typename T> see below;
    concept IntegralConstantExpressionType<typename T> see below;
    concept IntegralType<typename T> see below;
    concept EnumerationType<typename T> see below;
    concept FloatingPointType<typename T> see below;
    concept SameType<typename T, typename U> { }
    concept DerivedFrom<typename Derived, typename Base> { }
}

最後の２つは、特に興味深いものです。SameType< T, U >は、テンプレート引数T、Uが等価な型であることを要求します。また、DerivedFrom< Derived, Base >はクラス型Derivedが、Baseと同じか、又は公開派生した型であることを要求します。

標準ライブラリが提供するコンセプト

ヘッダでは、再利用可能な多数のコンセプトが定義されています。詳細は、N2914の518頁から始まる20.2 Conceptsを参照して下さい。

namespace std
{
    // 20.2.1, type transformations:
    auto concept IdentityOf<typename T> see below;
    auto concept RvalueOf<typename T> see below;
    template<typename T> concept_map RvalueOf<T&> see below;

    // 20.2.2, true:
    concept True<bool> { }
    concept_map True<true> { }

    // 20.2.3, type classifications
    concept LvalueReference<typename T> { }
    template <typename T> concept_map LvalueReference<T&> { }
    concept RvalueReference<typename T> { }
    template <typename T> concept_map RvalueReference<T&&> { }

    // 20.2.4, operator concepts:
    auto concept HasPlus<typename T, typename U> see below;
    auto concept HasMinus<typename T, typename U> see below;
    auto concept HasMultiply<typename T, typename U> see below;
    auto concept HasDivide<typename T, typename U> see below;
    auto concept HasModulus<typename T, typename U> see below;
    auto concept HasUnaryPlus<typename T> see below;
    auto concept HasNegate<typename T> see below;
    auto concept HasLess<typename T, typename U> see below;
    auto concept HasGreater<typename T, typename U> see below;
    auto concept HasLessEqual<typename T, typename U> see below;
    auto concept HasGreaterEqual<typename T, typename U> see below;
    auto concept HasEqualTo<typename T, typename U> see below;
    auto concept HasNotEqualTo<typename T, typename U> see below;
    auto concept HasLogicalAnd<typename T, typename U> see below;
    auto concept HasLogicalOr<typename T, typename U> see below;
    auto concept HasLogicalNot<typename T> see below;
    auto concept HasBitAnd<typename T, typename U> see below;
    auto concept HasBitOr<typename T, typename U> see below;
    auto concept HasBitXor<typename T, typename U> see below;
    auto concept HasComplement<typename T> see below;
    auto concept HasLeftShift<typename T, typename U> see below;
    auto concept HasRightShift<typename T, typename U> see below;
    auto concept HasDereference<typename T> see below;
    auto concept HasAddressOf<typename T> see below;
    auto concept HasSubscript<typename T, typename U> see below;
    auto concept Callable<typename F, typename... Args> see below;
    auto concept HasAssign<typename T, typename U> see below;
    auto concept HasPlusAssign<typename T, typename U> see below;
    auto concept HasMinusAssign<typename T, typename U> see below;
    auto concept HasMultiplyAssign<typename T, typename U> see below;
    auto concept HasDivideAssign<typename T, typename U> see below;
    auto concept HasModulusAssign<typename T, typename U> see below;
    auto concept HasBitAndAssign<typename T, typename U> see below;
    auto concept HasBitOrAssign<typename T, typename U> see below;
    auto concept HasBitXorAssign<typename T, typename U> see below;
    auto concept HasLeftShiftAssign<typename T, typename U> see below;
    auto concept HasRightShiftAssign<typename T, typename U> see below;
    auto concept HasPreincrement<typename T> see below;
    auto concept HasPostincrement<typename T> see below;
    auto concept HasPredecrement<typename T> see below;
    auto concept HasPostdecrement<typename T> see below;
    auto concept HasComma<typename T, typename U> see below;

    // 20.2.5, predicates:
    auto concept Predicate<typename F, typename... Args> see below;

    // 20.2.6, comparisons:
    auto concept LessThanComparable<typename T> see below;
    auto concept EqualityComparable<typename T> see below;
    auto concept StrictWeakOrder<typename F, typename T> see below;
    auto concept EquivalenceRelation<typename F, typename T> see below;

    // 20.2.7, construction:
    auto concept HasConstructor<typename T, typename... Args> see below;
    auto concept Constructible<typename T, typename... Args> see below;
    auto concept DefaultConstructible<typename T> see below;
    concept TriviallyDefaultConstructible<typename T> see below;

    // 20.2.8, destruction:
    auto concept HasDestructor<typename T> see below;
    auto concept HasVirtualDestructor<typename T> see below;
    auto concept NothrowDestructible<typename T> see below;
    concept TriviallyDestructible<typename T> see below;

    // 20.2.9, copy and move:
    auto concept MoveConstructible<typename T> see below;
    auto concept CopyConstructible<typename T> see below;
    concept TriviallyCopyConstructible<typename T> see below;
    auto concept MoveAssignable<typename T> see below;
    auto concept CopyAssignable<typename T> see below;
    concept TriviallyCopyAssignable<typename T> see below;
    auto concept HasSwap<typename T, typename U> see below;
    auto concept Swappable<typename T> see below;

    // 20.2.10, memory allocation:
    auto concept FreeStoreAllocatable<typename T> see below;

    // 20.2.11, regular types:
    auto concept Semiregular<typename T> see below;
    auto concept Regular<typename T> see below;

    // 20.2.12, convertibility:
    auto concept ExplicitlyConvertible<typename T, typename U> see below;
    auto concept Convertible<typename T, typename U> see below;

    // 20.2.13, arithmetic concepts:
    concept ArithmeticLike<typename T> see below;
    concept IntegralLike<typename T> see below;
    concept SignedIntegralLike<typename T> see below;
    concept UnsignedIntegralLike<typename T> see below;
    concept FloatingPointLike<typename T> see below;
}

また、ヘッダでは、イテレータコンセプトが定義されています。詳細は、N2914の852頁から始まる24.2 Iterator conceptsを参照して下さい。

namespace std
{
    concept Iterator<typename X> see below;

    // 24.2.2, input iterators:
    concept InputIterator<typename X> see below;

    // 24.2.3, output iterators:
    auto concept OutputIterator<typename X, typename Value> see below;

    // 24.2.4, forward iterators:
    concept ForwardIterator<typename X> see below;

    // 24.2.5, bidirectional iterators:
    concept BidirectionalIterator<typename X> see below;

    // 24.2.6, random access iterators:
    concept RandomAccessIterator<typename X> see below;
    template<ObjectType T> concept_map RandomAccessIterator<T*> see below;
    template<ObjectType T> concept_map RandomAccessIterator<const T*> see below;

    // 24.2.7, shuffle iterators:
    auto concept ShuffleIterator<typename X> see below;

    // 24.2.8, ranges:
    concept Range<typename T> see below;
    template<class T, size_t N> concept_map Range<T[N]> see below;
}

その他にも、標準ライブラリの様々な部分でコンセプトが使用されています。詳細は、N2914の（ｒｙ

コンセプトベースの関数オーバーロード

ところで、ヘッダでは、次のような関数オーバーロードが定義されています：

namespace std
{
    // 24.4, iterator operations:
    template <InputIterator Iter>
    void advance(Iter& i, Iter::difference_type n);

    template <BidirectionalIterator Iter>
    void advance(Iter& i, Iter::difference_type n);

    template <RandomAccessIterator Iter>
    void advance(Iter& i, Iter::difference_type n);
}

このような関数オーバーロードは、C++03には存在しませんでした。オーバーロードされている関数テンプレートは、constrained templateであり、テンプレート仮引数に対するコンセプト要件が異なっているのです。このように、コンセプトを導入した結果、オーバーロード解決するために候補となる関数の種類が増えることになります。
また、advance()のオーバーロード解決によって最適化が実現されます。各イテレータのアクセス特性に応じて、最適な実装をコンパイラが選択してくれるのです。この他にも、ヘッダでは、次のような関数オーバーロードが定義されています：

namespace std
{
    template <InputIterator Iter>
    Iter::difference_type distance(Iter first, Iter last);

    template <RandomAccessIterator Iter>
    Iter::difference_type distance(Iter first, Iter last);
}

range-based for文

コンセプトが草案から削除される前は、range-based for文はコンセプトに基づいていました。コンセプトRangeに適合する任意の型が、range-based for文で使用できたのです。コンセプトRangeは、ヘッダで定義されています：

concept Range<typename T>
{
    InputIterator iterator;
    iterator begin(T&);
    iterator end(T&);
}

template<class T, size_t N>
concept_map Range<T[N]>
{
    typedef T* iterator;
    iterator begin(T(&a)[N]) { return a; }
    iterator end(T(&a)[N]) { return a + N; }
}

コンセプトRangeに適合する型Tは、InputIteratorを返すbegin(T&)、end(T&)を備えなければなりません。続くconcept map templateでは、任意の配列をコンセプトRangeに適合させています。次の２つのコードは、同じ意味になります：

for ( for-range-declaration : expression ) statement

{
    auto && __range = ( expression );
    for ( auto __begin = std::Range<_RangeT>::begin(__range),
               __end = std::Range<_RangeT>::end(__range);
          __begin != __end;
          ++__begin )
    {
        for-range-declaration = *__begin;
        statement
    }
}

なぜ、コンセプトは草案から削除されたのか？

ググると、当時のいきさつを解説するサイトがたくさんあったので、まず紹介します。

  1. 本の虫: コンセプトが廃止になった理由 明快かつ簡潔な説明
  2. 本の虫: Douglas Gregor、フランクフルト会議について語る 明示的コンセプトを推したDouglas Gregorによる記事
  3. 本の虫: Bjarne Stroustrup、Conceptと未来を語る 暗黙のコンセプトを推したBjarne Stroustrupへのインタビュー
  4. C++0x、コンセプト除外の決断 - nursの日記 Bjarne Stroustrupによる記事
  5. C++0x、コンセプト除外の決断（3ページ目） - nursの日記 Bjarne Stroustrupによる記事（続き）
  6. C++0x からコンセプトが削除 | okuの日記 | スラド The Artima Developer Communityによる解説

まず、標準化委員会で合意が形成されなかった最大の要因として「明示的コンセプト」と「暗黙のコンセプト」によって顕在化した言語思想の相違が挙げられます。この相違とは、コンセプトのデフォルトとして明示的コンセプト、暗黙のコンセプトどちらを採用するかに現れています。これは、C++におけるジェネリック・プログラミングの方向性を決めるため、多くの議論が行われました。
問題の根源は、静的型付けと動的型付けの相違と、どのような方法で静的型付けの制約を回避するか、にあります。ジェネリック・プログラミングとは、静的型付けの制約を取り払い、柔軟なプログラミングを実現する機能です。よくよく考えると当たり前のことですが、動的型付けの言語ではテンプレートなどというものは不要なのです。
明示的コンセプトをデフォルトとして認めると、プログラマが型を定義する毎にコンセプトマップを書く必要がありますが、意図しない型が偶然、コンセプトに適合する事故を防ぐことができます。コンセプトへの適合を明示的に要求するこの方法は、テンプレートの型安全を十分確保し、C++の強い静的型付けに近いため、言語仕様として美しいものになります。
一方で、暗黙のコンセプトをデフォルトとして認めると、プログラマがコンセプトマップを書く必要はほとんど無くなります。コンセプトマップの役割を思い出して下さい：

  • コンセプトと実在する型を関連付ける
  • 実在する型がコンセプトに適合するために不足している要件を（もしあれば）補う。つまり、実在する型のシンタックスを曲げる

この内、最初の役割を不要にするのが暗黙のコンセプトなのです。逆に言うと、コンセプトに適合させるため、既存の型のシンタックスを曲げる用途だけに、コンセプトマップを使うことになります。この立場では意図しない型が偶然、コンセプトに適合する事故は問題にならない、と考えます。C++03のテンプレートを使っていて、そのような問題が重要にならなかったというのが、その主な理由です。暗黙のコンセプトをデフォルトにすると、テンプレート機能は動的型付けに近くなります。なお、C++03のテンプレートは、暗黙のコンセプトよりもずっと強い動的型付けの性格をもっています。

  • 明示的コンセプトは、単純明快で型安全なテンプレートを１から綺麗に構築するイメージ
  • 暗黙のコンセプトは、C++03のテンプレートを修正して、静的型付けの側に引き寄せるイメージ

1.の記事に書かれてあるとおり、この相違は少なくとも2005年から存在していました。Douglas Gregorによるインディアナ提案とBjarne Stroustrupによるテキサス提案が、その違いを浮き彫りにしています。その後、歩み寄りが図られ、この２者がConceptsを共同提案するにあたって、この相違は克服できたかに思えました。
N2914ではデフォルトが明示的コンセプトであり、キーワードautoを付けることで暗黙のコンセプトを記述します。しかし、この方法によると、プログラマがコンセプトに適合する型を書く毎に、いちいちコンセプトマップを定義する必要があります。加えて、コンセプトマップの本体が空になることも多く、ユーザビリティの悪さが指摘されるようになります。
その後、2009年６月にBjarne StroustrupはSimplifying the use of conceptsを著し、デフォルトとして暗黙のコンセプトを採用するように提案したのです。それから１ヶ月も経たない2009年７月、フランクフルト会議で行われた投票によって、コンセプトは委員会草案から削除されました。

ConceptGCCについて

ConceptGCCは、明示的コンセプトを推したDouglas GregorらによるGCCから派生した処理系です。やや重いという難点はありますが、N2914の仕様を概ね実装しています。標準化委員会において、コンセプトの実験場という位置づけのようです。詳細は、generic-programming.orgを参照して下さい。あと、よく調査しなかったのですがgeneric-programming.orgなるものもあるそうです。
ここでは、Cygwinでビルドする方法をメモしておきます。まず、Cygwinをインストールします。パッケージは、デフォルトのものに加えてautoconf2.1、flex、gcc-core、gcc-g++、make、subversion、gmp、mpfrあたりをインストールすれば良いかと思います。次に、Cygwin Terminalを開きます：

$ cd $HOME
$ svn co https://svn.osl.iu.edu/svn/hlo/releases/conceptgcc-4.3.0-alpha-7
$ mkdir conceptgcc
$ cd conceptgcc
$ ../conceptgcc-4.3.0-alpha-7/configure --program-transform-name='s/^g++$/conceptg++/' --prefix=$HOME/conceptgcc --enable-languages=c++
$ make
$ make install

最後に~/conceptgcc/binにパスを通して終了です。コンパイルコマンドは、conceptg++です。
なお、筆者の環境では１回ほどコンパイルエラーでビルドが止まりました。よくエラーメッセージを見ると、関数定義のシグネチャがプロトタイプ宣言のそれと一致していないことが分かります。シグネチャが一致するように関数定義からconstを削除して、再度makeしました。また、ソースファイルのダウンロードとコンパイルには、結構時間がかかります。ソースファイルは、少なくとも100MBはあると思います。筆者の環境（Nehalem、４コア）では、コンパイルに約３時間強かかりました。

参考文献

  1. コンセプト (C++) - Wikipedia
  2. generic-programming.org コンセプトに関係する概念の説明
  3. generic-programming.org チュートリアル形式のコンセプト入門
  4. http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2081.pdf Concepts (Revision 1)
  5. http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2009/n2906.pdf Simplifying the use of concepts
  6. http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2009/n2914.pdf コンセプトが記載された最後の規格書ドラフト

まとめ

いかがでしたでしょうか？コンセプトを導入することによって、既存のテクニックであるtraits、SFINAE等を使わずに本質的な問題解決の手段を得ることができます。これによって、C++におけるジェネリック・プログラミングは、柔軟性に加えて型安全性を備えるのです。
そのようなコンセプトが委員会草案から削除されたのは、大変残念ではあります。総論では多くがコンセプトに賛成しても、各論に入ると意見の相違が露呈したのかもしれません。ただ、この問題には更に時間をかけて議論する価値があると思います。皆さんは明示的コンセプト、暗黙のコンセプトのどちらがC++に相応しいと思いますか？
なお、この記事で言及できなかった項目として、キーワードlate_checkがあります。その他にも、コンセプトに関連する話題を全てカバーできていないかもしれません。あと、コンセプト名の命名規則としてsome_conceptの形式を使用しましたが、今になって思えばSomeConceptの形式の方が適切だったかもしれません。その他この記事には、筆者の偏見がいくらか入っていたかもしれません。もし、間違いがあった場合は是非コメントをお願い致します。