2011-02-27

range-based forに対する意見求む

現在、range-based forに対して、改良を加えられるチャンスがある。これはまだ議論中であり、次のFDISに入るかどうか分からないが、未来のC++0xユーザー候補が、今知るべきことだと思うので、ここで説明する。意見がほしい。

問題は、あるクラスを、どのようにrange-based forに対応させるかというものである。現行ドラフトを簡単に説明すると、以下のようになっている。

range-based forに渡した式を引数に取り、イテレーターを返す、begin(expr)、end(expr)を、ADLにより探す。

// Cの構造体による既存のコード
struct Container
{
    int * ptr ;
    std::size_t size ;
} ;

int * begin( Container & c ) { return ptr ; }
int * end( Container & c ) { return ptr + size ; }
// 同様のconst版

これは、同じ名前空間スコープにbegin、endという名前の関数を書けばいいだけなので、初心者にも簡単といえるだろう。また、クラス定義を変更する必要がない。

また、range-based forのADLには、std名前空間が特別にassociated namespaceとして付け加えられる。std名前空間には、クラスのbegin/endという名前のメンバー関数を呼び出す関数があるので、これを利用することでも、クラスをrange-based forに対応させられる。

つまり、クラス内で、イテレーターを返すbegin/endという名前のメンバー関数を定義する。

// 標準ライブラリのコード
namespace std
{
template <class C> auto begin(C& c) -> decltype(c.begin());
template <class C> auto begin(const C& c) -> decltype(c.begin())
template <class C> auto end(C& c) -> decltype(c.end());
template <class C> auto end(const C& c) -> decltype(c.end());
}

// Containerのためのイテレータークラス
// もちろん、ポインターによる実装も可能
class Iterator ;
class Container
{
    Iterator begin( ) ;
    Iterator end( ) ;
// 同様のconst版
} ;

この対応は、クラス定義が変更できる場合に、使うことができる。しかし、既存のクラス定義は、様々な理由で、自由に変更できない可能性がある。例えば、Cコードの構造体や、外部のライブラリであり、変更できないという状況は、現実のプログラミングでは、大いにありうる。

しかし、多くの中級者以上のC++プログラマーが知るように、ADLは根本的に邪悪である。今、range-based forに対して、最後の変更を行うチャンスがある。

案1は、現状を維持する。変更は行わない。

案2は、traitsベースの実装に変更する。つまり、range-based forにおけるイテレーターの取得を、テンプレートクラスを通じて行うようになる。

namespace std
{

template<class T>
struct range_traits
{
 static typename T::iterator begin(T& t) { return t.begin(); }
 static typename T::iterator end(T& t) { return t.end(); }
 // 同様のconst版など
} ;

}

クラスをrange-based forに対応させるには、range_traitsの特殊化を行う。

// C++0xの新機能、別の名前空間スコープにおけるテンプレートの特殊化
template < >
struct std::range_traits<Container>
{
    int * begin( Container & c ) { return c.ptr ; }
    int * end( Container & c ) { return c.ptr + c.size ; }
// 同様のconst版など
} ;

しかしこれでは、ユーザーはテンプレートの特殊化、しかも、STLのテンプレートの特殊化(規格上許可されている)という、かなり上級者向けのコードを書かなければならない。

案3は、案2に加えて、ADLフォールバック機能がつくものである。すなわち、range_traitsによるイテレーターの取得ができなければ、現行のADLベースの実装を使うというものである。これは、range_traitsによる優れた実装を提供しながら、ADLによる泥臭い実装も提供するという意味である。

案4は、イテレーターの取得方法には、メンバー関数、begin/endを使うというものである。つまり、traitsによる対応もできないし、クラス外での関数による対応もできない。ただし、クラス定義を変更せずにrange-based forに対応させる方法はある。アダプターである。

// 既存のCの構造体のような使い方をするクラス
struct Container
{
    int * ptr ;
    std::size_t size ;
} ;

class Adaptor
{
private :
    Container & ref ;
public :
    explicit Adaptor( Container & ref )
    : ref(ref)
    { }

    int * begin() const { return ref.ptr ; }
    int * end() const { return ref.ptr + ref.size ; }
} ;


int main()
{
    Container c = { new int[10], 10 } ;

    for ( auto & value : Adaptor(c) )
    {
        value = 123 ;
    }

    delete[] c.ptr ;
}

つまり、言語側の機能は最小限にして、ユーザーコードで対処しようというものである。このようなアダプタークラスは簡単に書けるし、パフォーマンス上の問題もない。また、make_adaptorなどといったヘルパー関数のテクニックを使えば、テンプレート化もできる。

