続編へ

Ruby 2.0 メモ: Lazy と LINQ とループ融合

2012-06-15 (鈴)

1. はじめに

本稿では Ruby 2.0 に予定されている Enumerator::Lazy について,先行する概念と対照して考察する。 それが計算量の観点からループ融合の最適化に等しいことを非形式的に論ずる。 また,C# の LINQ と実質的に同じものであることを示す。 以上の議論から Enumerator::Lazy が来るべき Ruby 2.0 の最も重要な機能の一つであることを示す。

2. Ruby 2.0 開発版のインストール

執筆時現在,Ruby 2.0 の処理系は https://github.com/ruby/ruby から

$ git clone https://github.com/ruby/ruby.git

として開発版を入手できる。 git [git-scm.com] をインストールしていない, あるいは通信経路・プロトコルの制限等により git が使えない環境でも同ページの Downloads リンクから HTTPS 経由で tar.gz ファイルをダウンロードできる。

現在,最新版の tar.gz ファイルの URL はリビジョンにかかわらず https://nodeload.github.com/ruby/ruby/tarball/master です。 しかし,(企業内からのアクセス経路にしばしば設置され,man in the middle として HTTPS の通信内容を平文でモニタするタイプの) HTTP プロキシを経由してダウンロードする場合は,プロキシで同一のリクエストであると判断されて, いつまでも同じ古いファイルがプロキシのキャッシュから返されることがあります。 そのような場合,バッド・ノウハウですが,例えば今が 6 月 8 日の朝であると仮定してその時点での最新版 0d92aac602 を取るには https://nodeload.github.com/ruby/ruby/tarball/0d92aac のように URL を指定して ruby-ruby-0d92aac.tar.gz をダウンロードします。

6 月 8 日朝の 0d92aac602 を https://github.com/ruby/ruby の Downloads リンクから ruby-ruby-0d92aac.tar.gz としてダウンロードし,~/src にソースを展開して ~/ruby-2.0.0 にバイナリを構築した。 下記は Linux (Vine Linux 5.2) の例だが Mac OS X 等でも同様である。

01:~/src$ tar xf ruby-ruby-0d92aac.tar.gz
01:~/src$ cd ruby-ruby-0d92aac
01:~/src/ruby-ruby-0d92aac$ autoconf -v
……出力略……
01:~/src/ruby-ruby-0d92aac$ ./configure --prefix="$HOME/ruby-2.0.0"
……出力略……
01:~/src/ruby-ruby-0d92aac$ make
……出力略……
01:~/src/ruby-ruby-0d92aac$ make install
……出力略……
01:~/src/ruby-ruby-0d92aac$ cd
01:~$ ./ruby-2.0.0/bin/ruby -v
ruby 2.0.0dev (2012-06-07) [i686-linux]
01:~$ ./ruby-2.0.0/bin/irb --simple-prompt
>>  

3. Enumerator::Lazy

Ruby で 1 から 30 までの整数のうち十進表現に 3 が含まれるものの最初の三つを求めるには,

>> (1..30).map{|i| i.to_s}.select{|s| /3/ === s}.take(3)
=> ["3", "13", "23"]

1 から 30 までの整数について

  1. Enumerable#map で各整数を文字列化する。 => ["1", "2", "3", ……略……, "28", "29", "30"]
  2. Enumerable#select で文字列に 3 が出現するものを正規表現で選択する。=> ["3", "13", "23", "30"]
  3. Enumerable#take で先頭の三つを取り出す。=> ["3", "13", "23"]

しかし,これには明らかな無駄がある。 map メソッドや select メソッドはそれぞれ計算結果を Array 値としていったん完成させてから次に渡している。 そのため 23 まで数え上げれば十分なのに,24 から 30 まで余分に同じだけの処理をして計算時間とメモリを費やしている。

演算過程を分かりやすくするため print をさしはさむと,この様子を垣間見ることができる。

