SICP

Exercise 4.17.   Draw diagrams of the environment in effect when evaluating the expression < e3 > in the procedure in the text, comparing how this will be structured when definitions are interpreted sequentially with how it will be structured if definitions are scanned out as described. Why is there an extra frame in the transformed program? Explain why this difference in environment structure can never make a difference in the behavior of a correct program. Design a way to make the interpreter implement the "simultaneous'' scope rule for internal definitions without constructing the extra frame. SOLUTION The progressive environment diagrams are here . There is an extra frame in the transformed program because the evaluator transforms the 'let' expression into a lambda expression which becomes another procedure object which executes in a new frame. One of the purposes of the environment structure is to ensure that each procedure execution gets a separate spac

Exercise 4.16.   In this exercise we implement the method just described for interpreting internal definitions. We assume that the evaluator supports  let  (see exercise  4.6 ). a.  Change  lookup-variable-value  (section  4.1.3 ) to signal an error if the value it finds is the symbol  *unassigned* . b.  Write a procedure  scan-out-defines  that takes a procedure body and returns an equivalent one that has no internal definitions, by making the transformation described above. c.  Install  scan-out-defines  in the interpreter, either in  make-procedure  or in  procedure-body  (see section  4.1.3 ). Which place is better? Why? SOLUTION The code and tests are here . It is better to install ' scan-out-defines ' in ' make-procedure ' because by doing this the transformation of the procedure body happens only once for a given procedure during definition time. If we install it in ' procedure-body ' the transformation will happen every time the procedure is executed. Th

Exercise 4.15.    Given a one-argument procedure  p  and an object  a ,  p  is said to ``halt'' on  a  if evaluating the expression  (p a)  returns a value (as opposed to terminating with an error message or running forever). Show that it is impossible to write a procedure  halts?  that correctly determines whether  p  halts on  a  for any procedure  p  and object  a . Use the following reasoning: If you had such a procedure  halts? , you could implement the following program: (define (run-forever) (run-forever)) (define (try p)   (if (halts? p p)       (run-forever)       'halted)) Now consider evaluating the expression  (try try)  and show that any possible outcome (either halting or running forever) violates the intended behavior of  halts? . 23 R E A S O N I N G The following is a simple zero-argument procedure that runs forever: (define (run-forever) (run-forever)) The following is a hypothetical procedure that checks if procedure p halts on input a: (define (halts? p

Exercise 4.14.   Eva Lu Ator and Louis Reasoner are each experimenting with the metacircular evaluator. Eva types in the definition of  map , and runs some test programs that use it. They work fine. Louis, in contrast, has installed the system version of  map  as a primitive for the metacircular evaluator. When he tries it, things go terribly wrong. Explain why Louis's  map  fails even though Eva's works. EXPLANATION & SOLUTION Part a of this problem: I implement Eva's way of explicitly typing in  the definition of 'map' into the metacircular evaluator's input prompt. I also type in the  definition of an 'inc' procedure to increment its (numerical) input. And also make use  of Racket's primitive procedure 'abs'. 'inc' and 'abs' are the procedure arguments to  'map' in different tests. As can be seen from the test results, everything works as expected.  Note that in this program, 'map' and 'inc' are

Exercise 4.13.   Scheme allows us to create new bindings for variables by means of  define , but provides no way to get rid of bindings. Implement for the evaluator a special form  make-unbound!  that removes the binding of a given symbol from the environment in which the  make-unbound!  expression is evaluated. This problem is not completely specified. For example, should we remove only the binding in the first frame of the environment? Complete the specification and justify any choices you make. SOLUTION I decided to remove only the binding in the first frame of the environment. The same variable could be bound to different values in different frames and if we remove the variable from all frames, then it can cause unexpected behaviors in other procedure executions. The code and tests are here .

Exercise 4.12.   The procedures  set-variable-value! ,  define-variable! , and  lookup-variable-value  can be expressed in terms of more abstract procedures for traversing the environment structure. Define abstractions that capture the common patterns and redefine the three procedures in terms of these abstractions. SOLUTION The code and tests are here . The abstractions that capture the common patterns in traversing the environment structure can be found in the new procedures named ' find-variable-position-in-env ' and ' find-variable-position-in-frame '.

Exercise 4.11.   Instead of representing a frame as a pair of lists, we can represent a frame as a list of bindings, where each binding is a name-value pair. Rewrite the environment operations to use this alternative representation. SOLUTION The code and tests are here .

Exercise 4.10.    By using data abstraction, we were able to write an  eval  procedure that is independent of the particular syntax of the language to be evaluated. To illustrate this, design and implement a new syntax for Scheme by modifying the procedures in this section, without changing  eval  or  apply . SOLUTION Here are the syntax changes I made: Comparison expressions of like (< x y) changed to a more intuitive (x < y). This  applies to the following operators: <, >, <=, >= and ==. Note that for equality I have  introduced the operator "==". This is because I want to reserve "=" for assignments  and definitions Assignment syntax changed from (set! x value) to (x = value) 'if' syntax changed (see "if" section below) The code and tests are here .

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>)   until (condition) ) Use the while block construct t

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 0)         b         (fib-iter (+ a b) a (- count 1))))) Modify  let->combination  of exercise  4.6  to also support named  let . SOLUTION The code and tests are here .

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 non-derived expressions? SOLUTION E X P L A N A T I O N (let* ((x 3)  (y (+ x 2))  (z (+ x y 5)))     (* x z) ) can be written as: (let ((x 3))     (let ((y (+ x 2)))         (let ((z (+ x y 5)))             (* x z)         )     )

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)     exp1     (if (not (eq? (assoc 'b '((a 1) (b 2))) false))         (single-argument-proc (assoc 'b '((a

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 have implemented the solution in two ways as suggested in the problem above: a) Installed 

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  (call factorial 3)  and instead of  (+ 1 2)  we will have to wri

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 .