enumerable_lz による遅延評価のススメ

• はじめに
• enumerable_lz の基本
  • インストール
  • 使い方
• 遅延評価で何ができるの？
  • 「遅延評価メソッド」とは？
  • できること (1): 無駄な評価を減らして効率化
  • できること (2): 無限リストを扱う
  • できること (3): 可読性と簡潔性の両立
    • ロジックと処理の分離
• まとめ : Enumerable を、もっと Enumerable に！
• 終わりに
• 著者について

書いた人: antimon2 (@antimon2)

はじめに

enumerable_lz とは、拙作の遅延評価ライブラリです。Ruby 標準の Enumerable モジュールに、いくつかの遅延評価メソッドを追加します。

ただ「遅延評価」と言っても、それによって何ができるのか、何がうれしいのか、そもそも『遅延評価』って何なの？ 等、よく分からないという方も多いと思います。

本稿では、enumerable_lz を導入することによって、どんなことができるようになるのか、何の役に立つのか、といったところを解説していきます。

キーワードは、「Enumerable をもっと Enumerable に！」

enumerable_lz の基本

インストール

enumerable_lz は gem として公開しています。原稿執筆時点 (2011/05 現在) の最新版は 0.1.4 です。

インストールは以下のコマンド一発で OK。

$ gem install enumerable_lz

