Tuesday, January 13, 2009

SICP Section 4.1 The Metacircular Evaluator

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.

Answer: Version of list-of-values that evaluates from left to right irrespective of order of evaluation in the underlying Lisp.

Version of list-of-values that evaluates from right to left irrespective of order of evaluation in the underlying Lisp.

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 write (call + 1 2).

Answer: a. After Louis' changes, all definitions will be evaluated as procedure applications. This can lead to errors. In the example (define x 3) will be treated as the application of the procedure define on the values x and 3.

b. This can be achieved by changing the selectors.

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

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.


Exercise 4.5. Scheme allows an additional syntax for cond clauses, ( => ). If evaluates to a true value, then is evaluated. Its value must be a procedure of one argument; this procedure is then invoked on the value of the , and the result is returned as the value of the cond expression. For example

returns 2. Modify the handling of cond so that it supports this extended syntax.


Exercise 4.6. Let expressions are derived expressions, because

is equivalent to

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.


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

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

or must we explicitly expand let* in terms of non-derived expressions?

Answer: a.

b. It is sufficient to add the given snippet to eval to make let* work.

Exercise 4.8. ``Named let'' is a variant of let that has the form

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:

Modify let->combination of exercise 4.6 to also support named let.


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.


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.

Answer: Lookup function remains unchanged. Changed code follows.

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.

Answer: This solution depends on the original mechanism of representing frames.

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.

Answer: I prefer to treat make-unbound! as the functional opposite of define-variable!. Therefore it should only remove the binding from the first frame. This also prevents the operation from affecting the global environment, which is desirable. The operation raises an error if the value being unbound is not present in the first frame.

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.

Answer: Louis' version of map uses the primitive version of the procedure. This version expects a <procedure> in the *native language* as the first argument, to be applied by the *native apply*. However the argument supplied to map is in the *new language*. This leads to errors.

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:

Now consider evaluating the expression (try try) and show that any possible outcome (either halting or running forever) violates the intended behavior of halts?.

Answer: Executing (try try) evaluates (halts? try try). Assume that this returns true, implying that the application of (try try) is expected to halt. However this leads to the program running forever as (run-forever) is invoked.

If the return value is false, indicating that (try try) should not halt, then the program will halt. As both the outcomes contradicts the purpose of checking using halt?, there cannot be such a function.

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?

Answer: a.


c. A procedure is defined or redefined fewer times than it is executed/applied. As procedure-body is used by apply for each execution of the procedure it is better to install scan-out-defines in make-procedure which is used only when the procedure definition is being evaluated.

Exercise 4.17. Draw diagrams of the environment in effect when evaluating the expression 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.

Answer: The new frame is introduced due to the let operation being used. Every time a let is used a new frame is added which contains the expressions defined in the let.

As this newly introduced frame contains only those variables used by the let it should not make any difference to the behaviour of a correct program.

Exercise 4.18. Consider an alternative strategy for scanning out definitions that translates the example in the text to

Here a and b are meant to represent new variable names, created by the interpreter, that do not appear in the user's program. Consider the solve procedure from section 3.5.4:

Will this procedure work if internal definitions are scanned out as shown in this exercise? What if they are scanned out as shown in the text? Explain.

