Concepts Extending C++ Templates For Generic Programming

この情報は恐ろしく昔のもので、現在のドラフト規格とまったくあっておりません。検索で飛んでこられた方は、この情報を信用せず、ご自分で規格をご確認ください。

　これは最高にためになる動画だ。
　コンセプトとは、C++のパラダイムのひとつ、ジェネリックプログラミングを、もっと分かりやすくするための文法だ。

　前半の5分ほどは、ジェネリックプログラミングはなんであるかを解説している。

The reason we think that we can make it simpler is that many of the way people use template now are... tricks! There're complelcated tricks. You can't even read in the book in many faces. You have to dig for newsgroup to see how they work recall look at boost C++ library to see what those guys did.

　今のテンプレートは、複雑なトリックを多用しすぎている。多くのトリックは、本にも載っていない。Boost C++ライブラリを書いている連中が何をやっているのかを知るためには、ニュースグループを調べなければならない。（原文が正しい自信がない）

　conceptには三つの機能がある。
Concept Difinitions
　ある型にたいする要求を定義する。たとえば、ある型TはT:func()というメンバ関数を持っていなければならないとか、T::value_typeという型が定義されていなければならないなどだ。
Where Clauses
　テンプレートパラメータに必要なコンセプトを明示的に指定できる。
Concept Map
　既存の型を、どのようにコンセプトの要求どおりに使うかを指定できる。個人的な感想は、恐ろしく賢いマクロか、恐ろしく便利なシンタックスシュガー。

template < typename T > where LessThanComparable<T> const T & min(const T & x, const T & y) {return x < y ? x : y ;}

　この例では、型Tは、less than演算子を持っていなければならないというコンセプトが示されている。たとえば、比較演算子としてgreater than演算子（＞）を使った場合は、コンパイラがエラーを出す。less than演算子で比較できない型を渡した場合も、コンパイラはエラーをだす。しかも、コンパイラが吐くエラーは、「LessThanComparableの要求を満たしていません」等といった、人間に分かりやすいエラーだ。従来の、インスタンシエイトの過程を追っていくような、人間にとって暗号に近いエラーメッセージではない。

それでは、LessThanComparableというconceptはどうやって定義するのか。

