続編へ

解説: Ruby/mruby LINQ ライク・メソッド

2012-07-05 (鈴)

1. はじめに

"Ruby 1.8.7 からの LINQ ライクな Enumerable メソッド" では,C# の LINQ と実質的に同じものである Ruby 2.0.0 開発版の Enumerator::Lazy と同等の機能を,Enumerable モジュールのメソッドとして Ruby 1.8.7 や mruby で実現できることを示した。

今までこのような機能は,Ruby 言語の設計者による 2006年1月25日のメモ (Y. Matsumoto: [Ruby] 遅延Enumerable [rubyist.net]) で漠然と構想されていたように,外部イテレータ Enumerator のようなものが必要であると暗黙のうちに考えられていた:

ところで、現在Enumerable#selectなど一連のメソッドは Arrayを返しているわけだが、これを Enumeratorを返すようにすると、一種の遅延実行が実現できるのではないだろうか。

確認できる限りでは,外部イテレータが実際には必要でないことを指摘したのは 2009年11月11日の ku-ma-me: [Ruby] enumerabler.rb: Enumerable の遅延評価版メソッドライブラリ [hatena.jp] が最初である。 その実装は依然として,2008年11月3日の B. Candler: Feature #708: Lazy Enumerator#select, Enumerator#map etc. [ruby-lang.org] と同じく Ruby 1.9 以降のブロック付き Enumerator コンストラクタを使うものであったが,次のように明言していた:

いいえ、enumerabler.rb を使うだけでは、Fiber の生成や呼び出しは一切起こりません。なぜだか気になる人は Ruby のソースを読んでください。
見てきたように書いていますが,実際はこのところ調べた事のまとめです。 今の視点から見れば, Enumerator を本来の Enumerator の役割である外部イテレータとしては使っていないという指摘がなされた時点で,そこからもう一歩だけ推し進めて,当時おそらく最も普及していた Ruby 1.8.6 による実現の可能性まで考えが及んでいたならば,と思います。

実際には "Ruby 1.8.7 からの LINQ ライクな Enumerable メソッド - 第3節" で示したように,そうしたメソッドを作るためには Enumerator クラスを必要としないどころか,ほとんど引数の受け渡しとその呼び出ししかしていない,まるで中身がないような簡単なコードで十分である。 _enum.rb を初めて見たとき,少なくない読者が狐につままれたような,何かごまかされたような気がしたのではないかと思う。 本稿では,この,字面では全く単純にみえながら動作が必ずしも自明ではないコードの説明を試みる。 それとともに,時間的・空間的な計算量の点でも特に問題がないことを示す。

2. 実験

_enum.rb (行番号付き閲覧用ソース) の動作を確認するために下記のスクリプトを実行しよう。 このスクリプトでは,_enum.rb が定義する Enumerable::Iterator クラスの each メソッドと Enumerable::Iterator::Yielder クラスの << メソッドを再定義して,メソッドの入り口と出口でその時点の入れ子深さを - の列で表示するようにしている。 みかけは begin … ensure …end で厳めしくなっているが,動作確認用の表示を除く実質的な内容は元の定義と同じである。

     1  #!/usr/bin/ruby
     2  
     3  require '_enum'
     4  
     5  module Enumerable
     6  
     7    class Iterator
     8      include Enumerable
     9      def initialize(block); @block = block; end
    10      def each(&body)
    11        $nest += 1
    12        puts "-" * $nest + "(" + body.to_s + " " + @block.to_s
    13        begin
    14          @block[Yielder.new(body)]
    15        ensure
    16          puts "-" * $nest + ")"
    17          $nest -= 1
    18        end
    19      end
    20  
    21      class Yielder
    22        def initialize(body); @body = body; end
    23        def << (val)
    24          $nest += 1
    25          puts "-" * $nest + "<" + @body.to_s + " " + val
    26          begin
    27            @body[val]
    28          ensure
    29            puts "-" * $nest + ">"
    30            $nest -= 1
    31          end
    32        end
    33      end
    34    end
    35  end
    36  
    37  $nest = 0
    38  p (1..300)._map{|k| k.to_s}._select{|s| /3/ === s}._take(3).to_a

