Groovy 応用: LINQ ライクなメソッドによるフィボナッチ数の計算

2012-09-12 改訂, 2013-01-10 使用例追加ほか (鈴)
2012-07-13 初出時のページ

1. はじめに

"Ruby 1.8.7 からの LINQ ライクな Enumerable メソッド" では,C# の LINQ と実質的に同じものである Ruby 2.0.0 開発版の Enumerator::Lazy と同等の機能を,Enumerable モジュールのメソッドとして Ruby 1.8.7 や mruby で実現できることを示し,それらを LINQ ライクなメソッドと表現した。 "解説: Ruby/mruby LINQ ライク・メソッド" では,それが Ruby のブロック付きメソッドの機構の応用であることをかみ砕いて解説した。

ほとんど明らかなように Ruby にインスパイアされて作られた Groovy でも同様なメソッドを同様な方法で実現できる。 ここではそれを実際に拡張モジュール linqlike-module.jar として与え,簡単な応用としてフィボナッチ数を計算する。

フィボナッチ数の計算は Groovy による遅延評価 (lazy evaluation) の実装例として "Groovy 応用: 遅延評価によるフィボナッチ数の計算" ですでに取り上げた。 それは遅延評価としてはたしかに正統だったが,おそらくその関数言語的なアプローチは多くの人にとって親しみにくいものだったと思う。 それに対し,LINQ ライクなメソッドは無限の列を扱う能力を同程度に実現しながら,§8 で示すように,より手続き的な表現を可能にする。

一方,LINQ ライクなメソッドはその振舞が遅延評価と似ており,しばしば遅延評価の実例として説明される。 しかし,その実態はしばしば lazy という形容にはほど遠い。 このことは "Groovy 応用: 遅延評価によるフィボナッチ数の計算" と同じアプローチをあえて採ったとき明らかになる。 最後にそれを §9 で示す。

伝統的な遅延評価と,なんちゃって遅延評価の対決……というわけではありませんが,読者が比較しやすいように同じ題材を選びました。 call-by-name 的に動作する LINQ ライクなアプローチを「遅延評価」と呼ぶ流儀もありますが,ここでは call-by-need を行う伝統的な意味での遅延評価との混同を避けるため,LINQ ライクなメソッドの形容としては「遅延」の語を意識的に避けます。

2. Groovy のための LINQ ライクなメソッド

拡張モジュール linqlike-module.jar は Groovy に LINQ ライクなメソッドを追加する。 これは次のように使うことができる。

01:~/tmp$ groovysh -cp linqlike-module.jar
Groovy Shell (2.0.6, JVM: 1.6.0_37)
Type 'help' or '\h' for help.
-------------------------------------------------------------------------------
groovy:000> (1..30)._collect{it.toString()}._findAll{it.contains("3")}.take(3)
===> [3, 13, 23]
groovy:000> (1..30)._collect{print it; it.toString()}._findAll{print "-"; it.con
tains("3")}.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]
groovy:000>  

最初の式 (1..300)._collect{it.toString()}._findAll{it.contains("3")}.take(3) は,1 から 300 までの数について,それぞれ it.toString() で文字列化し, it.contains("3") で 3 を含んだものだけ残し, take(3) でその最初の三つをリストにする。

これに対して結果の値が [3, 13, 23] と表示される。

次の式 (1..30)._collect{print it; it.toString()}._findAll{print "-"; it.contains("3")}.take(3) は最初の式と基本的に同じだが,処理の途中経過を print で表示する。

これに対して 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 1.8.7 からの LINQ ライクな Enumerable メソッド - 4. 使用例" にある Ruby (irb -r _enum) の

>> (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"]
>>   

と比較しよう。

Groovy は結果の値を toString メソッドを適用した文字列表現で表示します。 文字列 "3" も表示上は 3 となります。 これが Ruby で ["3", "13", "23"] と表示されたのが Groovy で [3, 13, 23] と表示される理由です。 このままでは数と見分けられませんから,本当に各要素が文字列なのか getClass メソッドを適用して確かめてみましょう。
groovy:000> (1..30)._collect{it.toString()}._findAll{it.contains("3")}.
take(3).collect{it.getClass()}
===> [class java.lang.String, class java.lang.String, class java.lang.S
tring]
groovy:000>  
たしかに java.lang.String のインスタンスつまり文字列です。

以下の数節では LINQ ライク・メソッドの実装について説明する。

3. 実装解説: 拡張モジュールとカテゴリ

拡張モジュール linqlike-module.jar は,LinqLikeCategory.groovygroovyc コマンドでコンパイルし,下記の META-INF/services/org.codehaus.groovy.runtime.ExtensionModule モジュール記述子ファイルとともに jar ファイルにまとめたものである。 具体的な手順については Groovy 応用: 遅延評価によるフィボナッチ数の計算 - 付録 2. 拡張モジュールの作り方 を参考にされたい。

moduleName = linqlike-module
moduleVersion = 1.1
extensionClasses = jp.oki_osk.esc.LinqLikeCategory
staticExtensionClasses =

LinqLikeCategory.groovy の最外の構造を示す。

package jp.oki_osk.esc;

/**  Groovy の Object クラスに LINQ ライクなメソッドを追加する。*/
@Category(Object)
class LinqLikeCategory {
  ……
}

LinqLikeCategory クラスに付けたアノテーション @Category(Object) は,そのクラスの非静的メソッドをアノテーションの引数のクラス (ここでは Object) への追加メソッドとして使えるようにする。 すなわち,LinqLikeCategory クラスのコンパイル時に次のような AST 変換を行う。

  1. 非静的メソッドの定義を静的メソッドの定義に書き換える。
  2. メソッドの仮引数の並びの先頭に Object クラスの仮引数を第1引数として割り込ませる。 今までの第1引数は第2引数に,第2引数は第3引数になる。
groovyc でコンパイルして得られる *.class ファイルを javap コマンド等で調べて,実際にこのように AST 変換が行われていることを確かめてください。 AST 変換とは抽象構文木 (Abstract Syntax Tree) に対する変換ですから,その内容は Lisp のマクロ適用と似たようなものです。 逆にいえば,Lisp はたまたま抽象構文木がそのままソースの表現形式となっている言語ですから,手軽に AST 変換を組めます。 それを Lisp ではマクロと呼んでいるわけです。

このコンパイル結果と前述のモジュール記述子ファイルを拡張モジュールにまとめることにより Object へメソッドが追加される。 さらに言えば,たとえ拡張モジュールにしなくても次の方法でメソッドを Object クラスへ追加できる。

  1. use (jp.oki_osk.esc.LinqLikeCategory) {} で囲む。この中で追加メソッドを使うことができる。あるいは,
  2. Object.mixin(jp.oki_osk.esc.LinqLikeCategory) を行う。それ以降どこでも追加メソッドを使うことができる。

この場合は必ずしも LinqLikeCategory クラスをコンパイルしておく必要はない。 下記の実行例ではソースを格納した src ディレクトリを -cp オプションで指定しているだけである。

01:~/tmp$ ls src/jp/oki_osk/esc
LinqLikeCategory.groovy
01:~/tmp$ groovysh -cp src
Groovy Shell (2.0.6, JVM: 1.6.0_37)
Type 'help' or '\h' for help.
-------------------------------------------------------------------------------
groovy:000> import jp.oki_osk.esc.LinqLikeCategory
===> [import jp.oki_osk.esc.LinqLikeCategory]
groovy:000> use (LinqLikeCategory) { x = (1..100)._findAll{ it % 3 == 0 } }
===> jp.oki_osk.esc.LinqLikeCategory$Iter@6765
groovy:000> use (LinqLikeCategory) { x.take(5) }
===> [3, 6, 9, 12, 15]
groovy:000>  
歴史的にはこちらの方法が先でした。拡張モジュールは Groovy 2.0 で追加された新機能です。

4. 実装解説: Iter クラスと iter 関数

LinqLikeCategory クラスは下記のように入れ子クラス Iter と便宜関数 iter を定義する。 これらは Ruby 版実装 _enum.rb (Web 閲覧用ソース) の Iterator クラスと iterator 関数にそれぞれ対応する。 名前を変えたのは,Java の java.util.Iterator クラスおよび java.lang.Iterable<T>#iterator() メソッドとの名前の衝突を避けるためである。

§7 で説明するように Groovy は Iteralbe インタフェースの iterator メソッドを Object に追加しています。衝突回避は必須です。

定義の内容は Ruby 版実装と同様である。 メソッドの具体的な動作については "解説: Ruby/mruby LINQ ライク・メソッド" を参照されたい。

  /** 1引数クロージャを内部イテレータに仕立てる。*/
  static class Iter {
    private Closure block;

    Iter(Closure block) { this.block = block }

    Object each(Closure body) { // cf. Groovy Object#each
      block(new Yielder(body));
      return this;
    }

    /** 1引数クロージャの実引数となる。*/
    static class Yielder {
      private Closure body;

      Yielder(Closure body) { this.body = body }

      void leftShift(val) {     // "<<" operator
        body(val);
      }
    }

    ……略……
  }

  /** 1引数クロージャから内部イテレータを作って返す。
      クロージャの仮引数を y としたとき,y << e で式 e が yield される。
   */
  Iter iter(block) { return new Iter(block) }

Iterクラスを直接使うことは普通はしないが可能である。 下記の例では 10 と 20 からなる仮想的な列 s を作り,each メソッドで列挙している。

groovy:000> s = new jp.oki_osk.esc.LinqLikeCategory.Iter({y -> y<<10; y<<20})
===> jp.oki_osk.esc.LinqLikeCategory$Iter@160e069
groovy:000> s.each { println it }
10
20
===> jp.oki_osk.esc.LinqLikeCategory$Iter@160e069
groovy:000>  

便宜関数 iter を使えば s の代入はこう書ける。

groovy:000> s = iter { y -> y<<10; y<<20 }

_collect メソッドと _findAll メソッドの定義を示す。 それぞれ Ruby 版実装の _collect メソッドと _find_all メソッドに対応する。

  /** LINQ ライクな Groovy Object#collect */
  Iter _collect(Closure transform) {
    return iter { y ->
      each {
        y << transform(it);
      }
    }
  }

  /** LINQ ライクな Groovy Object#findAll */
  Iter _findAll(Closure closure) {
    return iter { y ->
      each {
        if (closure(it))
          y << it;
      }
    }
  }

前述の仮想的な列 s に適用した例を示す。

groovy:000> s._collect{ it * 100 }.each{ println it }
1000
2000
===> jp.oki_osk.esc.LinqLikeCategory$Iter@1353154
groovy:000> s._findAll{ it > 15 }.each{ println it }
20
===> jp.oki_osk.esc.LinqLikeCategory$Iter@bc9673
groovy:000>  

5. 実装解説: 従来のクラスとの関係

前節に掲げたコードの注釈の中で Java の java.lang.Object クラスにはない Object#each, Object#collect, Object#findAll に言及していることに気付いたと思う。 これらは Groovy が標準で用意している追加メソッドである。 詳細については Groovy JDK [codehaus.org] を参照されたい。

Java の基本的な欠陥の一つとして,配列や文字列を含めた順序付き集合体に対する統一されたインタフェースの欠如が挙げられる。 共通のメソッドをもたない集合体クラスが乱立する混乱した Java のクラス構造のなかで Ruby のような一様性のあるメソッド体系を実現するため,Groovy は,一見すると非常識だが,おおもとの Object クラスに each, collect, findAll などを追加している。 LinqLikeCategory クラスで Object_collect などのメソッドを追加することは,その自然な拡張である。

each メソッドの動作は,Object では単にレシーバ自身をクロージャ引数に渡して1回呼び出すだけだが, 配列や文字列などでは期待されるとおりレシーバの各要素を順にクロージャ引数に渡して繰り返し呼び出す。

groovy:000> x = new Object()
===> java.lang.Object@154c054
groovy:000> x.each { println it }
java.lang.Object@154c054
===> java.lang.Object@154c054
groovy:000> "Groovy!".each { println it }
G
r
o
o
v
y
!
===> Groovy!
groovy:000>  

したがって each メソッドに依存する私たちの LINQ ライクなメソッドは配列や文字列などにも適切に動作する。

groovy:000> "Groovy!"._collect{ "." + it }.take(6)
===> [.G, .r, .o, .o, .v, .y]
groovy:000>  

また Groovy はいくつかのメソッドを java.lang.Iterable に実装付きで追加している。

ちなみに Java 本来の Iterable はインタフェースとして1個のメソッド iterator() のシグネチャを規定しているだけです。

便宜のため,それらのうちリスト化メソッド toList などを下記のように LinqLikeCategoryObject に追加した。

toList メソッドは Ruby の to_a メソッドに相当します。
  // 以下,Groovy の Iterable にあるメソッドを便宜のため Object に定義する。

  /** each メソッドで得られる要素をリストにして返す。*/
  List toList() {
    List y = [];
    each { y << it }
    return y;
  }

  /** Groovy Iterable#drop と同様 */
  List drop(int n) { return _drop(n).toList() }

  /** Groovy Iterable#take と同様 */
  List take(int n) { return _take(n).toList() }

  /** Groovy Iterable#dropWhile と同様 */
  List dropWhile(Closure c) { return _dropWhile(c).toList() }

  /** Groovy Iterable#takeWhile と同様 */
  List takeWhile(Closure c) { return _takeWhile(c).toList() }

ここで非 LINQ ライク・メソッド drop(n) が,LINQ ライク・メソッド _drop(n) とリスト化メソッド toList() の連鎖として定義できることに注意しよう。 この逆はできない。 他のメソッドについても一般に同様である。

このように LINQ ライク・メソッドの方がより基礎的であることが,Unix の exit ライブラリ関数と _exit システム・コール等の関係にちなんだメソッド名の下線の由来です。 "Ruby 1.8.7 からの LINQ ライクな Enumerable メソッド - 3." もお読みください。

_drop(n) メソッドの定義と使用例を示す。

  /** LINQ ライクな Groovy Iterable#drop */
  Iter _drop(int n) {
    return iter { y ->
      int i = 0;
      each {
        if (i < n) {
          i++;
        } else {
          y << it;
        }
      }
    }
  }
groovy:000> s = "Groovy!"._drop(1)
===> jp.oki_osk.esc.LinqLikeCategory$Iter@140d415
groovy:000> s.toList().join()
===> roovy!
groovy:000>  

6. 実装解説: _take, _takeWhile ループからの脱出

"解説: Ruby/mruby LINQ ライク・メソッド - 4. クロージャと自由変数" で説明したように,Rubyeach メソッドのブロック,つまりループ本体から break するとき,実際には何重もの呼出し階層が一度に畳まれる。

  # Ruby では break 文でブロックから脱出できる
  def _take_while
    return enum_for(:_take_while) unless block_given?
    iterator {|y| each {|e|
        break unless yield e
        y << e
      }}
  end

しかし,Java と同じく Groovy の break 文は同じ階層にある while 文などからの脱出にしか使えない。 Ruby と異なり,幾重もの呼出し階層を越えて脱出するようには作られていない。 仮に上記の Ruby コードをそのまま Groovy に直訳しても,break 文がループでも switch でもない場所に出現したとしてコンパイルに失敗する。

念のために言えば,Groovy では,たとえ while 文の中でも,そこに置かれたクロージャからは break できません。コンパイルに失敗します。 これは Java で while 文の内部で定義した無名クラスのメソッドから break できないことと同じです。

そこでループから脱出するために例外オブジェクト (正確には java.lang.Error 派生クラスのインスタンス) を使うことにした。

  /** 内部イテレータから脱出するためのエラー */
  static class BreakError extends Error {}

LINQ ライク・メソッドが連鎖している場合,例外を throw して呼出し階層を一気に畳む途中で,階層の中間にある try 文が誤ってその例外を catch してしまうかもしれない。 そこで try 文に入る前にあらかじめ例外オブジェクトを作成しておき,もしも throw するときはこの作り置きの例外オブジェクトを throw する。 例外を catch したときは,その例外がここで作成した例外オブジェクトかどうかをテストする。 もし別の例外だったら再 throw する。

_takeWhile(condition) メソッドの定義と使用例を示す。

  /** LINQ ライクな Groovy Iterable#takeWhile */
  Iter _takeWhile(Closure condition) {
    return iter { y ->
      BreakError ex = new BreakError();
      try {
        each {
          if (!condition(it))
            throw ex;
          y << it;
        }
      } catch (BreakError ex1) {
        if (ex1 != ex)
          throw ex1;
      }
    }
  }
groovy:000> s = "Groovy!"._takeWhile{it != "v"}
===> jp.oki_osk.esc.LinqLikeCategory$Iter@ca5bff
groovy:000> s.toList().join()
===> Groo
groovy:000>  

コードの掲示は省略するが _take(n) メソッドも同じように例外オブジェクトを使ってループを脱出する。

周知のように Error からクラスを派生して利用することは一般的ではない。 ここでそうしているのには理由がある。 当初,この用途に使う例外の基底クラスとして,チェックされない例外である java.lang.RuntimeException と,用途に特定の色が着いていない java.lang.Throwable を検討した。 しかし,RuntimeException は途中の階層にある妥当な (しかし内部実装を知らない) Java または Groovy のコードによって偶然に catch されるおそれがある。 一方,Throwable はチェックされる例外であり,途中の階層を Java で記述するときに差し障りとなるおそれがある。 この二つの理由から,ほとんど乱用に近いが,本来は重大な問題を示すために使われる Error クラスを選択した。

自分自身,この選択に完全に満足しているわけではありません……。

7. 実装解説: Iter クラスの外部イテレータ

Java は Ruby でいう外部イテレータを定義するインタフェースとして java.util.Iteratorjava.lang.Iterable を用意している。 前者は外部イテレータそのものを表現する。 後者はインタフェースが規定する唯一のメソッドである iterator によってその外部イテレータを構築する抽象的な "列" (sequence) を表現する。

Java の言語設計の大失敗の一つは,歴史的経緯があるにせよ,概念的に "列" を表現する標準の型すべてがこの Iterable インタフェースを実装するとは規定しなかったことである。 その結果,例えば拡張 for 文の仕様記述では Iterable 一本にまとめることができず,配列に対して個別に対応せざるを得なくなっている。

そして Java では文字列に対して拡張 for 文は使えません。いかにもその場しのぎの中途半端な対応と言わざるを得ません。 ちなみに Java としばしば対比される C# にはこの問題はありません。 C# の String も配列もすべて Java の Iterable に相当する IEnumerable インタフェースを実装しており,一様にファーストクラスの "列" として扱えます。

この Java の基本的な欠陥に対し,前々節 §5 で説明したように Groovy は大胆にも java.lang.Object クラスに each, collect, findAll 等のメソッドを追加して一様性の欠如を補っている。 実のところ Groovy は Object クラスに iterator メソッドも追加しており,他の each 等のメソッドはすべてこれから組み立てている。

Groovy による Object への追加メソッドとしての iterator のデフォルト実装は,そのレシーバ自身を唯一の要素として列挙するイテレータを構築して返す。 配列や文字列など個々のクラスはこの iterator メソッドを要素を列挙できるように適切に再定義する。 それによって each, collect, findAll 等のメソッドは自動的にそれぞれのクラスに対して適切に動作するわけである。

お気づきのようにこれは Groovy 入門 §5.5 の復習です。 Ruby は each メソッドからほとんどのコレクション用メソッドを組み立てますが,Groovy は each メソッドも含めたそれらを iterator メソッドから組み立てます。 Ruby を見習いながらも Groovy はできる限り Java 族としての定石を踏もうとしているわけです。

一方,ここでは Groovy 版 LINQ ライク・メソッドを (_zip メソッドを例外として) 内部イテレータを実現する each メソッドに依存して組み立てた。 これは Ruby の collectfind_all などのメソッドや Ruby 版 LINQ ライク・メソッドと共通する構成方法である。 したがって Ruby 版実装と同じく Iter クラスではコンストラクタと each メソッドだけ定義すれば, さしあたり LINQ ライク・メソッドを連鎖させることができる。

実際,ここまで挙げた例に限って言えば破綻しません。

しかし,それだけでは Groovy の collectfindAll などのメソッドを私たちの LINQ ライク・メソッドの後ろに連鎖させたとき,連鎖もとになる Iter インスタンスの iterator メソッドが Object クラスのデフォルト実装のままになるから適切には動作しない。 同様に,暗黙裏に iterator メソッドを呼び出す拡張 for 文も適切には動作しない。

つまり,LINQ ライク・メソッドの結果を Groovy の世界でファーストクラスの "列" として扱えるようにするためには Iter クラスで iterator メソッドを適切に再定義する必要がある。

下記に Iter クラスでの iterator メソッドの定義を示す。 このメソッドではスレッドと内部イテレータから外部イテレータを組み立てる。 決定性のある (つまり deterministic な) 動作にするため,二つの同期キューを使ってわざと逐次的に動作するようにした。 START_TOKEN には null 以外の任意の値を与えることができ,一意性さえ要求されないことに注意しよう。 平凡な値を使わなかったのはデバッグのしやすさを考えてのことである。

  /** 1引数クロージャを内部イテレータに仕立てる。*/
  static class Iter {
    ……
    Object each(Closure body) { …… }
    ……

    /** for 文などのために each メソッドから外部イテレータを生成する。
        並行動作ではなく hasNext(), next() ごとの逐次動作をする。
    */
    Iterator iterator() {
      def requestQ = new java.util.concurrent.SynchronousQueue();
      def responseQ = new java.util.concurrent.SynchronousQueue();
      def START_TOKEN = 789;    // 識別しやすい値 (e.g. 本宮山の標高)
      def END_VALUE = new Object();  // ユニークな値
      def VOID_VALUE = new Object(); // ユニークな値
      Closure cl = { ->
        try {
          Object a = requestQ.take(); // ループ開始の合図を待つ
          assert a.is(START_TOKEN);
          this.each {
            responseQ.put(it);   // 今回のデータを送る
            a = requestQ.take(); // ループ再開の合図を待つ
            assert a.is(START_TOKEN)
          }
          responseQ.put(END_VALUE); // ループ終了の合図を送る
        } catch (InterruptedException ex) {
          // interrupt されたらただちに終了する
        }
      }

      return new Iterator() {
        private Thread th = Thread.startDaemon(cl);
        private Object current = VOID_VALUE;

        /** 回収時,もしまだスレッドが生きていたら interrupt する。*/
        protected void finalize() {
          if (th.isAlive())
            th.interrupt();
        }

        private void takeCurrent() {
          if (current.is(VOID_VALUE)) {
            requestQ.put(START_TOKEN);  // ループ(再)開始の合図を送る
            current = responseQ.take(); // 今回のデータを待つ
          }
        }

        boolean hasNext() {
          takeCurrent();
          return !current.is(END_VALUE);
        }

        Object next() {
          takeCurrent();
          if (current.is(END_VALUE))
            throw new NoSuchElementException();
          Object result = current;
          current = VOID_VALUE;
          return result;
        }

        void remove() {
          throw new UnsupportedOperationException();
        }
      }
    }
  }
この実装はスレッドを使っていますから効率は決して良くありません。 ただ,幸いなことに LINQ ライクなメソッドの普通の使い方では iterator メソッドが呼ばれることは,メソッド連鎖の最終段に対する拡張 for 文を除き,あまりないはずです。
groovy:000> s = iter { y -> y<<7; y<<8; y<<9; y<<2 }
===> jp.oki_osk.esc.LinqLikeCategory$Iter@1b29f80
groovy:000> for (e in s) println e
7
8
9
2
===> null
groovy:000> for (e in s._findAll{it > 5}) println e
7
8
9
===> null
groovy:000> t = "本宮山山頂"
===> 本宮山山頂
groovy:000> for (e in t._takeWhile{ it != "山" }) print e
本宮===> null
groovy:000>  

8. フィボナッチ数の計算 1: 半手続き的なアプローチ

Ruby では,フィボナッチ数の無限の列を "Ruby 1.8.7 からの LINQ ライクな Enumerable メソッド"_enum.rb (Web 閲覧用ソース) を使って次のように書くことができる。

#!/usr/bin/env ruby

require '_enum'

fib = Enumerable::iterator {|y|
  a = b = 1
  loop {
    y << a
    a, b = b, a + b
  }
}

p fib.take(50)
Ruby 1.9.* ならば Enumerable::iterator を Enumerator::new に置き換えて標準クラス・ライブラリだけで書くこともできます。 LINQ ライク・メソッドの高速化と Ruby 1.9 - §3 もお読みください。

この Ruby スクリプトは数列 fib の先頭の 50 個を take(50) で取り出して p で表示する。 ruby 1.8.7 での実行例を示す。

01:~/tmp$ ./fib.rb
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181
, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 83204
0, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63
245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 18363
11903, 2971215073, 4807526976, 7778742049, 12586269025]
01:~/tmp$  

