weima learns to program

my attempt to do the exercises in sicp.

Thursday, January 6, 2011

sicp exercise 3.82



;; 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.


;; get-random-stream is a procedure which generates a stream of random pairs of (x,y) which lie within x1 y1 x2 y2

(define (estimate-integral integral x1 x2 y1 y2)
  (define input (get-random-stream x1 x2 y1 y2))
  (define area (abs (* (- x1 x2) (- y1 y2))))
  (define (iter passed total in-stream)
    (let ((x (car (stream-car in-stream)))
          (y (cdr (stream-car in-stream))))
      (if (integral x y)
          (cons-stream (* area (/ (+ passed 1) (+ 1 total)))
                       (iter (+ 1 passed) (+ 1 total) (stream-cdr in-stream)))
          (cons-stream (* area (/ passed (+ 1 total)))
                       (iter passed (+ 1 total) (stream-cdr in-stream))))))
  (iter 0 0 input))

sicp exercise 3.81



;; 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.


(define (display-line str)
  (display str)
  (newline))

(define (display-stream str num)
  (define (internal index)
    (if (> index num) 'printed
        (begin
          (display-line (stream-ref str index))
          (internal (+ 1 index)))))
  (newline)
  (internal 0))

(define (random-numbers input-stream rand-init)
  (define (rand-update n)(+ 10 n))
    (let ((command (stream-car input-stream)))
      (cond ((eq? command 'generate)
             (let ((random-number (rand-update rand-init)))
               (cons-stream random-number
                            (random-numbers (stream-cdr input-stream) random-number))))
            ((and (pair? command) (eq? (car command) 'reset))
              (let ((random-number (rand-update (cadr command))))
                (cons-stream random-number
                             (random-numbers (stream-cdr input-stream) random-number))))
            (else
              '()))))
              


(define infinite-input
  (cons-stream 'generate infinite-input))

(display-stream (random-numbers infinite-input 0) 20)

(define input
  (cons-stream 'generate
    (cons-stream 'generate
      (cons-stream 'generate
        (cons-stream (list 'reset 2)
          (cons-stream 'generate
            (cons-stream 'generate
              (cons-stream 'generate '()))))))))

(newline)
(display (stream-ref (random-numbers input 0) 0))(newline)
(display (stream-ref (random-numbers input 0) 1))(newline)
(display (stream-ref (random-numbers input 0) 2))(newline)
(display (stream-ref (random-numbers input 0) 3))(newline)
(display (stream-ref (random-numbers input 0) 4))(newline)
(display (stream-ref (random-numbers input 0) 5))(newline)
(display (stream-ref (random-numbers input 0) 6))(newline)

;Loading "sicp_prob_03.81.scm"...
;10
;20
;30
;40
;50
;60
;70
;80
;90
;100
;110
;120
;130
;140
;150
;160
;170
;180
;190
;200
;210
;
;10
;20
;30
;12
;22
;32
;42
;... done


Tuesday, January 4, 2011

sicp exercise 3.80



;; 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



;;and the circuit connections dictate the relations



;;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



;;The signal-flow diagram representing this system of differential equations is shown in figure 3.37.



;;Figure 3.36:  A series RLC circuit.



;;Figure 3.37:  A signal-flow diagram for the solution to a series RLC circuit.

;;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.


(define (display-line str)
  (display str)
  (newline))

(define (display-stream str num)
  (define (internal index)
    (if (> index num) 'printed
        (begin
          (display-line (stream-ref str index))
          (internal (+ 1 index)))))
  (newline)
  (internal 0))

(define (display-stream-pair p num)
  (define (internal index)
    (if (> index num) 'printed
        (begin
          (display-line (list (stream-ref (car p) index) (stream-ref (cdr p) index)))
          (internal (+ 1 index)))))
  (newline)
  (internal 0))
 


(define (scale-stream stream factor)
  (stream-map (lambda (x) (* x factor)) stream))

(define (add-streams s1 s2)
  (stream-map + s1 s2))

(define (integral delayed-integrand initial-value dt)
  (define int
    (cons-stream initial-value
                 (let ((integrand (force delayed-integrand)))
                   (add-streams (scale-stream integrand dt)
                                int))))
  int)

(define (RLC R L C dt)
  (lambda(vc0 il0)
    (define vc (integral (delay dvc) vc0 dt))
    (define il (integral (delay dil) il0 dt))
    (define dvc (scale-stream il (/ -1 C)))
    (define dil (add-streams (scale-stream il (/ (* -1 R) L))
                             (scale-stream vc (/ 1 L))))
    (cons vc il)))

(define RLC123 (RLC 1 0.2 1 0.1))

(display-stream-pair (RLC123 10 0) 40)


;; Output
;Loading "sicp_prob_03.80.scm"...
;(10 0)
;(10 5.)
;(9.5 7.5)
;(8.75 8.5)
;(7.9 8.625)
;(7.0375000000000005 8.2625)
;(6.211250000000001 7.6499999999999995)
;(5.446250000000001 6.930624999999999)
;(4.753187500000001 6.1884375)
;(4.134343750000001 5.470812500000001)
;(3.587262500000001 4.802578125000001)
;(3.107004687500001 4.194920312500001)
;(2.687512656250001 3.6509625000000008)
;(2.322416406250001 3.1692375781250006)
;(2.005492648437501 2.7458269921875007)
;(1.7309099492187507 2.375659820312501)
;(1.4933439671875006 2.0532848847656258)
;(1.2880154787109381 1.7733144259765632)
;(1.1106840361132817 1.5306649523437508)
;(.9576175408789066 1.3206744942285162)
;(.825550091456055 1.1391460175537114)
;(.7116354897006838 .9823480545048832)
;(.6134006842501954 .8469917721027835)
;(.528701507039917 .7301962281764895)
;(.4556818842222681 .6294488676082033)
;(.39273699746144775 .5425653759152357)
;(.33848045986992414 .4676511866883417)
;(.29171534120109 .40306582327913293)
;(.2514087588731767 .34739058224011143)
;(.21666970064916558 .29939967055664407)
;(.18672973359350117 .2580346856029048)
;(.1609262650332107 .222382209598203)
;(.1386880440733904 .19165423731570685)
;(.11952262034181971 .16517114069454863)
;(.10300550627236485 .14234688051818417)
;(.08877081822054643 .1226761933952745)
;(.07650319888101897 .10572350580791047)
;(.06593084830022793 .09111335234446472)
;(.05681951306578145 .07852210032234633)
;(.04896730303354682 .06767080669406389)
;(4.2200222364140436e-2 5.8319054863805356e-2)
;... done


sicp exercise 3.79


;; 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).

(define (integral delayed-integrand initial-value dt)
  (define int
    (cons-stream initial-value
                 (let ((integrand (force delayed-integrand)))
                   (add-streams (scale-stream integrand dt)
                                int))))
  int)

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

sicp exercise 3.78


;; Exercise 3.78. 



;;Figure 3.35:  Signal-flow diagram for the solution to a second-order linear differential equation.
;;Consider the problem of designing a signal-processing system to study the homogeneous second-order linear differential equation



;;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.


(define (display-line str)
  (display str)
  (newline))

(define (display-stream str num)
  (define (internal index)
    (if (> index num) 'printed
        (begin
          (display-line (stream-ref str index))
          (internal (+ 1 index)))))
  (newline)
  (internal 0))

(define (scale-stream stream factor)
  (stream-map (lambda (x) (* x factor)) stream))

(define (add-streams s1 s2)
  (stream-map + s1 s2))

(define (integral delayed-integrand initial-value dt)
  (define int
    (cons-stream initial-value
                 (let ((integrand (force delayed-integrand)))
                   (add-streams (scale-stream integrand dt)
                                int))))
  int)

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


sicp exercise 3.77



;; 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):

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

;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.


(define (add-streams s1 s2)
  (stream-map + s1 s2))

(define (scale-stream stream factor)
  (stream-map (lambda (x) (* x factor)) stream))

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


(define (solve f y0 dt)
  (define y (integral (delay dy) y0 dt))
  (define dy (stream-map f y))
  y)

(newline)
(display (stream-ref (solve (lambda (y) y) 1 0.001) 1000))


Sunday, January 2, 2011

sicp exercise 3.76



;; 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.


(define (display-line str)
  (display str)
  (newline))

(define (display-stream str num)
  (define (internal index)
    (if (> index num) 'printed
        (begin
          (display-line (stream-ref str index))
          (internal (+ 1 index)))))
  (newline)
  (internal 0))

(define (make-zero-crossings input-stream last-value)
  (let ((avpt (/ (+ (stream-car input-stream) last-value) 2)))
    (cons-stream (sign-change-detector avpt last-value)
                 (make-zero-crossings (stream-cdr input-stream)
                                      avpt))))

(define (avg x y)(/ (+ x y) 2))

(define (smooth s)
  (define (iter x y str)
    (cons-stream (avg x y)
                 (iter y (stream-car str) (stream-cdr str))))
  (iter (stream-car s)
        (stream-car (stream-cdr s))
        (stream-cdr (stream-cdr s))))

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

(define integers (integers-from-n 0))

(define (make-zero-crossings input-stream last-value)
  (cons-stream
   (sign-change-detector (stream-car input-stream) last-value)
   (make-zero-crossings (stream-cdr input-stream)
                        (stream-car input-stream))))

(define zero-crossings (make-zero-crossings (smooth (cons-stream 0 sense-data)) 0))