らむだる。 - udon's blog

先日のBMG読書会の懇親会でもちょっと話題になったので、今日ちょっと~~仕事サボって~~c++のlambda(ラムダ)を調べてみたんです。

http://cpplover.blogspot.jp/2009/11/lambda.html

ここの内容をぽちぽち写経しまして。まだ途中だけど、「お〜〜おもしろいなぁ〜〜！」という感じでした。

で、このラムダを使うシーンって何があるんだろうな？と思ったんですね。 OOPなコードに突如登場するの？とかね。

で、多少ぼやいてるとよさそうなサイトを紹介してもらえました。

http://d.hatena.ne.jp/faith_and_brave/20110520/1305873112

pdfを落としてワタシの死にかけSO-01Bで読んでたけど、なんだかもや〜っとした感じが拭えなかったので、ちゃんと腰据えて和訳をしてみようかなと。ちなみにワタシのmacはgcc4.7を入れてるのでちゃんとビルドできるわけです！ *1

以下pdf資料の意訳

Syntax

[ キャプチャ ] ( パラメータ ) -> ret { 処理; }

サンプル

int sum = 0;
long long product = 1;
for_each( values.begin(), values.end(), [&](int i){
  sum += 1;
  product *= i;
} );

[ キャプチャ ]

外側の変数を値、または参照を指定してキャプチャする

( パラメータ )

引数を指定。空でもOK

-> ret

新しい記法。0ないしはひとつの戻り値の場合はオプション。

{ 処理 }

ラムダの処理本体を記述する

例

ラムダの定義よりも前にあるスコープ内の変数を指定。

変数名指定でコピーキャプチャする。呼び出す際は指定なしでもOK

widget w;
auto lamb = [w] { for(int i = 0; i < 100; i++) f(w); };
lamb();  // 指定なしで呼び出し可能

変数を参照指定でキャプチャする。

widget w;
auto da = [&w] (const int & i){ return f(w, i); };
int i = 42;
da( i );   // 有効なスコープ内ならラムダ本体より後で定義された変数でもOK

　
よってラムダの構文は以下の様な意味合いになる

// ラムダ構文 [capture](params){statements;} と同義なクラス
class __functor {
private:
  CaptureType __captures;
public:
  __functor( CaptureType capture ) : __captures( capture ){}
  auto operator() (params) -> ret { statements; }
};

　
実際の記述で考えると

// [c1, &c2] {f(c1, c2);} と同等なクラス
class __functor {
private:
  C1 __c1; C2& __c2
public:
  __functor( C1 c1, C2& c2 ) : __c1(c1), __c2(c2){}
  void operator()() { f(__c1, __c2); }
};

// [](P1 p1, const P2& p2) { f(p1, p2); }
// 原文では共通な箇所は省略されていると思われる
class __functor {
public:
  void operator()(P1 p2, const P2& p2) { f(p1, p2); }
};

// "auto"はc++11から
// [] (auto p1, const auto& p2){ f(p1, p2); }
class __functor {
public:
  template<typename T1, typename T2>
  void operator()(T1 p1, const T2& p2) { f(p1, p2); }
};

　
大体ポリモフィック構文 *2

// [](p1, p2){ f(p1, p2); }
class __functor {
public:
  template<typename T1, typename T2>
  void operator()(const T1& p1, const T2& p2) { f(p1, p2); }
};

ローカルネスト関数

GotW #53に、このような書き方が便利だと書かれている、が、正しくない

