Scheme第19歩

遅延評価の話その2。

せっかく関数型言語を使うからには、カッコよく高階関数を使いたい。特にmapのようなリストを操作する関数を上手く使うと、実に簡潔に記述できることが多い。その一方で、問題の規模が大きくなると、大量のデータをリストで丸抱えするのは性能面で望ましくない。

そんな理想と現実の狭間に立たされたとき、仕方なく理想を捨てるしかないのだろうか？ いやいや、遅延評価が理想と現実の架け橋となってくれるのだ。

例えば、入力ポートiから読み込んだ各行を()で括って出力ポートoへ書き出すことを考えてみよう。まずは遅延評価を使わないバージョン。

(define (read-lines i)
  (let ((lines '()) (tail '()))
    (let loop ((line (read-line i)))
      (cond
        ((eof-object? line)
          lines)
        ((null? lines)
          (set! lines (cons line '()))
          (set! tail lines)
          (loop (read-line i)))
        (else
          (set-cdr! tail (cons line '()))
          (set! tail (cdr tail))
          (loop (read-line i)))))))
; main
(define all-lines (read-lines i))
(for-each
  (lambda (line) (display line o) (newline o))
  (map
    (lambda (line) (string-append “(“ line “)”))
    all-lines))

read-linesは読み込んだ全ての行をリストの形で返す関数。それを使って取得したall-linesに対して、mapを使って()で括ってからfor-eachで出力しているのだが、このコードの問題は入力を読み尽してから文字列操作や出力を行う点。入力が100万行あれば100万行の入力と100万行のmap結果を蓄えるメモリが必要になるし、入力元がユーザーのキーボードであれば、CTRL-D等で入力を止めるまでレスポンスが見えない。

それではいよいよ、遅延評価を使ってみよう。

(define (lazy-read-lines i)
  (delay
    (let ((line (read-line i)))
      (if (eof-object? line)
        '()
        (cons line (lazy-read-lines i))))))
(define (lazy-null? p) (null? (force p)))
(define (lazy-car p) (car (force p)))
(define (lazy-cdr p) (cdr (force p)))
(define (lazy-map f ls)
  (delay
    (if (lazy-null? ls)
      '()
      (cons (f (lazy-car ls)) (lazy-map f (lazy-cdr ls))))))
(define (lazy-for-each f ls)
  (let loop ((p ls))
    (unless (lazy-null? p)
      (f (lazy-car p))
      (loop (lazy-cdr p)))))
; main
(define all-lines (lazy-read-lines i))
(lazy-for-each
  (lambda (line) (display line o) (newline o))
  (lazy-map
    (lambda (line) (string-append "(" line ")"))
    all-lines))

メインの処理は、記述上は遅延評価版の関数(lazy-xx)を使うよう変更しただけに見えるが、実際には大きく異なる。lazy-xxでは単純なリストの代わりに、forceするとリストのように見えるプロミスを扱うのだ。以下、このプロミスを便宜上、遅延リストと呼ぶ。

遅延リストは、forceすると空リストかドット対になるプロミスである。ドット対だった場合、そのcarはリストの要素、cdrは残りの要素を表す遅延リストである。この遅延リストを使えば、forceしてリストの要素を参照してみるまで、その要素の評価を後回しにすることができる。今回の例では

1. displayするために、map結果の要素が1つ必要になる
2. map結果の要素を1つ求めるために、all-linesの要素が1つ必要になる
3. all-linesの要素を1つ求めるために、read-lineを1回実行する
4. read-line結果を()で括る
5. ()で括ったread-line結果をdisplayする

と、実際に大きなリストが作られることはなく、1行ずつ処理されるのだ。Marvelous!

当たり前の話ではあるが、本質的に後回しにできない処理は遅延評価でも改善できない。例えば全ての入力行をクイックソートして出力する場合、どう足掻いても、まずは全ての行を読むしかない。