SICP 3.5.4 Streams and Delayed Evaluation - プログラミング再入門

ノート

ストリームと遅延評価。

The interpreter's ability to deal with such an implicit definition depends on the delay that is incorporated into cons-stream.

implicitだと行っているのはintとしては明示的に再帰的な定義になっているが、評価されるタイミングはcons-streamが展開されてdelayに渡される事が表には見えていない事を意味している様に思われる。確かにdelayが入ってここの部分は直ぐには評価されない様になっていないと、この定義は成り立たない。

時にはcons-streamに隠されたdelay以外にも明示的にdelayを使う必要がある事がある。
integralの中で暗黙のdelayで定義されているのは良いが、integralともう一つの関数との組み合わせにフィードバックループがある場合、delayを明示的に使う必要がある。

Racketのstreamは使わずに以下の定義と、

#lang racket
(define-syntax cons-stream
  (syntax-rules ()
    ((cons-stream a b)
     (cons a (delay b)))))

(define stream-null? null?)
(define the-empty-stream null)

テキストのコードのみで動作確認

> (stream-ref (solve (lambda (y) y) 1 0.001) 1000)
2.716923932235896
>

Exercise 3.77

第１引数をdeleyed-integrantとして、最初に使用する前にforceするのは明白。
ただ、それだけだとforceしたものをまたforceしているとエラーになる。
確かに再帰でintegralを呼ぶ時の第１引数はstream-cdrを評価してから渡る。stream-cdrは２番目の要素をforceするので、その先でまたforceしてしまう。なので渡す手前でdelayする。

(define (integral delayed-integrand initial-value dt)
  (cons-stream initial-value
               (let ((integrand (force delayed-integrand)))
                 (if (stream-null? integrand)
                     the-empty-stream
                     (integral (delay (stream-cdr integrand))
                               (+ (* dt (stream-car integrand))
                                  initial-value)
                               dt)))))

動作確認

> (stream-ref (solve (lambda (y) y) 1 0.001) 1000)
2.716923932235896
>

Exercise 3.78

ダイヤグラムをそのままコードに落とし込むと

(define (solve-2nd a b dt y0 dy0)
  (define y (integral (delay dy) y0 dt))
  (define dy (integral (delay ddy) dy0 dt))
  (define ddy (add-streams (scale-stream dy a)
                           (scale-stream y b)))
  y)

動作の確認が難しい。とりあえず拾って来たデータで動く事は確認できた。

> (stream-ref (solve-2nd 5 -4 0.001 1 1) 2000)
7.381675653556238
>

何か分かりやすい値か式になるサンプルがあると良いのだが。

Exercise 3.79

$\frac{d^2y}{dt^2}-a\frac{dy}{dt}-by=0$ すなわち $\frac{d^2y}{dt^2}=a\frac{dy}{dt}+by$ の右辺をfと言う関数で一般化する。

(define (solve-2nd f dt y0 dy0)
  (define y (integral (delay dy) y0 dt))
  (define dy (integral (delay ddy) dy0 dt))
  (define ddy (stream-map f dy y))
  y)

ここでfはdyとyを引数に取る関数。

> (stream-ref (solve-2nd (lambda (dy y) (+ (* 5 dy) (* -4 y))) 0.001 1 1) 2000)
7.381675653556238
>

Exercise 3.80

(define (RLC R L C dt)
  (lambda (vC0 iL0)
    (define vC (integral (delay dvC) vC0 dt)) 
    (define iL (integral (delay diL) iL0 dt))
    (define dvC (scale-stream iL (/ -1 C)))
    (define diL (add-streams (scale-stream vC (/ 1 L))
                             (scale-stream iL (/ (- R) L))))
    (stream-map (lambda (vCn iLn) (cons vCn iLn)) vC iL)))

各信号のdefineの順番が実は少しややこしい。中でforceしてくれるのはintegralなのでdelayして渡せるのはintegral。なのでintegralを最初に定義して、そこに必要なパラメータの定義をその下に書くと良さそう。
動作確認

||
数値が正しいかは分からないが、振動しながら減衰する様子が少し分かる。
>|scheme|
> (stream->list ((RLC 1 1 0.2 0.1) 10 0) 40)
'((10 . 0)
  (10 . 1.0)
  (9.5 . 1.9)
  (8.55 . 2.66)
  (7.220000000000001 . 3.249)
  (5.5955 . 3.6461)
  (3.77245 . 3.84104)
  (1.8519299999999999 . 3.834181)
  (-0.0651605000000004 . 3.6359559)
  (-1.8831384500000004 . 3.2658442599999997)
  (-3.5160605800000004 . 2.750945989)
  (-4.8915335745 . 2.1242453320999997)
  (-5.95365624055 . 1.4226674414399998)
  (-6.66498996127 . 0.6850350732409998)
  (-7.0075074978905 . -0.049967430210100305)
  (-6.982523782785449 . -0.7457214369781403)
  (-6.609663064296379 . -1.3694016715588713)
  (-5.924962228516943 . -1.893427810832622)
  (-4.978248323100632 . -2.296581252601054)
  (-3.829957696800105 . -2.5647479596510117)
  (-2.547583716974599 . -2.691268933365921)
  (-1.2019492502916387 . -2.676900411726789)
  (0.136500955571756 . -2.529405295583274)
  (1.401203603363393 . -2.262814670467771)
  (2.5326109385972786 . -1.8964128430846547)
  (3.480817360139606 . -1.4535104649164614)
  (4.2075725925978364 . -0.9600776824108546)
  (4.687611433803264 . -0.4433126549099854)
  (4.909267761258256 . 0.06977975396133962)
  (4.874377884277586 . 0.5537285546910313)
  (4.59751360693207 . 0.9857934876496868)
  (4.104616863107227 . 1.3469654995779252)
  (3.4311341133182642 . 1.6227306359308553)
  (2.6197687953528366 . 1.8035709836695961)
  (1.7179833035180385 . 1.8851907648379203)
  (0.7753879210990783 . 1.868470018705932)
  (-0.15884708825388782 . 1.7591618089452465)
  (-1.0384279927265112 . 1.567360919225333)
  (-1.8221084523391777 . 1.3067820280301485)
  (-2.475499466354252 . 0.9938929799932159))
>

Normal-order evaluation

新しいintegralは引数の一つをdelayさせないといけない。integralを使う場合にはこの事を常に覚えておかなければならない。関数、引数によってdelayを使ったり使わなかったりと言う状況は不便。
全ての引数を自動的にdelayさせる方法も取れる。これを正規順序評価（normal-order evaluation）と言い、substitution modelに相当する。最外簡約、つまり引数の評価より前に関数の評価を行う。
ストリームを扱う様なプログラムでは自然でエレガントなプログラムが書けるが、イベント、代入、書き換え可能なデータ、I/Oを伴うプログラムには向かない。これら二つの世界が混ざっていると大混乱を起こす。これらの二つの世界を一つの言語で扱う方法は研究中。