int f( int i ){
  int j = i*2;
  int g( int k ){  // 関数f内にネストした関数定義は書けない
    return j+k;
  }
  j += 4;
  return g( 3 );   // ローカル定義した関数を予防としている

　
このコードにどのような意味合いがあるかを考える

オリジナルコードは関数gは、変数 j=i*4 を呼び出し箇所で使用したい意図がある=> 参照によるキャプチャになる
時々関数gの定義箇所で変数 j=i*2 を使用したい場合もあるだろう => 値によるキャプチャになる

今日のC++による代替案

いくつかの代替案がある * 幾つかはシンプルだが使いにくい * それ以外は複雑だが早い　

代替案１：ローカルクラス（複雑で、もろい）

関数をローカルクラスでラッピングする。関数はオブジェクトを介して呼び出す

int f( int i ){
  int j = j * 2;
  class g_ {
    int &j_;                 // ここでは参照を選んだ
  public:
    g_( int &j ) : j_(j){}   // ここでも同じ参照を
    int operator()( int k ){
      return j_ + k;         // 大元の変数jに参照アクセスする
    }
  }g(j);                     // 変数のキャプチャを期待
  j += 4;
  return g(3);               // ローカル関数の呼び出し
}

c++03ではこのようなローカルクラスでのインスタンス生成はできない。c++0xでは記述は可能だがその欠点は消える。

代替案２：関数内に変数をローカライズする

（よりシンプルで拡張性がある。ただし参照キャプチャしか使えない）　
functorクラスのスコープ内にキャプチャされた変数自身を持っていく。関数も同じく。

int f( int i ){
  struct AllLocals_{
    int j;            // キャプチャする変数を宣言
    int g()( int k ){
      return j + k;   // 変数jに直にアクセス
    }
    void x(){ /*...*/ } // 拡張案
    void y(){ /*...*/ }
    void z(){ /*...*/ }
  }local;

  local.j = i * 2;
  local.j += 4;
  local.x();
  local.y();
  local.z();
  return local.g(3);  // ローカル関数の呼び出し
}

ラムダならこうなる

オリジナルコードにさかのぼって考える。理想的には

int f( int i ){
  int j = i * 2;
  auto g = [&]( int k ){  // ローカル関数の定義
    return j + k;
  };
  j += 4;
  return g( 3 );          // 関数呼び出し
}

値でキャプチャしたい？なら & を = に変えればOK。　
　

Effective STLより

item 43: 手元のループを楽にするアルゴリズム
STLにはループをしてくれるアルゴリズムが幾つかある

for_each transform copy find remove

なぜこれらのアルゴリズムが必要になったのか？大きな理由は以下のとおり

パフォーマンス
- 一部的に：コピーコードを防ぐ
- 一般には：コードが最適化される
正確さ
- エンバグする可能性を下げる。特に難解なイテレータ無効化によるバグなど。
明瞭さ
- アルゴリズムの名称が、それが何をしようとするかを示しており、forの様に中身を読む必要性をなくしている。より意味付けされた用語を使用することで抽象化した記述が可能になる。

Effective STL 20項より

直接記述したループ

for( auto i = strings.begin(); i != strings.end(); ++i ){
  cout << *i << endl;
}

　
ラムダを使用しないSTL

copy( strings.begin(), strings.end(), ostream_iterator<string>(cout, "¥n") );

　
STLとラムダを併用

for_each( strings.begin(), strings.end(), [](string& s){
  cout << s << endl;
});

どれが読みやすいコードだろう？for？copy？for_each？　

多くのループはワンライナーにできない？

直接記述したループ

for( auto i = strings.begin(); i != strings.end() ++i ){
 // イロイロ処理
}

　
ラムダを使用しないSTL

for_each( strings.begin(), strings.end(), LoopBodyFunction(...) );
 // さぁループの本体を書くんだ！！

　
STLとラムダの併用

for_each( strings.begin(), strings.end(), [&](string& s){
  // いろんな処理
} );

視点を変えて：for_each VS for( x:coll )

STLとラムダを併用して呼び替えたコード

for_each( strings.begin(), strings.end(), [](string& s){
  cout << s << endl;
} );

　
c++0xではもっと素敵なforループがある

for( auto& s : strings ){
  cout << s << endl;
}

ただし、

なんだか前と変わってない？
他のアルゴリズムではこのように記述できない

つまりこんな書き方はできないってこと。

for_each( strings, []( s ){  // 将来的にはこう書ける様になるかも
  cout << s << endl;
} );

Effective STL 43項から

vの要素から条件「>x と <y」に合致するものを検索する。直接記述したループならこうなる

auto i = v.begin();        // iは後で使うのでループの外で宣言
for( ; i != v.end(); ++i ){
  if( *i > x && *i < y ) break;
}

　
ラムダを使わないSTLなら（c++03）

auto i = find_if( v.begin(), v.end(), 
                  bind( logical_and<bool>(),
                   bind( greater<int>(), _1, x),
                   bind( less<int>(), _1, y ) ) );

真剣に書いてコレ。　
ラムダを使うと

auto i = find_if( v.begin(), v.end(), [=](int i){ return i > x && i < y; } );

非常に簡潔になる。

ラムダにより幾つかのSTLアルゴリズムを置き換えられる

vectorを使ったベタなループ

int sum = 0; long long product = 1;
for( auto i = value.begin(); i != values.end(); ++i){
  sum += +i; product *= +i;
}

　
ラムダを使わないSTL

int sum = accumulate( c.begin(), c.end(); 0 );
long long product = accumulate( c.begin(), c.end(), 1, multiplies<int>() );

Multi-passだと遅い。また変数のゴミが残る。　

ラムダとSTLの併用

int sum = 0; long long product = 1;
for_each( values.begin(), values.end(), [&]( int i ){
  sum += i; product *= i;
} );

accumulate()よりもより簡潔に、かつ可読性が上がる　

パフォーマンスメモ

以下の変数strが与えられたとする

char str[] = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";

基本のポインタによるループ

char *end = &str[52];
for( char *p = str; p != end; ++p )
  ++*p;
}

