Gauche の util.stream の stream-delay はなぜあるのか、どういう場合にどのように使うものなのか？

All problems in computer science can be solved by another level of indirection. (David John Wheeler)
But that usually will create another problem.

これは、デビッド・ホイーラーさん*1（wikipedia:デビッド・ホイーラー）による格言ですが、遅延データ構造はインダイレクション（定訳は無い気もしますが「間接化」でしょうか）による御利益が最もよくわかるものの一つではないでしょうか。

Gauche の util.stream（ http://practical-scheme.net/gauche/man/?l=jp&p=util.stream ）では stream-delay というマクロが提供されています。このライブラリは SRFI-40（ http://srfi.schemers.org/srfi-40/srfi-40.html ）準拠ですから詳細はそちらを読めば全て書いてありますが、なぜ用意されていて、どういう場合にどう使うものか、ざっとまとめておく意味はあるように思いますので、以下にそれを書きます。

リファレンスマニュアルの記述

Gauche のリファレンスマニュアルには次のようにあります。

Macro: stream-delay expr

　　　　［SRFI-40］ exprの遅延形式であるストリームを返します。

　　　　原則として、ストリームを生成する関数はすべからく結果を stream-delayでラップすべきです。

「結果を」とありますが、関数の返す値が常に delay されたリスト、すなわちストリームであるべき、ということであれば、ストリームの構成子である stream-cons（と、stream-null ）の返す値がそうなっていれば良いはずで、実装が表に出てしまっているように見える stream-delay がなぜ存在するのか、いまいちわかりにくく感じられるかもしれません。

実際にはこれは「ストリームを生成する関数」の「結果だけ」ではなく、それ自体の振舞いに関係していて、SRFI-40 を実装したライブラリには必須のマクロです。

遅延プリミティブ

まず、ここでの議論のための実装のために、以下のような遅延プリミティブを使うこととします。

(define-syntax delay
  (syntax-rules ()
    ((_ val)
      (lambda () val))))

(define (force thunk) (thunk))

全くナイーブに実装した delay と force です。本格的にはメモ化とかを実装すべきでしょうが、ここでの議論にはこれで十分です。

oddストリーム

SRFI-40 中では、ストリームを実装する戦略について、oddとevenの2通りの戦略がある、と分類しています。oddとevenという名前の理由については後で説明します。SICP の本文中で示されている（日本語版では p. 189 にある）実装はoddで、SRFI-40 のストリームはevenです。oddストリームの実装は次のようになります（ここで、単に cons car cdr とあるのは、実装基盤のScheme処理系のそれを使うという意味になります）。SRFI-40 中の解説では cons1 などのように "1" というサフィックスが付いています。

(define-syntax odd-cons
  (syntax-rules ()
    ((_ elem strm)
      (cons elem (delay strm)))))

(define (odd-car strm)
  (car strm))

(define (odd-cdr strm)
  (force (cdr strm)))

見てわかるように、cdr-partだけを遅延させています。force / delay はそれぞれ1箇所に入り、実装の詳細は綺麗に掩蔽されていて、一見エレガントなように見えます。

しかし実際には問題があります。odd-cons はマクロですので、それ自体ではcar-partにあたる引数 elem を評価しませんが、展開結果に cons が直接あり、その引数として直接 elem を渡してしまっていますから、結果として odd-cons があると、そこで car-part の実引数は評価されてしまいます。これは「cons should not evaluate its arguments」という、遅延ストリームの基本に反しています。

わざとらしいですが、簡単な例で示します。

(define (my-take n strm)
  (if (= n 0)
      '()
      (cons (odd-car strm) (my-take (- n 1) (odd-cdr strm)))))

(define (stream-from-n n)
  (print n)
  (odd-cons n (stream-from-n (+ n 1))))

(print (my-take 4 (stream-from-n 0)))

実行すると次のように出力されます。

$ gosh sample-odd.scm
0
1
2
3
4
(0 1 2 3)

ここで my-take が odd-cons でストリームを作っていれば問題は無いわけですが、このように普通の cons でリストを作ろうとすると「その中身にアクセスされることはないが、odd-cdr によってforceされてしまうconsセル」は作ってしまうため、そのconsセルのcar-partに相当する評価は起きてしまいます。SRFI中では、ある種の off-by-one error（ http://catb.org/jargon/html/O/off-by-one-error.html ）だ、と言っています。

