For Gauche 0.9.5


Next: , Previous: , Up: 組み込みライブラリ   [Contents][Index]

6.19 遅延評価

Gaucheには、ふたつの組み込みの遅延評価メカニズムがあります。

ひとつめはScheme標準で定められている、明示的なメカニズムです。遅延評価したい式を delay構文でマークし、値が必要になったところでforceにより 評価を強制します。Gaucheはさらに、srfi-45で導入された、 末尾再帰アルゴリズムでメモリを効率的に利用するためのlazyというプリミティブも サポートしています。

もうひとつは遅延シーケンスです。こちらは評価をforceで明示する必要が ありません。Schemeプログラムからは、遅延シーケンスは通常のリストと全く 同じに見えます。carcdrを使ったり、mapを始めとする 様々なリスト手続きをそのまま適用することができます。けれども内部的には、 遅延シーケンスの要素は必要になるまで計算されません。


Next: , Previous: , Up: 遅延評価   [Contents][Index]

6.19.1 Delayとforceとlazy

Schemeは伝統的に、delayforceを使った 明示的な遅延評価メカニズムを提供してきました。しかし、R5RSの後で、 それが末尾再帰的なアルゴリズムとの相性がよくないことがわかりました。 末尾再帰的なアルゴリズムの本体が反復的に表現できるにもかかわらず、 メモリを際限なく要求してしまうのです。SRFI-45によって、 新たなプリミティブ構文lazyを使えばその問題が回避できることが示されました。 詳しい議論はSRFI-45のドキュメントを見てください。 ここではこれらのプリミティブの使い方を説明します。

Special Form: delay expression
Special Form: lazy expression

[R7RS][SRFI-45] これらの形式はexpressionの評価を遅延するプロミスを生成し ます。Expression はこのプロミスがforceにわたったときに評 価されます。

expression自身がプロミスを返す式ならlazyを、 そうでなければ、delayを使います。 型で考えるとわかりやすいでしょう。

lazy  : Promise a -> Promise a
delay : a -> Promise a

Schemeでは静的な型付けをしないので、この使い分けを強制することができません。 文脈にしたがってプログラマが適切に選択する必要があります。 一般的にはlazyは遅延アルゴリズムを表現している関数本体全体を囲む場合 にのみ出現します。

註: R7RSではlazydelay-forceと呼ばれています。概念的に (delay (force expr))という操作と考えられるからです (forceの型はPromise a -> aであると考えられます)。

lazyの実用的な使用例についてはutil.stream (ストリームライブラリ)の実装をチェックするといいでしょう。

Function: force promise

[R7RS] もし、promiseがプロミスでなければ、それをそのまま返します。

そうではない場合で、もしpromiseの値がまだ計算されていない場合には、 forcepromiseが内包している式を評価し、その結果を返します。

いったん、promiseの値が計算されると、その値はメモ化され、あとで 再びforceされても、再計算がおこなわれることはありません。

Function: promise? obj

[R7RS] objがプロミスオブジェクトである場合に #tを返します。


Previous: , Up: 遅延評価   [Contents][Index]

6.19.2 遅延シーケンス

イントロダクション

遅延シーケンスはリストのようなデータ構造ですが、要素は必要になるまで 計算されません。内部的には、これはcdrの評価が遅延される特別な種類の ペアを使って実現されています。しかし、Schemeのレベルで 「遅延ペア」のような特別なデータ型が見えることは決してありません。 遅延ペアにアクセスしようとした途端、Gaucheは自動的に 遅延されていた計算をforceして、遅延ペアは通常のペアに変化してしまうからです。

これはつまり、遅延シーケンスをcarcdrmapといった 通常のリスト処理手続きにそのまま渡せるということです。

次の例を見てください。generator->lseqは、 「呼ばれる度に次の値を返す」という手続きを取り、返される値からなる遅延シーケンス にして返す手続きです。