Answer: This procedure will not work if the internal definitions are scanned out as shown in this exercise. Consider the outer let statement. When it is evaluated y and dy are both set to '*unassigned*. Intermediate variables a and b are then evaluated in the inner let. Their values will be evaluated as (integral (delay '*unassigned*) y0 dt) and (stream-map f '*unassigned*) respectively. The latter throws an error as the second argument of stream-map is not a stream as expected.

Scanning out the internal definitions as shown in the text will work. In this case only one let expression is constructed. At the time of evaluation y and dy are initially assigned the value '*unassigned*. By the time the set! expression for dy is executed y has already been set to (integrate (delay dy) y0 dt), the result of which is in fact a stream. This satisfies the requirement that the second argument to stream-map should be a stream. Thereby the procedure works.

Exercise 4.19. Ben Bitdiddle, Alyssa P. Hacker, and Eva Lu Ator are arguing about the desired result of evaluating the expression

Ben asserts that the result should be obtained using the sequential rule for define: b is defined to be 11, then a is defined to be 5, so the result is 16. Alyssa objects that mutual recursion requires the simultaneous scope rule for internal procedure definitions, and that it is unreasonable to treat procedure names differently from other names. Thus, she argues for the mechanism implemented in exercise 4.16. This would lead to a being unassigned at the time that the value for b is to be computed. Hence, in Alyssa's view the procedure should produce an error. Eva has a third opinion. She says that if the definitions of a and b are truly meant to be simultaneous, then the value 5 for a should be used in evaluating b. Hence, in Eva's view a should be 5, b should be 15, and the result should be 20. Which (if any) of these viewpoints do you support? Can you devise a way to implement internal definitions so that they behave as Eva prefers?

Answer: The ideal case would be to have simultaneous evaluations as Eva prefers. However this is quite complex to implement, especially when mutual recursion is involved. Delay could be used in such cases thought it wouldn't be straightforward to implement. Given the difficulties involved in implementing the best alternative would be to support Alyssa's position and throw an error.

Exercise 4.20. Because internal definitions look sequential but are actually simultaneous, some people prefer to avoid them entirely, and use the special form letrec instead. Letrec looks like let, so it is not surprising that the variables it binds are bound simultaneously and have the same scope as each other. The sample procedure f above can be written without internal definitions, but with exactly the same meaning, as

Letrec expressions, which have the form

are a variation on let in which the expressions that provide the initial values for the variables are evaluated in an environment that includes all the letrec bindings. This permits recursion in the bindings, such as the mutual recursion of even? and odd? in the example above, or the evaluation of 10 factorial with

a. Implement letrec as a derived expression, by transforming a letrec expression into a let expression as shown in the text above or in exercise 4.18. That is, the letrec variables should be created with a let and then be assigned their values with set!.

b. Louis Reasoner is confused by all this fuss about internal definitions. The way he sees it, if you don't like to use define inside a procedure, you can just use let. Illustrate what is loose about his reasoning by drawing an environment diagram that shows the environment in which the is evaluated during evaluation of the expression (f 5), with f defined as in this exercise. Draw an environment diagram for the same evaluation, but with let in place of letrec in the definition of f.

Answer: a.

b. (1) f written as in this exercise using letrec. Consider how the letrec would have been transformed using lambda:

It is clear that the procedures even? and odd? can see each other as they are defined in the same environment. The rest-of-the-body-of-f is eveluated in the same environment as even? and odd?. This would not have been possible if let had been used instead of letrec (see below).

(2) f using let instead of letrec. In order to understand this better let us rewrite the let expression using lambda.

It can be seen that the rest-of-the-body-of-f is evaluated in an environment different from that of the two lambda procedures defining even? and odd?. These procedures cannot see each other - the body of even? will not find odd? and vice versa. Therefore this tranformation should not work. However this snippet *does* work in Dr Scheme. I suspect that this is perhaps because Dr Scheme treats such expressions in the same way as letrec.

Exercise 4.21. Amazingly, Louis's intuition in exercise 4.20 is correct. It is indeed possible to specify recursive procedures without using letrec (or even define), although the method for accomplishing this is much more subtle than Louis imagined. The following expression computes 10 factorial by applying a recursive factorial procedure:27

a. Check (by evaluating the expression) that this really does compute factorials. Devise an analogous expression for computing Fibonacci numbers.

b. Consider the following procedure, which includes mutually recursive internal definitions:

Fill in the missing expressions to complete an alternative definition of f, which uses neither internal definitions nor letrec:

Answer: a.


Exercise 4.22. Extend the evaluator in this section to support the special form let. (See exercise 4.6.)

Answer: We have already defined the opreation let->combination which transforms a given let expression to a lambda form. As analyze can understand lambda expressions it is sufficient to add the following condition to analyze to achieve the result:

Exercise 4.23. Alyssa P. Hacker doesn't understand why analyze-sequence needs to be so complicated. All the other analysis procedures are straightforward transformations of the corresponding evaluation procedures (or eval clauses) in section 4.1.1. She expected analyze-sequence to look like this:

Eva Lu Ator explains to Alyssa that the version in the text does more of the work of evaluating a sequence at analysis time. Alyssa's sequence-execution procedure, rather than having the calls to the individual execution procedures built in, loops through the procedures in order to call them: In effect, although the individual expressions in the sequence have been analyzed, the sequence itself has not been.

Compare the two versions of analyze-sequence. For example, consider the common case (typical of procedure bodies) where the sequence has just one expression. What work will the execution procedure produced by Alyssa's program do? What about the execution procedure produced by the program in the text above? How do the two versions compare for a sequence with two expressions?

Answer: Alyssa's version produces an execution procedure whose body contains a call to execute-sequence. Execute-sequence is actually run only at runtime when the execution procedure runs.

The original version of analyze-sequence invokes execute-sequence *during* anaylsis. The results of the call are embedded in the execution procedure.

Exercise 4.24. Design and carry out some experiments to compare the speed of the original metacircular evaluator with the version in this section. Use your results to estimate the fraction of time that is spent in analysis versus execution for various procedures.

Answer: Experiment:


Without analyze: cpu time: 44838 real time: 45448 gc time: 160

With analyze: cpu time: 21961 real time: 22004 gc time: 116. There is a saving of around 50%.

No comments: