続編へ

Ruby 1.8.7 からの LINQ ライクな Enumerable メソッド

2012-06-27 (鈴)

1. はじめに

"Ruby 2.0 メモ: Lazy と LINQ とループ融合" では Ruby 2.0 に予定されている Enumerator::Lazy が C# の LINQ と実質的に同じものであることを示した。 本稿ではそれと同等の機能を Enumerable モジュールの拡張として Ruby 1.8.7 以降のすべてのバージョンの Ruby (2.0.0 開発版を含む) で実現できることを示す。

2. LINQ のアイディアと Enumerable

LINQ [microsoft.com] の中心的なアイディアは,何らかの「列」(sequence) に対し,列の要素を評価しないままそれに基づく新しい抽象的な列を戻り値として返すメソッドを用意することにある。 そのようなメソッドを連鎖させることで,列に対するパイプライン的な (実質的に,遅延リストと同じような) 処理を自然に表現できる。 このパイプラインでは結果のために必要となる要素しか計算が駆動されないから,列そのものは無限長であってもよい。

このような抽象的な列の概念は Ruby では Enumerable モジュールで表現される。 そればかりか (偶然にせよ) LINQ と共通するアイディアもすでに Ruby 1.8.7 以降の Enumerable に部分的に入っている。

同モジュールに Ruby 1.8.7 以降で導入された each_cons メソッドは,必要となる要素だけ計算する Enumerable インスタンス (厳密には,その実装クラス Enumerator のインスタンス) を戻り値として返す。 レシーバとなる元の Enumerable 値は無限長であってもよい。

>> (1..20).each_cons(3)
=> #<Enumerable::Enumerator:0x5b2598>
>> (1..20).each_cons(3).take(5)
=> [[1, 2, 3], [2, 3, 4], [3, 4, 5], [4, 5, 6], [5, 6, 7]]
>> (1 .. 1.0/0.0).each_cons(3).take(5)
=> [[1, 2, 3], [2, 3, 4], [3, 4, 5], [4, 5, 6], [5, 6, 7]]
>>  
each_cons および Enumerator は,正確には,Ruby 1.8.7 で導入された,というよりは Ruby 1.9 で初めて導入され,Ruby 1.8 系列には Ruby 1.8.7 でレトロフィットされたものです。 Ruby 1.9 の新機能のすべてが Ruby 1.8.7 にレトロフィットされたわけではありませんから,時系列から見ると不正確ですが,Ruby 1.8.7 で使える範囲の新機能をさして「Ruby 1.8.7 以降で導入された」と形容することにします。

3. LINQ ライクな Enumerable メソッド

「LINQ ライクな Enumerable メソッド」を Array ではなく要素未評価の Enumerable インスタンスを返す Enumerable のメソッドのことであるとしよう。 すでに見たように each_cons はそのようなメソッドの一つである。

一方,これに対し collectselect のような古くからの Enumerable メソッドは,要素をすべて評価して Array として戻り値を返す。

しかし,概念の世界における列から列へと写す関数の,プログラミング言語での実装として collectselect のような Enumerable から Array へと写すメソッドを与えたことは,抽象性の程度にバランスを欠いていたとも言える。 サイズも不確かな Enumerable からは,同様にサイズも不確かな Enumerable へと写すことがより自然である。 ここではそのような LINQ ライクな Enumerable メソッドを追加する。 より本来的で基本的なメソッドであるという意味を込めて,その名前は collectselect に対して下線を接頭した _collect_select とする。

Unix のライブラリ関数 exit とシステム・コール _exit を考えてください。

_collect の定義例を下記に示す。

module Enumerable

  # {|y| ... y << v ...} を内部イテレータに仕立てる
  class Iterator
    include Enumerable
    def initialize(block); @block = block; end
    def each(&body); @block[Yielder.new(body)]; end

    # {|y| ... y << v ...} での y となる
    class Yielder
      def initialize(body); @body = body; end
      def << (val); @body[val]; end
    end
  end

  def iterator(&block); Iterator.new(block); end

  def _collect
    return enum_for(:_collect) unless block_given?
    iterator {|y| each {|e|
        y << (yield e)
      }}
  end

  # ちなみに,もしも従来の collect メソッドを同じように定義したとしたら
  #   def collect
  #     return enum_for(:collect) unless block_given?
  #     y = []
  #     each {|e|
  #       y << (yield e)
  #     }
  #     y
  #   end