(with-input-from-file "file"
  (^[] (let loop ([cs (generator->lseq read-char)] [i 0])
         (match cs
           [() #f]
           [(#\c (or #\a #\d) #\r . _) i]
           [(c . cs) (loop cs (+ i 1))]))))

このコードは、ファイルfile中に最初に出現する “car”または”cdr”という文字列の場所を返します。 文字は必要に応じて読まれ、目的の文字列が見つかれば残りは読まれません。 これを遅延無しでやろうとすると、一旦全てのファイルを読み込んでリストに 変換するか、あるいは便利なmatchマクロを使うのを諦めて 一文字つづ読み込んで処理する原始的な状態機械を書くしかないでしょう。

暗黙のforceの他にも、Gaucheの遅延シーケンスは Schemeの典型的な遅延ストリーム実装に比べて次のような違いがあります。

  1. 遅延シーケンスを、繰り返しによる怠惰なアルゴリズムから構築する際に、 遅延ペアのcdr側のみが遅延評価の対象となります。 ペアのcar側は直ちに評価されます。 一方、util.streamstream-consでは、 carcdrのどちらも遅延評価の対象となり、 必要となるまで評価されません (ストリームライブラリ参照)。
  2. Gaucheの遅延シーケンスは、常にひとつ余分に評価します。 遅延ペアを手にした段階で、その中身にアクセスするかしないかにかかわらず、 既にそのcarは評価済みであるということです。 ひとつ余分に計算してしまうことのコストは、通常はあまり問題にならないでしょう (全てを余分に計算するよりは良いわけですから)。けれども、自分自身を参照 する遅延データ構造、つまり、遅延シーケンスの次の要素を計算するために そのシーケンスの前の方の要素を参照する必要がある場合は注意が必要です。 遅延評価言語で正しい自己参照遅延データの生成コードが、 そのままではGaucheで停止しなくなる場合があります。後で例を示します。 また、評価に副作用がある場合にもこの差異が観測される場合があります。 例えば、ポートから一文字づつ読む遅延シーケンスは、 見かけよりも一文字余分に読むことになるでしょう。

プリミティブ

Function: generator->lseq generator
Function: generator->lseq item … generator

ジェネレータ手続きgeneratorから生成される値の列を、遅延シーケンスとして返します。 ジェネレータ手続きは引数を取らない手続きで、呼ばれる度に次の値を返すようなものです。 EOFが返されたら、シーケンスの終了とみなされます (EOF自体はシーケンスには含まれません)。 例えばread-charはそのままgeneratorに渡せます。 ジェネレータ手続きを作ったり加工したりする便利なユーティリティが gauche.generatorモジュールで提供されています (ジェネレータ参照)。

二番目の形式では、item …が遅延シーケンスの先頭に 配置されます。遅延ペアと通常のペアは区別できないので、これは (cons* item … (generator->lseq generator))とも書けますが、 少々冗長になるでしょう。

内部的には、Gaucheの遅延シーケンスはジェネレータを使うように最適化 されています。遅延シーケンスを作る最も効率の良い方法はこの手続きを使うことです。

Macro: lcons car cdr

carcdrからなる遅延ペアを作って返します。 carlconsを呼び出した時点で評価されますが、 cdrの評価は遅延されます。

遅延ペアと通常のペアを区別する方法はありません。ペアのcarcdrに アクセスしたり、それどころかpair?によって型を確かめただけでも、 遅延ペアのcdr側はforceされて、遅延ペアは通常のペアへと変化します。

consと違って、遅延ペアのcdrはリスト (遅延でも通常でも) を返す 関数でなければなりません。遅延シーケンスは全てforceされたら、 常に空リストで終端されているリストになる、と言っても良いでしょう。つまり、 ドット対を最後に持つような「不完全なリスト」に対応する「不完全な遅延シーケンス」 というものはありません。(Schemeは静的型ではないので、実際に評価するまで cdrが完全なリストを生成することを保証することができません。 現在の実装では、cdrがリストでない値を生成した場合、 それを単に無視して空リストが返されたかのように扱います)。

(define z (lcons (begin (print 1) 'a) (begin (print 2) '())))
 ⇒ ; car部はすぐに評価されるので、'1'が表示される

(cdr z) ⇒ () ;; そして'2'が表示される

;; これも'2'を表示する。遅延ペアのcarにアクセスすると、その時点で
;; cdr部の評価もforceされるので。
(car (lcons 'a (begin (print 2) '()))) ⇒ a

;; これも同じ。pair?と聞くだけで遅延ペアはforceされる
(pair? (lcons 'a (begin (print 2) '()))) ⇒ #t

;; 念のため。次の例では'2'は出力されない。二番目の遅延ペアはアクセス
;; されていないので、そのcdrも評価されない。
(pair? (lcons 'a (lcons 'b (begin (print 2) '())))) ⇒ #t

Gaucheの「一つ先の要素まで計算」が問題となる例も見ておきましょう。 次の例は、自己参照する遅延シーケンスを使った、とても美しい無限フィボナッチ数列の 定義です (lmapは遅延バージョンのmapで、gauche.lazyモジュールで 提供されています)。

(use gauche.lazy)  ;; for lmap
(define *fibs* (lcons* 0 1 (lmap + *fibs* (cdr *fibs*)))) ;; BUGGY

残念ながら、Gaucheではこれはうまく動きません。

(car *fibs*)
 ⇒ 0
(cadr *fibs*)
 ⇒ *** ERROR: Attempt to recursively force a lazy pair.

*fibs*の二番目の要素(cadr)にアクセスするということは、 *fibs*の二番目のペアのcarを取るということです。*fibs*の 二番目のペアは1(lmap ...)の遅延ペアになっています。 carを取ろうとした時点でこの遅延ペアはforceされ、そのcdrが計算されます。 lmapが最初に返さなければならないのは、*fibs*の一番目と二番目の 要素の和です。しかし*fibs*の二番目の要素は、今まさにアクセスしようと している値です!

この問題は、ある要素を計算するために直前の要素を参照しなければ回避できます。 フィボナッチ数はF(n) = F(n-1) + F(n-2) = 2*F(n-2) + F(n-3)と変形できるので、 遅延フィボナッチシーケンスはこう定義できます。

(define *fibs*
  (lcons* 0 1 1 (lmap (^[a b] (+ a (* b 2))) *fibs* (cdr *fibs*))))

これでok!

(take *fibs* 20)
  ⇒ (0 1 1 2 3 5 8 13 21 34 55 89 144 233
     377 610 987 1597 2584 4181)

多くの遅延アルゴリズムは、完全な遅延評価をするconsを基礎にしています。 そういったアルゴリズムをlconsを使ってGaucheに移植する際には、 Gaucheのこのちょっとした「熱心さ」に気をつけてください。

lconsは、実行の度にcdr部の評価を遅延するためのクロージャを 作るということにも注意してください。lconsを使った遅延アルゴリズムでは 要素ひとつにつきクロージャをひとつ作るオーバヘッドがかかります。 性能が重要な部分では、可能な限りgenerator->lseqを使いましょう。

ユーティリティ

Macro: lcons* x … tail
Macro: llist* x … tail

遅延バージョンのcons*です (リストの作成参照)。 lcons*llist*は全く同じです。 cons*/list*との対称性から両方の名前が定義されています。

tail引数は(遅延もしくは通常の)リストを生成する式でなければなりません。 tail引数の評価は遅延されます。x …引数はすぐに 評価されます。次の関係が成り立ちます。

(lcons* a)           ≡ a
(lcons* a b)         ≡ (lcons a b)
(lcons* a b ... y z) ≡ (cons* a b … (lcons y z))
Function: lrange start :optional end step

startからstepづつ増加し、endを越える直前までの遅延数列を 返します。stepのデフォルトは1、endのデフォルトは無限大です。 endを省略すると無限数列になるので、REPLで安易に (lrange 0)など評価しないようにしましょう。

startstepの少なくとも一方が不正確数なら、 不正確数列が返されます。

(take (lrange -1) 3) ⇒ (-1 0 1)

(lrange 0.0 5 0.5)
  ⇒ (0.0 0.5 1.0 1.5 2.0 2.5 3.0 3.5 4.0 4.5)

(lrange 1/4 1 1/8)
  ⇒ (1/4 3/8 1/2 5/8 3/4 7/8)
Function: liota :optional (count +inf.0) (start 0) (step 1)

遅延バージョンのiotaです (リストの作成参照)。 start(デフォルト0)からstep(デフォルト1)づつ増加する、 count個(デフォルト無限大)の遅延数列を返します。

iotaと同様、startstepの両方が正確数の時に限り、 結果は正確数のリストとなり、そうでなければ非正確数のリストとなります。

Function: port->char-lseq :optional port
Function: port->byte-lseq :optional port
Function: port->string-lseq :optional port
Function: port->sexp-lseq :optional port

これらの手続きは以下の式とそれぞれ同等です。このパターンは良く現れるので、 簡便のために用意しました。

(generator->lseq (cut read-char port))
(generator->lseq (cut read-byte port))
(generator->lseq (cut read-line port))
(generator->lseq (cut read port))

portが省略された場合はcurrent-input-portが使われます。

遅延シーケンスが入力をいくらかバッファする可能性があるので、 一度lseqを作った後では、portから直接読み出しをしないようにしてください。

遅延シーケンスはポートがEOFを返した時点で終端となりますが、 ポート自体はクローズされないことに注意してください。ポートの管理は、 遅延シーケンスを使う部分全体を囲むような大きな動的エクステントで 行う必要があります。

入力ポートを色々なリストに変換するには、他に次のような手続きがあります (入力ユーティリティ手続き参照)。lseq版がポートを 必要に応じて読むのに対し、 これらの手続きはポートをEOFに達するまで一気に読み込み、 全てのデータをリストにしてから返します。

(port->list read-char port)
(port->list read-byte port)
(port->string-list port)
(port->sexp-list port)

これらの手続きは、ポートからリストを作りだします。反対の手続きとして、 open-input-char-listopen-input-byte-listがあります (仮想ポート参照)。

遅延シーケンスを作るユーティリティ関数は他にもたくさん提供されています。 遅延シーケンスユーティリティを参照してください。

素数の無限列を計算してみましょう。(註: アプリケーションで素数が必要な場合は、わざわざ書かなくても math.primeが使えます。素数参照。)

まず、既にある程度の計算済みの素数列が*primes*にあるとします。 すると、与えられたn以上の素数をひとつ見つける手続きが次のとおり書けます (nは奇数とします。)

(define (next-prime n)
  (let loop ([ps *primes*])
    (let1 p (car ps)
      (cond [(> (* p p) n) n]
            [(zero? (modulo n p)) (next-prime (+ n 2))]
            [else (loop (cdr ps))]))))

この手続きは素数列をループし、(sqrt n)以下の素数で nを割ろうとします。一つも割りきれる素数がなければ、nが素数です。 (実際の条件は、(> p (sqrt n))より効率の良い(> (* p p) n)を 使っています)。 nを割り切る素数があった場合は、 next-primeを再帰的に呼んで(+ n 2)を試します。

next-primeを使うと、次々に素数を生成してゆくジェネレータを書くことができます。 次の手続きはlastより大きい素数を次々に生成するジェネレータです。

(define (gen-primes-above last)
  (^[] (set! last (next-prime (+ last 2))) last))

generator->lseqを使えば、 gen-primes-aboveを遅延シーケンスに変換することができ、 それを*prime*の値とすることができます。最初の方の素数を計算するために、 あらかじめ計算済みの素数をいくつか用意しておくのがポイントです。

(define *primes* (generator->lseq 2 3 5 (gen-primes-above 5)))

*primes*を直接REPLで評価しないように。無限リストなので、 REPLの表示が終わらなくなります。 かわりに、例えばこんなふうにして最初の20個の素数を見たり:

(take *primes* 20)
 ⇒ (2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71)

10000番目の素数は何かを見たり:

(~ *primes* 10000)
 ⇒ 104743

あるいは1000000以下の素数はいくつあるかを調べたりできます:

(any (^[p i] (and (>= p 1000000) i)) *primes* (lrange 0))
 ⇒ 78498

註:遅延評価な関数型言語に慣れたプログラマには、この例は奇妙に見えるかもしれません。 わざわざ副作用のあるジェネレータを経由しないでも、 次に示すとおり、素数列は純粋に関数的な方法で定義できます。

(use gauche.lazy)

(define (prime? n)
  (not (any (^p (zero? (mod n p)))
            (ltake-while (^k (<= (* k k) n)) *primes*))))

(define (primes-from k)
  (if (prime? k)
    (lcons k (primes-from (+ k 2)))
    (primes-from (+ k 2))))

(define *primes* (llist* 2 3 5 (primes-from 7)))

(gauche.lazyモジュールには、take-whileの 遅延バージョンltake-whileが定義されています。 anyについては、遅延バージョンは必要ありません。anyはもともと 述語が真を返したら直ちに評価をやめて残りは見ないからです)。

primes-fromでのlconsを使った余再帰は、 関数型プログラミングでの典型的なイディオムです。もちろん、 Gaucheでもこのようなコードを書くことに何の問題もありません。 ただし、Gaucheではジェネレータを使った方がずっと効率が良くなります (筆者のマシンでは、最初の5000個の素数を計算するのに、 ジェネレータ版は余再帰版より17倍速いです)。

だからといって何が何でも余再帰を避けるべきということにはなりません。 アルゴリズムが余再帰で自然にかけるならそうして構わないでしょう。 ただその場合でも、遅延評価な関数型言語とのセマンティクスの違いを いつも気をつけるようにしてください。単に遅延評価アルゴリズムのコードを そのまま移植しても動くとは限りません。


Previous: , Up: 遅延評価   [Contents][Index]