落ちてしまいます

質問

無限ストリームなのですが、

(define (stream-car stream) (car stream))

(define (stream-cdr stream) (force (cdr stream)))

(define (cons-stream a b) (cons a (delay b)))

(define (integers-starting-from n)
(cons-stream n (integers-starting-from (+ n 1))))

(define integers (integers-starting-from 1))　　　　　

(define (stream-ref s n)
(if (= n 0)
(stream-car s)
(stream-ref (stream-cdr s) (- n 1))))

(define (divisible? x y) (= (remainder x y) 0))

(define (sieve stream)
(cons-stream
(stream-car stream)
(sieve (stream-filter
(lambda (x)
(not (divisible? x (stream-car stream))))
(stream-cdr stream)))))

(define primes (sieve (integers-starting-from 2)))

(stream-ref primes 10)

integersを定義する段階で落ちてしまうようです。どうも遅延評価がうまくいってないようです。どうしたらよいでしょうか？どなたか助けてください。

回答No.1

cametan_42 · ベストアンサー

「計算機プログラムの構造と解釈」でしょ?

前も誰か投稿してたと思うんですけど、これって「激ムズの」教科書なんで、ここで訊かない方が良いですよ(笑)。SICPで検索すれば「勉強会」やってる専門サイトがいくつか見つかると思うんで、そっちで尋ねた方が良いです。
少なくとも、Schemeやこの教科書使ってる人ってのは「偏差値高めの」大学でキチンとした「計算機工学」を学んだ/学んでる人たちが多いんで、質問投稿するにせよ、場所を絞った方が良い、と思います。
しかも、投稿のコード見ると、まずは、

stream-filter

と言う手続きが「未定義」なんですよね。従って、仮にScheme持っててもこれじゃあ走りません。
「計算機プログラムの構造と解釈」見る限り、次の手続きと変数を定義しとかなきゃならないのです。

(define (stream-filter pred stream)
(cond ((stream-null? stream) the-empty-stream)
((pred (stream-car stream))
(cons-stream (stream-car stream)
(stream-filter pred
(stream-cdr stream))))
(else (stream-filter pred (stream-cdr stream)))))

(define (stream-null? string) (null? string))

(define the-empty-stream '())

でしょ?これ抜けてる以上、上の質問は不完全です。これも「教科書」共有してないと指摘出来ません。

さて、投稿コードを見ると、次のコードがおかしいのです。

(define (cons-stream a b) (cons a (delay b)))

これが問題です。と言うかこれが原因ですね。
「計算機プログラムの構造と解釈」見てみれば分かりますが、これってご自分で書いたんでしょ?と言うか、当該の教科書には「ハッキリとした」定義書いてないんですよね(笑)。
p.189辺りの下に次のような事が書かれています。

stream-carとstream-cdrは手続きとして定義出来るが、cons-streamは「特殊形式でなければならない」。

上のnerudaさん自作のコードは「手続き」です。従って、この条件を満たしていません。
ついでに、この議題は実はもっと先のp.243以降に持ち越されます。従って、「無限ストリーム」と言うお題ではここのコードは「動かせない」のです。

現時点での回避法は、平たく言っちゃうと、「特殊形式」を簡単に定義する……要するに「マクロ」としてcons-streamを設計しちゃう、と言う方法があります。
しかしながら、これはある意味「掟やぶり」で、と言うのも、「計算機プログラムの構造と解釈」ってマトモなマクロ解説、って無いんですよ。
現状のScheme、少なくともR5RSやR6RSは言語仕様としてマクロ持っていますが、「計算機プログラムの構造と解釈」が上梓された当時は、多分R3RSかR4RSの頃で、少なくとも「Appendix」扱いでマクロは正式仕様じゃなかった、んです。ちょっと「マクロの実装方法」に対して、Schemeコミュニティがまだ神経質だった頃に出版された本なんです(だからこそ、「特殊形式」でのstream-consの明確な記述を避けたのでしょう)。
実は今も「Schemeのマクロ実装方法」ってちょっと揉めてるんですけどね(笑)。一応、R5RSの正式なマクロ(なんだけど、これで書く人が少ない・笑)である「パターンマッチング式」のマクロでのstream-consの記述は以下の通り、です。

(define-syntax cons-stream
(syntax-rules ()
((_ a b) (cons a (delay b)))))

これだと引数a、bが「評価される事を」止めます。平たく言うと、マクロcons-stream自身は評価されず、呼び出し元のコード内で、(cons a (delay b))と言う形で「展開される」ようになるんです。
これを組み込んで動作させれば望む結果が得られるでしょう。例えば

> (stream-ref primes 10)
31

のように。

お礼

回答ありがとうございます。おっしゃるとおりSICPです。
stream-filterはコピペしそこなっていました。もうしわけございません。現在研究室ができたばかりなので学生は僕一人で先生と毎週３０P進んでいます、誰にもきけず孤軍奮闘で、なかなかきついです。

stream-carとstream-cdrは手続きとして定義出来るが、cons-streamは「特殊形式でなければならない」。

そうですね、自分でもおかしいと思いながらなんとか書いてみたとこです。

回答者様のおっしゃるようにしたらきちんと動きました。本当にありがとうございました。