Groovy 応用: 遅延評価によるフィボナッチ数の計算

2012-08-31 改訂, 2012-09-12 修正 (鈴)
2009-04-08 時点のページ

1. はじめに

Scheme に見られるような delay と force を定義して Groovy に遅延評価の機能を導入し,その上にフィボナッチ (Fibonacci) 数の無限データ構造を構築する。 その過程を通じて,入門編で十分に紹介できなかった Groovy の機能のいくつかを読者に紹介する。

2. 遅延評価の実験

遅延評価 (lazy evaluation) とは,式の値が実際に必要になるまでその評価を遅延する評価方法である。 問題によっては,遅延評価を使うとエレガントに解くことができる。 いくつかの例を より実用的な L2Lisp.rb / 付録: 簡単な遅延評価のプログラム例 に示した。

プログラミング言語 Scheme は遅延評価を主流の評価戦略とはしていないが,delay と force によってこれをサポートしている。 Groovy はクロージャとその簡潔な表記法を備えており,Scheme 報告書 R5RS (和訳 [unixuser.org]) 6.4 節にある delay と force の実装例と使用例をほぼ直訳することができる。 下記にその一例を示す。

// R5RS 6.4 から

def force(Closure object) {
    return object()
}

Closure delay(Closure proc) {
    boolean result_ready = false
    def result = false
    return {->
        if (! result_ready) {
            def x = proc()
            if (! result_ready) {
                result_ready = true
                result = x
            }
        }
        return result
    }
}

count = 0
p = delay {
    count += 1
    if (count > x) {
        count
    } else {
        force p
    }
}

x = 5
println p                       // => 約束
println force(p)                // => 6
println p                       // => 依然,約束
x = 10
println force(p)                // => 6

delay 関数はクロージャを引数にとり,約束オブジェクト (ここでは新しい別のクロージャ) を返す。 force 関数は約束オブジェクトを引数にとり,元のクロージャを高々1回だけ評価し,その値を返す。

01:~/tmp$ groovy lazy_test.groovy
lazy_test$_delay_closure2@fc63be
6
lazy_test$_delay_closure2@fc63be
6
01:~/tmp$  
ここに示した Groovy スクリプトは入門編で学んだ内容だけで完全に理解できるはずです。

トップレベルでメソッドや変数を定義したスクリプトをクラスとして扱ったときの振舞については入門編 6.1 節6.4 節で説明しました。 実際に,スクリプト lazy_test.groovy を対話シェルから試してみましょう。 lazy_test.groovy と同じディレクトリから無引数で groovysh を実行します。
01:~/tmp$ groovysh
復習になりますが,下記の点に注意してください。
  1. スクリプトのファイル名と同じ名前のクラス (ここでは lazy_test) が暗黙裏に定義される。
  2. スクリプトの実行文 (および,ここにはないが変数宣言) がその run() メソッドに収容される。
  3. 定義されたメソッド (ここでは delay と force) がそのクラスのインスタンスの公開メソッドになる。
  4. 宣言なしに定義された変数 (x と p) が binding variable (実装は違うが事実上そのクラスのインスタンスの公開フィールド) になる。
groovy:000> t = new lazy_test()
===> lazy_test@ddef87
groovy:000> t.run()
lazy_test$_delay_closure2@7779d2
6
lazy_test$_delay_closure2@7779d2
6
===> null
groovy:000> t.x
===> 10
groovy:000> t.p
===> lazy_test$_delay_closure2@7779d2
groovy:000> t.force(t.p)
===> 6
groovy:000> a = t.delay { println "hi ho"; "sw" }
===> lazy_test$_delay_closure2@e40a47
groovy:000> t.force a
hi ho
===> sw
groovy:000> t.force a
===> sw
groovy:000>  

3. Promise クラス

前節の実験的な実装にはいくつか難点がある。

  1. 約束オブジェクトをクロージャ (= Closure インスタンス) で代用するのではなく,固有のクラスとして扱いたい。
  2. 約束オブジェクトの式を評価した (= 約束をかなえた,deliver した) 後は,toString() メソッドによる文字列表現でその式の値が得られるようにしたい。
  3. 式の値を得るとき,それが約束オブジェクトならば force をしなければならず,約束でないならば force をしてはならない。 この使い分けは Scheme や Groovy のように動的に型を決める言語では人間に負担を強いる。 式の値を得るときは,とにかく force をすればよいようにしたい。