end

enum_for(:_collect) を除き,Ruby 言語の骨格となる機能しか使っていないことに注意されたい。 もし仮に Ruby 言語にスレッドやキューはもちろん,今のかたちの配列や整数さえなかったとしても,このコードは成立する。

つまり,LINQ ライクな Enumerable メソッドとは,決して近年の Ruby の新機能を使ってはじめて実現できるものではなく, むしろ Ruby の草創期からあってもおかしくはなかったメソッドです。 collect ではなく _collect のようなメソッドこそが,Ruby にブロックという言語要素を設けた時点で, そこに内在する必然性から自然に導出されるべきだった,といってよいかもしれません。

他のメソッドについては _enum.rb を参照されたい。

4. 使用例

_enum.rb により,Ruby 2.0.0 開発版の Enumerator::Lazy と同じ処理が Ruby 1.8.7 でも可能となる。 "Ruby 2.0 メモ: Lazy と LINQ とループ融合" から 1 から 30 までの整数のうち十進表現に 3 が含まれるものの最初の三つを求める例を示す。

01:~$ irb -r _enum
>> (1..30).map{|i| i.to_s}.select{|s| /3/ === s}.take(3)
=> ["3", "13", "23"]
>>  

これは旧来のメソッドを使った式である。 演算過程を分かりやすくするため print をさしはさむ。

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

これを _enum.rb の下線付きのメソッドを使うように書き換えると,

>> (1..30)._map{|i| print i; i.to_s}._select{|s| print '-'; /3/ === s}.take(3)
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"]
>>  

このとき,print の出力から分かるように _map_select の処理がパイプライン的に交互に実行される。 また,23 までで必要な結果が得られるから,24 以降のイテレートは行われない。

この例は次のようにも書けます。
>> (1..30)._map(&:to_s)._grep(/3/).take(3)
=> ["3", "13", "23"]
>>  
必要なだけのイテレートしかしていないことは,左端に print 専用の _map をさしはさむことで確認できます。
>> (1..30)._map{|e| print e; e}._map(&:to_s)._grep(/3/).take(3)
1234567891011121314151617181920212223=> ["3", "13", "23"]
>>  

5. _zip と外部イテレータ

LINQ ライクな Enumerable メソッドのうち,zip に対応する _zip は外部イテレータを必要とする点で他と異質である。

_zip は複数の列を並行して1回ずつイテレートし,得られた要素を組みにする。 しかし,Ruby に従来からある内部イテレータでは,複数の列を並行にイテレートできない。 これは,Ruby の祖語の一つ CLU から知られている制約である (日本語の資料としては "Ruby で作る Prolog 処理系 (補講)" - 注釈 3 参照)。

そこで,引数群に対して args.map {|e| e.to_enum} をして外部イテレータとしての Enumerator インスタンスを作成し,レシーバに対するイテレートごとにそれぞれ e.next で1回ずつ並行的にイテレートする。

  def _zip(*args, &block)       # これは外部イテレータを必要とする
    if block_given?
      _zip(*args).each(&block)
      nil
    else
      iterator {|y|
        ee = args.map {|e| e.to_enum}
        each {|e0|
          a = ee.map {|e|
            begin e.next
            rescue StopIteration
              def e.next; nil; end # Ruby 1.8.7 では必要
              nil
            end
          }
          y << a.unshift(e0)
        }}
    end
  end
つまり _zip について言えば,これは旧来の Ruby に対して自然なメソッドとは言えません。 近年の Ruby ではじめて可能になったメソッドです。

レシーバより先に引数のイテレートが先に終わった場合,StopIteration が発生する。 これをキャッチして nil に差し替える。 Ruby 1.8.7 では StopIteration 発生後にさらに e.next を行うとイテレートが最初に巻き戻って繰り返される。 そこで e.next を特異メソッドとして常に nil を返すように再定義する。 外部イテレータは _zip の呼出しごとに使い捨てにするから,この再定義は他に影響を与えない。 Ruby 1.9.3 等ではこの再定義は無駄だが,あっても誤動作はしない。

>> (1 .. 1.0/0.0)._zip((101 .. 1.0/0.0), ('a'..'c')).take(5)
=> [[1, 101, "a"], [2, 102, "b"], [3, 103, "c"], [4, 104, nil], [5, 105, nil]]
>>  

6. mruby への適用

