6.18.1 Delayとforceとlazy

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

Special Form: delay expression ¶

Special Form: lazy expression ¶

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

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

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

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

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

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

expressionは一回以上評価され得ることに気をつけてください。 expressionの評価中に再帰的にそれ自身のプロミスの値を必要とするかも しれませんし、複数のスレッドがexpressionの計算を並行して行うかもしれません。 一般的に、expressionの中に副作用を持つ式を入れるべきではありません。 たとえexpressionが一度しか評価されないとしても、 それがいつ評価されるかわからないかもしれないわけですから、 副作用を持つのはまずいでしょう。 (複数のスレッドがある場合のセマンティクスについては下のforceを 参照してください)。

Function: eager obj … ¶

Function: make-promise obj … ¶

[SRFI-45][SRFI-226] obj …を返すプロミスを作って返します。 eagerという名前はSRFI-45で導入されました。SRFI-45では一つの引数のみを 取るように定義されていますが、Gaucheでは複数の値を取って複数の値を返せるように 拡張されています。SRFI-226はmake-promiseを定義しましたが、 それは複数の値を取るeagerと同じです。 (R7RS-smallもscheme.lazyライブラリでmake-promiseを 定義しています(scheme.lazy - R7RS遅延評価参照)が、 この組み込み版とは少し異なります。 R7RS版はひとつだけ引数を取るのと、引数が既にプロミスならそのまま返されます。 この変更は意図的なものです。詳しくはSRFI-226を参照してください)。

これらは通常の手続きなので、引数の評価は遅延されせん。 評価を遅延することなく型変換(a -> Promise a)だけを行いたい 場合に使います。プロミスを返すことが要求される手続きで使われます。

Function: force promise ¶

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

そうではない場合で、もしpromiseの値がまだ計算されていない場合には、 forceはpromiseが内包している式を promiseが作られた時点でのパラメタライゼーションで評価し、その結果を返します。

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

Gaucheでは、遅延された式が複数の値を返した場合、forceもそれらの値を返します。 (R7RSではその場合の動作は未定義です)。

まだ計算されていないプロミスが複数のスレッドで同時にforceされた場合、 プロミスに内包される式の計算は複数のスレッドで並行して進行します。 一番最初に出た結果がプロミスの値として確定します。 他のスレッドは、自分の計算が終わった時に既にプロミスの値が確定していたら、 自分の計算結果を捨てて確定済みの値を返します。

下の例は、プロミスがdelayのあるパラメタライゼーションで評価される ことを示しています:

(define p (make-parameter 1))

(let1 v (parameterize ((p 2)) (delay (p)))
  (parameterize ((p 3))
    (force v)))
  ⇒ 2

註: R7RSでは未評価のプロミス本体はforceの呼び出された動的環境で 評価されるとしていましたが、これは間違いであったとみなされています。 一般的に、どのforceの呼び出しが実際にプロミス本体を評価するのかは 気にされるべきではなく、従ってどこでforceを呼び出すかによって結果が変わるのは おかしいからです。SRFI-226でこれは正されました。

Function: promise? obj ¶

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

6.18.2 遅延シーケンス

イントロダクション

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

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

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

註: ポータブルな遅延シーケンスはR7RSのscheme.lseq (SRFI-127)でも提供されています (scheme.lseq - R7RS遅延シーケンス参照)。SRFI-127では、遅延シーケンスを扱う 専用のAPI (lseq-cdr等) を提供することで、ポータブルな実装を可能にしています。 GaucheではSRFI-127の遅延シーケンスはGaucheの組み込み遅延シーケンスそのものです。 移植性が重要であれば、SRFI-127を使うのが良いでしょう。但し、遅延シーケンスと 通常のリストを混ぜないように気をつけてください。Gaucheは問題なく処理しますが、 他のScheme処理系は喉を詰まらせてしまうかもしれません。

プリミティブ

Function: generator->lseq generator ¶

Function: generator->lseq item … generator ¶

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

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

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

註: SRFI-127もgenerator->lseqを定義していますが、Gaucheではそれは この手続きと同じものです。

Macro: lcons car cdr ¶

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

遅延ペアと通常のペアを区別する方法はありません。ペアのcarやcdrに アクセスしたり、それどころか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)など評価しないようにしましょう。

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

(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と同様、startとstepの両方が正確数の時に限り、 結果は正確数のリストとなり、そうでなければ非正確数のリストとなります。

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-listとopen-input-byte-listがあります (gauche.vport - 仮想ポート参照)。

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

例

素数の無限列を計算してみましょう。(註: アプリケーションで素数が必要な場合は、わざわざ書かなくても math.primeが使えます。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倍速いです)。

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