下記はこのうち 1. と 2. の要件を満たすように定義したクラス Promise である。 3. については 3.1 節で解決する。

package jp.oki_osk.esc

import groovy.transform.CompileStatic

/** Scheme 由来の「約束」。R5RS 6.4 の make-promise 手続きを参照。
*/
@CompileStatic
class Promise {
  private boolean resultReady = false
  private result = null
  private Closure<Object> proc

  /** 約束を作る。
   * @param proc  無引数のクロージャ
   */
  Promise(Closure<Object> proc) {
    this.proc = proc
  }

  /** まだかなえられていなければ,約束をかなえる。
   * @return 最初に無引数クロージャ proc を呼び出して得られた結果の値
   */
  Object deliver() throws Exception {
    if (! resultReady) {
      def x = proc()
      proc = null               // proc はもう不要だから参照を取り消す
      if (! resultReady) {
        resultReady = true
        result = x
      }
    }
    return result
  }

  /** @return 約束をかなえていればその値の文字列。そうでなければ 
   *          生の Object の文字列。
   */
  String toString() {
    if (resultReady) result.toString() else super.toString()
  }
}

/** … */ は Java と同様のドキュメンテーション・コメントである。 これからドキュメントを自動生成する方法を 付録 1. groovydoc の使い方 に簡単にまとめた。

前節の実験では「約束」の内部状態を表現する変数を delay 関数のローカル変数として作り,delay 関数の終了後もクロージャの生きている限りその自由変数として保持していた。 Promise クラスはこれらの状態を陽に private フィールドとして保持する。

result フィールドに対して型を明記していないことに注意してください。 private キーワードから宣言または定義であることが明らかなので省略できます。

例外を送出し得る任意の約束オブジェクトを Java からも支障無く利用できるように,deliver() メソッドに throws Exception 句を付けて,そのメソッドが Exception インスタンスを送出し得ると宣言する。 ただし,この宣言が意味をもつのは Java から deliver() メソッドを呼び出したときだけである。 Groovy では意味をもたない。

String toString() メソッドでは,評価済みかどうかのフラグ・フィールド resultReady の値をもとに戻り値を切り替える。

ファイル Promise.groovy を src/jp/oki_osk/esc/Promise.groovy として置いて対話シェルで実験してみましょう。
01:~/tmp$ groovysh -cp src
または
01:~/tmp$ cd src
01:~/tmp/src$ groovysh
として開始します。 new 式では最外でも引数の丸括弧を省略できないことに注意してください。 Groovy の奇妙なクセです。
groovy:000> import jp.oki_osk.esc.Promise
===> [import jp.oki_osk.esc.Promise]
groovy:000> a = new Promise({ println "hi ho"; "sw" })
===> jp.oki_osk.esc.Promise@7e4345
groovy:000> a
===> jp.oki_osk.esc.Promise@7e4345
groovy:000> a.deliver()
hi ho
===> sw
groovy:000> a
===> sw
groovy:000> a.deliver()
===> sw
groovy:000>  

3.1 拡張モジュール

任意のクロージャとオブジェクトに対して,事実上,Scheme の delay と force と同様に使える関数を Groovy の拡張モジュール (extension module) を使って実現する。

package jp.oki_osk.esc;

import groovy.transform.CompileStatic

/** Scheme 由来の遅延評価関数。R5RS の 4.2.5 と 6.4 を参照。
 * グローバル関数とするため Object への拡張モジュールとして与える。
 */
@CompileStatic
class LazyExtension {
  /** 無引数のクロージャを与えて約束を作る。
   * @param proc 無引数のクロージャ
   * @return 作った約束
   */
  static Promise delay(Object self, Closure<Object> proc) {
    new Promise(proc)
  }