Groovy も拡張モジュール linqlike-module.jar を使ってほぼ同じように書くことができる。 1Gjava.math.BigInteger の 1 を意味する。

def fib = iter { y ->
  def a = 1G;
  def b = 1G;
  for (;;) {
    y << a;
    (a, b) = [b, a + b];
  }
}

println fib.take(50)

groovy 2.0.6 での実行例を示す。

01:~/tmp$ groovy -cp linqlike-module.jar fib0.groovy
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181
, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 83204
0, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63
245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 18363
11903, 2971215073, 4807526976, 7778742049, 12586269025]
01:~/tmp$  

どちらも無限のフィボナッチ数列をローカル変数への代入を行う手続きで表現していることに注意しよう。

ちなみに,言わば LINQ の本家である C# では次のように書くことができる。

using System;
using System.Collections.Generic;
using System.Linq;

class F
{
    static IEnumerable<long> Fib() {
        long a = 1;
        long b = 1;
        for (;;) {
            yield return a;
            long t = b;
            b = a + b;
            a = t;
        }
    }

    static void Main(String[] args)
    {
        var x = Fib().Take(50).ToArray();
        Console.WriteLine("[" + String.Join(", ", x) + "]");
    }
}

.NET 互換環境 Mono [mono-project.com] の Mono.framework 2.10.9_11 for OS X による実行例を示す。