案5は、案4に加えて、メンバー関数が見つからなかった場合に、ADLへのフォールバック機能を付け加えるというものである。案2に対する案3と同じである。つまり、ADLによる泥臭い機能は残される。案5は、現状維持とさほど変わらない。ただ、順番が変わっただけである。ADLの前に、メンバー関数を探しにいくようになるのだ。

私は、案4が最適だと考えている。ADLを利用してはならない。ましてや、range-based forは、将来のC++にコンセプトが入った場合、コンセプトを使った実装に書き換えられるはずなのだ。いま、ADLという穴を作るわけにはいかない。これは、range-based forからADLを外せる、最後のチャンスである。今、ADLを許可すると、一生ADLをサポートしなければならない。

ちなみに、案4のアダプターは、完全にユーザーレベル、ライブラリレベルでの対応なので、どの案を選んだとしても、行うことができる。むしろ、アダプターパターンは非常に一般的なので、C++プログラマーならば、アダプターという手法は、関数を書くことのように、空気を吸って吐くことのように、HBの鉛筆をベキッとヘシ折れるように、できて当然である。アダプターパターンにパフォーマンス上の欠点はない。

意見求む。

追記:配列について

配列は、現行ドラフトですでに、特別に処理されるようになっている。この問題は、配列以外の型に対する実装である。どの案を選んでも、配列に対してrange-based forが使えなくなるということはない。

16 comments:

SubaruG said...

僕も案4がいいと思います。
ただ、案4を採用した場合、配列の扱いはどうするか(配列に関しては言語コアで特別扱いするか、それとも特別扱いはせず標準ライブラリ辺りにアダプタを用意してフォローするか)、という問題もあるんですよね。
その辺りが議論になって規格制定が遅れるのは微妙な気もします。

Anonymous said...

私は案2に賛成です。

>このようなアダプタークラスは簡単に書けるし、パフォーマンス上の問題もない。また、make_adaptorなどといったヘルパー関数のテクニックを使えば、テンプレート化もできる。

>案4のアダプターは、完全にユーザーレベル、ライブラリレベルでの対応なので、どの案を選んだとしても、行うことができる。

このような点では、アダプターは素晴らしいと思うのですが、結局、関数オブジェクトに対するラムダ式のように便利なものが出てきたときに、取って変わられるような気がします。

yoki said...

ADL の場合、インターフェースなのかそれ以外の普通の関数なのか一見区別がつかないのが問題ですが、うまく使えばコンパイル時ポリモーフィズムに絶大な威力を発揮するので、むしろそのことを標準が示して欲しいと思います。

以前、oven の mb2 氏もいろいろ試してましたが、引数に専用のタグを指定して、意図をはっきりさせるなんてのはどうでしょうかね。

namespacep std {
struct range_overload {};
template auto begin(range_overload, T& r) -> decltype(r.begin());
template auto end(range_overload, T& r) -> decltype(r.end());
}

int* begin(std::range_overload, Container& c) { return c.ptr; }
int* end(std::range_overload, Container& c) { return c.ptr + c.size; }

ADL はもう無くせないと思います。ならばフタをするより飼いならす方向で。

次点だと、案2の traits が numeric_limits<> の前例があるので、あまり違和感はないです。
案4 のアダプタクラスは、やりたいことに一段階遠回りしている感があります。クラスに名前つけて作成するのも面倒だし、for (i : std::make_range_adaptor(v)) とかせっかくの言語組み込みの range-base for なのに直接使えないなんて残念過ぎます。

Anonymous said...

for文で最優先で実現してほしいのは、STLコンテナと配列のループをシンプルに書けることで、それ以外はおまけだと思います。なので、begin/endメンバ関数だけで十分だと思います。おまけのためにこれ以上複雑な文法を導入するのはやめてほしいです。
ところで、不勉強で申し訳ありませんが、ADLって何ですか?

Flast said...

私は2案を推します。