Mac OS X 10.6.8 上の ruby 1.8.7 (2010-01-10 patchlevel 249) での実行例を下記に示す。 Proc インスタンスの文字列表現に含まれるファイル名と行番号から処理の流れを追跡されたい (そのために本稿では掲載ソースに行番号を付した)。

01:~/tmp$ ./enum_test.rb
-(#<Proc:0x002199cc@./enum_test.rb:38> #<Proc:0x0021aea8@./_enum.rb:110>
--(#<Proc:0x0021b060@./_enum.rb:113> #<Proc:0x0021c050@./_enum.rb:78>
---(#<Proc:0x0021c0a0@./_enum.rb:78> #<Proc:0x0021d3d8@./_enum.rb:29>
----<#<Proc:0x0021c0a0@./_enum.rb:78> 1
---->
----<#<Proc:0x0021c0a0@./_enum.rb:78> 2
---->
----<#<Proc:0x0021c0a0@./_enum.rb:78> 3
-----<#<Proc:0x0021b060@./_enum.rb:113> 3
------<#<Proc:0x002199cc@./enum_test.rb:38> 3
------>
----->
---->
----<#<Proc:0x0021c0a0@./_enum.rb:78> 4
---->
----<#<Proc:0x0021c0a0@./_enum.rb:78> 5
---->
----<#<Proc:0x0021c0a0@./_enum.rb:78> 6
---->
----<#<Proc:0x0021c0a0@./_enum.rb:78> 7
---->
----<#<Proc:0x0021c0a0@./_enum.rb:78> 8
---->
----<#<Proc:0x0021c0a0@./_enum.rb:78> 9
---->
----<#<Proc:0x0021c0a0@./_enum.rb:78> 10
---->
----<#<Proc:0x0021c0a0@./_enum.rb:78> 11
---->
----<#<Proc:0x0021c0a0@./_enum.rb:78> 12
---->
----<#<Proc:0x0021c0a0@./_enum.rb:78> 13
-----<#<Proc:0x0021b060@./_enum.rb:113> 13
------<#<Proc:0x002199cc@./enum_test.rb:38> 13
------>
----->
---->
----<#<Proc:0x0021c0a0@./_enum.rb:78> 14
---->
----<#<Proc:0x0021c0a0@./_enum.rb:78> 15
---->
----<#<Proc:0x0021c0a0@./_enum.rb:78> 16
---->
----<#<Proc:0x0021c0a0@./_enum.rb:78> 17
---->
----<#<Proc:0x0021c0a0@./_enum.rb:78> 18
---->
----<#<Proc:0x0021c0a0@./_enum.rb:78> 19
---->
----<#<Proc:0x0021c0a0@./_enum.rb:78> 20
---->
----<#<Proc:0x0021c0a0@./_enum.rb:78> 21
---->
----<#<Proc:0x0021c0a0@./_enum.rb:78> 22
---->
----<#<Proc:0x0021c0a0@./_enum.rb:78> 23
-----<#<Proc:0x0021b060@./_enum.rb:113> 23
------<#<Proc:0x002199cc@./enum_test.rb:38> 23
------>
----->
---->
---)
--)
-)
["3", "13", "23"]
01:~/tmp$  

3. 実験結果の解説

スクリプト末尾の

p (1..300)._map{|k| k.to_s}._select{|s| /3/ === s}._take(3).to_a

が実行されるとき,まず,式 (1..300)._map{|k| k.to_s}._select{|s| /3/ === s}._take(3) が評価される。 そしてその結果の値である Enumerable::Iterator インスタンスをレシーバとして to_a メソッドが呼び出される。

to_a メソッドはレシーバの each メソッドを呼び出し,each メソッドはさらに _take メソッド内の iterator のブロック引数を呼び出す。