01:~/tmp$ dmcs fib.cs
01:~/tmp$ mono fib.exe
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181
, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 83204
0, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63
245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 18363
11903, 2971215073, 4807526976, 7778742049, 12586269025]
01:~/tmp$  

最後に,計算量を確かめるために加算演算ごとに * を印字させて再び Groovy で実行してみよう。

def fib = iter { y ->
  def a = 1G;
  def b = 1G;
  for (;;) {
    y << a;
    print "*";    // 計算量を確かめるために加算演算ごとに * を印字する
    (a, b) = [b, a + b];
  }
}

println fib.take(50)
01:~/tmp$ groovy -cp linqlike-module.jar fib1.groovy
*************************************************[1, 1, 2, 3, 5, 8, 13, 21, 34, 
55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46
368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5
702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 2
67914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 
7778742049, 12586269025]
01:~/tmp$  

take(50) により 50 回目のループの y << a の中で throw 文を実行してループを脱出 (§6) するから,49 個の * が印字される。 これを "Groovy 応用: 遅延評価によるフィボナッチ数の計算" §4 の結果と比較しよう。 計算量の点では遅延評価にもとづく遅延リストによるアプローチと実質的に同じである。

9. フィボナッチ数の計算 2: Don't say "They are lazy"

ここで比較のため,"Groovy 応用: 遅延評価によるフィボナッチ数の計算" §4 の遅延リストによるアプローチ

  def fib;
  fib = [1G,
         [1G, delay {
             zipWith({ x, y -> print "*"; x + y }, fib, fib[1])
           }]]