読んだ限り
for(auto x:range){...}
があった場合、
std::range_traits
が使用されるということだと思うのですが、デフォルトで提供されるstd::range_traitsがメンバ関数を使用するとすると、実質的に案4と同等だと考えます。
少なくとも毎回適用する必要があるアダプタをユーザーに強要するよりは良いかと思います。(尤も忘れたことによってバグになるようなコンテナを作って/使ってる側がいけないのですが

また、本文中で仰られていた通りアダプタはどの案にも適用できるので、ある程度挙動を制御できる方法があってもいいのではないでしょうか。そもそも"range"というものが厳密に規定されていないと思われるので。

また、アダプタにはprvalueのlifetimeの問題が発生すると思います。moveすれば解決する問題ですが、万が一moveできないコンテナだった場合、無駄なオーバーヘッドを発生させます。
さらに、もし、なんでそんなもの作ったか知りませんが、copyもできないコンテナなんてものが、となったときにそれを解決する手立てを提供できないのは、いかがなものかと思います。

ライブラリがADLを使用するのは、なんとか思いとどまって許容したとしても、言語コアがそれを使用するのはどうしようもなくなってしまうので避けたいですね。

PG_kura said...

僕は案3が良いと思います。アダプタは、俺々アダプタの量産を招きそうですし、メタプログラミングの邪魔になるケースが出てきそうかなと思います。

江添亮 said...

自前のアダプタークラスを書くことは、何ら問題になりません。
このようなアダプタークラスは、関数を書くことと同じぐらい、気軽に書くべきコードなのです。

Anonymous said...

アダプタが問題なのは、ライブラリレベルではなくユーザーレベルで書かなくてはならないからじゃないですかね。うまいフォールバックがあればいいのですが。
アダプト対象の型とは別の型になってしまうというのがTMP的にちょっと…という気持ちもちょっと分かります。

satore said...

私も案4を推します
仕様を知らない人にも「begenとendをメンバとして定義しておけばこの書き方でループ出来るんですよ」
で説明出来るので。
アダプターもその延長で説明できますしね。

テンプレートの特殊化は初心者への説明は難しいですしADLは最早不可能でしょう

Flast said...

私のコメントの4行目がどうやらパーサーに食われているので補足を...4行目は
std::range_traits<decltype(range)>
です。(これで見えるかな...

テンプレートの特殊化は別に初心者に説明する必要はなく、デフォルトのrange_traitsを使うのであれば「begin/endメンバを追加」というのはtraitsでも同じ説明になるはずです。

satore said...

>>Flastさん
書き方を教える場合はそれでよいのですが、書かれたコードの読み方を教える時の方を想定していました。

周りのレベルなどの状況に合わせて
・range-based forで書かない
・説明が簡単なAdapterにしておく
・tepmlateの特殊化を使用する
を選べるような案2がC++的な感じもするのですが、今のところtemplateの特殊化にした場合のメリットがわからないので、私には案2を推す理由がありません。
覚えることは少ない方が良いですしね。

不勉強で申し訳ないですが、Flastさんの挙げているlifetimeの問題の方ですがなぜコンテナをcopyとかmoveとかしなければならないのか、templateの特殊化にした場合になぜそれを回避できるのかもわからないです。

江添亮 said...

リファレンスに束縛された一時オブジェクトの寿命は、リファレンスの寿命と同じになるように延長されます。

Flast said...

私はrange based forがBoost.Foreachに近い形で展開されることを想定して議論しているので、もしかしたらlifetimeの問題は発生しないかもしれないのです。

で、私が記憶している限り、prvalueのlifetime延長はrvalue referenceまたはconst lvalue referenceに直接束縛した時だけだったと記憶しています。
つまり関数などを介した場合、prvalueのlifetime延長は行われず、
https://ideone.com/1Ve10
のように本体が実行される前にrangeのdtorが呼ばれてしまうのではないかということです。

なお、n3242の6.5.4/1を参照する限り、等価とされる展開の仕方がBoost.Foreachと同じなので、アダプタだけだとやはりこの手の問題は起きるのではないでしょうか。

江添亮 said...

range-based forはコア言語機能です。
当然、一時オブジェクトを渡した際の寿命についても、考慮されています。

satore said...

>>Flastさん

仮にrange based forに渡した一時オブジェクトなAdapterがデストラクトされたとしてもコピーやムーブは必要無いですよね?
一時オブジェクトなAdapterが返すイテレータなりポインタなりはアダプタが死んでもコンテナが生きている限り生きているはずですから、最大でも
・アダプタのコンストラクタ実行
・コンテナの参照のをコピー
・アダプタのデストラクタ実行
のコストしか発生しませんし、それすら最適化されて消えてしまうような気がします。

それともrange-based forに渡した一時オブジェクトのlifetimeがよきに計らわれるのは前提で、一時オブジェクトなコンテナをそのままrange-based forに渡せないのが不便?とかそういう話なのでしょうか?

yak_ex said...

とりあえず

1) デフォルトの実装(メンバ関数のbegin(),end())を提供する
2) 特定の型に対するデフォルトの実装を提供する(for毎になんか書くの面倒)
3) その場その場で辿り方を指定する

ぐらいができれば良いと思うのですが traits の場合、主 template で 1) を、特殊化で 2) を実現でき、3) はアダプタ使えばいいので将来的な事を考えず現時点だけで考えるならば案2が一番いいと思います。