実験結果の
-(#<Proc:0x002199cc@./enum_test.rb:38> #<Proc:0x0021aea8@./_enum.rb:110>
はこの呼び出しに対応します。

それは each メソッドを呼出し,each メソッドはさらに _select こと _find_all メソッド内の iterator のブロック引数を呼び出す。

実験結果の
--(#<Proc:0x0021b060@./_enum.rb:113> #<Proc:0x0021c050@./_enum.rb:78>
はこの呼び出しに対応します。

それは each メソッドを呼出し,each メソッドはさらに _map こと _collect メソッド内の iterator のブロック引数を呼び出す。

実験結果の
---(#<Proc:0x0021c0a0@./_enum.rb:78> #<Proc:0x0021d3d8@./_enum.rb:29>
はこの呼び出しに対応します。
ここまではそれぞれ1回ずつしか起こりません。つまり _take などの各メソッドの iterator のブロック引数 (Enumerable::Iterator インスタンスの @block) の呼び出しはそれぞれ1回どおりだけです。

それは each メソッドを呼び出し,each メソッドは (1..300) をレシーバとして,繰返し本体 {|e| y << (yield e)}複数回実行する

本来ならば 300 回実行しますが,この実験では _take での break により 23 回で打ち切られます。

そのたびに (yield e) によって _collect のブロック引数 {|k| k.to_s} が実行され,その結果の値を引数として,y << によって _find_all 内の each の繰返し本体が呼び出される。

実験結果の
----<#<Proc:0x0021c0a0@./_enum.rb:78> n
(ただし 1 ≤ n ≤ 23) はこの呼び出しに対応します。

そのたびに _find_all 内の each の繰返し本体内の yield e によって _find_all のブロック引数 {|s| /3/ === s} が実行され,その結果が真ならば y << e によって _take 内の each の繰返し本体が呼び出される。

実験結果の
-----<#<Proc:0x0021b060@./_enum.rb:113> n
(ただし n = 3, 13, 23) はこの呼び出しに対応します。

そのたびに _take 内の each の繰返し本体内の y << e によって to_a 内の each の繰返し本体が実行される。

実験結果の
------<#<Proc:0x002199cc@./enum_test.rb:38> n
(ただし n = 3, 13, 23) はこの呼び出しに対応します。 to_a 内の each の繰返し本体に該当する部分は ruby 処理系に組み込まれていますから,ここでは to_a を呼び出したスクリプトとその行番号 ./enum_test.rb:38 が表示されています。

_take 内の each の繰返しが所定回数 (ここでは 3 回) に達したとき,繰返し本体内から breakeach の次へと脱出する。

_take, _find_all, _collect の三者に関する呼出し階層で,_takeeach の繰返し本体は最末端に位置し,それを取り囲む周辺部分は最基層に位置する。 最末端から最基層に break するとき,呼出しスタックが一気に,しかしあくまで正しく畳まれる。

実験結果の末尾近くで
------>
----->
---->
---)
--)
と,一つずつ入れ子深さが戻っていることに注意してください。 それぞれの呼び出し階層で,打ち切り時にそれぞれ正しく ensure 節が実行されていることが分かります。

なお,実験結果から分かるとおり,呼び出しの入れ子深さはメソッド連鎖の長さのおおよそ2倍になる。 まず各 each メソッドが連鎖の逆順に1回どおり呼び出され,その深さからさらに, each に与えられた繰返し本体が何回も連鎖の順に呼び出される。 実行時に必要となるスタックの大きさは概ねメソッド連鎖の長さに比例する。 入力量に伴って必要なメモリ量が増大する要因は,これらのメソッド自身にはない,つまり入力量に対しては変化しない。

メソッド連鎖のおおもとのレシーバ (ここでは (1..300)) が与える1個の要素値に対して,連鎖の順にそれぞれたかだか1回どおりの繰返しが駆動されるだけだから, 要素1個に対するオーバーヘッドは概ねメソッド連鎖の長さに比例する。 入力量に伴って1個あたりに必要な計算の手間が増大する要因は,これらのメソッド自身にはない,つまり入力量に対しては比例する。

つまり,空間的にも,時間的にも,実行時の入力に対する計算量のオーダーは,同じ処理を単純なループで構成した場合と変わらない。

4. クロージャと自由変数

もしもまだ理解しにくいときは,each メソッドの繰返し本体とその周辺が平坦につながっているわけではないことを思い出されたい。

下記に _enum.rb から _take メソッドの定義を示す。 緑色に塗った部分は,今回の実験で1回しか実行されない。 一方,each の繰返し本体となる茶色の部分は3回実行される。 ただ回数が異なるだけではない。 両者は別々の関数呼び出しとして実行される。 3回の実行とは3回の呼び出しである。

前節で解説したように,実行時,両者のスタック・フレーム間には _select こと _find_all と,_map こと _collect に関する呼出し階層がまるまるはさまっており,break 時にはその階層がすべて畳まれる。

   109    def _take(n)
   110      iterator {|y|
   111        if n > 0
   112          i = 0
   113          each {|e|
   114            i += 1
   115            y << e
   116            break unless i < n
   117          } 
   118        end
   119      } 
   120    end
仮に,呼び出しごとに "標高" が高くなるとすれば,緑色の部分はいわば平野であり,茶色の部分はそこから突出して高くなった山岳地帯です。 break 時には山の頂上付近からふもとの平野まで一気に駆け下りるわけです。

茶色の部分は,呼び出しのたびに新しいデータ値 e が与えられる。 しかし,ループ・カウンタである i前回の呼び出しのときの値が継続して使われる。

スレッドまたはコルーチン (coroutine) を内部実装としてもつ外部イテレータが必要になりそうだという直観はたしかに,ある意味,妥当だった。 新しいデータ値がもたらされて繰返し本体に制御が戻ったとき,前回と同じローカル変数が再現される必要があるからである。

しかし,もしも繰返し本体がブロックとしてまとまっているならば,そのブロックをクロージャ (closure) とするだけで十分である。 このときは,再現されるべきローカル変数を,繰返し本体の周辺の地の部分 (つまり,茶色の山間部に対する緑色の平野部) で設けておき,そのクロージャにとっての自由変数 (free variable) とすればよい。

クロージャが呼び出されるたびに,ローカル変数は自由変数としてそこに現れ,前回から継続して読み書きされる。 繰返しが終了して制御が地の部分に戻ったときも,もちろん同じローカル変数が継続して使われる。

以上のために必要なメカニズム一式を Ruby はもともとブロック付きメソッドを実現するために用意している。 新しく作り上げるべきことはほとんどない。 これが,ほとんど引数の受け渡しとその呼び出ししかしていない,まるで中身がないようなクラス定義で,あたかも魔法のように LINQ ライクなメソッドを実現できる理由である。

5. おわりに

本稿では LINQ ライクな Enumerable メソッドの実装である _enum.rb の動作について解説した。 実行時,ループの地の部分が最初に1回どおりメソッド連鎖をさかのぼって呼び出され, そこから各データごとにループ本体がメソッド連鎖の順に呼び出される。 前回のループまでのローカル変数の復元は,クロージャを実体とする Ruby のブロックからの自由変数の参照として自動的に行われる。

本質的に外部イテレータを必要とする _zip と, Enumerator インスタンスを戻り値とするブロック引数省略時の動作を除き, 実装に必要な機能は,遅くとも,まだ Enumerator が導入されない Ruby 1.8.6 の時点で (おそらく実際にはほとんど草創期から) すべてそろっていた。現在の mruby でもそろっている。 本稿ではそのことを動作の解説を通して示した。

前世紀末の 1999 年に出版された,
まつもと, 石塚:「オブジェクト指向スクリプト言語 Ruby」, アスキー, 1999, ISBN 4-7561-3254-5
を読むかぎり,この時点ですでに LINQ ライクなメソッドの実装に必要な機能はそろっています。 つまり,6 年半前 (資料でさかのぼることができる 2006年 1月25日) から探し求められていた青い鳥は,実ははじめからずっとそばにいたわけです。

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