をあえて LINQ ライクなメソッドで採ってみよう。

まず始めに

groovy:000> s = [1, 2, 3]

groovy:000> s = iter { y -> y << 1; y << 2; y << 3 }

がどちらも同じように 1, 2, 3 の列として扱えることを思い出そう。 それと同じように考えれば,無限のフィボナッチ数列 fib は,y << 1G を2回繰り返した後, その数列と,その数列の初項を取り去った数列 fib.drop(1)_zip でとじ合わせ, each でそれぞれの要素 a, b に対して y << a + b をすれば表せることが分かる。

def fib;

fib = iter { y ->
  y << 1G;
  y << 1G;
  fib._zip(fib._drop(1)).each { a, b ->
    print "*";    // 計算量を確かめるために加算演算ごとに * を印字する
    y << a + b;
  }
}

println fib.take(15)

すぐに判明するように,この方法で第 50 項まで求めるのは無謀である。ここでは第 15 項までにとどめる。

01:~/tmp$ groovy -cp linqlike-module.jar fib2.groovy
********************************************************************************
********************************************************************************
********************************************************************************
********************************************************************************
********************************************************************************
********************************************************************************
********************************************************************************
********************************************************************************
********************************************************************************
********************************************************************************
********************************************************************************
********************************************************************************
********************************************************************************
********************************************************************************
********************************************************************************
********************************************************************************
********************************************************************************
********************************************************************************
********************************************************************************
*************************************************************[1, 1, 2, 3, 5, 8, 
13, 21, 34, 55, 89, 144, 233, 377, 610]
01:~/tmp$  