concept LessThanComparable< typename T > { // Syntactic requirement bool operator < (T, T) ; // Semantic requirement axiom Irreflexivity(T x) { !(x < x) ; } axiom Asymmetry(T x, T y) { if (x < y) !(y < x) ; } axiom Transitivity(T x, T y, T z) { if (x < y && y < z) x < x ; } } ;

　文法的な要求と、意味的な要求を定義できる。講演では、axiomについては詳しく述べていない。しかし、この機能はどうやって実現するのか疑問だ。本当に、これをコンパイル時にチェックできるのだろうか。ここでの、syntactic requirementは、T型の引数を二つ取り、bool型を返す、less than演算子がなければならないというものだ。もちろん、現在のテンプレートパラメータのように、複数指定できる。Why not?

concept Foo<typename T1, typename T2, typename T3>{ } ;

　他にも、value_typeという型を持っていなければならない要求や、それらの型に対するコンセプトをネストして指定できる機能など。

concept InputIterator < typename Iter > { typename value_type ; // Iter must has typename Iter::value_type typename difference_type ; // Iter must has typename Iter::difference_type where SignedIntegral<difference_type> // Iter::difference_type must meet requirements of SignedIntegral concept Iter & operator++(Iter &) ; // pre-increment Iter & operator++(Iter &, int) ; //post-increment bool operator==(Iter, Iter) ; //equality comparison bool operator!=(Iter, Iter) ; //inequality comparison value_type operator * (Iter) ; // dereference } ;

　where clauseは、次のように指定できる。

template < typename Iter, typename T> where InputIterator<Iter> && EqualityComparable<InputIterator<Iter>::value_type, T > Iter find(Iter first, Iter last, const & value) { while( first != last && !(*first == value) ) { ++first ; } return first ; } ;

　ここで質問がある。InputIterator<Iter>::value_typeには、typenameの指定はいらないのかというものだ。もちろんここは型を指定すると決まっているので、必要がない。コンパイラは適切に判断できる。 　たとえば次のようにすれば、conceptをサポートしていないコンパイラに対する、下位互換性も保てるだろう。

template < typename Iter, typename T> #ifdef COMPILER_SUPPORT_CONCEPT where InputIterator<Iter> && EqualityComparable<InputIterator<Iter>::value_type, T > #endif Iter find(Iter first, Iter last, const & value) { while( first != last && !(*first == value) ) { ++first ; } return first ; } ;

　さて、28分あたりから、いよいよ、超強力なconcept_mapの解説に入る。先ほどのfindという関数は、イテレータに対しては問題なく対処できた。でも、int型の配列に対してはどうだろう。int型の配列の先頭要素へのポインタは、十分にイテレータとして通用する。しかし、組み込み型であるので、value_typeやdifference_type等を持っていない。そこで、Concept Mapを使い、どうやってコンセプトに合うようにするか、いわばマップを行う。 　Concept Mapとは、How（如何にして）conceptの要求を満たすかを定義する。たとえば、int型のポインタに、value_typeとdifference_typeが必要というのであれば、定義してやるだけだ。

concept_map InputIterator< int * > { typedef int value_type ; typedef ptrdiff_t difference_type ; } ;

　とはいっても、組み込み型だけでも、かなりの数がある。いちいちひとつずつやっていくのは面倒だ。ここは、テンプレートを使うべきだ。Why not?

template < typename T > concept_map InputIterator< T * > { typedef T value_type ; typedef ptrdiff_t dirrefence_type ; } ;

　これで、すべてのポインタは、InputIteratorのコンセプトを満たすようになった。

　コンセプトは、階層構造にすることができる。Concept Refinementという。

concept BidirectinalIterator< typename Iter > : InputIterator<Iter> { Iter & operator -- (Iter &) ; Iter operator -- (Iter &, int) ; } ; concept RandomAccessIterator< typename Iter > : BidirectionalIterator<Iter> { Iter operator + (Iter, difference_type) ; // ... } ;

every random access iterator is a bidirectional iterator is a input iterator

　ランダムアクセスイテレータは、バイディレクショナルイテレータであり、インプットイテレータである。 　このヒエラルキーは、Overload Resolutionに絡めることができるらしい。たとえば、イテレータを、指定された個数分進めるadvanceであるが、

template < InputIterator Iter > void advance( Iter & x, Iter::difference_type n ) { while(m > 0) { ++x ; --n ;} } //O(n) template < RandomAccessIterator > void advance( Iter & x, Iter::difference_type n ) { x = x + n ; } // O(n)

　この例では、where clauseがないが、これは簡便なショートカットシンタックスである。意味も分かりやすい。ワーオ！

　まず、最初のadvance関数は、非常にジェネリックで、どんなイテレータでも使うことが出来る。しかし、ランダムアクセスイテレータの場合、これは無駄が多すぎる。そこで、RandomeAccessIteratorのコンセプトを使ってやる。コンパイラは、ベストマッチを探してくれる。ご存知の通り、Bidirectional Iteratorは、Input Iterator　「である」ので、最初の関数にマッチする。それにしても、タダでさえOverload Resolutionはややこしいというのに、さらに複雑になるのだろうか。現状では、テンプレートは、インスタンシエイトされてから、Overload Resolutionにかけられる。これだけでもややこしいというのに……。

　さて、さらにConcept Mapの話は続く。こんどは、あるコンテナの全要素をイテレートするというものだ。いわばfor-each loopだが、これをどうするか。もちろん自分でやってもいいのだが、全要素をループさせるというのは、よくある操作なので、楽をしたい。他の言語はどのようにしているかというと。

　Pythonは、イテレータとコンテナのプロトコルを定義している（ある決まった形でなければならない）
　Perlは、ユーザ定義型を無視する（ハァ？　組み込み型以外は知ったこっちゃないね）
　C#は、IEnumerableインターフェースを使う（既存の俺様コンテナは知ったこっちゃないね）
　C++0xは、concept mapを使う。
　次のForコンセプトを満たす必要がある。

concept For< typename X > { typename iterator ; where InputIterator<iterator> ; iterator begin(X &) ; iterator end(X &) ; } ;

　つまり、次のコードが、

vector<int> v ; for (int i : v) cout << i << ' ' ;

　シンタックスシュガーにより、このように展開される。

for( For<vector<int> >::iterator first = For<vector<int>>::begin(v) , last = For<vector<int>>::end(v) ; first != last ; ++first ) { int i(*first) ; cout << i << ' ' ; }

　何の解説もないが、原文のbracket parentheseの間に空白がないのは、意識してやっているのだろうか。これをできるようにしようという提案がされているのだが。もうひとつ、こんな風にコンセプトを明示的に使うことも出来るのだろうか。解説がないが。

　たとえば、int型の配列に対しては、次のようにする。

template < typename T, size_t N> concept_map For<T[N]> { typedef T * iterator ; T * begin( T array[N] ) { return array ;} T * end( T array[N] ) { return &array[N} ; } } ; int some_primes[6] = {2, 3, 5, 6, 11, 13} ; for ( int prime : some_primes ) std::cout << prime << ' ' ;

　これを使えば、STLとは微妙に違う、俺様コンテナであっても、コンセプトに合わせるようにしてやれば、俺様コンテナ自身を変更することなく、for-each loopに書けることができる。これはいい。既存の、既に問題なく動いているコードや、共通のフレームワークなどを変更せずにすむからだ。 　質問があるが、コンセプトはnamespaceの中に入る。これは当然だ。

　ところで、STLのmultisetには、equal_rangeというメンバ関数がある。これは、引数として指定した値の範囲のイテレータを、pairで返す。コンテナではないが、for-each loopに必要な情報は、すべてそろっている。ではどうやってForコンセプトに合わせるのか。

template < InputIterator Iter > concept?map For< pair<Iter, Iter> > { typedef Iter iterator ; Iter begin(pair<Iter, Iter> & p) { return p.first ; } Iter end(pair<Iter, Iter> & p) { return p.second ; } } std::multiset<int> elements ; for ( int i : elements.equal_range(17) ) std::cout << i << ' ' ;

　恐ろしや恐ろしや。
　しかし、ひとつひとつ、これを定義していくのは、面倒である。我々はすでに、Containerというコンセプトを定義した。これを使えばよい。

template < Container C > concept_map For<C> { typedef Container<C>::iterator iterator ; iterator begin(C & c) { return c.begin() ; } iterator end(C & c) {return c.end() ; } } ;

　これで、Containerコンセプトを満たす型は、すべてforループにかけられる。とてもとても汎用的だ。

　テンプレートがらみのエラーメッセージに辟易としない人はいないはずだ。コンパイラは、インスタンシエイトの過程を追っていくので、エラーメッセージは膨大になり、人間が簡単に読めるものではなくなってしまう。しかも、内部の実装の詳細の識別子などがでてくるので、まずわけが分からない。

int main() { std::list<int> l ; std::sort(l.begin(), l.end() ) ; }

　上記のコードの、VC8のエラーメッセージは次の通りである。

D:\Program Files\Microsoft Visual Studio 8\VC\include\algorithm(3112) : error C2784: 'reverse_iterator<_RanIt>::difference_type std::operator -(const std::reverse_iterator<_RanIt> &,const std::reverse_iterator<_RanIt2> &)' : テンプレート 引数を 'const std::reverse_iterator<_RanIt> &' に対して 'std::list<_Ty>::_Iterator<_Secure_validation>' から減少できませんでした
with
[
_Ty=int,
_Secure_validation=true
]
D:\Program Files\Microsoft Visual Studio 8\VC\include\xutility(1856) : 'std::operator -' の宣言を確認してください。
.\test01.cpp(10) : コンパイルされたクラスの テンプレート のインスタンス化 'void std::sort<std::list<_Ty>::_Iterator<_Secure_validation>>(_RanIt,_RanIt)' の参照を確認してください
with
[
_Ty=int,
_Secure_validation=true,
_RanIt=std::list<int>::_Iterator<true>
]
D:\Program Files\Microsoft Visual Studio 8\VC\include\algorithm(3112) : error C2784: 'reverse_iterator<_RanIt>::difference_type std::operator -(const std::reverse_iterator<_RanIt> &,const std::reverse_iterator<_RanIt2> &)' : テンプレート 引数を 'const std::reverse_iterator<_RanIt> &' に対して 'std::list<_Ty>::_Iterator<_Secure_validation>' から減少できませんでした
with
[
_Ty=int,
_Secure_validation=true
]
D:\Program Files\Microsoft Visual Studio 8\VC\include\xutility(1856) : 'std::operator -' の宣言を確認してください。
D:\Program Files\Microsoft Visual Studio 8\VC\include\algorithm(3112) : error C2784: 'reverse_iterator<_RanIt>::difference_type std::operator -(const std::reverse_iterator<_RanIt> &,const std::reverse_iterator<_RanIt2> &)' : テンプレート 引数を 'const std::reverse_iterator<_RanIt> &' に対して 'std::list<_Ty>::_Iterator<_Secure_validation>' から減少できませんでした
with
[
_Ty=int,
_Secure_validation=true
]
D:\Program Files\Microsoft Visual Studio 8\VC\include\xutility(1856) : 'std::operator -' の宣言を確認してください。
D:\Program Files\Microsoft Visual Studio 8\VC\include\algorithm(3112) : error C2784: 'reverse_iterator<_RanIt>::difference_type std::operator -(const std::reverse_iterator<_RanIt> &,const std::reverse_iterator<_RanIt2> &)' : テンプレート 引数を 'const std::reverse_iterator<_RanIt> &' に対して 'std::list<_Ty>::_Iterator<_Secure_validation>' から減少できませんでした
with
[
_Ty=int,
_Secure_validation=true
]
D:\Program Files\Microsoft Visual Studio 8\VC\include\xutility(1856) : 'std::operator -' の宣言を確認してください。
D:\Program Files\Microsoft Visual Studio 8\VC\include\algorithm(3112) : error C2676: 二項演算子 '-' : 'std::list<_Ty>::_Iterator<_Secure_validation>' は、この演算子または定義済の演算子に適切な型への変換の定義を行いません。(新しい動作; ヘルプを参照)
with
[
_Ty=int,
_Secure_validation=true
]
D:\Program Files\Microsoft Visual Studio 8\VC\include\algorithm(3112) : error C2780: 'void std::_Sort(_RanIt,_RanIt,_Diff,_Pr)' : 4 引数が必要です - 3 が設定されます。
D:\Program Files\Microsoft Visual Studio 8\VC\include\algorithm(3231) : 'std::_Sort' の宣言を確認してください。

　これをまともに読める人間は、まずいないだろう。次のようになれば、読みやすいのではないかと思う。
「std::list::iteratorは、RandomAccessIteratorコンセプトを満たしていません。適合するconcept mapも見つかりません。」
　他にも、インスタンシエイトされる前に、テンプレートのコードが、コンセプトにあったものかを、コンパイラがチェックすることができる。たとえば動画の例では、InputIteratorは、less than演算子を使うことが出来ない。
　最後の質問でも出ているのだが、これらの機能にはコストがかかる。Boostのライブラリをふんだんに使ったコードのコンパイルには、かなりの時間がかかるが、コンセプトもテンプレートと同じく、かなり多くの処理を行わなければならない。どうなることやら。
　しかし、仕様が確定するのが2009年で、ISOの認可がおりるのが、2010年、それから主要なコンパイルベンダーが実装するのに、数年はかかるだろうから、案外楽観視していいのかもしれない。ムーアの法則が続いていればの話だが。