はじめに
Scheme ではデータ構造としてリストを扱いますが、リストを処理していくために通常は全要素を持つリストをまず用意しなければいけません。さらにリストの全要素について処理を完了しなければ次の処理ができないという問題が発生します。この問題はリストが大きくなるにつれて深刻になっていきます。これを解決するための手段の１つとして「遅延リスト」を考え、その応用として「無限ストリーム」を導入します。
「ストリーム」って何？
身近な例で存在するものと言えば「整数列」です。ご存知のとおり整数の列は
1 2 3 4 5 6 7 ...
これですね。整数は無限に存在しますが、プログラムで扱う場合、「無限に用意する」のは不可能です。そこで実際にコードを書く場合は制限を設けることで、この問題を避けています。具体的には、
このプログラムで扱う整数は、1 から 10000 まで。
などです。このようなデータの並びを「ストリーム」と呼びます。先程示した整数列は「整数が有限個あるストリーム」と言えます。ファイルなどもストリームの一種です。なお、本稿では Scheme を扱いますので、ストリームはリストとして表現します。
「無限ストリーム」とは？
無限ストリームとは有限個ではないストリームの事です。ただし無限に続くものをコンピュータで表現するのは不可能であると言いました。コンピュータのリソースは有限ですから、無限個あるものをそのまま表現することは不可能なはずです。では、無限ストリームを実現するためにはどうすれば良いのでしょうか？
考え方
無限ストリームでは、各要素の値を最初から用意するのではなく、必要となった時点で値を用意します。もっ具体的に言うと、評価（つまり値の決定）を未来に遅延させています。すべての値が予め用意されている必要はなく、その値が必要になったときに値を用意すれば良いのです。
私たち人間が整数を考える時も、プログラムで整数を扱う時も、無限個ある整数をすべて用意することはしませんね？ これとまったく同じ考え方です。無限ストリームを利用するプログラムからすると、その無限ストリームは最初から無限個の値を持っているかのように振る舞います。
Scheme で無限ストリームを作る
無限ストリームを作るには以下の基本的な手続きが 3 つあれば十分です。
(define (stream-car s)
(car s))
(define (stream-cdr s)
(force (cdr s)))
(define-syntax cons-stream
(syntax-rules ()
((_ a b) (cons a (delay b)))))
cons-stream はマクロを使用していますが、やっていることは cons とほぼ同じです。違うのは2つ目の値の評価を delay 手続きを使って遅延させています。
stream-cdr も cdr とほぼ同じですが、force 手続きを使用して「遅延させていた評価」を直ちに評価して値を確定させます。
stream-car は car とまったく同じ動作をします。別名を与えているだけです。
実際に無限ストリームを作ってみる
まずはじめに、整数の無限ストリームを作ってみます。
(define (integer-starting-from n)
(cons-stream n (integer-starting-from (+ n 1))))
(define integer-infinite-stream (integer-starting-from 1))
このように書くことができます。普通に実装したのでは integer-starting-from は自身を再帰呼び出ししていて、終了条件も書いていないため、無限ループとなり異常終了してしまいますが、無限ストリームならば遅延評価を用いているので問題ありません。
integer-infinite-stream を評価して中身を見てみましょう。
gosh> integer-infinite-stream
(1 . #<promise 0x700000786aa0>)
1 つ目の要素は、「1」です。2 つ目の要素は #<promise XXXXX> となっていますが、これは評価をまだ遅延している事を表しています。(「XXXXX」の部分の値は気にしなくて大丈夫です)
それぞれ値を取り出してみましょう。
gosh> (stream-car integer-infinite-stream)
1
1 つ目の要素を取り出しました。stream-car は car の別名ですし、これは特に問題ないですね。
再度 integer-infinite-stream を見てみます。
gosh> integer-infinite-stream
(1 . #<promise 0x700000786aa0>)
特に何も変化はありません。
次は stream-cdr を使って、最初の要素以外を取り出してみます。
gosh> (stream-cdr integer-infinite-stream)
(2 . #<promise 0x700000a1a2e0>)
strean-cdr したので、今度は 2 が先頭の要素になりました。delay 手続きで遅延されていた評価が force 手続きによって評価され 2 という値になりました。
もう一度 integer-infinite-stream を評価してみます。
gosh> integer-infinite-stream
(1 . #<promise 0x700000786aa0 (forced)>)
今度は「promise の値「XXXXX」の後ろに「(forced)」が付きました。これが「遅延されていた評価」が評価されたということを表しています。
また、内部的な話になってしまいますが、一度 force されると、以後は値として扱われます。つまり、無限ストリームの値は最初に force する場合に限って値を決定するための処理コストがかかりますが、一度 force されてしまえばで処理コストはかかりません。
無限ストリームを使った数列の例(1)「フィボナッチ数列」
フィボナッチ数列は
1 1 2 3 5 8 13 21 34 55 89 144 ...
このような数列で、次にくる数字は、手前の２つの連続する数字の和になっています。
これを無限ストリームで作ってみます。
(define (fibgen a b)
(cons-stream a (fibgen b (+ a b))))
(define fibonacci-infinite-stream (fibgen 1 1))
fibgen 手続きがフィボナッチ数列を生成する手続きです。
フィボナッチ数列はこのように再帰的に定義できます。
早速、値を取り出してみます。
gosh> (stream-car fibonacci-infinite-stream)
1
gosh> (stream-car (stream-cdr fibonacci-infinite-stream))
1
gosh> (stream-car (stream-cdr (stream-cdr fibonacci-infinite-stream)))
2
gosh> (stream-car (stream-cdr (stream-cdr (stream-cdr fibonacci-infinite-stream))))
3
gosh> (stream-car (stream-cdr (stream-cdr (stream-cdr (stream-cdr fibonacci-infinite-stream)))))
5
gosh> (stream-car (stream-cdr (stream-cdr (stream-cdr (stream-cdr (stream-cdr fibonacci-infinite-stream))))))
8
確かにフィボナッチ数列になっています。stream-cdr をたくさん書かないといけないのは不便なので、無限ストリーム版 stream-ref を用意します。
(define (stream-ref s i)
(if (= i 0)
(stream-car s)
(stream-ref (stream-cdr s) ( - i 1))))
stream-ref を使えば各要素への参照が少し楽になります。
gosh> (stream-ref fibonacci-infinite-stream 0)
1
gosh> (stream-ref fibonacci-infinite-stream 1)
1
gosh> (stream-ref fibonacci-infinite-stream 2)
2
gosh> (stream-ref fibonacci-infinite-stream 3)
3
gosh> (stream-ref fibonacci-infinite-stream 4)
5
gosh> (stream-ref fibonacci-infinite-stream 5)
8
gosh> (stream-ref fibonacci-infinite-stream 6)
13
gosh> (stream-ref fibonacci-infinite-stream 7)
21
gosh> (stream-ref fibonacci-infinite-stream 8)
34
gosh> (stream-ref fibonacci-infinite-stream 9)
55
gosh> (stream-ref fibonacci-infinite-stream 10)
89
さらにもっと使い勝手を良くするために連続した整数リストを作る enumerate-interval 手続きを導入します。この手続きは普通のリストを作ります。
(define (enumerate-interval low high)
(if (> low high)
nil
(cons low (enumerate-interval (+ low 1) high))))
この手続きを使って、より Scheme 言語らしく値を表示することができます。
はじめの 20 個を表示してみます。
gosh> (map (lambda (i) (stream-ref fibonacci-infinite-stream i)) (enumerate-interval 0 19))
(1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765)
無限ストリームを使った数列の例(2)「素数列」
次は素数列を無限ストリームで作ってみます。
まず始めに無限ストリーム版のフィルター手続きを用意します。
(define (stream-filter pred s)
(if (pred (stream-car s))
(cons-stream (stream-car s)
(stream-filter pred (stream-cdr s)))
(stream-filter pred (stream-cdr s))))
stream-filter を使って 7 の倍数の整数列を作ってみます。
(ここでは stream-filter 手続きの使い方の例として紹介しますが、7 の倍数の整数列は stream-filter 手続きを使わず、もっと簡単に作る方法があります。)
gosh> (define sevens (stream-filter (lambda (x) (= (remainder x 7) 0)) integer-infinite-stream))
sevens
gosh> (map (lambda (i) (stream-ref sevens i)) (enumerate-interval 0 9))
(7 14 21 28 35 42 49 56 63 70)
整数の無限ストリームについて、7 で割った時に余りがゼロになるもの(つまり 7 の倍数)をフィルターすることで、7 の倍数の整数列を作ることができます。
エラトステネスの篩
整数列から素数列を生成する方法として「エラトステネスの篩」という有名な方法があります。考え方は単純です。
・1 は素数ではないので除外して、2 から始めます。
・最初の値は 2 です。2 だけ残して、2 の倍数をすべて消しこみます。
・残っている次の最小の値は 3 です。同様に 3 だけ残して、3 の倍数をすべて消しこみます。
・4 は 2 の倍数なのでもう消えています。
・残っている次の最小の値は 5 です。同様に 5 だけ残して、5 の倍数をすべて消しこみます。
・6 は 2 の倍数なのでもう消えています。
・次は 7 です。同様に 7 だけ残して、7 の倍数をすべて消しこみます。
・8 は 2 の倍数なのでもう消えています。
・9 は 3 の倍数なのでもう消えています。
・10 は 2 の倍数なのでもう消えています。
・次は 11 です。同様に 11 だけ残して、11 の倍数をすべて消しこみます。
という操作を永遠にやっていくと、素数だけが残ります。この「消し込み」に先程紹介した stream-filter 手続きを使います。
(define (divisible? x y)
(= (remainder x y) 0))
(define (sieve s)
(cons-stream
(stream-car s)
(sieve (stream-filter
(lambda (x) (not (divisible? x (stream-car s))))
(stream-cdr s)))))
(define primes (sieve (integer-starting-from 2)))
最初の素数を 20 個を表示してみます。
gosh> (map (lambda (i) (stream-ref primes i)) (enumerate-interval 0 19))
(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71)
おわりに
今回は無限ストリームを紹介し、フィボナッチ数列や素数列などの数列を実際に作ってみました。いろいろな数列を作って試してみたり、どんな事に無限ストリームが使えそうかを考えてみるのも面白いと思います。
今回は無限ストリームを導入することで、全要素を用意しなければ次の処理が行うことができないという問題は回避できたかも知れません。しかし無限ストリームであっても「無限にあるもの」を表現することは不可能です。具体的には、無限ストリームの各要素を force して値をどんどん確定していくと、手続きの動作はどんどん遅くなっていき、やがて Scheme 処理系もろとも異常終了してしまうでしょう。クリティカルなシステム（業務アプリケーションなど）において無限ストリームを使用するのはリスクでしかありません。とはいえ無限ストリームを使用して学習目的などでプログラムを書くことが無意味かというと、そんなことは決してありません。実用的ではないから無駄であると切り捨ててしまうのは愚かなことだと思います。
課題
もっと本質的な問題として
・無限とはそもそもなにか
・無限は実在するのか、それとも概念なのか
・無限を思考する意味合い
・われわれ人間の脳は「無限」をどのように扱っているか
などについて、数学・物理学・哲学・認知科学や天文学（最新の宇宙論）さらには量子力学などまで様々な分野・観点から「無限」というテーマについて深く考察してみるのも良いかもしれません。
（注意 答えにたどりつくのはとても難しい）
参考文献
計算機プログラムの構造と解釈 3.5節「ストリーム」