>> (1..30).map{|i| print i; i.to_s}.select{|s| print '-'; /3/ === s}.take(3)
123456789101112131415161718192021222324252627282930------------------------------=> ["3
", "13", "23"]

ここで Ruby 2.0 の新しいメソッド Enumerable#lazy を使うと,この無駄をなくすことができる。 lazy メソッドが結果として返す値の型は,ある特別な Enumerable 型である。 Enumerable 型には違いないから,従来の式に置き換えることができる。 しかしこの型は,結果を Array ではなくやはりその特別な Enumerable 型として返すように map メソッドや select メソッドを再定義している。 mapselect の演算は実際に要素の値が必要になったとき行われる。 実際に要素の値を必要とさせる典型的な方法として Array 型へと変換する Enumerable#to_a メソッドがある。

lazy メソッドを使った下記の例は,print の出力から確認できるように,1 から順に一つ一つ文字列化してから 3 が出現するものを選択し,先頭の三つが得られたところで終了している。

>> (1..30).lazy.map{|i| print i; i.to_s}.select{|s| print '-'; /3/ === s}.take(3).to_a
1-2-3-4-5-6-7-8-9-10-11-12-13-14-15-16-17-18-19-20-21-22-23-=> ["3", "13", "23"]

この式の意味を操作的に言えば,

  1. to_a が結果の Array 値を得るために,自分のレシーバに最初の要素を要求する。
  2. これに応えるため take(3) の結果が自分のレシーバにその最初の要素を要求する。
  3. これに応えるため select の結果が自分のレシーバにその最初の要素を要求する。
  4. これに応えるため map の結果が自分のレシーバにその最初の要素を要求する。
  5. これに応えるため (1..30).lazy の結果が 1 を返す。
  6. これから map の結果が "1" を返す。 (以下,簡単のため「の結果」と「自分のレシーバに」を省略する)
  7. これを selectfalse と評価する。 これは take(3) に返せないから,次の要素を map に要求する。
  8. これに応えるため map が次の要素を要求する。
  9. これに応えるため (1..30).lazy2 を返す。
  10. これから map"2" を返す。
  11. これを selectfalse と評価する。 これは take(3) に返せないから,さらに次の要素を map に要求する。
  12. これに応えるため map がさらに次の要素を要求する。
  13. これに応えるため (1..30).lazy3 を返す。
  14. これから map"3" を返す。
  15. これを selecttrue と評価し,"3" を返す。
  16. これから take(3)"3" を返す。
  17. これを to_a が結果の Array の最初の要素とする。
  18. それから to_a が結果の Array の次の要素を要求する……等々である。

もしも末尾の to_a が無ければ,特にこれといった演算をせずに,その特別な Enumerable 型のインスタンスを式の評価結果の値として作っただけで終わる。

>> (1..30).lazy.map{|i| print i; i.to_s}.select{|s| print '-'; /3/ === s}.take(3)
=> #<Enumerator::Lazy: #<Enumerator::Lazy: #<Enumerator::Lazy: #<Enumerator::Lazy: 1..3
0>:map>:select>:take(3)>

これに見るように,その特別な Enumerable 型とは Enumerator::Lazy である。 典型的には, Enumerator::Lazy のインスタンスは Enumerable#lazy メソッドの戻り値として得られるほか,(Enumerator::Lazy#map などのように) 元々は Array を返すように定義されていた (が,Enumerator::Lazy で再定義された) Enumerable メソッドの戻り値として得られる。

lazy メソッドの結果をじかに見ると,たしかに
>> (1..30).lazy
=> #<Enumerator::Lazy: 1..30>
>> (1..30).lazy.is_a? Enumerator::Lazy
=> true
となります。その継承関係は
>> Enumerator::Lazy.superclass
=> Enumerator
>> Enumerator.include? Enumerable
=> true
ですから,Enumerator::Lazy と Enumerable の関係も推移的に
>> Enumerator::Lazy.include? Enumerable
=> true
となります。 したがって Enumerator::Lazy は Enumerable メソッドをすべて使うことができますが,特に Enumerator::Lazy で定義または再定義しているインスタンス・メソッドを見ると次のとおりになります。
>> Enumerator::Lazy.instance_methods(false)
=> [:map, :collect, :flat_map, :collect_concat, :select, :find_all, :reject, :grep,
 :zip, :take, :take_while, :drop, :drop_while, :cycle, :lazy, :force]
Enumerator::Lazy は map, select, take のような元々は Array インスタンスを返すように定義されたメソッドを,Enumerator::Lazy インスタンスを返すように再定義しています。

print を外すと,最初の例とは lazyto_a が追加されている以外に見かけ上の違いはない。

>> (1..30).lazy.map{|i| i.to_s}.select{|s| /3/ === s}.take(3).to_a
=> ["3", "13", "23"]

しかし,入力が大きくなっても同じように動くかどうかという点で実質的に異なる。

>> (1..3000000000).lazy.map{|i| i.to_s}.select{|s| /3/ === s}.take(3).to_a
=> ["3", "13", "23"]
>> (1..3000000000).map{|i| i.to_s}.select{|s| /3/ === s}.take(3)
……計算にとりかかったまま戻ってこない……

4. ループ融合としての解釈

lazy を使わない例

>> (1..30).map{|i| print i; i.to_s}.select{|s| print '-'; /3/ === s}.take(3)
123456789101112131415161718192021222324252627282930------------------------------=> ["3
", "13", "23"]

の操作を伝統的なループにあてはめると次のようになる。

seq1 = []
for i in 1..30
  print i
  s = i.to_s
  seq1.push(s)
end

seq2 = []
for s in seq1
  print '-'
  next unless /3/ === s
  seq2.push(s)
end

seq3 = []
len = 0
for s in seq2
  break if len == 3
  seq3.push(s)
  len += 1
end

seq3

これをファイル rb1.rb として保存して実行すると,

>> eval File.new("rb1.rb").read
123456789101112131415161718192021222324252627282930------------------------------=> ["3
", "13", "23"]

一方,lazy を使った例

>> (1..30).lazy.map{|i| print i; i.to_s}.select{|s| print '-'; /3/ === s}.take(3).to_a
1-2-3-4-5-6-7-8-9-10-11-12-13-14-15-16-17-18-19-20-21-22-23-=> ["3", "13", "23"]

の操作を伝統的なループにあてはめると次のようになる。 全体の処理が一つの大きなループへと融合している点に注意されたい。

seq3 = []
len = 0
for i in 1..30
  break if len == 3

  print i
  s = i.to_s

  print '-'
  next unless /3/ === s

  seq3.push(s)
  len += 1
end

seq3

これをファイル rb2.rb として保存して実行すると,

>> eval File.new("rb2.rb").read
1-2-3-4-5-6-7-8-9-10-11-12-13-14-15-16-17-18-19-20-21-22-23-=> ["3", "13", "23"]

ループへと変形した前後で操作を変えていないから, 現在の Ruby 2.0.0 実装と,ループにあてはめたかたちの計算量のオーダーは同じであると見てよい。 入力が大きなとき (例えば 1..3000000000),lazy を使わない版は,それに比例した空間 (つまりメモリ) と時間が,計算途中の結果を保つために必要となる。 一方,lazy を使う版では (take(3)if len == 3 を変更しない限り) 計算量は変わらない。

つまり,Enumerator::Lazy は,処理の各ステップの字面上のモジュール性を維持したまま, 計算量の観点では ループ融合の最適化をしていると言える。

(字面の上で) モジュール性を維持している (この例では map, select, take の3ステップへの分割を維持している) ことは,将来的な問題の複雑化に人間が (部分問題へと分解することで) 対応できることにつながる。 (計算量の観点で) ループ融合の最適化をしていることは,あくまで一つの要因にすぎないとはいえ, 将来的な問題の大規模化に対し計算機が破綻せずに演算できることにつながる。

Enumerator::Lazy は決してあらゆる問題を解決する万能薬ではないが,Ruby 2.0 の最も興味深い新機能であるといって過言ではない。

現在の Ruby 2.0.0 開発版の内部で行われる処理はもっと非効率なようですが, 原理的な可能性としては,静的であれ動的であれ,ループへと変形することがきっと可能でしょう。 他言語のはなしですが,現に C# 2.0 以降のコンパイラは,いわゆる内部イテレータとして字面の上で記述されたメソッド定義を, 大胆なコード変形によって,いかなる意味のスレッドも必要としない効率の良い外部イテレータへと変換しています (A. Hejlsberg et al.: "The C# Programming Language", 4th Ed., Addison-Wesley, 2011, ISBN 978-0-321-74176-9 の 10.14.6 節 pp.597-605 参照)。 この変換を,手続き間最適化によってもう一歩押し進めたところに目指すべき境地があります。 将来の Ruby 最適化コンパイラが挑戦すべき課題と言えるでしょう。

5. C# の LINQ との比較

Enumerator::Lazy は決して新規の概念ではない。 遅延評価の典型的な応用例として遅延リスト (残りの要素を約束として持つリスト) が従来から有名である (なぜ関数プログラミングは重要か [sampou.org] と 簡単な遅延評価のプログラム例 を参照されたい)。 Enumerator::Lazy は Ruby 言語に対し,全面的に遅延評価の機構を取り込むような大改造を施すことなく,効果的に遅延リストの利点を取り入れたものと言える。

そして,これには重要な先例がある。 それは C# 3.0 以降で採られた LINQ (Language Integrated Query) である。 本節ではメソッド構文による LINQ を示すことで,両者が実質的に同じものであることを示そう。 以下の例ではオープンソースの .NET 互換環境 Mono [mono-project.com] の Mono.framework 2.10.9_11 for OS X を使った。

LINQ を説明する資料として LINQ: .NET Language Integrated Query [microsoft.com] が挙げられます。しかし,その和訳である LINQ: .NET 統合言語クエリ [microsoft.com] については注意してください。 LINQ は決して伝統的な意味での遅延評価 (lazy evaluation) そのものを実現するわけではありません。 それゆえ原文では慎重に Lazy の単語を避けて "Deferred Query Evaluation" としています。 和訳ではその心づかいに気付いていないのか,lazy と deferred の訳し分けをせず,そして注釈を付けずにこれを「クエリの遅延評価」と訳しています。

もっとも,もし仮に今から新しく訳語を決められるものならば,おそらく deferred にこそ 遅延 の訳語をあてるべきであり,lazy には 怠惰 か 怠け の訳語をあてるべきだったでしょう。 deferred evaluation が普通一般のいわゆる「遅延評価」の理解と一致している一方で,伝統的ながらあまり知られていない厳密な意味での lazy evaluation には,単に評価を必要になるまで遅らせるだけではなく,(ものぐさにも) 同じ式に対して一度評価したら二度としない,という含意があるわけですから。

普通一般には,しばしば単に関数クロージャ (closure) を必要なときに呼び出すだけのことを指して, あるいはその時になってクロージャにキャプチャされていた自由変数が参照されることを指して 「遅延評価」と呼ぶことがあります。 しかし,それだけでは,一度評価したら二度としない,という含意がありません。 関数クロージャをとることが当たり前な関数型プログラミングの世界でなお lazy evaluation という言葉が特別な意味合いを持っていることの理由を考えてください。

ただ,そう考えると Enumerator::Lazy の呼び名が微妙ですが,これは典型的な用法として遅延リスト (lazy list) に相当するものを (本来の意味での遅延評価とは異なったアプローチながらも) 実現するからと解すべきでしょう。
>> (1..30).lazy.map{|i| i.to_s}.select{|s| /3/ === s}.take(3).to_a
=> ["3", "13", "23"]

に相当する C# プログラムとそのコンパイル&実行例を示す。

using System;
using System.Linq;

class A
{
    static void Main(string[] args)
    {
        var x = Enumerable.Range(1, 30)
            .Select((i) => i.ToString())
            .Where((s) => s.Contains("3"))
            .Take(3)
            .ToArray();

        Console.WriteLine("=> " + String.Join(", ", x));
    }
}
01:~/tmp$ dmcs a.cs
01:~/tmp$ mono a.exe
=> 3, 13, 23
01:~/tmp$  

Ruby の (1..30).lazy が C# の Enumerable.Range(1, 30) に, mapSelect に, selectWhere に, takeTake に, to_aToArray にそれぞれ該当する。 (i) => i.ToString()i を仮引数とし,i.ToString() を結果の値とする匿名関数ないしラムダ式である。 i の有効範囲はこのラムダ式に限られる。 ラムダ式の引数と結果の値の型は自動的に型推論される。

変数 x"3", "13", "23" を要素とする String[] 値となる。 これを String.Join", " を要素間にはさみ, + 演算子で "=> " を接頭して Console.WriteLine でコンソールに表示している。

次に

>> (1..30).lazy.map{|i| print i; i.to_s}.select{|s| print '-'; /3/ === s}.take(3).to_a
1-2-3-4-5-6-7-8-9-10-11-12-13-14-15-16-17-18-19-20-21-22-23-=> ["3", "13", "23"]

に相当する C# プログラムとそのコンパイル&実行例を示す。

using System;
using System.Linq;

class B
{
    static void Main(string[] args)
    {
        var x = Enumerable.Range(1, 30)
            .Select((i) => {
                    Console.Write(i);
                    return i.ToString();
                })
            .Where((s) => {
                    Console.Write('-');
                    return s.Contains("3");
                })
            .Take(3)
            .ToArray();

        Console.WriteLine("=> " + String.Join(", ", x));
    }
}
01:~/tmp$ dmcs b.cs
01:~/tmp$ mono b.exe
1-2-3-4-5-6-7-8-9-10-11-12-13-14-15-16-17-18-19-20-21-22-23-=> 3, 13, 23
01:~/tmp$  

ラムダ式の本体を波括弧で囲んだ複数の文とすることができる。 このとき結果の値は return 文で指定する。 上記の実行結果から,C# の LINQ でも同様にループを融合したような動作をしていることが分かる。

ただし,LINQ の通常の用法から見ると,上に掲げた二つの C# プログラムは若干作為的である。 普通は次のように foreach 文を通して各要素を扱う。

using System;
using System.Linq;

class C
{
    static void Main(string[] args)
    {
        var x = Enumerable.Range(1, 30)
            .Select((i) => i.ToString())
            .Where((s) => s.Contains("3"))
            .Take(3);

        foreach (var e in x)
            Console.WriteLine(e);
    }
}
01:~/tmp$ dmcs c.cs
01:~/tmp$ mono c.exe
3
13
23
01:~/tmp$  

しかし,Ruby の Enumerator::Lazy もこれと同様のことができる。

>> x = (1..30).lazy.map{|i| i.to_s}.select{|s| /3/ === s}.take(3)
=> #<Enumerator::Lazy: #<Enumerator::Lazy: #<Enumerator::Lazy: #<Enumerator::Lazy: 1..3
0>:map>:select>:take(3)>
>> for e in x do puts e end
3
13
23
==> nil
>> x.each {|e| puts e}
3
13
23
==> nil
>>  
このように両者は似た者どうしです。 Ruby の for 式については Ruby チュートリアル - 2. 制御構造 第3節 を参照してください。

6. おわりに

LINQ の利点として LINQ to Objects [microsoft.com] では次の三つを挙げている。

  1. 簡潔で読みやすい (特に複数の条件をフィルター処理する場合)。
  2. 強力なフィルター処理,並べ替え,およびグループ化機能を最小限のアプリケーション コードで実現できる。
  3. ほとんど変更せずに,他のデータ ソースに移植できる。

Enumerator::Lazy によって Ruby もこの利点を享受することが可能になる。 今日 LINQ は必ずしも大成功を収めているわけではない。 しかし,構文的にぎこちないところがある C# と比べ,より軽やかな Ruby では Enumerator::Lazy が言語の中心的な機能になる見込みがありそうに思われる。 そのとき Ruby は関数型言語と特長の多くを共有することになるだろう。 惜しむらくはこれがあくまで後付けのクラスであり,単なる Enumerator とは呼ばれないことである。 逆に,これを Enumerator として再定義した Ruby の派生言語を考えたとき,広く普及した Ruby 1.8 との互換性を維持するためにどれだけの変更が Ruby 2.0 開発版に必要となるか,そしてどれだけの概念が簡素化され,表現力が強化されるかを考えることは,言語設計の興味深い課題となるだろう。

Ruby 2.0 の Enumerator::Lazy の直接の源流は Ruby 2.0 Enumerable::Lazy | Railsware Blog [railsware.com] (by I. Mihailov) にある。 同記事はこのトピックに関する最も重要な資料である。

本稿の執筆は 怠惰な Rubyist への道 - Enumerator::Lazy の使い方 [speakerdeck.com] (by C. Tomoyuki) に動機づけられた。 第3節の例は,その p.42 にある下記の例から直接のヒントを得た。

# 1 から 1000 のうち任意の桁に 7 を含む数を返す
(1..1000).lazy.map(&:to_s).select {|s|
   /7/ =~ s
}.force
本稿では,伝統的な意味での遅延評価を実現する Scheme の同名の手続きと微妙に一致しない force の語を避け,=~ のかわりに左辺にしたがって適切に振舞う簡略な関係演算子 === を使いました。 この関係演算子の使い方は Ruby の case 式 でおなじみのはずです。

Copyright (c) 2012 OKI Software Co., Ltd.