  /** 約束の実現を強制する。
   * @param p 約束または任意の値
   * @return p が約束ならばかなえた値。そうでなければそのままの値。
   */
  static force(Object self, p) throws Exception {
    if (p instanceof Promise) p.deliver() else p
  }
}

二つの静的メソッド static Promise delay(Object self, Closure proc)static force(Object self, p)java.lang.Object への追加メソッドとして使われることを意図している。

force メソッドに対して戻り値型を明記していないことに注意してください。 static キーワードから宣言または定義であることが明らかなので省略できます。

入門編 4.3 節 では java.lang.Object への追加メソッドとして println が標準で用意されていることを説明した。 この LazyExtension クラスのように静的メソッドからなるクラスを用意し,付録 2. 拡張モジュールの作り方 のような手順を踏んで (あるいは何らかのツールにその手順を踏ませて) lazy-module.jar のような拡張モジュールを作れば,println のようなメソッドを自由に利用者が定義できる。 このとき,その拡張モジュールに CLASSPATH を通す以外の手続きは不要である。

対話シェルで拡張モジュールを使ってみましょう。cp オプションで CLASSPATH を通します。
01:~/tmp$ groovysh -cp lazy-module.jar
delay と force を組込み関数のように使うことができます。
groovy:000> a = delay { println "hi ho"; "sw" }
===> jp.oki_osk.esc.Promise@1a3b359
groovy:000> a
===> jp.oki_osk.esc.Promise@1a3b359
groovy:000> force a
hi ho
===> sw
groovy:000> a
===> sw
groovy:000> force a
===> sw
groovy:000>  
C# の拡張メソッドと異なり,利用するとき import 宣言は不要です。 これは反面,どのような拡張モジュールを使ってそのコードが書かれているのか Groovy スクリプトやクラス定義から直接は分からない,ということを意味します。 これを Groovy の恐ろしい欠点ととらえる人がいても反論はしません。

3.2 静的コンパイル

ファイル Promise.groovyLazyExtension.groovy では下記のような記述をした。