for_each、イテレータとラムダを用いる

array_range<char> r(str);   // バウンダリチェック済イテレータラッパー
for_eacch( r, [](char& c){ ++c; } );

array_range()はプロトタイプでまだ採用されていないものである点に注意。 VS2010 RC on Windows7のdebugビルドにて計測すると、最悪値でポインタループの1.8倍の速度であった（最善値では0.8倍）

これらから学んだこと

もう「手書きループのほうが良い」なんて言えないよね？
ラムダを使うことにより、algorithmは更に良くなる
- パフォーマンスの向上
- 正確性、デバッグのしやすさ
- 明確さ。可読性の向上。
幾つかのSTLを置き換えることすら可能
ラムダは任意長の本体と同様に動作する *3
- 明らかな結果：すべてのalgorithmが言語機能としてループとなりえる
- その意味：アナタの書いた任意のalgorithmが含まれる
- 結論：新しいループや機能がほしいでしょう？さぁ"関数"を書こう。言語に新しいループ機能を追加するように。。。

新しいアルゴリズムを書いたよね？

全要素について"step"を実施する

template<typename C, typename F>
void for_each_nth( C& coll, step s, F func){
 ...
}

　
新種のループが書けるよ！

// for every 3rd element in v...
for_each_nth( v, 3, []( Widget& w )){
 ...
});

どんなループでも・・・

C++のループの代わりに

do{
  // do this while ...
)while( !Done() );

　
もっと簡単な書き方

do_while( [&]{
   // do this while ...
}, []{ return !Done(); } );

　
もしパスカルライクな記法がお好みならrepeat_untilを使ったループもある

repeat_until( [&]{
   // do this until ...
}, []{ return Done(); } );

どんな種類のalgorithmでも

こんなC#/Javaなコードの代わりに

lock( mutX ){
  ... use x ...
}

synchronized( mutX ){
   ... use x ...
}

こんな書き方ができる

{
  lock_guard<mutex> hold( mutX );
   ... use x ...
}

もしC#/javaライクなスタイルがお好みならそれも簡単にこう書ける

lock( mutX, [&]{
  ... use x ...
});

synchronized( mutX, [&]{
  ... use x ...
});

アクティブオブジェクト：対象にしているのは

独自のスレッドで動作するアクティブオブジェクト
- 各オブジェクトは非同期エージェントである
メソッド呼び出しは非同期メッセージングとなる
- メソッドシンタックスは理解しやすく、コードも汎用的になる *4
- アクティブオブジェクトスレッドのメインラインはメッセージパンプである。シーケンシャルなメッセージ処理はそれらをお互いにアトミックにし、内部・外部にロック構造を必要としない　　例）

class Active {
public:
  void Func(){ ... }
};

// 呼び出しコード。アクティブオブジェクトを使用する
Active a;
a.Func();    // ノンブロッキングな呼び出し
 ... more work

class Backgrounder{
public:
  void Save( string filename ){
    a.Send( bind( &Backgrounder::DoSave, this, filename ) );
  }

  void Print( Data& data ){
    a.Send( bind( &Backgrounder::DoPrint, this ref(data) ) );
  }   // ref()が重要！

private:
  ...       // スレッド内部データ
  Active a; // スレッドメッセージキュー、ループをカプセル化
  void DoSave( string filename ){ ... }
  void DoPrint( Data& data ){ ... }
};

class Backgrounder{
public:
  void Save( string filename ){ a.Send( [=]{
    ...
  }); }

  void Print( Data& data ){ a.Send( [=, &data] {
    ...
  }); }
private:
  ...       // スレッドローカルデータ
  Active a;
};

何を学べた？

堅牢なクラス定義を通常の記述と変わらない方法で記述できた
ヘルパーメンバを追加して、単に "a.Send([=] {"という風に各メンバ関数の先頭に記述すれば良い
言語に組み込まれているアクティブオブジェクトがなくっても悪くはない

