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.
(define (list-of-values exps env) (define (iter results exps) (if (no-operands? exps) results (let ((result (eval (first-operand exps) env))) (iter (cons result results) (rest-operands exps))))) (iter '() exps))
Version of list-of-values that evaluates from right to left irrespective of order of evaluation in the underlying Lisp.
(define (list-of-values exps env) (if (no-operands? exps) '() (let ((right (list-of-values (rest-operands) exps))) (cons (eval (first-operand exps) env) right))))
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.
(define (application? exp) (tagged-list? exp 'call)) (define (operator exp) (cadr exp)) (define (operands exp) (cddr exp))
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.).


(define (eval exp env) (cond ((self-evaluating? exp) exp) ((variable? exp) (lookup-variable-value exp env)) ((get 'eval (car exp)) ((get 'eval (car exp)) exp env)) ((application? exp) (apply (eval (operator exp) env) (list-of-values (operands exp) env))) (else (error "Unknown expression type -- EVAL" exp)))) ;; (put 'quote (lambda (exp env) (text-of-quotation exp))) ;; (put 'set! eval-assignment) ;; (put 'define eval-definition) ;; (put 'if eval-if) ;; (put 'lambda (lambda (exp env) (make-procedure (lambda-parameters exp) ;; (lambda-body exp) ;; env))) ;; (put 'begin eval-sequence) ;; (put 'cond (lambda (exp env) (eval (cond->if exp) env)))
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.

Answer:
(define (and? exp) (tagged-list? exp 'and)) (define (eval-and exp env) (define (iter ops) (if (no-operands? ops) true (if (eval (first-operand ops) env) (iter (rest-operands ops)) false))) (iter (operands exp))) (define (or? exp) (tagged-list? exp 'or)) (define (eval-or exp env) (define (iter ops) (if (no-operands? ops) false (let ((value (eval (first-operand ops) env))) (if value value (iter (rest-operands ops)))))) (iter (operands exp))) ;; Implementation as derived expressions (define (and->if exp) (expand-and-clauses (and-clauses exp))) (define (expand-and-clauses clauses) (if (null? clauses) 'true (make-if (car clauses) (expand-and-clauses (cdr clauses)) 'false))) (define (or->if exp) (expand-or-clauses (and-clauses exp))) (define (expand-or-clauses clauses) (if (null? clauses) 'false (make-if (car clauses) 'true (expand-or-clauses (cdr clauses)))))
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
(cond ((assoc 'b '((a 1) (b 2))) => cadr) (else false))
returns 2. Modify the handling of cond so that it supports this extended syntax.

Answer:
(define (cond-additional-syntax? clause) (and (= (length clause) 3) (eq? (caddr clause) '=>))) (define (expand-clauses clauses) (if (null? clauses) 'false (let ((first (car clauses)) (rest (cdr clauses))) (if (cond-else-clause? first) (if (null? rest) (sequence->exp (cond-actions first)) (error "ELSE clause isn't last -- COND->IF" clauses)) (let ((predicate (cond-predicate first)) (actions (cond-actions first))) (if (cond-additional-syntax? clause) (make-if predicate (list (cadr actions) predicate) (expand-clauses rest)) (make-if predicate (sequence->exp actions) (expand-clauses rest)))))))
Exercise 4.6. Let expressions are derived expressions, because
(let ((<var1> <exp1>) ... (<varn> <expn>)) <body>)
is equivalent to
((lambda (<var1> ... <varn>) <body>) <exp1> <expn>)
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.

Answer:
(define (let? exp) (tagged-list? exp 'let)) (define (let-variables-and-expressions exp) (cadr exp)) (define (let-body exp) (caddr exp)) (define (let->combination exp) (let ((variables-and-expressions (let-variables-and-expressions exp)) (body (let-body exp))) (let ((parameters (map car variables-and-expressions)) (expressions (map cadr variables-and-expressions))) (cons (make-lambda parameters body) 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
(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?

Answer: a.
(define (make-let variable-and-expression body) (list 'let variable-and-expression body)) (define (let*->nested-lets exp) (define (iter variables-and-expressions body) (if (null? variables-and-expressions) body (make-let (car variables-and-expressions) (iter (cdr variables-and-expressions) body)))) (iter (let-variables-and-expressions exp) (let-body exp)))
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
(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.

Answer:
(define (named-let? exp) (and (let? exp) (= (length exp) 4))) (define (let-var exp) (if (named-let? exp) (cadr exp) '())) (define (let-bindings exp) (if (named-let? exp) (caddr exp) (cadr exp))) (define (let-body exp) (if (named-let? exp) (caddr exp) (cadddr exp))) (define (make-named-lambda-definition var parameters body) (list 'define var (make-lambda parameters body))) (define (let->combination exp) (let ((var (let-var exp)) (bindings (let-bindings exp)) (body (let-body exp))) (let ((parameters (map car bindings)) (expressions (map cadr bindings))) (if (named-let? exp) (list (make-named-lambda-definition var parameters body) (cons var expressions)) (cons (make-lambda parameters body) expressions)))))
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.

Answer:
(define (while? exp) (tagged-list? exp 'while)) (define (while-predicate exp) (cadr exp)) (define (while-body exp) (caddr exp)) (define (while->combination exp) (let ((predicate (while-predicate exp)) (body (while-body exp))) (sequence->exp (list (make-named-lambda-definition 'while-loop '() (make-if predicate (list body (list 'while-loop)) 'true)) (list 'while-loop)))))
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.
(define (make-frame variables values) (define (iter variables values frame) (if (null? variables) frame (iter (cdr variables) (cdr values) (cons (cons (car variables) (car values)) frame)))) (iter variables values '())) (define (frame-variables frame) (map car frame)) (define (frame-values frame) (map cdr frame)) (define (add-binding-to-frame! var val frame) (let ((old-car (car frame)) (new-car (cons var val))) (set-car! frame new-car) (set-cdr! frame (cons old-car (cdr frame))))) (define (set-variable-value! var val env) (define (env-loop env) (define (scan pairs) (cond ((null? pairs) (env-loop (enclosing-environment env))) ((eq? var (caar pairs)) (set-cdr! (car pairs) val)) (else (scan (cdr pairs))))) (if (eq? env the-empty-environment) (error "Unbound variable -- SET!" var) (let ((frame (first-frame env))) (scan frame)))) (env-loop env)) (define (define-variable! var val env) (let ((frame (first-frame env))) (define (scan pairs) (cond ((null? pairs) (add-binding-to-frame! var val frame)) ((eq? var (caar pairs)) (set-cdr! (car pairs) val)) (else (scan (cdr pairs))))) (scan frame)))
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.
(define (lookup-value-in-frame var frame) (define (iter variables values) (cond ((null? variables) false) ((eq? var (car variables)) (car values)) (else (iter (cdr variables) (cdr values))))) (iter (frame-variables frame) (frame-values frame))) (define (lookup-variable-value var env) (define (env-loop env) (if (eq? env the-empty-environment) (error "Unbound variable" var) (let ((value (lookup-value-in-frame var (first-frame env)))) (if value value (env-loop (enclosing-environment env)))))) (env-loop env)) (define (set-value-in-frame! var val frame) (define (iter variables values) (cond ((null? values) false) ((eq? var (car variables)) (set-car! values val)) (else (iter (cdr variables) (cdr values))))) (iter (frame-variables frame) (frame-values frame))) (define (set-variable-value! var val env) (define (env-loop env) (if (eq? env the-empty-environment) (error "Unbound variable -- SET!" var) (let ((result (set-value-in-frame! var val (first-frame env)))) (if (not result) (env-loop (enclosing-environment env)))))) (env-loop env)) (define (define-variable-in-frame! var val frame) (if (not (set-value-in-frame! var val frame)) (add-binding-to-frame! var val frame))) (define (define-variable! var val env) (let ((frame (first-frame env))) (define-variable-in-frame! var val frame)))
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.
(define (remove-binding-from-frame var frame) (let ((new-vars '()) (new-vals '())) (define (iter variables values) (cond ((not (null? variables)) (cond ((not (eq? var (car variables))) (set! new-vars (cons (car variables) new-vars)) (set! new-vals (cons (car values) new-vals)))) (iter (cdr variables) (cdr values))))) (iter (frame-variables frame) (frame-values frame)) (set-car! frame new-vars) (set-cdr! frame new-vals))) (define (make-unbound! var env) (let ((frame (first-frame env))) (if (lookup-value-in-frame var frame) (remove-binding-from-frame var frame) (error "Unbound variable -- REMOVE!" var))))
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:
(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?.

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.
(define (lookup-value-in-frame var frame) (define (iter variables values) (cond ((null? variables) false) ((eq? var (car variables)) (let ((value (car values))) (if (eq? value '*unassigned*) (error "Value is *unassigned* -- LOOKUP" var) value))) (else (iter (cdr variables) (cdr values))))) (iter (frame-variables frame) (frame-values frame))) ;; This part is unchanged. (define (lookup-variable-value var env) (define (env-loop env) (if (eq? env the-empty-environment) (error "Unbound variable" var) (let ((value (lookup-value-in-frame var (first-frame env)))) (if value value (env-loop (enclosing-environment env)))))) (env-loop env))
b.
(define (create-special-bindings vars) (map (lambda (v) (list v '*unassigned*)) vars)) (define (make-set variable expression) (list 'set! variable expression)) (define (create-set-expressions variables expressions) (map (lambda (v e) (make-set v e)) variables expressions)) (define (scan-out-defines procedure-body) (define (collect seq variables expressions rest) (cond ((null? seq) (list variables expressions rest)) ((definition? (car seq)) (collect (cdr seq) (cons (definition-variable (car seq)) variables) (cons (definition-value (car seq)) expressions) rest)) (else (collect (cdr seq) variables expressions (cons (car seq) rest))))) (let ((collection (collect (lambda-body procedure-body) '() '() '()))) (let ((variables (car collection)) (expressions (cadr collection)) (rest (reverse (caddr collection)))) (make-lambda (lambda-parameters procedure-body) (make-let (create-special-bindings variables) (append (create-set-expressions variables expressions) rest))))))
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
(lambda <vars> (let ((u '*unassigned*) (v '*unassigned*)) (let ((a <e1>) (b <e2>)) (set! u a) (set! v b)) <e3>))
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:
(define (solve f y0 dt) (define y (integral (delay dy) y0 dt)) (define dy (stream-map f y)) y)
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
(let ((a 1)) (define (f x) (define b (+ a x)) (define a 5) (+ a b)) (f 10))
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
(define (f x) (letrec ((even? (lambda (n) (if (= n 0) true (odd? (- n 1))))) (odd? (lambda (n) (if (= n 0) false (even? (- n 1)))))) <rest of body of f>))
Letrec expressions, which have the form
(letrec ((<var1> <exp1>) ... (<varn> <expn>)) <body>)
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
(letrec ((fact (lambda (n) (if (= n 1) 1 (* n (fact (- n 1))))))) (fact 10))
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.
(define (letrec? exp) (tagged-list? exp 'letrec)) (define (letrec-bindings exp) (cadr exp)) (define (letrec-body exp) (caddr exp)) (define (letrec->let exp) (let ((bindings (letrec-bindings exp)) (body (letrec-body exp))) (let ((variables (map car bindings)) (expressions (map cadr bindings))) (make-let (create-special-bindings variables) (append (create-set-expressions variables expressions) body)))))
b. (1) f written as in this exercise using letrec. Consider how the letrec would have been transformed using lambda:
((lambda (even? odd?) (set! even? (lambda (n) (if (= n 0) true (odd? (- n 1))))) (set! odd? (lambda (n) (if (= n 0) false (even? (- n 1))))) <rest-of-body-of-f>) '*unassigned '*unassigned)
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.
( (lambda (even? odd?) <rest-of-body-of-f>) (lambda (n) (if (= n 0) true (odd? (- n 1)))) even? (lambda (n) (if (= n 0) false (even? (- n 1)))) odd? )
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
((lambda (n) ((lambda (fact) (fact fact n)) (lambda (ft k) (if (= k 1) 1 (* k (ft ft (- k 1))))))) 10)
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:
(define (f x) (define (even? n) (if (= n 0) true (odd? (- n 1)))) (define (odd? n) (if (= n 0) false (even? (- n 1)))) (even? x))
Fill in the missing expressions to complete an alternative definition of f, which uses neither internal definitions nor letrec:
(define (f x) ((lambda (even? odd?) (even? even? odd? x)) (lambda (ev? od? n) (if (= n 0) true (od? <??> <??> <??>))) (lambda (ev? od? n) (if (= n 0) false (ev? <??> <??> <??>)))))
Answer: a.
((lambda (n) ((lambda (fib) (fib fib n)) (lambda (f k) (cond ((= k 0) 0) ((= k 1) 1) (else (+ (f f (- k 1)) (f f (- k 2)))))))) 9)
b.
(define (f x) ((lambda (even? odd?) (even? even? odd? x)) (lambda (ev? od? n) (if (= n 0) true (od? ev? od? (- n 1)))) (lambda (ev? od? n) (if (= n 0) false (ev? ev? od? (- n 1))))))
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:
((let? exp) (let->combination exp))
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:
(define (analyze-sequence exps) (define (execute-sequence procs env) (cond ((null? (cdr procs)) ((car procs) env)) (else ((car procs) env) (execute-sequence (cdr procs) env)))) (let ((procs (map analyze exps))) (if (null? procs) (error "Empty sequence -- ANALYZE")) (lambda (env) (execute-sequence procs env))))
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:
(define the-global-environment (setup-environment)) (eval '(define (factorial n) (if (= n 1) 1 (* (factorial (- n 1)) n))) the-global-environment) (time (for-each (lambda (x) (eval '(factorial 35) the-global-environment)) (enumerate-interval 1 10000)))
Results:

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