まず具体例として、ある整数区間の全ての偶数の和を求める関数sum-evensを実装することを考える。ただでは便宜上、区間内の偶数の和を計算する方法は、それを列挙してひたすら足していく以外の方法は知られていないものとする。この仮定が気になる場合は、prime?という素数を判定する関数を定義して区間内の全ての素数の和を求める関数を考えてもよい。
繰り返しを利用してsum-evnsを実装する方針を取った場合、この関数は次のように定義出来る。
(define (sum-evens a b)
(define (iter count acc)
(cond ((> count b) acc)
((even? count)
(iter (+ count 1) (+ count acc)))
(else (iter (+ count 1) acc))))
(iter a 0))
この定義は少し長いため、map命令のようにリストを直接操作する関数を使う事で、より簡潔に書く方法を考える。この方法では、組み込み関数のfilter関数(下記の使用例参照)を利用する他、accumulateおよびenumerate-interval 関数が次の例を満たすように適切に実装されているものとする。
> (filter odd? (list 1 2 3 4 5)) ;;条件を満たす要素をリストから抽出し、新たなリストを返す。
(1 3 5)
> (accumulate + 0 (list 1 2 3 4 5)) ;; リストの要素を全て足す
15
> (enumerate-interval 2 7) ;; 一つ目の要素から二つ目の要素までの整数のリストを返す。
(2 3 4 5 6 7)
これらの関数を利用すると、sum-evens関数は次のように簡潔に書く事が可能である。
(define (sum-evens2 a b)
(accumulate + 0 (filter even? (enumerate-interval a b))))
このようにリストを直接操作する関数を用いることで、sum-evens関数のように具体的に手続きを書く必要がなく抽象化された操作のみで関数を実装することが可能となる。しかし、残念ながらこちらの実装には大きな問題がある。(sum-evens2 10000 10000000)などを評価することを考えると明らかであるが、この場合はまずenumerate-interval関数の評価が最初に行われるため、約1000万個の整数のリストが作成されることとなる。すなわち、一つ目の繰り返しを利用した実装と比べて、計算の途中に必要なメモリが莫大になり計算が非効率となってしまう。
計算の効率性を担保したまま、抽象化された操作のみで簡潔に関数を実装する方法が、ストリームを利用する方法である。ストリームとはdelayとforceと呼ばれる2つの特殊フォームを利用して実装されている。delayとforceの説明の前に、まず簡単な使い方を見てみることとする。
> (define x (+ 1 2))
> x
3
> (define x (delay (+ 1 2)))
> x
#<promise #<procedure ...>> ;; ...の中に何が表記されるかは場合による
> (force x)
3
1行目と2行目はdelayとforceを利用していないこれまで通りの式であり、xを1+2と定義してからxを評価すると、3が得られている。4行目がdelayを利用した式である。これは1行目とほぼ同じであるが内部にdelayが挟まっており、このようにxを定義してからxを評価すると、1行目とは異なり3が得られず、#<promise ...>というものが得られる。これに対して7行目のようにforce命令を利用すると、3行目と同じく3が得られる。
この例を踏まえた上で、delayがどのような操作を行う特殊フォームであるか説明すると、delayとは式の評価を行わず、将来式の評価を行うという約束(promise)をした遅延オブジェクトと呼ばれるものを返す特殊フォームである。そしてforceがその対となる特殊フォームであり、遅延オブジェクトを引数として取ることでその約束を果たし、式の評価を行う。このような評価方法を、遅延評価と呼ぶ。ストリームとは、この遅延評価を用いて定義された遅延リストである。たとえば、(list 1 2 3)をストリームとして表現したい場合には、次のxのように定義することができる。
> (define x (cons 1 (delay (cons 2 (delay (cons 3 (delay '())))))))
> x
(1. #<promise #<procedure ...>>)
> (car x)
1
> (car (force (cdr x)))
2
定義されたxでは、2つ目以降の要素はすぐには評価されず、forceを用いることで初めて評価されることとなり、定義した段階では全ての要素が評価されていないという点が重要なポイントである。このことから、上記のsum-evens2の例において、enumerate-intervalをストリームを利用して書き換え、整数のリストをいきなり全部作らず必要に応じて評価することにすれば、非効率な計算を行わずにすむことが想像できるのではないかと思う。
上記ではストリームの具体的な内容を解説するためにdelayとforceを直接用いてストリームを定義したが、guileにはストリームを利用するためのライブラリが用意されており、今後はそちらを利用して説明を行う。(そのため、delayとforceを明示的に利用する必要はない。) ライブラリの基本的な使い方は下記の通りである。
> (import (rnrs) (srfi :41)) ;;ライブラリのインポート
> (define p (stream-cons 1 2)) ;;ストリームとしてペアを作成
> p
#<stream ...>
> (stream-car p) ;;carのストリーム版
1
> (stream-cdr p) ;;cdrのストリーム版
2
> (define l (list->stream (list 1 2 3))) ;;リストをストリームに変更
こちらで定義されているストリームに対しては通常のcarやcdrを利用することはできないので注意されたい。これを利用して、enumerate-intervalのストリーム版を定義すると、次のようになる。
(define (stream-enumerate-interval low high)
(if (> low high)
stream-null
(stream-cons low (stream-enumerate-interval (+ low 1) high))))
ストリームを利用すると、与えられた範囲の中で２番目に小さい偶数なども計算の無駄なく得ることが可能である。(stream-filterはライブラリの中で定義されており実装する必要はない)。また、stream-ref関数を利用すると、ストリームにおいて引数として与えたn番目の要素を取得することが出来る。
> (stream-car
> (stream-cdr
> (stream-filter even? (stream-enumerate-interval 10000 10000000))))
10002
> (stream-ref (stream-filter even? (stream-enumerate-interval 10000 10000000)) 10) ;;ストリームの中で10番目の要素を取得する。ただし、先頭の要素は0番目とする。
10020
ストリームでは2つ目以降の要素は必要にならない限り評価されないことから、無限の要素を持つストリームを作成することが可能である。たとえば、正の整数のストリームは次のように定義することが出来る。
(define (integers-starting-from n)
(stream-cons n (integers-starting-from (+ n 1))))
(define integers (integers-starting-from 1))
これを利用すると、たとえば7の倍数のストリームなども次のように定義することが可能である。
> (define (divisible? x y) (= (remainder x y) 0))
> (define sevens
> (stream-filter (lambda (x) (divisible? x 7)) integers))
> (stream-car sevens)
7
> (stream-ref sevens 2)
21
無限ストリームを利用して、i <= j であるような全ての正の自然数のペアを表現するストリームを定義することを考える。一般化すると、2つのストリームSとTが与えられており、(S0, T0), (S0, T1), (S1, T1), (S0, T2), (S1, T2), (S2, T2), ..., というペアを全て含むストリームを(pairs S T)として、pairsを定義することを考える。この時、全ての整数のペアは(pairs integers integers)と書くことができる。
ここでは(pairs S T)は、1. (S0, T0)、2. S0を一つ目に持つ(S0, T0)以外の全てのpair、3. 1でも2でもない残りのpair、という3つの構成要素から成り立っており、これを全て連結させることでpairsが表現されると考えると、pairsは次のように定義すれば良さそうである。(stream-appendはライブラリの中で定義されており実装する必要はない。)
(define (pairs s t)
(stream-cons
(list (stream-car s) (stream-car t)) ;; 1つ目の構成要素
(stream-append
(stream-map (lambda (x) (list (stream-car s) x))
(stream-cdr t)) ;;2つ目の構成要素
(pairs (stream-cdr s) (stream-cdr t))))) ;;3つ目の構成要素、再帰的に定義する。
このように定義したpairsを使うと、次の結果が得られる。
> (define int_pairs (pairs integers integers))
> (stream-ref int_pairs 0)
(1 1)
> (stream-ref int_pairs 1)
(1 2)
> (stream-ref int_pairs 2)
(1 3)
> (stream-ref int_pairs 3)
(1 4)
> (stream-ref int_pairs 4)
(1 5)
どうやら得られたストリームは期待に反して、pairの最初の要素が1の場合のみを返しそれ以外の要素が返ってこない。これは先ほどの構成部分でいうならば、3番目の構成要素の部分が全く返ってきていないことを意味している。これでは、ペアの無限ストリームを表現しているとはいえず、どこかに不適切な箇所が含まれていると考えられる。
答えをいうと、不適切な箇所は2番目の要素と3番目の要素を連結する際にstream-appendを利用した点にある。appendは1つ目のリストの後ろの2つ目のリストを連結する関数であり、stream-appendもストリームに対してそのような動作をする。しかし今回の場合は1つ目のストリームは無限ストリームであるため終わることがなく、したがって2つ目のストリームの要素にアクセスすることはない。よってストリームを連結させる際に、stream-appendではなく、ストリームが無限であっても1つ目のストリームにも2つ目のストリームにもアクセスされる事が保証される関数を利用すれば良いと考えられる。その操作を行う関数が次のinterleave関数であり、それを用いるとpairsは次のように定義される。
(define (interleave s1 s2)
(if (stream-null? s1)
s2
(stream-cons (stream-car s1)
(interleave s2 (stream-cdr s1)))))
(define (pairs s t)
(stream-cons
(list (stream-car s) (stream-car t))
(interleave ;;ここだけ先ほどのプログラムから変更する。
(stream-map (lambda (x) (list (stream-car s) x))
(stream-cdr t))
(pairs (stream-cdr s) (stream-cdr t)))))
再定義したpairsを用いて先ほどの評価を行うと、次の結果が得られる。
> (define int_pairs (pairs integers integers))
> (stream-ref int_pairs 0)
(1 1)
> (stream-ref int_pairs 1)
(1 2)
> (stream-ref int_pairs 2)
(2 2)
> (stream-ref int_pairs 3)
(1 3)
> (stream-ref int_pairs 4)
(2 3)
このように、pairの最初の要素が1以外のpairも正しく返ってきており、期待した結果が得られていることがわかる。