シーケンシャルループ

Foo()を配列の各要素に適用する

void DoFoo( float a[], int n ){
  for( int i = 0; i < n; ++i ){
    Foo( a[i] );
  }
}

同じことがstd::for_eachでできる

void DoFoo( float a[], int n ){
  for_each( &a[0], &a[0]+n, [](float f){
    Foo( f );
  } );
}

Intel TBB parallel_for

最初にファンクタを定義する

class ApplyFoo{
  float *const my_a;
public:
  void operator(){ const blocked_range<int>& r ) cconst {
    float *a = my_a;
    for( int i = r.begin(); i != r.end(); ++i ){
      Foo( a[i] );
    }
  }

  ApplyFoo( float a[] ):my_a(a){}
};

次に、parallel_forを使う

void DoFoo( float a[], int n ){
  parallel_for( blocked_range<int>(0, n), ApplyFoo(a) );
}

Intel TBB 2.2+でラムダったparallel_for

void DoFoo( float a[], int n ){
  parallel_for( 0, n, 1, [=](int i){ Foo( a[i] ); } );
}

こっちの書き方も可能

void DoFoo( float a[], int n ){
  parallel_for( 0, n, 1, [=](int i){
    Foo( a[i] );
  } );
}

　
（このあと同じコードの VS2010のサンプルがあるけど省略）

スケーラブル並列処理

このシーケンシャルなコードを考えている

void SendPackets( Buffers& buf ){
  for( auto b : bufs ){
    Decorate( b );
    Compress( b );
    Encrypt( b );
  }
}

　
ループ内で呼び出している関数について考察する * お互いに副作用は無いと仮定する（もしそうならパイプラインループが可能） * 処理されるパケットの順は不同とする（もしそうなら完全な並列化が可能）

分割して統治

スレッドプール、もしくはPPLタスクグループであるpoolが与えられたとする

void SendPackets( Buffers& bufs ){
  auto i = bufs.begin();
  while( i != bufs.end() ){
    auto next = i + min( chunkSize, distance(i, bufs.end()) );
    pool.run( [=]{
      for( i = first; i != next; ++i ){
        Decorate( *i );
        Compress( *i );
        Encrypt( *i );
      }
    } );
    i = next;
  }
  pool.join();
}

何を学んだか

ラムダは並列ループ、分解、fork/joinなどが簡単に記述できる
- ループ内部が並列に実行されることに寄り、アルゴリズムの一箇所だけに集中できる
- コード自体も構造化な状態が維持される。これ重要。

初期化

"tohava"によるサンプル

int x = 1;       // constであるべき、だが
for( int i = 2; i <= N; ++i ){
  x += i;        // この様な幾つかの処理が必要な初期化もある
}                // この場合にxは単純にconst宣言はできない
// この時点からxがconstになるべきである

この様なxをどうやってconstにしようか？？

案１ : まぁまぁ

初期化処理を関数に分割する

int XInit( int N ){
  int ret = 1;
  for( int i = 2; i <= N; ++i ){
    ret += i;
  }
  return ret;
}

その後、、、

  const int x = XInit( N  );  // 成功する

利点：動く
欠点：局所性を失う。関数名の爆発（AInit, BInit, CInit....)

案２ : もっと良い方法オリジナルコードをラムダ化する

const int x = [=]{
  int ret = 1;
  for( int i = 2; i <= N; ++i ){
    ret += i;
  }
  return ret;   // 戻り値でxを初期化
}();

利点
1. 動く
2. 局所性を失わない
3. 新しい関数名不要

初期化　：　さらなる問題点

David Svobodaからの変数のサンプル

int x = 0;  /* ダミー値 */
try{
  for( int i = 2; i <= N; ++i ){
    x += Calc(i);      // この値で初期化！
  }
}
catch( XInitException ){
  x = 0;               // か、例外時は0で！
}
// ここ以降xはconstになるべき

　
ラムダを用いた解決案

const int x = [=] -> int{
  try{
    int ret = 0;
    for( int i = 2; i <= N; ++i){
      ret += Calc(i);
    }
    return ret;
  }
  catch( XInitException ){
    return 0;
  }
}();

<< p.32からは今度追記する >>

*1:win機のcygwinでトライしてみたけど何か上手くいってない・・・

*2:原文：Possible Alternative Polymorphic Syntax

*3:原文：work equally well for bodies of arbitrary length

*4:原文： lets generic code treat active and ordinary objects uniformly