import groovy.transform.CompileStatic
@CompileStatic
class LazyExtension {

後者はクラスの静的コンパイル (static compilation) を指示するアノテーションであり,前者はそのための import 宣言である。 静的コンパイルは *.groovy ファイルから *.class ファイルへのコンパイル時に静的に型を決定することによって,Java に近い効率のコードを生成することを可能にする。

lib ディレクトリの下にコンパイルした jp/oki_osk/esc/LazyExtension.class を置いているとして,実際の生成コードを調べてみよう。

01:~/tmp$ javap -c -classpath lib jp.oki_osk.esc.LazyExtension

force メソッドの部分は次のようになっている。

public static java.lang.Object force(java.lang.Object, java.lang.Object)   throw
s java.lang.Exception;
  Code:
   0:	aload_1
   1:	instanceof	#37; //class jp/oki_osk/esc/Promise
   4:	ifeq	18
   7:	aload_1
   8:	checkcast	#37; //class jp/oki_osk/esc/Promise
   11:	invokevirtual	#53; //Method jp/oki_osk/esc/Promise.deliver:()Ljava/lan
g/Object;
   14:	areturn
   15:	goto	20
   18:	aload_1
   19:	areturn
   20:	aconst_null
   21:	areturn

次に,LazyExtension.groovy@CompileStatic の行を消してからコンパイルして同じように調べよう。

静的コンパイルした上のコードでは Promise#delver メソッドを仮想メンバ関数としてそのまま呼び出しているが, そうではない (従来どおりの Groovy の) 下のコードでは Groovy 内部の実行時インタフェースの1引数汎用メソッドを呼び出している。

public static java.lang.Object force(java.lang.Object, java.lang.Object)   throw
s java.lang.Exception;
  Code:
   0:	invokestatic	#24; //Method $getCallSiteArray:()[Lorg/codehaus/groovy/
runtime/callsite/CallSite;
   3:	astore_2
   4:	aload_1
   5:	instanceof	#37; //class jp/oki_osk/esc/Promise
   8:	ifeq	25
   11:	aload_2
   12:	ldc	#57; //int 1
   14:	aaload
   15:	aload_1
   16:	invokeinterface	#61,  2; //InterfaceMethod org/codehaus/groovy/runtime/c
allsite/CallSite.call:(Ljava/lang/Object;)Ljava/lang/Object;
   21:	areturn
   22:	goto	27
   25:	aload_1
   26:	areturn
   27:	aconst_null
   28:	areturn

ただし,残念ながら現在の静的コンパイル機能は日常の道具としては完全ではない。

それを確かめるため,Promise.groovy の中に出現する Closure<Object>Closure に置き換えよう。 つまり,置換え前と diff コマンドで比較して次のように出力されるように書き換えるわけである。

01:~/tmp/src/jp/oki_osk/esc$ diff Promise.groovy~ Promise.groovy
12c12
<   private Closure<Object> proc
---
>   private Closure proc
17c17
<   Promise(Closure<Object> proc) {
---
>   Promise(Closure proc) {
11:~/tmp/src/jp/oki_osk/esc$  

これをコンパイルすると奇妙な結果になる。

01:~/tmp/src/jp/oki_osk/esc$ cd ../../../..
01:~/tmp$ groovyc -d lib src/jp/oki_osk/esc/Promise.groovy
null
11:~/tmp$  

ただ null とだけ表示され,終了コード 1 でエラー終了し,*.class ファイルは生成されない。 原因はおそらく Closure の戻り値型が指定されないことから静的な型決定に失敗したためだが,この振舞は満足できるものではない。

この振舞は Java 1.6.0_33 上の Groovy 2.0.1 でのものです。きっと速やかに解決されるでしょう。

4. フィボナッチ数の計算

拡張モジュールで実現した delayforce を利用して, より実用的な L2Lisp.rb / 付録: 簡単な遅延評価のプログラム例 / 2. フィボナッチ数列 の L2 Lisp で書かれたフィボナッチ数列の無限データ構造を Groovy で書いてみよう。

L2 Lisp の遅延評価の仕組みは基本的には Scheme と同じだが,プリミティブ関数が自動的に force を行う (= implicit forcing を行う) 点で異なる。 ここでは force メソッドを陽に書く必要がある。

// H24.8/27 (鈴) 遅延リストによるフィボナッチ数列のテスト

// ここでは LazyExtension の delay と force を使う。
// 遅延リストを [ head, 約束 ] で表現する。

def zipWith(Closure f, x, y) {
  x = force(x)
  y = force(y)
  if (x == null || y == null) {
    null
  } else {
    [
      f(x[0], y[0]),
      delay { zipWith(f, x[1], y[1]) }
    ]
  }
}

def start() {
  // 遅延リストによるフィボナッチ数列を定義する (初項は 1G)。
  // 計算量を確かめるため加算演算ごとに * を印字する。
  def fib;
  fib = [1G,
         [1G, delay {
             zipWith({ x, y -> print "*"; x + y }, fib, fib[1])
           }]]

  // 第50項まで値を評価して,数列を印字する。
  def f = fib
  50.times { f = force(f)[1] }
  println fib
}

start()

元の例ではゼロから数えて 33 番目の値を印字していたが,ここでは景気良く(?) 50.times {…} で第 50 項まで評価してから,数列全体を印字する。 また,遅延評価での計算量を確認するため,次の項を求めるための加算演算を1回するごとに * を1個印字させる。 下記はその実行例である。

01:~/tmp$ groovy -cp lazy-module.jar fib.groovy
************************************************[1, [1, [2, [3, [5, [8, [13, [21
, [34, [55, [89, [144, [233, [377, [610, [987, [1597, [2584, [4181, [6765, [1094
6, [17711, [28657, [46368, [75025, [121393, [196418, [317811, [514229, [832040, 
[1346269, [2178309, [3524578, [5702887, [9227465, [14930352, [24157817, [3908816
9, [63245986, [102334155, [165580141, [267914296, [433494437, [701408733, [11349
03170, [1836311903, [2971215073, [4807526976, [7778742049, [12586269025, jp.oki_
osk.esc.Promise@16de067]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]
01:~/tmp$  

12586269025 の次以降はまだ未評価の約束 jp.oki_osk.esc.Promise@16de067 である。 * は 48 個印字されているが,数列の最初の2項は BigInteger 定数 1G として与えられているから,これは期待どおりの結果である。 加算演算は (lazy という語感のとおりに) 必要最低限の回数しか行われていない。

5. おわりに

本稿で著者は Groovy がよく遅延評価の計算を表現できることを例によって示した。 それと同時に,チュートリアルの一環として拡張モジュールなど Groovy の発展的な機能を紹介した。 ドキュメンテーション・コメントから文書を生成する groovydoc は現実の Java プロジェクトに Groovy を混ぜ込ませるとき,おそらく重要になるだろう。

付録 1. groovydoc の使い方

Groovy には Java の javadoc コマンドに準ずる groovydoc コマンドがある。 Groovy 入門 第 2.2 節 と同じようにして groovydoc コマンドを使えるようにしよう。

01:/usr/local/bin$ sudo ln -s ../share/groovy-2.0.1/bin/groovydoc .

今,src ディレクトリの下に jp.oki_osk.esc.Promise クラスのソース・ファイル jp/oki_osk/esc/Promise.groovy 等があると仮定する。

01:~/tmp$ groovydoc -d doc -sourcepath src jp.oki_osk.esc

とすると,もしなければ doc ディレクトリが作られ,そこに jp.oki_osk.esc パッケージのクラスのソース・ファイル (ここでは Promise.groovy 等) のドキュメンテーション・コメント /** .. */ に由来する HTML ドキュメントが一式作成される。

Mac OS X では次のようにしてデフォルト・ブラウザでこれを閲覧できる。Cygwin では cygstart コマンドを使えばよい。

01:~/tmp$ open doc/index.html
01:~/tmp$  
今のところ jp ディレクトリをカレント・ディレクトリ直下に置いて -sourcepath にカレント・ディレクトリ "." を指定すると,package に置いたはずのクラス定義が誤って "Default Package" にあるものとしてドキュメントが作成される不具合があります。 src のようなディレクトリを1段はさめば回避できます。

付録 2. 拡張モジュールの作り方

3.1 節のクラスを拡張モジュールとする手順を説明する。

ディレクトリ src/jp/oki_osk/esc にソース・ファイル LazyExtension.groovyPromise.groovy を用意し,これを groovyc でコンパイルする。

01:~/tmp$ groovyc -cp src -d lib src/jp/oki_osk/esc/LazyExtension.groovy

ソースを収めた src ディレクトリを CLASSPATH として指定することに注意しよう。 これがないと LazyExtension クラスは Promise クラスの定義を収めた Promise.groovy を見つけることができない。 やや意外なことに,こうしても lib/jp/oki_osk/esc には LazyExtension.classPromise.class の両方が作られる。

コンパイル結果が置かれた lib ディレクトリ に META-INF/services ディレクトリを作り,モジュール記述子を置く。

01:~/tmp$ cd lib
01:~/tmp/lib$ mkdir -p META-INF/services
01:~/tmp/lib$ emacs META-INF/services/org.codehaus.groovy.runtime.ExtensionModule 

ここでモジュール記述子 org.codehaus.groovy.runtime.ExtensionModule は次の内容とする。

moduleName = lazy-module
moduleVersion = 1.0
extensionClasses =
staticExtensionClasses = jp.oki_osk.esc.LazyExtension

LazyExtension クラスの各メソッドは java.lang.Object 型の第1引数を全く使っていないから,java.lang.Object の非静的メソッドとしても,静的メソッドとしても追加することができる。 ここでは後者とするため staticExtensionClasses にクラス名を記述する。

静的メソッドとして追加したとき,第1引数には null が渡されます。

この lib ディレクトリを CLASSPATH に含めるか,あるいは

01:~/tmp/lib$ jar cf lazy-module.jar .
01:~/tmp/lib$ mv lazy-modue.jar ..
01:~/tmp/lib$  

のように jar ファイルを作成して,それを CLASSPATH に含める。 どちらの場合も,自動的に jp.oki_osk.esc.LazyExtension のメソッドが Groovy の追加メソッドとなる。

詳細については Groovy - Creating an extension module [codehaus.org] を参照してください。


目次へ


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