またソースコードは github で公開 (https://github.com/antimon2/enumerable_lz) しています。

なお動作環境は、Ruby1.8.7 と Ruby1.9.x 以降です。JRuby、MacRuby でも動作します。

使い方

require ‘enumerable_lz’ すると、Enumerable に 3 つの「遅延評価メソッド」が追加されます。

• Enumerable#filter
• Enumerable#filter_with_initproc
• Enumerable#transform

これらのうち、filter メソッドと transform メソッドについて簡単に説明します (filter_with_initproc メソッドの説明は省略します)。

filter メソッドは、その名のとおり Enumerable の各要素をフィルタリングして結果を返すメソッドです。引数には、パターンかブロックを受け取ります。

transform メソッドもその名の示すとおり、Enumerable の各要素を変換して結果を返します。引数はブロックのみです。

いずれも戻り値は Enumerable で、そのまま他の Enumerable モジュールのメソッド (map、inject、等) をチェインできます。

例えば以下のような記述ができます。

list1. enumerable_lz のサンプルコード 1¹²

# require RUBY_VERSION >= '1.9'
require 'enumerable_lz'
require 'prime'

p (1..Float::INFINITY).transform{|n|n**2+1}.filter{|m|m.prime?}.take(100)
# => [2, 5, ... , 682277, 739601] for a few msec.

また require ‘enumerable_lz/enumerable_ex’ すると、Enumerable にさらにいくつかの「遅延評価メソッド」を追加します。

• Enumerable#select_lz
• Enumerable#find_all_lz
• Enumerable#reject_lz
• Enumerable#grep_lz
• Enumerable#map_lz
• Enumerable#collect_lz
• Enumerable#drop_lz
• Enumerable#drop_while_lz
• Enumerable#take_lz
• Enumerable#take_while_lz

これらのメソッドは、Enumerable に存在するオリジナルのメソッドにサフィックス ‘_lz’ を追加したもので、元のメソッドの「遅延評価版メソッド」であることを表しています。

例えば先ほどの例はこれらのメソッドを利用して、以下のようにも書くことができます。

list2. enumerable_lz のサンプルコード 2

# require RUBY_VERSION >= '1.9'
require 'enumerable_lz'
require 'enumerable_lz/enumerable_ex'
require 'prime'

p (1..Float::INFINITY).map_lz{|n|n**2+1}.select_lz{|m|m.prime?}.take_lz(100).to_a
# => [2, 5, ... , 682277, 739601] for a few msec.

なおこれらのメソッドは、いずれも Enumerable#filter、Enumerable#filter_with_initproc および Enumerable#transform を用いて記述されています。

遅延評価で何ができるの？

前章で「enumerable_lz は遅延評価メソッドを追加する」という説明をしました。そもそも「遅延評価メソッド」とは何か、何ができるのか、を説明します。

キーワードは、以下の 3 つ：

• 無駄な評価を減らして効率化
• 無限リストを扱う
• 可読性と簡潔性の両立

「遅延評価メソッド」とは？

「遅延評価」というのは、「その値が必要になるまで実際の計算を行わない評価方式」のことです。前もって評価した結果を利用するのではなく、それが必要になったときに初めて評価して結果を得る、ということです。ちなみに「前もって評価しておく方式」のことは「先行評価」と言います。

そして「遅延評価メソッド」とは、「(先行評価した結果を返すのではなく) 遅延評価する『仕組み』を返すメソッド」のことです。

先ほど挙げた、サフィックス ‘_lz’ のついたメソッドを見てみてください。元の (サフィックス ‘_lz’ を取り除いた) メソッドは、すべて配列 (Array) を戻り値とするメソッドです³。

• Enumerable#select
• Enumerable#find_all
• Enumerable#reject
• Enumerable#grep
• Enumerable#map
• Enumerable#collect
• Enumerable#drop
• Enumerable#drop_while
• Enumerable#take
• Enumerable#take_while

つまりこれらのメソッドは、「レシーバ (Enumerable) の各要素を先行評価して、その結果を配列に格納して返す」という共通の仕様に沿っているのです。

enumerable_lz が提供する「遅延評価メソッド」は、配列ではなく「その都度評価した結果を順次送出する Enumerable (＝遅延評価する『仕組み』) を返す」仕様⁴になっています。

できること (1): 無駄な評価を減らして効率化

例えば、以下の例をご覧ください。

list3. 1000 〜 10000 から最初の 2 つの素数を抽出するコード例 1

require 'prime'
result = (1000..10000).select{|n|n.prime?}  # [※1]
p result.take(2)
# => [1000, 1013]

select は、「レシーバ (Enumerable) の各要素を__すべて評価__して true となるものを格納した__配列 (Array)__」を返すメソッドです。つまり [※1] のコードは、1000 〜 10000 の 9001 個の要素をすべて評価 (先行評価) して、1061 個の素数からなる配列を作成しています。result に格納されている値は配列です。

これを enumerable_lz を用いて書き直してみましょう。

list4. 1000 〜 10000 から最初の 2 つの素数を抽出するコード例 2

require 'enumerable_lz'
require 'prime'
result = (1000..10000).filter{|n|n.prime?}  # [※2]
p result.take(2)
# => [1000, 1013]

filter は、「レシーバ (Enumerable) の各要素を__その都度評価__して true となるものを順次渡す Enumerable」を返すメソッドです。つまり [※2] のコードでは、まだ評価は行われていません。「遅延評価する『仕組み』を用意しているだけ」です。result に格納されている値は Enumerable です。

そして次行の result.take(2) で、初めて評価が行われ、filter に通った最初の 2 件だけが取得されます。このとき、filter メソッドが用意した Enumerable の中では、その更に元の Enumerable である (1000..10000) の各要素も初めて評価されますが、2 つ目の素数が見つかった時点で処理が終了するので、実際に評価される全要素数は 1000 〜 1013 のたった 14 個です。

つまりこのような使い方をする上では、遅延評価を利用するととても効率が良くなるのです。試しにベンチマークをとってみました。

list5. 1000 〜 10000 から最初の 2 つの素数を抽出するコードのベンチマーク

require 'enumerable_lz'
require 'prime'
require 'benchmark'

Benchmark.bmbm do |b|
  b.report "select" do
    100.times{(1000..10000).select{|n|n.prime?}.take(2)}
  end
  b.report "filter" do
    100.times{(1000..10000).filter{|n|n.prime?}.take(2)}
  end
end
# v- Result
# Rehearsal ------------------------------------------
# select  12.766000   0.031000  12.797000 ( 12.968750)
# filter   0.016000   0.000000   0.016000 (  0.015625)
# -------------------------------- total: 12.813000sec
# 
#              user     system      total        real
# select  12.750000   0.031000  12.781000 ( 12.937500)
# filter   0.015000   0.000000   0.015000 (  0.015625)

1000 倍に近いオーダーで歴然とした差が出ています。

できること (2): 無限リストを扱う

次に、こんな例を考えてみましょう⁵。

list6. 無限リストを扱うコード例 1

# Do not execute this
(1..1.0/0).map{|n|n.even? ? n/2 : n*3+1}.take_while{|m|m<100}

list7. 無限リストを扱うコード例 2

require 'enumerable_lz'
(1..1.0/0).transform{|n|n.even? ? n/2 : n*3+1}.take_while{|m|m<100}

list6. は実行しないでください。実行すると、半永久的に評価を繰り返した挙句、NoMemoryError で落ちます⁶。

これは、map が「レシーバ (Enumerable) の各要素を__すべて評価__した結果を格納した__配列 (Array)__」を返すメソッドだからです。

評価が終わるまでチェインしている take に処理は引き継がれませんが、(1..1.0/0) が__無限リスト__なので、map メソッドの評価は永遠に終わりません⁷。

これに対して list7. は、やはり結果は一瞬で返ってきます。

これは transform が「レシーバ (Enumerable) の各要素を__その都度評価__してその結果を順次渡す__Enumerable__」を返すメソッドだからです。

この例の transform メソッドは、無限リストを別の無限リストに変換しています。その都度遅延評価するという性質を利用して、ロジックだけを指定して新しい無限リストが作れるわけです。これは標準の Enumerable のメソッドではできないことです。

できること (3): 可読性と簡潔性の両立

こんな Quiz を考えてみましょう。

Quiz
整数 (>0) の 2 乗 +1 のカタチになっている素数を小さい順に 100 個取得するコードを書け。
できるだけ簡潔に。
※ Ruby1.9 の prime ライブラリは使用可。

この仕様だけを見て、どんなコードを思い浮かべますか？

まず、ロジックがちがちのこんなコードは容易に思いつくと思います。

list8. 整数 (>0) の 2 乗 +1 のカタチになっている素数を小さい順に 100 個取得するコード例 1

require 'prime'

n = 1
result = []
loop do
  m = n ** 2 + 1
  if m.prime?
    result << m
    break result if result.size == 100
  end
  n += 1
end

確かに正しい結果は得られますし、実行速度は速いです。でも、Ruby のコードとしてはイケテナイ感が否めません。だって他の言語でも書けるロジック (アルゴリズム) をそのまんま記述しただけですから。

Ruby のライブラリや文法を利用すれば、もっと簡潔にできるはず。例えば、以下のようなコードは 1 つの回答例です。

list9. 整数 (>0) の 2 乗 +1 のカタチになっている素数を小さい順に 100 個取得するコード例 2⁸

require 'prime'

result = (1..1.0/0).inject [] do |r, n|
  break r if r.size == 100
  (m = n ** 2 + 1).prime? ? r << m : r
end

でも、何の前知識も無しにいきなりこのコードを見せられて、これが何をするコードなのか、分かりますか？ 多分、分からないと思います。

これ以上簡潔にまとめられて、かつ可読性の高いコードなんて、書けるのでしょうか？

実は、今までの書き方ではこの辺りが限界なのです。

• ある程度の可読性を確保しようとすると、ループの中に色々な処理や判定が入るので、コードが長くなり、テストもしにくくなる。
• ある程度簡潔に書こうとすると、メソッドを本来とは異なる使い方をしたり、処理や判定が複雑に絡み合ったりして、可読性が落ちる。

このように、可読性を捨てるか簡潔性を捨てるか、の板挟みになってしまいます。

そこで、Quiz に、以下のように 1 つ条件を加えてみましょう。

Quiz (改)
整数 (>0) の 2 乗 +1 のカタチになっている素数を小さい順に 100 個取得するコードを書け。
できるだけ簡潔に。
※ Ruby1.9 の prime ライブラリは使用可。
※ enumerable_lz で提供される『遅延評価メソッド』も使用可。

すると、以下のような書き方が出来てしまいます！

list10. 整数 (>0) の 2 乗 +1 のカタチになっている素数を小さい順に 100 個取得するコード例 3⁹

require 'prime'
require 'enumerable_lz'

result = (1..1.0/0).transform{|n|n**2+1}.filter{|m|m.prime?}.take(100)

Range オブジェクト (1..1.0/0) を Enumerable#transform メソッドを使って各要素を n**2+1 に変換。そのうち素数 (m.prime?) のものだけを Enumerable#filter で抽出。最後に take(100) で100件取得。すこぶる直感的であり、たった 1 行で記述されていて、とってもスマートです。

しかも、ちゃんと期待通りに動作して、正しい結果を返してくれます。

このように「遅延評価」を (無限リストと組み合わせて) 使用すると、それぞれの処理や判定を独立した__部品 (メソッド)__ に分解してそれらを__組み合わせること (メソッド・チェイン)__ で、複雑なループ処理を実現できます。このとき、まとめると以下のことが成立しています。

• 全体として行っている処理が直感的に理解できる (可読性)
• それぞれのコード、そしてコード全体が短くなる (簡潔性)

つまり、可読性と簡潔性が両立できているのです！

でも、これらが本当に「遅延評価」のおかげで成立しているのか？ という疑問を抱く方もいらっしゃるかもしれません。そこで、このコードの transform を map に、filter を select に置き換えた以下のコードを考えてみましょう。

list11. 整数 (>0) の 2 乗 +1 のカタチになっている素数を小さい順に 100 個取得するコード例 (NG例)

require 'prime'

# Do Not Execute This!
result = (1..1.0/0).map{|n|n**2+1}.select{|m|m.prime?}.take(100)

見た目は、使用しているメソッド名が変わっている以外はまったく同じです。これでも良いのではないか？ と一瞬思ってしまうかもしれません。

でも、今までの説明を読んでいただけていたら分かると思いますが、このコードは完全に NG です。map メソッドが無限リストを処理しようとしているので、実行すると、半永久的に処理を続けて NoMemoryError で落ちます¹⁰。

list10. は、遅延評価メソッドを利用して、結果ではなく「遅延評価する仕組み」を連鎖させている形になっているので、問題がないのです。

ロジックと処理の分離

list11. と list10. の違いを、少し突っ込んで説明します。

list11. は「処理の連鎖」をしようとしています。詳しく言うと、「一連の処理を実行して、その結果をまた次の処理の入力として連携する」というプログラムになっているのです。見た目は「ロジック (処理の定義)」が書かれていますが、実際にはその処理が実行されてしまっている、ということです。

それに対して list10. は、「ロジックの連鎖」になっています。つまり、見た目通り (transform と filter に関しては) 「ロジック」つまり「処理の定義」が用意されているだけで、実際の処理は実行されません。最後の take メソッドで初めて全てのロジックを解釈し、全ての処理が実行される仕組みになっています。

同じことが list6. と list7. についても言えます。もちろん、list3. と list4. も同様です。特に list7. と list10.、つまり「無限リストを扱うこと」と「可読性と簡潔性の両立」は、このように「ロジックと処理が分離」されていなければ得られない、大きなメリットとなっています。

まとめ : Enumerable を、もっと Enumerable に！

Ruby1.8.7 で大幅に拡充された Enumerable モジュールは、とても有用なメソッドを用意してくれています。でも、本稿で示した通り、そのいくつかはその設計に問題があると思っています。

そもそも Enumerable は、Array を抽象化したモノ。そのメソッドは、要素を列挙しイテレーションを行うための each メソッドに (のみ) 依存したモノになっています。そして多くの Enumerable を include しているクラスのオブジェクトは、each メソッドで次の要素をその都度算出しています。つまり、内部的には「遅延評価」しているのです¹¹。

そのメソッドの戻り値を Array にしてしまったら、せっかくの遅延評価が有効活用できない。それによって困ることもあります。

むしろ (Array ではなく) Enumerable を返すようにすると、これまで見てきたように、「遅延評価」由縁の色々なメリットを享受できるのです¹²。

「Enumerable をもっと Enumerable らしく」。enumerable_lz は、その 1 つの提案です。

終わりに

本稿の内容は、名古屋 Ruby 会議 02 における発表「Enumerable はもっと Enumerable になれると思うんだ」を元にしております。その場で受けた指摘事項等を踏まえて、内容を見直し再構成したものです。 発表資料は http://www.antimon2.atnifty.com/works/slide_20110226 に_こっそり_上げてあります (字が小さめなので拡大してご覧ください……) が、書いてある内容はこの記事の方が詳しく分かりやすく親切になっています。

「あの発表は正直失敗だった」と反省しきりだった私に、「るびまの記事」というリベンジの場を与えてくださった、編集部の桑田さん、応援してくれた Ruby 東海の皆さん、そしてこの記事を読んでくださった皆さんに、心から感謝いたします。

著者について

antimon2 (@antimon2)

名古屋でプログラマ / Web エンジニアやってます。でも Ruby は仕事とは関係なく趣味でいろいろ遊んでいます。ちなみに第 1 言語は JavaScript。株式会社コスモルート所属。