1581 個の * が印字される。 lazy どころか実際には crazy なほど再帰的に同じ計算を繰り返すからである。

i = 1, 2, 3, ..., 15 に対して fib.take(i) が印字する * の個数は 0, 0, 1, 3, 7, 14, 26, 46, 79, 133, 221, 364, 596, 972, 1581 になります。 これは初項が 0, 隣り合う項の差がフィボナッチ数列に等しい数列を作ったとき, 初項が 0,隣り合う項の差がその数列に等しい数列に相当します。
    1   1   2   3   5    8    13   21   34   55    89   144   233
  0   1   2   4   7   12   20   33   54   88   143   232   376   609
0   0   1   3   7  14   26    46   79  133  221   364   596   972  1581
この数列については A001924 - OEIS [oeis.org] を参照してください。

10. おわりに

ここでは,イテレータを通して要素を与える抽象的な "列" をレシーバとし,イテレータを呼び出さないまま新しい抽象的な "列" を返す LINQ ライクなメソッドの Groovy での実装例を示した。

それらのメソッドは決して関数型言語に見られる伝統的な意味での遅延評価 (lazy evaluation) を実現するものではなく,遅延評価とみなして使ったときは極めて悲惨な結果に終わる場合がある。 しかし,副作用をいたるところで使う現在主流の手続き的なプログラミングでは, いつ実際の評価が行われるか必ずしも判然としない伝統的な遅延評価よりも, いつ評価が行われるかを明確に制御できる LINQ ライク・メソッドにこそ積極的な価値があるとも言える。

あくまで遅延評価だとするならば LINQ: .NET Language-Integrated Query [microsoft.com] で使われているような "deferred evaluation" の訳語としての「遅延評価」をまず定着させるべきでしょう。 それらを lazy と呼ぶべきではありません。

この LINQ ライクなメソッドの枠組みのもとでは,個々の処理を従来型の手続きとして記述しながら, 全体の処理をあたかも純粋な関数型言語の遅延リストであるかのように構成することができる。 そのことは,このような枠組みの発端となった C# の LINQ と同じく,手続き型プログラミングに慣れ親しんだ多くのソフトウェア技術者が関数型プログラミングの利点の多くを享受することを可能にすると期待される。

もちろん,ここでオブジェクト指向プログラミングは,手続き型プログラミング,関数型プログラミングと直行する概念として, 当然の前提となっていることに注意してください。 ある意味,今まで典型的に行われてきたオブジェクト指向プログラミングは, その実態として古めかしい手続き型プログラミングとペアにされていたところに限界があった,と言えるかもしれません。 この状況を穏やかに,漸進的に改善する方法として LINQ ライクなメソッドを使うことができます。

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