_enum.rb のコードは 2012年 6月 27日現在の mruby [github.com] でも動作する。 ただし,Ruby 1.8.7 以降で導入された Enumerator クラスが mruby にはないから,次の二つの制限がある。

  1. _zip は動作しない。 実行すると,外部イテレータとしての Enumerator 値を作るために to_enum メソッドを呼び出そうとして失敗する (前節参照)。
  2. _grep を除き,ブロック引数を省略することはできない。 ブロック引数を省略すると,戻り値としての Enumerator 値を作るために enum_for メソッドを呼び出そうとして失敗する (第3節参照)。

_grep メソッドは,ブロック引数が省略されたときは === 演算子による検索を行い,ブロック引数が与えられたときは,その結果をブロック引数による _collect に連鎖させる。 mruby では,どちらの場合も動作する。

  def _grep(pattern, &block)
    return _grep(pattern)._collect(&block) if block_given?
    iterator {|y| each {|e|
        y << e if pattern === e
      }}
  end
Enumerator 値を作ろうとしてブロック引数を省略することはできない,という制限は,旧来の Ruby のイテレータと同じです。 二つの制限を除き,mruby で動くという事実は,確かにこれが Ruby 言語の基本的な構成要素だけから成り立っていることを示しています。

7. おわりに

Ruby 2.0.0 開発版の Enumerator::Lazy の直接の源流は I. Mihailov: Ruby 2.0 Enumerable::Lazy | Railsware Blog [railsware.com] にある。 そこで言及されているように,さらにその源は Y. Hara: Feature #4890: Enumerable#lazy [ruby-lang.org] による Ruby 言語自身による実装にあり,またその他にいくつかの実装が試みられている。 そして,それらの元になったアイディアは2008 年 11月 3日の B. Candler: [ruby-core:19679] [Feature #707] Documentation for Enumerator chaining [nagaokaut.ac.jp] の下記の投稿に求めることができる:

Enumerators now support a horizontal filter/chaining pattern:

  generator.filter1 { ... }.filter2 { ... }.filter3 { ... }.consumer

The overall pattern for a filter is:

  Enumerator.new do |y|
    source.each do |input|     # filter INPUT
      ...
      y << output              # filter OUTPUT
    end
  end

This is extremely powerful. However it is not obvious to the newcomer
that this is even possible. (Confusion may arise where people know
Ruby 1.8's Enumerator, which cannot do this)
……以下略……

また同日 B. Candler: Feature #708: Lazy Enumerator#select, Enumerator#map etc. [ruby-lang.org] として lazy_enum.rb が提案された。

ある意味,2008 年の文化の日が Ruby の Enumerable にとって運命の日だったわけです。

これらの資料から理解するところによれば,本稿でいう LINQ ライクなメソッドを実現するその後の試みはすべて 11月 3日の投稿で用法が示されたブロック付きの Enumerator コンストラクタを基礎としてきた。 これは Ruby 1.8.7 にレトロフィットされなかった Ruby 1.9 の新機能である。 Enumerator はもともと外部イテレータを実現するために Ruby 1.9 で追加されたクラスである。 それと心象的に分ち難く結び付いたためか,そのようなメソッドが (本稿でいう _zip を除き) Ruby の草創期からあっても不自然ではなかったものである,という認識はついに生まれなかった。

Enumerable#each_cons のようなメソッドがすでにあることを考えれば, Ruby 2.0.0 開発版の Enumerator::Lazy のように別のクラスとして建てるよりも,本稿の _enum.rb のように今までの Enumerable モジュールを拡張するほうが,おそらく Ruby の伝統的な大クラス主義と矛盾しないだろう。

本稿で示した LINQ ライクな Enumerable メソッドの実装は,現在使われている Ruby 処理系で広くただちに利用できる。 その経験から,実地に即し,分かりやすく,使いやすい妥当な解が見つかることを期待したい。

現在の視点からみると,LINQ のようなアイディアが Ruby から (少なくとも体系だっては) 生まれなかったことが不思議に思われます。 昔の Ruby にも道具立てはほとんどそろっていたにもかかわらず,そして,わずかな量のコードで実現できるにもかかわらず (広く知られる限りでは) 誰も思いつきませんでした。 この事実は,LINQ という考えが一つの新しいパラダイムである,ということを雄弁に語っているのでしょう。 私たちは新しいパラダイムが統べるプログラミングの世界の入り口に今,立っているのかもしれません。

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