tag:blogger.com,1999:blog-82866066703386927912024-03-13T01:28:26.776-07:00weima learns to programmy attempt to do the exercises in sicp.weimahttp://www.blogger.com/profile/13250647442722796831noreply@blogger.comBlogger215125tag:blogger.com,1999:blog-8286606670338692791.post-16925951256782710502011-01-06T17:42:00.000-08:002011-01-06T17:41:29.754-08:00sicp exercise 3.82<span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; Exercise 3.82. Redo exercise 3.5 on Monte Carlo integration in terms of streams. The stream version of estimate-integral will not have an argument telling how many trials to perform. Instead, it will produce a stream of estimates based on successively more trials.</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; get-random-stream is a procedure which generates a stream of random pairs of (x,y) which lie within x1 y1 x2 y2</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (estimate-integral integral x1 x2 y1 y2)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (define input (get-random-stream x1 x2 y1 y2))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (define area (abs (* (- x1 x2) (- y1 y2))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (define (iter passed total in-stream)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (let ((x (car (stream-car in-stream)))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (y (cdr (stream-car in-stream))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (if (integral x y)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream (* area (/ (+ passed 1) (+ 1 total)))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (iter (+ 1 passed) (+ 1 total) (stream-cdr in-stream)))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream (* area (/ passed (+ 1 total)))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (iter passed (+ 1 total) (stream-cdr in-stream))))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (iter 0 0 input))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> weimahttp://www.blogger.com/profile/13250647442722796831noreply@blogger.com0tag:blogger.com,1999:blog-8286606670338692791.post-20881577592049246902011-01-06T08:54:00.001-08:002011-01-06T08:54:02.859-08:00sicp exercise 3.81<span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; Exercise 3.81. Exercise 3.6 discussed generalizing the random-number generator to allow one to reset the random-number sequence so as to produce repeatable sequences of ``random'' numbers. Produce a stream formulation of this same generator that operates on an input stream of requests to generate a new random number or to reset the sequence to a specified value and that produces the desired stream of random numbers. Don't use assignment in your solution.</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (display-line str)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (display str)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (newline))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (display-stream str num)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (define (internal index)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (if (> index num) 'printed</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (begin</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (display-line (stream-ref str index))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (internal (+ 1 index)))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (internal 0))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (random-numbers input-stream rand-init)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (define (rand-update n)(+ 10 n))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (let ((command (stream-car input-stream)))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cond ((eq? command 'generate)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (let ((random-number (rand-update rand-init)))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream random-number</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (random-numbers (stream-cdr input-stream) random-number))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> ((and (pair? command) (eq? (car command) 'reset))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (let ((random-number (rand-update (cadr command))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream random-number</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (random-numbers (stream-cdr input-stream) random-number))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (else</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> '()))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> </span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define infinite-input</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream 'generate infinite-input))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display-stream (random-numbers infinite-input 0) 20)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define input</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream 'generate</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream 'generate</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream 'generate</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream (list 'reset 2)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream 'generate</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream 'generate</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream 'generate '()))))))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref (random-numbers input 0) 0))(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref (random-numbers input 0) 1))(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref (random-numbers input 0) 2))(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref (random-numbers input 0) 3))(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref (random-numbers input 0) 4))(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref (random-numbers input 0) 5))(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref (random-numbers input 0) 6))(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;Loading "sicp_prob_03.81.scm"...</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;10</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;20</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;30</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;40</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;50</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;60</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;70</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;80</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;90</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;100</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;110</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;120</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;130</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;140</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;150</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;160</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;170</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;180</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;190</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;200</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;210</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;10</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;20</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;30</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;12</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;22</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;32</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;42</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;... done</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> weimahttp://www.blogger.com/profile/13250647442722796831noreply@blogger.com0tag:blogger.com,1999:blog-8286606670338692791.post-40427619030182410672011-01-04T16:41:00.000-08:002011-01-04T16:40:39.674-08:00sicp exercise 3.80<span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; Exercise 3.80. A series RLC circuit consists of a resistor, a capacitor, and an inductor connected in series, as shown in figure 3.36. If R, L, and C are the resistance, inductance, and capacitance, then the relations between voltage (v) and current (i) for the three components are described by the equations</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <img style="font-family: courier new,monospace;" src="http://mitpress.mit.edu/sicp/full-text/book/ch3-Z-G-55.gif" border="0"><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;;and the circuit connections dictate the relations</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <img style="font-family: courier new,monospace;" src="http://mitpress.mit.edu/sicp/full-text/book/ch3-Z-G-56.gif" border="0"><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;;Combining these equations shows that the state of the circuit (summarized by vC, the voltage across the capacitor, and iL, the current in the inductor) is described by the pair of differential equations</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <img style="font-family: courier new,monospace;" src="http://mitpress.mit.edu/sicp/full-text/book/ch3-Z-G-57.gif" border="0"><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;;The signal-flow diagram representing this system of differential equations is shown in figure 3.37.</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <img style="font-family: courier new,monospace;" src="http://mitpress.mit.edu/sicp/full-text/book/ch3-Z-G-58.gif" border="0"><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;;Figure 3.36: A series RLC circuit.</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <img style="font-family: courier new,monospace;" src="http://mitpress.mit.edu/sicp/full-text/book/ch3-Z-G-59.gif" border="0"><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;;Figure 3.37: A signal-flow diagram for the solution to a series RLC circuit.</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;;Write a procedure RLC that takes as arguments the parameters R, L, and C of the circuit and the time increment dt. In a manner similar to that of the RC procedure of exercise 3.73, RLC should produce a procedure that takes the initial values of the state variables, vC0 and iL0, and produces a pair (using cons) of the streams of states vC and iL. Using RLC, generate the pair of streams that models the behavior of a series RLC circuit with R = 1 ohm, C = 0.2 farad, L = 1 henry, dt = 0.1 second, and initial values iL0 = 0 amps and vC0 = 10 volts.</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (display-line str)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (display str)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (newline))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (display-stream str num)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (define (internal index)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (if (> index num) 'printed</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (begin</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (display-line (stream-ref str index))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (internal (+ 1 index)))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (internal 0))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (display-stream-pair p num)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (define (internal index)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (if (> index num) 'printed</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (begin</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (display-line (list (stream-ref (car p) index) (stream-ref (cdr p) index)))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (internal (+ 1 index)))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (internal 0))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> </span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (scale-stream stream factor)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (stream-map (lambda (x) (* x factor)) stream))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (add-streams s1 s2)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (stream-map + s1 s2))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (integral delayed-integrand initial-value dt)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (define int</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream initial-value</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (let ((integrand (force delayed-integrand)))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (add-streams (scale-stream integrand dt)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> int))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> int)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (RLC R L C dt)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (lambda(vc0 il0)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (define vc (integral (delay dvc) vc0 dt))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (define il (integral (delay dil) il0 dt))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (define dvc (scale-stream il (/ -1 C)))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (define dil (add-streams (scale-stream il (/ (* -1 R) L))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (scale-stream vc (/ 1 L))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons vc il)))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define RLC123 (RLC 1 0.2 1 0.1))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display-stream-pair (RLC123 10 0) 40)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; Output</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;Loading "sicp_prob_03.80.scm"...</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(10 0)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(10 5.)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(9.5 7.5)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(8.75 8.5)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(7.9 8.625)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(7.0375000000000005 8.2625)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(6.211250000000001 7.6499999999999995)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(5.446250000000001 6.930624999999999)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(4.753187500000001 6.1884375)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(4.134343750000001 5.470812500000001)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(3.587262500000001 4.802578125000001)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(3.107004687500001 4.194920312500001)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(2.687512656250001 3.6509625000000008)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(2.322416406250001 3.1692375781250006)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(2.005492648437501 2.7458269921875007)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(1.7309099492187507 2.375659820312501)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(1.4933439671875006 2.0532848847656258)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(1.2880154787109381 1.7733144259765632)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(1.1106840361132817 1.5306649523437508)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(.9576175408789066 1.3206744942285162)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(.825550091456055 1.1391460175537114)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(.7116354897006838 .9823480545048832)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(.6134006842501954 .8469917721027835)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(.528701507039917 .7301962281764895)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(.4556818842222681 .6294488676082033)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(.39273699746144775 .5425653759152357)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(.33848045986992414 .4676511866883417)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(.29171534120109 .40306582327913293)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(.2514087588731767 .34739058224011143)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(.21666970064916558 .29939967055664407)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(.18672973359350117 .2580346856029048)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(.1609262650332107 .222382209598203)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(.1386880440733904 .19165423731570685)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(.11952262034181971 .16517114069454863)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(.10300550627236485 .14234688051818417)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(.08877081822054643 .1226761933952745)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(.07650319888101897 .10572350580791047)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(.06593084830022793 .09111335234446472)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(.05681951306578145 .07852210032234633)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(.04896730303354682 .06767080669406389)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(4.2200222364140436e-2 5.8319054863805356e-2)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;... done</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> weimahttp://www.blogger.com/profile/13250647442722796831noreply@blogger.com1tag:blogger.com,1999:blog-8286606670338692791.post-89097482856661795182011-01-04T16:38:00.000-08:002011-01-04T16:37:22.620-08:00sicp exercise 3.79<span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; Exercise 3.79. Generalize the solve-2nd procedure of exercise 3.78 so that it can be used to solve general second-order differential equations d2 y/dt2 = f(dy/dt, y).</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (integral delayed-integrand initial-value dt)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (define int</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream initial-value</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (let ((integrand (force delayed-integrand)))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (add-streams (scale-stream integrand dt)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> int))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> int)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (solve f y0 dy0 dt)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (define y (integral (delay dy) y0 dt))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (define dy (integral (delay ddy) dy0 dt))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (define ddy (stream-map f y dy))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> y)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> weimahttp://www.blogger.com/profile/13250647442722796831noreply@blogger.com0tag:blogger.com,1999:blog-8286606670338692791.post-11299192859850117052011-01-04T16:37:00.000-08:002011-01-04T16:36:41.375-08:00sicp exercise 3.78<span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; Exercise 3.78. </span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <img style="font-family: courier new,monospace;" src="http://mitpress.mit.edu/sicp/full-text/book/ch3-Z-G-53.gif" border="0"><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;;Figure 3.35: Signal-flow diagram for the solution to a second-order linear differential equation.</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;;Consider the problem of designing a signal-processing system to study the homogeneous second-order linear differential equation</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <img style="font-family: courier new,monospace;" src="http://mitpress.mit.edu/sicp/full-text/book/ch3-Z-G-54.gif" border="0"><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;;The output stream, modeling y, is generated by a network that contains a loop. This is because the value of d2y/dt2 depends upon the values of y and dy/dt and both of these are determined by integrating d2y/dt2. The diagram we would like to encode is shown in figure 3.35. Write a procedure solve-2nd that takes as arguments the constants a, b, and dt and the initial values y0 and dy0 for y and dy/dt and generates the stream of successive values of y.</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (display-line str)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (display str)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (newline))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (display-stream str num)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (define (internal index)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (if (> index num) 'printed</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (begin</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (display-line (stream-ref str index))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (internal (+ 1 index)))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (internal 0))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (scale-stream stream factor)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (stream-map (lambda (x) (* x factor)) stream))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (add-streams s1 s2)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (stream-map + s1 s2))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (integral delayed-integrand initial-value dt)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (define int</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream initial-value</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (let ((integrand (force delayed-integrand)))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (add-streams (scale-stream integrand dt)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> int))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> int)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (solve-2nd a b dt y0 dy0)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (define y (integral (delay dy) y0 dt))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (define dy (integral (delay ddy) dy0 dt))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (define ddy (add-streams (scale-stream dy a)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (scale-stream y b)))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> y)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> weimahttp://www.blogger.com/profile/13250647442722796831noreply@blogger.com0tag:blogger.com,1999:blog-8286606670338692791.post-13063823929924042182011-01-04T16:36:00.000-08:002011-01-04T16:35:56.960-08:00sicp exercise 3.77<span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; Exercise 3.77. The integral procedure used above was analogous to the ``implicit'' definition of the infinite stream of integers in section 3.5.2. Alternatively, we can give a definition of integral that is more like integers-starting-from (also in section 3.5.2):</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(define (integral integrand initial-value dt)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">; (cons-stream initial-value</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">; (if (stream-null? integrand)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">; the-empty-stream</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">; (integral (stream-cdr integrand)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">; (+ (* dt (stream-car integrand))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">; initial-value)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">; dt))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;When used in systems with loops, this procedure has the same problem as does our original version of integral. Modify the procedure so that it expects the integrand as a delayed argument and hence can be used in the solve procedure shown above.</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (add-streams s1 s2)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (stream-map + s1 s2))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (scale-stream stream factor)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (stream-map (lambda (x) (* x factor)) stream))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (integral delayed-integrand initial-value dt)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream initial-value</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (let ((integrand (force delayed-integrand)))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (if (stream-null? integrand)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> the-empty-stream</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (integral (delay (stream-cdr integrand))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (+ (* dt (stream-car integrand))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> initial-value)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> dt)))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (solve f y0 dt)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (define y (integral (delay dy) y0 dt))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (define dy (stream-map f y))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> y)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref (solve (lambda (y) y) 1 0.001) 1000))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> weimahttp://www.blogger.com/profile/13250647442722796831noreply@blogger.com0tag:blogger.com,1999:blog-8286606670338692791.post-13682310234050425482011-01-02T15:25:00.000-08:002011-01-02T15:24:31.390-08:00sicp exercise 3.76<span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; Exercise 3.76. Eva Lu Ator has a criticism of Louis's approach in exercise 3.75. The program he wrote is not modular, because it intermixes the operation of smoothing with the zero-crossing extraction. For example, the extractor should not have to be changed if Alyssa finds a better way to condition her input signal. Help Louis by writing a procedure smooth that takes a stream as input and produces a stream in which each element is the average of two successive input stream elements. Then use smooth as a component to implement the zero-crossing detector in a more modular style.</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (display-line str)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (display str)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (newline))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (display-stream str num)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (define (internal index)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (if (> index num) 'printed</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (begin</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (display-line (stream-ref str index))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (internal (+ 1 index)))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (internal 0))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (make-zero-crossings input-stream last-value)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (let ((avpt (/ (+ (stream-car input-stream) last-value) 2)))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream (sign-change-detector avpt last-value)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (make-zero-crossings (stream-cdr input-stream)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> avpt))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (avg x y)(/ (+ x y) 2))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (smooth s)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (define (iter x y str)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream (avg x y)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (iter y (stream-car str) (stream-cdr str))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (iter (stream-car s)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (stream-car (stream-cdr s))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (stream-cdr (stream-cdr s))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (integers-from-n n)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream n (integers-from-n (+ 1 n))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define integers (integers-from-n 0))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (make-zero-crossings input-stream last-value)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (sign-change-detector (stream-car input-stream) last-value)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (make-zero-crossings (stream-cdr input-stream)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (stream-car input-stream))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define zero-crossings (make-zero-crossings (smooth (cons-stream 0 sense-data)) 0))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> weimahttp://www.blogger.com/profile/13250647442722796831noreply@blogger.com0tag:blogger.com,1999:blog-8286606670338692791.post-4721472252757080152011-01-02T14:55:00.000-08:002011-01-02T14:54:12.855-08:00sicp exercise 3.75<span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; Exercise 3.75. Unfortunately, Alyssa's zero-crossing detector in exercise 3.74 proves to be insufficient, because the noisy signal from the sensor leads to spurious zero crossings. Lem E. Tweakit, a hardware specialist, suggests that Alyssa smooth the signal to filter out the noise before extracting the zero crossings. Alyssa takes his advice and decides to extract the zero crossings from the signal constructed by averaging each value of the sense data with the previous value. She explains the problem to her assistant, Louis Reasoner, who attempts to implement the idea, altering Alyssa's program as follows:</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(define (make-zero-crossings input-stream last-value)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">; (let ((avpt (/ (+ (stream-car input-stream) last-value) 2)))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">; (cons-stream (sign-change-detector avpt last-value)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">; (make-zero-crossings (stream-cdr input-stream)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">; avpt))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;This does not correctly implement Alyssa's plan. Find the bug that Louis has installed and fix it without changing the structure of the program. (Hint: You will need to increase the number of arguments to make-zero-crossings.)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (make-zero-crossings input-stream last-value last-avg-value)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (let ((avpt (/ (+ (stream-car input-stream) last-value) 2)))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream (sign-change-detector avpt last-avg-value)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (make-zero-crossings (stream-cdr input-stream)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (stream-car input-stream) avpt))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> weimahttp://www.blogger.com/profile/13250647442722796831noreply@blogger.com0tag:blogger.com,1999:blog-8286606670338692791.post-1705924820041243182011-01-02T13:24:00.000-08:002011-01-02T13:23:54.563-08:00sicp exercise 3.74<span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;;Exercise 3.74. Alyssa P. Hacker is designing a system to process signals coming from physical sensors. One important feature she wishes to produce is a signal that describes the zero crossings of the input signal. That is, the resulting signal should be + 1 whenever the input signal changes from negative to positive, - 1 whenever the input signal changes from positive to negative, and 0 otherwise. (Assume that the sign of a 0 input is positive.) For example, a typical input signal with its associated zero-crossing signal would be</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">; ...1 2 1.5 1 0.5 -0.1 -2 -3 -2 -0.5 0.2 3 4 ...... </span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">; 0 0 0 0 0 -1 0 0 0 0 1 0 0 ...</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;In Alyssa's system, the signal from the sensor is represented as a stream sense-data and the stream zero-crossings is the corresponding stream of zero crossings. Alyssa first writes a procedure sign-change-detector that takes two values as arguments and compares the signs of the values to produce an appropriate 0, 1, or - 1. She then constructs her zero-crossing stream as follows:</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(define (make-zero-crossings input-stream last-value)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">; (cons-stream</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">; (sign-change-detector (stream-car input-stream) last-value)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">; (make-zero-crossings (stream-cdr input-stream)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">; (stream-car input-stream))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(define zero-crossings (make-zero-crossings sense-data 0))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;Alyssa's boss, Eva Lu Ator, walks by and suggests that this program is approximately equivalent to the following one, which uses the generalized version of stream-map from exercise 3.50:</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(define zero-crossings</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">; (stream-map sign-change-detector sense-data <expression>))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;Complete the program by supplying the indicated <expression>.</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define zero-crossings</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (stream-map sign-change-detector sense-data (cons-stream 0 sense-data)))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> weimahttp://www.blogger.com/profile/13250647442722796831noreply@blogger.com0tag:blogger.com,1999:blog-8286606670338692791.post-1622492423403241922011-01-02T13:17:00.000-08:002011-01-02T13:16:55.428-08:00sicp exercise 3.73<span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; Exercise 3.73. </span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; v = v0 + (1/C)0ti dt + R i </span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <img style="font-family: courier new,monospace;" src="http://mitpress.mit.edu/sicp/full-text/book/ch3-Z-G-50.gif" border="0"><br style="font-family: courier new,monospace;"> <img style="font-family: courier new,monospace;" src="http://mitpress.mit.edu/sicp/full-text/book/ch3-Z-G-51.gif" border="0"><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;;Figure 3.33: An RC circuit and the associated signal-flow diagram.</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;;We can model electrical circuits using streams to represent the values of currents or voltages at a sequence of times. For instance, suppose we have an RC circuit consisting of a resistor of resistance R and a capacitor of capacitance C in series. The voltage response v of the circuit to an injected current i is determined by the formula in figure 3.33, whose structure is shown by the accompanying signal-flow diagram.</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;;Write a procedure RC that models this circuit. RC should take as inputs the values of R, C, and dt and should return a procedure that takes as inputs a stream representing the current i and an initial value for the capacitor voltage v0 and produces as output the stream of voltages v. For example, you should be able to use RC to model an RC circuit with R = 5 ohms, C = 1 farad, and a 0.5-second time step by evaluating (define RC1 (RC 5 1 0.5)). This defines RC1 as a procedure that takes a stream representing the time sequence of currents and an initial capacitor voltage and produces the output stream of voltages.</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (scale-stream stream factor)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (stream-map (lambda (x) (* x factor)) stream))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (integral integrand initial-value dt)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (define int</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream initial-value</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (add-streams (scale-stream integrand dt)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> int)))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> int)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (RC R C dt)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (lambda(i v0)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (add-stream (scale-stream i R)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (integral (scale-stream i (/ 1 C)) v0 dt))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define RC1 (RC 5 1 0.5))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> weimahttp://www.blogger.com/profile/13250647442722796831noreply@blogger.com0tag:blogger.com,1999:blog-8286606670338692791.post-72251336992774001672011-01-02T11:45:00.000-08:002011-01-02T11:44:47.802-08:00sicp exercise 3.72<span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">; Exercise 3.72. In a similar way to exercise 3.71 generate a stream of all numbers that can be written as the sum of two squares in three different ways (showing how they can be so written).</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (display-line str)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (display str)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (newline))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (display-stream str num)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (define (internal index)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (if (> index num) 'printed</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (begin</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (display-line (stream-ref str index))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (internal (+ 1 index)))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (internal 0))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (integers-from-n n)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream n (integers-from-n (+ 1 n))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define integers (integers-from-n 1))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (merge-weighted s1 s2 weight)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cond ((stream-null? s1) s2)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> ((stream-null? s2) s1)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (else</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (let ((s1car (stream-car s1))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (s2car (stream-car s2)))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cond ((< (weight s1car) (weight s2car))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream s1car (merge-weighted (stream-cdr s1) s2 weight)))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (else</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream s2car (merge-weighted s1 (stream-cdr s2) weight))))))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (f1 s t)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream (list (stream-car s) (stream-car t))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (f1 s (stream-cdr t))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (f0 s t weight)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream (list (stream-car s) (stream-car t))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (merge-weighted (f1 s (stream-cdr t))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (f0 (stream-cdr s) (stream-cdr t) weight)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> weight)))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (weighted-pairs s t weight) (f0 s t weight))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (square x)(* x x))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define square-weighted-pairs (weighted-pairs integers integers (lambda(s)(+ (square (car s)) (square (cadr s))))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(display-stream square-weighted-pairs 50)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (check-eq-weight s weight)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (let ((a (stream-car s))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (b (stream-car (stream-cdr s)))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (c (stream-car (stream-cdr (stream-cdr s)))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (if (and (= (weight a) (weight b))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (= (weight b) (weight c)))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream (list (weight a) a b c)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (check-eq-weight (stream-cdr s) weight))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (check-eq-weight (stream-cdr s) weight))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define result (check-eq-weight square-weighted-pairs (lambda(s)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (+ (square (car s))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (square (cadr s))))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display-stream result 4)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;Loading "sicp_prob_03.72.scm"...</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(325 (10 15) (6 17) (1 18))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(425 (13 16) (8 19) (5 20))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(650 (17 19) (11 23) (5 25))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(725 (14 23) (10 25) (7 26))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(845 (19 22) (13 26) (2 29))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;... done</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> weimahttp://www.blogger.com/profile/13250647442722796831noreply@blogger.com0tag:blogger.com,1999:blog-8286606670338692791.post-74047279900006002422011-01-02T11:29:00.000-08:002011-01-02T11:28:25.521-08:00sicp exercise 3.71<span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; Exercise 3.71. Numbers that can be expressed as the sum of two cubes in more than one way are sometimes called Ramanujan numbers, in honor of the mathematician Srinivasa Ramanujan.70 Ordered streams of pairs provide an elegant solution to the problem of computing these numbers. To find a number that can be written as the sum of two cubes in two different ways, we need only generate the stream of pairs of integers (i,j) weighted according to the sum i3 + j3 (see exercise 3.70), then search the stream for two consecutive pairs with the same weight. Write a procedure to generate the Ramanujan numbers. The first such number is 1,729. What are the next five?</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (display-line str)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (display str)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (newline))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (display-stream str num)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (define (internal index)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (if (> index num) 'printed</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (begin</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (display-line (stream-ref str index))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (internal (+ 1 index)))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (internal 0))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (integers-from-n n)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream n (integers-from-n (+ 1 n))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define integers (integers-from-n 1))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (merge-weighted s1 s2 weight)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cond ((stream-null? s1) s2)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> ((stream-null? s2) s1)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (else</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (let ((s1car (stream-car s1))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (s2car (stream-car s2)))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cond ((< (weight s1car) (weight s2car))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream s1car (merge-weighted (stream-cdr s1) s2 weight)))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (else</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream s2car (merge-weighted s1 (stream-cdr s2) weight))))))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (f1 s t)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream (list (stream-car s) (stream-car t))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (f1 s (stream-cdr t))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (f0 s t weight)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream (list (stream-car s) (stream-car t))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (merge-weighted (f1 s (stream-cdr t))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (f0 (stream-cdr s) (stream-cdr t) weight)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> weight)))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (weighted-pairs s t weight) (f0 s t weight))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (cube x)(* x x x))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define cube-weighted-pairs (weighted-pairs integers integers (lambda(s)(+ (cube (car s)) (cube (cadr s))))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(display-stream cube-weighted-pairs 20)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (check-eq-weight s weight)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (let ((a (stream-car s))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (b (stream-car (stream-cdr s))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (if (= (weight a) (weight b))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream (list (weight a) a b)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (check-eq-weight (stream-cdr s) weight))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (check-eq-weight (stream-cdr s) weight))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define ramanujan-numbers (check-eq-weight cube-weighted-pairs (lambda(s)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (+ (cube (car s))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cube (cadr s))))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display-stream ramanujan-numbers 4)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;Loading "sicp_prob_03.71.scm"...</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(1729 (9 10) (1 12))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(4104 (9 15) (2 16))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(13832 (18 20) (2 24))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(20683 (19 24) (10 27))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(32832 (18 30) (4 32))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;... done</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> weimahttp://www.blogger.com/profile/13250647442722796831noreply@blogger.com0tag:blogger.com,1999:blog-8286606670338692791.post-32364333899411510122011-01-02T10:32:00.001-08:002011-01-02T10:32:06.004-08:00sicp exercise 3.70<span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;Exercise 3.70. It would be nice to be able to generate streams in which the pairs appear in some useful order, rather than in the order that results from an ad hoc interleaving process. We can use a technique similar to the merge procedure of exercise 3.56, if we define a way to say that one pair of integers is ``less than'' another. One way to do this is to define a ``weighting function'' W(i,j) and stipulate that (i1,j1) is less than (i2,j2) if W(i1,j1) < W(i2,j2). Write a procedure merge-weighted that is like merge, except that merge-weighted takes an additional argument weight, which is a procedure that computes the weight of a pair, and is used to determine the order in which elements should appear in the resulting merged stream.69 Using this, generalize pairs to a procedure weighted-pairs that takes two streams, together with a procedure that computes a weighting function, and generates the stream of pairs, ordered according to weight. Use your procedure to generate</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">; a. the stream of all pairs of positive integers (i,j) with i < j ordered according to the sum i + j</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">; b. the stream of all pairs of positive integers (i,j) with i < j, where neither i nor j is divisible by 2, 3, or 5, and the pairs are ordered according to the sum 2 i + 3 j + 5 i j.</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (display-line str)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (display str)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (newline))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (display-stream str num)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (define (internal index)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (if (> index num) 'printed</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (begin</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (display-line (stream-ref str index))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (internal (+ 1 index)))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (internal 0))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (integers-from-n n)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream n (integers-from-n (+ 1 n))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define integers (integers-from-n 1))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (merge-weighted s1 s2 weight)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cond ((stream-null? s1) s2)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> ((stream-null? s2) s1)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (else</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (let ((s1car (stream-car s1))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (s2car (stream-car s2)))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cond ((< (weight s1car) (weight s2car))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream s1car (merge-weighted (stream-cdr s1) s2 weight)))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (else</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream s2car (merge-weighted s1 (stream-cdr s2) weight))))))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (f1 s t)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream (list (stream-car s) (stream-car t))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (f1 s (stream-cdr t))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (f0 s t weight)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream (list (stream-car s) (stream-car t))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (merge-weighted (f1 s (stream-cdr t))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (f0 (stream-cdr s) (stream-cdr t) weight)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> weight)))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (weighted-pairs s t weight) (f0 s t weight))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display-stream (weighted-pairs integers integers (lambda(s)(+ (car s) (cadr s)))) 20)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (div-by x y)(= 0 (remainder x y)))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define integers-not-div-by-2-3-5</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (stream-filter (lambda(x)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (not (or (div-by x 2)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (div-by x 3)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (div-by x 5))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> integers))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(display-stream integers-not-div-by-2-3-5 20)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define result (weighted-pairs integers-not-div-by-2-3-5</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> integers-not-div-by-2-3-5</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (lambda(s)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (let ((i (car s))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (j (cadr s)))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (+ (* 2 i)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (* 3 j)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (* 5 i j))))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display-stream result 20)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;Loading "sicp_prob_03.70.scm"...</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(1 1)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(1 2)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(2 2)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(1 3)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(2 3)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(1 4)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(3 3)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(2 4)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(1 5)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(3 4)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(2 5)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(1 6)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(4 4)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(3 5)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(2 6)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(1 7)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(4 5)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(3 6)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(2 7)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(1 8)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(5 5)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(1 1)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(1 7)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(1 11)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(1 13)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(1 17)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(1 19)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(1 23)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(1 29)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(1 31)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(7 7)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(1 37)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(1 41)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(1 43)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(1 47)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(1 49)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(1 53)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(7 11)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(1 59)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(1 61)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(7 13)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(1 67)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;... done</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> weimahttp://www.blogger.com/profile/13250647442722796831noreply@blogger.com0tag:blogger.com,1999:blog-8286606670338692791.post-87999389582495895712011-01-01T15:47:00.000-08:002011-01-01T15:46:50.260-08:00sicp exercise 3.69<span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">; Exercise 3.69. Write a procedure triples that takes three infinite streams, S, T, and U, and produces the stream of triples (Si,Tj,Uk) such that i < j < k. Use triples to generate the stream of all Pythagorean triples of positive integers, i.e., the triples (i,j,k) such that i < j and i^2 + j^2 = k^2.</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (display-line str)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (display str)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (newline))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (display-stream str num)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (define (internal index)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (if (> index num) 'printed</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (begin</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (display-line (stream-ref str index))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (internal (+ 1 index)))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (newline)(internal 0))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (interleave s1 s2)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (if (stream-null? s1)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> s2</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream (stream-car s1)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (interleave s2 (stream-cdr s1)))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (integers-from-n n)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream n (integers-from-n (+ 1 n))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define integers (integers-from-n 1))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; another way to construct all pairs <i,j>, same as produces in exercise 67</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; the same idea is being used to produce triples below</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (incr1 s t)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream (list (stream-car s) (stream-car t)) (incr1 (stream-cdr s) t)))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (incr2 s t)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream (list (stream-car s) (stream-car t)) (incr2 s (stream-cdr t))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (pair2 s t)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream (list (stream-car s)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (stream-car t))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (interleave (incr2 s (stream-cdr t)) </span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (interleave (incr1 (stream-cdr s) t)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (pair2 (stream-cdr s) (stream-cdr t))))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;;(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;;(display-stream (pair2 integers integers) 20)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (f1 s t u)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream (list (stream-car s)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (stream-car t)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (stream-car u))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (f1 s t (stream-cdr u))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (f2 s t u)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream (list (stream-car s)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (stream-car t)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (stream-car u))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (interleave (f1 s t (stream-cdr u))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (f2 s (stream-cdr t) (stream-cdr u)))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (f0 s t u)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream (list (stream-car s)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (stream-car t)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (stream-car u))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (interleave (f1 s t (stream-cdr u))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (interleave (f2 s (stream-cdr t) (stream-cdr u))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (f0 (stream-cdr s)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (stream-cdr t)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (stream-cdr u))))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define triples (f0 integers integers integers))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(display-stream triples 20)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (stream-filter pred stream)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cond ((stream-null? stream) the-empty-stream)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> ((pred (stream-car stream))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream (stream-car stream)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (stream-filter pred</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (stream-cdr stream))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (else (stream-filter pred (stream-cdr stream)))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (pythagorean? p)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (= (+ (square (car p))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (square (cadr p)))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (square (caddr p))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display-stream (stream-filter pythagorean? triples) 2)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; Output:</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;Loading "sicp_prob_03.69.scm"...</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(3 4 5)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(6 8 10)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(5 12 13)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;... done</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> weimahttp://www.blogger.com/profile/13250647442722796831noreply@blogger.com0tag:blogger.com,1999:blog-8286606670338692791.post-80628278019285511802010-12-27T17:03:00.000-08:002010-12-27T17:02:04.775-08:00sicp exercise 3.68<span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; Exercise 3.68. Louis Reasoner thinks that building a stream of pairs from three parts is unnecessarily complicated. Instead of separating the pair (S0,T0) from the rest of the pairs in the first row, he proposes to work with the whole first row, as follows:</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(define (pairs s t)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">; (interleave</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">; (stream-map (lambda (x) (list (stream-car s) x))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">; t)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">; (pairs (stream-cdr s) (stream-cdr t))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;Does this work? Consider what happens if we evaluate (pairs integers integers) using Louis's definition of pairs.</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; Answer: This way, the problem cannot be cleanly decomposed recursively into smaller parts like shown in the example, </span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; and since the second pairs being invoked from body f pairs, is not a part of a cons-stream, so it will be evaluated immedialtely instead of being delayed. which leads to an infinite loop.</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; replacing this definition of pairs in the previous exercise leads to:</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; Answer:</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;Loading "sicp_prob_03.68.scm"... aborted</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;Aborting!: maximum recursion depth exceeded</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> weimahttp://www.blogger.com/profile/13250647442722796831noreply@blogger.com0tag:blogger.com,1999:blog-8286606670338692791.post-22292346387162674362010-12-22T14:14:00.000-08:002010-12-22T14:13:44.626-08:00sicp exercise 3.67<span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; Exercise 3.67. Modify the pairs procedure so that (pairs integers integers) will produce the stream of all pairs of integers (i,j) (without the condition i < j). Hint: You will need to mix in an additional stream.</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (display-line str)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (display str)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (newline))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (display-stream str num)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (define (internal index)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (if (> index num) 'printed</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (begin</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (display-line (stream-ref str index))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (internal (+ 1 index)))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (internal 0))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (interleave s1 s2)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (if (stream-null? s1)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> s2</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream (stream-car s1)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (interleave s2 (stream-cdr s1)))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (pairs s t)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (list (stream-car s) (stream-car t))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (interleave</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (stream-map (lambda (x) (list (stream-car s) x))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (stream-cdr t))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (interleave</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (stream-map (lambda(x)(list x (stream-car t)))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (stream-cdr s))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (pairs (stream-cdr s) (stream-cdr t))))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (integers-from-n n)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream n (integers-from-n (+ 1 n))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define integers (integers-from-n 1))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define int-pairs (pairs integers integers))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display-stream int-pairs 20)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; Answer:</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;Loading "sicp_prob_03.67.scm"...</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(1 1)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(1 2)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(2 1)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(1 3)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(2 2)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(1 4)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(3 1)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(1 5)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(2 3)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(1 6)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(4 1)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(1 7)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(3 2)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(1 8)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(5 1)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(1 9)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(2 4)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(1 10)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(6 1)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(1 11)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(3 3)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;... done</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> weimahttp://www.blogger.com/profile/13250647442722796831noreply@blogger.com0tag:blogger.com,1999:blog-8286606670338692791.post-76544260114106804802010-12-22T13:58:00.000-08:002010-12-22T13:57:49.107-08:00sicp exercise 3.66<span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; Exercise 3.66. Examine the stream (pairs integers integers). Can you make any general comments about the order in which the pairs are placed into the stream? For example, about how many pairs precede the pair (1,100)? the pair (99,100)? the pair (100,100)? (If you can make precise mathematical statements here, all the better. But feel free to give more qualitative answers if you find yourself getting bogged down.)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (display-line str)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (display str)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (newline))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (display-stream str num)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (define (internal index)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (if (> index num) 'printed</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (begin</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (display-line (stream-ref str index))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (internal (+ 1 index)))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (internal 0))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (interleave s1 s2)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (if (stream-null? s1)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> s2</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream (stream-car s1)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (interleave s2 (stream-cdr s1)))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (pairs s t)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (list (stream-car s) (stream-car t))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (interleave</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (stream-map (lambda (x) (list (stream-car s) x))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (stream-cdr t))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (pairs (stream-cdr s) (stream-cdr t)))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (integers-from-n n)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream n (integers-from-n (+ 1 n))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define integers (integers-from-n 1))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define int-pairs (pairs integers integers))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display-stream int-pairs 10)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; Felt bogged down, so ran the program to find the answer</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;Loading "sicp_prob_03.66.scm"...</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(1 1)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(1 2)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(2 2)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(1 3)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(2 3)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(1 4)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(3 3)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(1 5)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(2 4)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(1 6)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;(3 4)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;... done</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> weimahttp://www.blogger.com/profile/13250647442722796831noreply@blogger.com0tag:blogger.com,1999:blog-8286606670338692791.post-65452300205825098102010-12-21T15:50:00.001-08:002010-12-21T15:50:03.654-08:00sicp exercise 3.65<span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; Exercise 3.65. Use the series</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <img style="font-family: courier new,monospace;" src="http://mitpress.mit.edu/sicp/full-text/book/ch3-Z-G-44.gif" border="0"><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; to compute three sequences of approximations to the natural logarithm of 2, in the same way we did above for . How rapidly do these sequences converge?</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define count 0)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (euler-transform s)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (let ((s0 (stream-ref s 0)) ; Sn-1</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (s1 (stream-ref s 1)) ; Sn</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (s2 (stream-ref s 2))) ; Sn+1</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream (- s2 (/ (square (- s2 s1))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (+ s0 (* -2 s1) s2)))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (euler-transform (stream-cdr s)))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (make-tableau transform s)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream s</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (make-tableau transform</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (transform s))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (accelerated-sequence transform s)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (stream-map stream-car</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (make-tableau transform s)))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (partial-sums s)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (define result (cons-stream (stream-ref s 0)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (add-streams (stream-cdr s) result)))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> result)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (add-streams s1 s2)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (stream-map + s1 s2))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (stream-limit stream tolerance)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (define (iter initial-value str)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (let ((s (stream-car str)))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (if (> tolerance (abs (- s initial-value))) s</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (iter s (stream-cdr str)))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (iter (stream-car stream) (stream-cdr stream)))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (incr n)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (set! count (+ count 1))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (+ 1 n))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (ln-2-summands n)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream (/ 1.0 n)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (stream-map - (ln-2-summands (incr n)))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define ln-2-stream</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (partial-sums (ln-2-summands 1)))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define acc-ln-2-stream (accelerated-sequence euler-transform (partial-sums (ln-2-summands 1))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; Value of ln 2 from wolfram alpha:</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;;0.6931471805599453094172321214581765680755001343602552541206...</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-limit ln-2-stream 0.0001))(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display count)(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(set! count 0)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-limit acc-ln-2-stream 0.00001))(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display count)(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; Output:</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;Loading "sicp_prob_03.65.scm"...</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;.6930971830599583</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;9999</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;.6931471960735491</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;8</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;... done</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> weimahttp://www.blogger.com/profile/13250647442722796831noreply@blogger.com0tag:blogger.com,1999:blog-8286606670338692791.post-67330212722680308592010-12-21T15:16:00.000-08:002010-12-21T15:15:37.574-08:00sicp exercise 3.64<span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; Exercise 3.64. Write a procedure stream-limit that takes as arguments a stream and a number (the tolerance). It should examine the stream until it finds two successive elements that differ in absolute value by less than the tolerance, and return the second of the two elements. Using this, we could compute square roots up to a given tolerance by</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; (define (sqrt x tolerance)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; (stream-limit (sqrt-stream x) tolerance))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (average x y)(/ (+ x y) 2))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (sqrt-improve guess x)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (average guess (/ x guess)))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (sqrt-stream x)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (define guesses</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream 1.0</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (stream-map (lambda (guess)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (sqrt-improve guess x))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> guesses)))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> guesses)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (stream-limit stream tolerance)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (define (iter initial-value str)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (let ((s (stream-car str)))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (if (> tolerance (abs (- s initial-value))) s </span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (iter s (stream-cdr str)))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (iter (stream-car stream) (stream-cdr stream)))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (sqrt x tolerance)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (stream-limit (sqrt-stream x) tolerance))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (sqrt 30000 0.0000000000003))(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;;Output:</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;Loading "sicp_prob_03.64.scm"...</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;173.20508075688772</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;... done</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> weimahttp://www.blogger.com/profile/13250647442722796831noreply@blogger.com0tag:blogger.com,1999:blog-8286606670338692791.post-52828572705141723082010-12-21T13:36:00.000-08:002010-12-21T13:35:59.380-08:00sicp exercise 3.63<span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;;Exercise 3.63. Louis Reasoner asks why the sqrt-stream procedure was not written in the following more straightforward way, without the local variable guesses:</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;;(define (sqrt-stream x)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; (cons-stream 1.0</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; (stream-map (lambda (guess)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; (sqrt-improve guess x))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; (sqrt-stream x))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;;</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;;Alyssa P. Hacker replies that this version of the procedure is considerably less efficient because it performs redundant computation. Explain Alyssa's answer. Would the two versions still differ in efficiency if our implementation of delay used only (lambda () <exp>) without using the optimization provided by memo-proc (section 3.5.1)?</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; Answer:</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; The version presented above doesnt work on the already created stream, it starts creating stream right from the beginning for every iteration of the computation. This method is of same efficiency as the version of delay without memo-proc.</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> weimahttp://www.blogger.com/profile/13250647442722796831noreply@blogger.com0tag:blogger.com,1999:blog-8286606670338692791.post-48058385342181142042010-12-21T10:11:00.000-08:002010-12-21T11:46:43.338-08:00sicp exercise 3.62<span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; Exercise 3.62. Use the results of exercises 3.60 and 3.61 to define a procedure div-series that divides two power series. Div-series should work for any two series, provided that the denominator series begins with a nonzero constant term. (If the denominator has a zero constant term, then div-series should signal an error.) Show how to use div-series together with the result of exercise 3.59 to generate the power series for tangent.</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (integrate-series s)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (define (integrate-series-i s n)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream (/ (stream-car s) n)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (integrate-series-i (stream-cdr s) (+ 1 n))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (integrate-series-i s 1))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (mul-stream s1 s2)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (stream-map * s1 s2))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define minus-one</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream -1 minus-one))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (scale-stream stream factor)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (stream-map (lambda (x) (* x factor)) stream))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (add-streams s1 s2)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream (+ (stream-car s1) (stream-car s2))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (add-streams (stream-cdr s1)(stream-cdr s2))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (mul-series s1 s2)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream </span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (* (stream-car s1)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (stream-car s2))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (add-streams </span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (add-streams (scale-stream (stream-cdr s1) (stream-car s2))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (scale-stream (stream-cdr s2) (stream-car s1)))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream 0 (mul-series (stream-cdr s1) (stream-cdr s2))))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (invert-unit-series s)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (define X</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream 1 (mul-stream minus-one (mul-series (stream-cdr s) X))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> X)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (div-series s1 s2)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (if (= 0 (stream-car s2)) 'Error</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (mul-series s1 (invert-unit-series s2))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define cosine-series</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream 1 (mul-stream minus-one (integrate-series sine-series))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define sine-series</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream 0 (integrate-series cosine-series)))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define tangent-series (div-series sine-series cosine-series))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref tangent-series 0))(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref tangent-series 1))(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref tangent-series 2))(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref tangent-series 3))(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref tangent-series 4))(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref tangent-series 5))(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref tangent-series 6))(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref tangent-series 7))(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref tangent-series 8))(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref tangent-series 9))(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref tangent-series 10))(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref tangent-series 11))(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; Output</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;Loading "sicp_prob_03.62.scm"...</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;0</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;1</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;0</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;1/3</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;0</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;2/15</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;0</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;17/315</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;0</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;62/2835</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;0</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;1382/155925</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;... done</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <img style="font-family: courier new,monospace;" src="http://www3.wolframalpha.com/Calculate/MSP/MSP493819de23dc56853h6e000064e34fg9969894a5?MSPStoreType=image/gif&s=22&w=332&h=40" border="0"><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> weimahttp://www.blogger.com/profile/13250647442722796831noreply@blogger.com0tag:blogger.com,1999:blog-8286606670338692791.post-58416858464431021952010-12-21T09:23:00.001-08:002010-12-21T11:46:43.339-08:00sicp exercise 3.61<span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;;Exercise 3.61. Let S be a power series (exercise 3.59) whose constant term is 1. Suppose we want to find the power series 1/S, that is, the series X such that S · X = 1. Write S = 1 + SR where SR is the part of S after the constant term. Then we can solve for X as follows:</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <img style="font-family: courier new,monospace;" src="http://mitpress.mit.edu/sicp/full-text/book/ch3-Z-G-40.gif" border="0"><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;;In other words, X is the power series whose constant term is 1 and whose higher-order terms are given by the negative of SR times X. Use this idea to write a procedure invert-unit-series that computes 1/S for a power series S with constant term 1. You will need to use mul-series from exercise 3.60.</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (integrate-series s)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (define (integrate-series-i s n)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream (/ (stream-car s) n)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (integrate-series-i (stream-cdr s) (+ 1 n))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (integrate-series-i s 1))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (mul-stream s1 s2)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (stream-map * s1 s2))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define minus-one</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream -1 minus-one))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (scale-stream stream factor)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (stream-map (lambda (x) (* x factor)) stream))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (add-streams s1 s2)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream (+ (stream-car s1) (stream-car s2))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (add-streams (stream-cdr s1)(stream-cdr s2))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (mul-series s1 s2)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream </span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (* (stream-car s1)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (stream-car s2))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (add-streams </span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (add-streams (scale-stream (stream-cdr s1) (stream-car s2))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (scale-stream (stream-cdr s2) (stream-car s1)))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream 0 (mul-series (stream-cdr s1) (stream-cdr s2))))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (invert-unit-series s)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (define X</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream 1 (mul-stream minus-one (mul-series (stream-cdr s) X))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> X)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define exp-series</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream 1 (integrate-series exp-series)))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define inverse-exp-series (invert-unit-series exp-series))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; Testing:</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; computing series expansion of 1/e^x. which is equal to e^-x</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; so the result should be same as e^x but with alternate signs</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref inverse-exp-series 0))(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref inverse-exp-series 1))(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref inverse-exp-series 2))(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref inverse-exp-series 3))(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref inverse-exp-series 4))(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref inverse-exp-series 5))(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref inverse-exp-series 6))(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref inverse-exp-series 7))(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref inverse-exp-series 8))(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; Output:</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;Loading "sicp_prob_03.61.scm"...</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;1</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;-1</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;1/2</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;-1/6</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;1/24</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;-1/120</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;1/720</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;-1/5040</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;1/40320</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;... done</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">; Indeed it is.....</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> weimahttp://www.blogger.com/profile/13250647442722796831noreply@blogger.com0tag:blogger.com,1999:blog-8286606670338692791.post-26218271472170353552010-12-19T15:51:00.000-08:002010-12-21T11:46:43.340-08:00sicp exercise 3.60<span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; Exercise 3.60. With power series represented as streams of coefficients as in exercise 3.59, adding series is implemented by add-streams. Complete the definition of the following procedure for multiplying series:</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; (define (mul-series s1 s2)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; (cons-stream <??> (add-streams <??> <??>)))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; You can test your procedure by verifying that sin^2 x + cos^2 x = 1, using the series from exercise 3.59.</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (integrate-series s)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (define (integrate-series-i s n)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream (/ (stream-car s) n)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (integrate-series-i (stream-cdr s) (+ 1 n))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (integrate-series-i s 1))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (mul-stream s1 s2)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (stream-map * s1 s2))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define minus-one</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream -1 minus-one))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define cosine-series</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream 1 (mul-stream minus-one (integrate-series sine-series))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define sine-series</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream 0 (integrate-series cosine-series)))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (scale-stream stream factor)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (stream-map (lambda (x) (* x factor)) stream))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (add-streams s1 s2)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream (+ (stream-car s1) (stream-car s2))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (add-streams (stream-cdr s1)(stream-cdr s2))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (mul-series s1 s2)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream </span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (* (stream-car s1)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (stream-car s2))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (add-streams </span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (add-streams (scale-stream (stream-cdr s1) (stream-car s2))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (scale-stream (stream-cdr s2) (stream-car s1)))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream 0 (mul-series (stream-cdr s1) (stream-cdr s2))))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define test (add-streams (mul-series sine-series sine-series)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (mul-series cosine-series cosine-series)))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref test 0))(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref test 1))(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref test 2))(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref test 3))(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref test 4))(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref test 5))(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;;Output:</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;Loading "sicp_prob_03.60.scm"...</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;1</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;0</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;0</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;0</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;0</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;0</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;... done</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> weimahttp://www.blogger.com/profile/13250647442722796831noreply@blogger.com0tag:blogger.com,1999:blog-8286606670338692791.post-80018898975113183962010-12-19T13:16:00.001-08:002010-12-21T11:46:43.341-08:00sicp exercise 3.59<span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; Exercise 3.59. In section 2.5.3 we saw how to implement a polynomial arithmetic system representing polynomials as lists of terms. In a similar way, we can work with power series, such as</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; </span><br style="font-family: courier new,monospace;"> <img style="font-family: courier new,monospace;" src="http://mitpress.mit.edu/sicp/full-text/book/ch3-Z-G-36.gif" border="0"><br style="font-family: courier new,monospace;"> <img style="font-family: courier new,monospace;" src="http://mitpress.mit.edu/sicp/full-text/book/ch3-Z-G-37.gif " border="0"><br style="font-family: courier new,monospace;"> <img style="font-family: courier new,monospace;" src="http://mitpress.mit.edu/sicp/full-text/book/ch3-Z-G-38.gif" border="0"><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; </span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; represented as infinite streams. We will represent the series a0 + a1 x + a2 x2 + a3 x3 + ··· as the stream whose elements are the coefficients a0, a1, a2, a3, ....</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; </span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; a. The integral of the series a0 + a1 x + a2 x2 + a3 x3 + ··· is the series</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;;</span><br style="font-family: courier new,monospace;"> <img style="font-family: courier new,monospace;" src="http://mitpress.mit.edu/sicp/full-text/book/ch3-Z-G-39.gif " border="0"><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; </span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; where c is any constant. Define a procedure integrate-series that takes as input a stream a0, a1, a2, ... representing a power series and returns the stream a0, (1/2)a1, (1/3)a2, ... of coefficients of the non-constant terms of the integral of the series. (Since the result has no constant term, it doesn't represent a power series; when we use integrate-series, we will cons on the appropriate constant.)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; </span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; b. The function x->e^x is its own derivative. This implies that ex and the integral of ex are the same series, except for the constant term, which is e0 = 1. Accordingly, we can generate the series for ex as</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; </span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; (define exp-series</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; (cons-stream 1 (integrate-series exp-series)))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; </span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; Show how to generate the series for sine and cosine, starting from the facts that the derivative of sine is cosine and the derivative of cosine is the negative of sine:</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; </span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; (define cosine-series</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; (cons-stream 1 <??>))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; (define sine-series</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; (cons-stream 0 <??>))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (integrate-series s)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (define (integrate-series-i s n)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream (/ (stream-car s) n)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (integrate-series-i (stream-cdr s) (+ 1 n))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (integrate-series-i s 1))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (mul-stream s1 s2)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (stream-map * s1 s2))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define minus-one</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream -1 minus-one))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define cosine-series</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream 1 (mul-stream minus-one (integrate-series sine-series))))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define sine-series</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream 0 (integrate-series cosine-series)))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref sine-series 0))(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref sine-series 1))(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref sine-series 2))(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref sine-series 3))(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref sine-series 4))(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref sine-series 5))(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref sine-series 6))(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref sine-series 7))(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref sine-series 8))(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display "----------------------")(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref cosine-series 0))(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref cosine-series 1))(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref cosine-series 2))(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref cosine-series 3))(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref cosine-series 4))(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref cosine-series 5))(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref cosine-series 6))(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref cosine-series 7))(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref cosine-series 8))(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; Output:</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;Loading "sicp_prob_03.59.scm"...</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;0</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;1</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;0</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;-1/6</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;0</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;1/120</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;0</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;-1/5040</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;0</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;----------------------</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;1</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;0</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;-1/2</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;0</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;1/24</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;0</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;-1/720</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;0</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;1/40320</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;... done</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> weimahttp://www.blogger.com/profile/13250647442722796831noreply@blogger.com0tag:blogger.com,1999:blog-8286606670338692791.post-47086484593721395072010-12-19T13:16:00.000-08:002010-12-21T11:46:43.342-08:00sicp exercise 3.58<span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; Exercise 3.58. Give an interpretation of the stream computed by the following procedure:</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;;</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;;(define (expand num den radix)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; (cons-stream</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; (quotient (* num radix) den)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;; (expand (remainder (* num radix) den) den radix)))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;;</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;;(Quotient is a primitive that returns the integer quotient of two integers.) What are the successive elements produced by (expand 1 7 10) ? What is produced by (expand 3 8 10) ?</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(define (expand num den radix)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (cons-stream</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (quotient (* num radix) den)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"> (expand (remainder (* num radix) den) den radix)))</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref (expand 1 7 10) 0)) (newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref (expand 1 7 10) 1)) (newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref (expand 1 7 10) 2)) (newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref (expand 1 7 10) 3)) (newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref (expand 1 7 10) 4)) (newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref (expand 1 7 10) 5)) (newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref (expand 1 7 10) 6)) (newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref (expand 1 7 10) 7)) (newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref (expand 1 7 10) 8)) (newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref (expand 3 8 10) 0)) (newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref (expand 3 8 10) 1)) (newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref (expand 3 8 10) 2)) (newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref (expand 3 8 10) 3)) (newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref (expand 3 8 10) 4)) (newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref (expand 3 8 10) 5)) (newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref (expand 3 8 10) 6)) (newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref (expand 3 8 10) 7)) (newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">(display (stream-ref (expand 3 8 10) 8)) (newline)</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">; Output:</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;Loading "sicp_prob_03.58.scm"...</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;1</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;4</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;2</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;8</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;5</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;7</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;1</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;4</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;2</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;3</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;7</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;5</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;0</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;0</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;0</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;0</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;0</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;0</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;">;... done</span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> <span style="font-family: courier new,monospace;"></span><br style="font-family: courier new,monospace;"> weimahttp://www.blogger.com/profile/13250647442722796831noreply@blogger.com0