ストリームがこのような「oddストリーム」であるため、SICPの本文中のコードには、陽に delay を使っているものがあり、なぜそうしなければならないかという練習問題になっています。

evenストリーム

SRFI-40 では、以上のようなoddストリームの問題が解決された手法として、evenストリームというものが示されています（他にもう一つの考え方としては、cdr-part だけでなく car-part も遅延させる、という方法もあると考えられます。Haskellなどの、任意の値が遅延されるスタイルに近いのはそちらとも言えます）。

evenストリームの実装を示します。SRFI-40 中の解説では cons2 などのように "2" というサフィックスが付いています。

(define-syntax even-cons
  (syntax-rules ()
    ((_ elem strm)
      (delay (cons elem strm)))))

(define (even-car strm)
  (car (force strm)))

(define (even-cdr strm)
  (cdr (force strm)))

こちらでは、even-cons の展開結果の最上位に delay がありますから、consセルに含まれる要素（consセルが要素として指すもの）ではなく、consセル自身が遅延されたものになっています。その代わり、carを取るにもcdrを取るにも、まず force する必要があるように、force / delay があらゆる場所に必要になっています。言い換えると、このモデルは、oddストリームからバグを除いたという良い特性の代わりに、掩蔽が綺麗にできないものになっている、ということになります（ここでは議論しませんが、実用的な実装では force / delay のメモ化も重要になるでしょう）。

ここで、mapについて考えてみます。evenストリームによるmapの実装は次のようになります。

(define (even-map f strm)
  (delay (force
    (if (even-null? strm)
      even-null
      (even-cons
        (f (even-car strm))
        (even-map f (even-cdr strm)))))))

「 (delay (force 」とあるのは一見無意味なように見えます、が、無意味ではなく、「evenストリームとして正しい」mapは、このようになっている必要があります。以下でそれを説明します。

evenストリームにおける even-cons の定義から、その cdr-part である strm は、even-cons の時点では評価されず、後でforceされた時点で初めて評価される、ということがわかります。evenストリームにおいては、他の「ストリームを受け取り、そのストリームに何かをして返す」というような関数では全て原則として同様に、引数として渡されたリストの評価は、その関数が返した値がforceされるまで遅延されなければならない、ということになります。

even-map のコードを見ればあきらかと思いますが、もし「 (delay (force 」が無ければ、渡されたストリームは even-null? によってforceされ評価されてしまいますから、このように全体が遅延されるように囲ってやる必要があるわけです。

Gauche の util.stream など、SRFI-40 の実装では明示的なforceが要らないようになっているので、このコードにおける delay の側だけが stream-delay として残るということになるわけですが、それがなぜ要るかという理由は以上のようになります。

名前について

oddとevenという名前は、oddストリームの挙動は少し変だ（oddだ）ということにも掛けられていますが、SRFI-41（ http://srfi.schemers.org/srfi-41/srfi-41.html ）にわかりやすい表現があります。

すなわち、oddストリームのその実際の構造は次のようになってます。

(cons 1 (delay (cons 2 (delay (cons 3 (delay '()))))))

ここで、終端されているリストであれば、構成子 {delay, cons, '()} の数が、常に奇数（odd number）個になるはずです。

一方、evenストリームは、その前にもう1個 delay が付いて、

(delay (cons 1 (delay (cons 2 (delay (cons 3 (delay '())))))))

のようになり、常に偶数（even number）個になるはずだ、ということから、それぞれの名前となっています。

SRFI-41 との関係

（SRFI-41 をそんなに読み込めてないのですが）SRFI-40 では、以上のように「実装が掩蔽し切れないdelay」について、ユーザにはプリミティブである stream-delay のみを提供するというスタイルとしていますが、ユーザの負担が大きいという判断か、SRFI-41 は、より多い機能を提供するものになっているようです。

SRFI-45 と lazy

Gauche のマニュアルに「Delayとforceとlazy」として記述がありますが（ http://practical-scheme.net/gauche/man/?l=jp&p=Delay%E3%81%A8force%E3%81%A8lazy ）、この記事で説明したように「 (delay (force 」を重ねるのは、ある種のスペースリークとも言えますので、それを潰したようなプリミティブが lazy で SRFI-45 で議論されています（ http://srfi.schemers.org/srfi-45/srfi-45.html ）。

*1:ブロックソートにおける「BW変換」の W の由来であり、古いコンピュータに詳しい人であれば Wheeler Jump の名も出てくるでしょう。