SICP

Exercise 4.9.    Many languages support a variety of iteration constructs, such as  do ,  for ,  while , and  until . In Scheme, iterative processes can be expressed in terms of ordinary procedure calls, so special iteration constructs provide no essential gain in computational power. On the other hand, such constructs are often convenient. Design some iteration constructs, give examples of their use, and show how to implement them as derived expressions. SOLUTION The code and tests are  here . I have implemented the following expressions: do-while do-until for while The 'do-while' construct can be as follows: (do   (<one or more statements>)   while (condition) ) Use the while block construct to convert it as follows: (begin   <statements>   (while (condition)   <statements>   ) ) The 'do-until' construct can be as follows: (do   (<one or more statements>) ...

Exercise 4.8.    ``Named  let '' is a variant of  let  that has the form (let < var > < bindings > < body >) The < bindings > and < body > are just as in ordinary  let , except that < var > is bound within < body > to a procedure whose body is < body > and whose parameters are the variables in the < bindings >. Thus, one can repeatedly execute the < body > by invoking the procedure named < var >. For example, the iterative Fibonacci procedure (section  1.2.2 ) can be rewritten using named  let  as follows: (define (fib n)   (let fib-iter ((a 1)                  (b 0)                  (count n))     (if (= count...

Exercise 4.7.    Let*  is similar to  let , except that the bindings of the  let  variables are performed sequentially from left to right, and each binding is made in an environment in which all of the preceding bindings are visible. For example (let* ((x 3)        (y (+ x 2))        (z (+ x y 5)))   (* x z)) returns 39. Explain how a  let*  expression can be rewritten as a set of nested  let  expressions, and write a procedure  let*->nested-lets  that performs this transformation. If we have already implemented  let  (exercise  4.6 ) and we want to extend the evaluator to handle  let* , is it sufficient to add a clause to  eval  whose action is (eval (let*->nested-lets exp) env) or must we explicitly expand  let*  in terms of...

Exercise 4.6.    Let  expressions are derived expressions, because (let ((< var 1 > < exp 1 >)  ...  (< var n > < exp n >))   < body >) is equivalent to ((lambda (< var 1 >  ...  < var n >)    < body >)  < exp 1 >  .  .  .  < exp n >) Implement a syntactic transformation  let->combination  that reduces evaluating  let  expressions to evaluating combinations of the type shown above, and add the appropriate clause to  eval  to handle  let  expressions. SOLUTION The code and tests are here .

Exercise 4.5.    Scheme allows an additional syntax for  cond  clauses,  (< test > => < recipient >) . If < test > evaluates to a true value, then < recipient > is evaluated. Its value must be a procedure of one argument; this procedure is then invoked on the value of the < test >, and the result is returned as the value of the  cond  expression. For example (cond ((assoc 'b '((a 1) (b 2))) => cadr)       (else false)) returns 2. Modify the handling of  cond  so that it supports this extended syntax. SOLUTION The following example code shows how the extended syntax described in this problem can be represented using an 'if' structure: (cond ((< a b) exp1)     ((assoc 'b '((a 1) (b 2))) => single-argument-proc)     ((< m n) exp2)     (else exp3)) is equivalent to: (if (< a b) ...

Exercise 4.4.    Recall the definitions of the special forms  and  and  or  from chapter 1: and : The expressions are evaluated from left to right. If any expression evaluates to false, false is returned; any remaining expressions are not evaluated. If all the expressions evaluate to true values, the value of the last expression is returned. If there are no expressions then true is returned. or : The expressions are evaluated from left to right. If any expression evaluates to a true value, that value is returned; any remaining expressions are not evaluated. If all expressions evaluate to false, or if there are no expressions, then false is returned. Install  and  and  or  as new special forms for the evaluator by defining appropriate syntax procedures and evaluation procedures  eval-and  and  eval-or . Alternatively, show how to implement  and  and  or  as derived expressions. SOLUTION I h...

Exercise 4.3.    Rewrite  eval  so that the dispatch is done in data-directed style. Compare this with the data-directed differentiation procedure of exercise  2.73 . (You may use the  car  of a compound expression as the type of the expression, as is appropriate for the syntax implemented in this section.). SOLUTION The code and tests are here .  Note: The tests demonstrate that the data-directed dispatch happens correctly. Ignore the subsequent (environment related) errors for now. (These will be corrected in the upcoming exercises.)

Exercise 4.2.    Louis Reasoner plans to reorder the  cond  clauses in  eval  so that the clause for procedure applications appears before the clause for assignments. He argues that this will make the interpreter more efficient: Since programs usually contain more applications than assignments, definitions, and so on, his modified  eval  will usually check fewer clauses than the original  eval  before identifying the type of an expression. a. What is wrong with Louis's plan? (Hint: What will Louis's evaluator do with the expression  (define x 3) ?) b. Louis is upset that his plan didn't work. He is willing to go to any lengths to make his evaluator recognize procedure applications before it checks for most other kinds of expressions. Help him by changing the syntax of the evaluated language so that procedure applications start with  call . For example, instead of  (factorial 3)  we will now have to write  (c...

Exercise 4.1.    Notice that we cannot tell whether the metacircular evaluator evaluates operands from left to right or from right to left. Its evaluation order is inherited from the underlying Lisp: If the arguments to  cons in  list-of-values  are evaluated from left to right, then  list-of-values  will evaluate operands from left to right; and if the arguments to  cons  are evaluated from right to left, then  list-of-values  will evaluate operands from right to left. Write a version of  list-of-values  that evaluates operands from left to right regardless of the order of evaluation in the underlying Lisp. Also write a version of  list-of-values  that evaluates operands from right to left. SOLUTION The code and tests are here .

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. SOLUTION The code and tests are here .

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. SOLUTION The code and tests are here .

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  v C , the voltage across the capacitor, and  i L , 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...

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  d 2   y / d t 2  =  f ( d y / d t ,  y ). SOLUTION The code is here .

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  d 2 y / d t 2 depends upon the values of  y  and  d y / d t  and both of these are determined by integrating  d 2 y / d t 2 . 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  d t and the initial values  y 0  and  d y 0  for  y  and  d y / d t  and generates the stream of successive values of  y . SOLUTION The code and tests are here . The plots are pasted below and also available  here ....

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

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. SOLUTION See in the tests below that the 'smooth' procedure after processing the parabolic  stream from Exercise 3.75, produces the same stream as what we saw produced by the  corrected procedure in Exercise 3.75. The new procedures are also tested on a random  value stream after this. The code and tests are here .

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: (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)                ...

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 ... 1  2  1.5  1  0.5  -0.1  -2  -3  -2  -0.5  0.2  3  4  ... ...  0  0    0  0    0     -1  0   0   0     0    1  0 ...

Exercise 3.73.               v  =  v 0  + (1/ C ) 0 t i   d t  +  R   i        Figure 3.33:   An RC circuit and the associated signal-flow diagram. 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. Write a procedure  RC  that models this circuit.  RC  should take as inputs the values of  R ,  C , and  d t and should return a procedure that takes as inputs a stream representin...

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). SOLUTION The code and tests are here .