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