Fourth Chapter
This chapter contains solutions to exercises from the fourth chapter of the SICP book.
To run the evaluator under DrRacket you must perform the following changes to the original sources:
- Add the
#lang planet neil/sicpdirective at the beginning of each file.- Rename
applytoapply-custom(or something else), as needed.
Exercise 4.1
(define (list-of-values-left->right exps env)
(if (no-operands? exps)
'()
(let ((x (eval (first-operand exps) env)))
(let ((y (list-of-values-left->right (rest-operands exps) env)))
(cons x y)))))
(define (list-of-values-right->left exps env)
(if (no-operands? exps)
'()
(let ((x (list-of-values-right->left (rest-operands exps) env)))
(let ((y (eval (first-operand exps) env)))
(cons y x)))))
We enforce ordering by nesting two let statements. In the code, you should comment out the original version, and simply introduce (define list-of-values <one of the above variant>). You may then test your code by executing the evaluator.
Exercise 4.2
Part a
Louis's evaluator will try to treat the expression (define x 3) as an application instead of definition. Similarly, a sequence starting with begin would also be attempted as application.
Part b
See the file chapter4/exercise4.2.rkt. To make the solution self-contained it includes the whole evaluator modified to support call. The only additional change (besides changing the order of cond clauses in eval) is related to the procedure application? and the matching selectors for the operator and operands.
Exercise 4.3
See the file chapter4/exercise4.3.rkt. The eval procedure is now really sleek and stable, and it looks like as follows:
(define (eval exp env)
(cond ((self-evaluating? exp) exp)
((variable? exp) (lookup-variable-value exp env))
((built-in-proc? exp) (eval-built-in-proc exp env))
((application? exp)
(apply-custom (eval (operator exp) env)
(list-of-values (operands exp) env)))
(else
(error "Unknown expression type -- EVAL" exp))))
The table structure reused from section 3.3.3 is 2-dimensional, and we use an artificial first key of 'keyword. The table is setup at the end of the code. The dispatching mechanism is basically the same as in exercise 2.73.
Subsequent solutions will use this version of the evaluator.
Exercise 4.4
See the file chapter4/exercise4.4.rkt. For a detailed explanation of implementing and and or as derived expressions take a look at the Instructor's Manual for the SICP book (page 126).
Exercise 4.5
See the file chapter4/exercise4.5.rkt. The expand-clauses procedure was restructured to incorporate a new case, as asked in this exercise (observe the new cond-impl-clause? procedure). The list of primitive procedures have been expanded with assoc and cadr, so that you may directly evaluate the test expression given in the SICP book.
Exercise 4.6
See the file chapter4/exercise4.6.rkt.
Exercise 4.7
Here is the let* expression of this exercise rewritten as a set of nested let expressions:
(let ((x 3)) ; (var1 exp1)
(let ((y (+ x 2))) ; (var2 exp2)
(let ((z (+ x y 5))) ; (var3 exp3)
(* x z)))) ; body
See the file chapter4/exercise4.7.rkt. We don't have to explicitly expand let* in terms of non-derived expressions. Nonetheless, for performance reasons we should do that, since we already have two levels of indirection (let was also implemented as a transformation to lambda).
The list of primitives have been extended with * and +, so that you may evaluate the provided let* expression.
Exercise 4.8
See the file chapter4/exercise4.8.rkt. The list of primitives have been extended with = and -, so that you may evaluate the provided expression and calculate Fibonacci numbers.
It is very easy to make a mistake in the implementation by allowing bindings to "see" the
<var>. The code must report an error when trying to evaluate(let test ((x test)) 1). The correct implementation must augment the body itself with an internal procedure definition.
Exercise 4.9
For loop
We can emulate Python's for loop by introducing the following syntax:
(for (<var> in <list-of-values>) <body>)
For example, we may print on each line the names of days in a week by issuing:
(for (name-of-day in '(Monday Tuesday Wednesday Thursday Friday Saturday Sunday))
(display name-of-day)
(newline))
The for loop can be translated as:
(let *iter* ((*list-of-values* <list-of-values>))
(if (not (null? *list-of-values*))
(let ((<var> (car *list-of-values*)))
<body>
(*iter* (cdr *list-of-values*)))))
The *iter* and *list-of-values* may potentially collide with existing names, but the probability is very low.
While loop
The while loop can be described as:
(while <predicate> <body>)
Here is a sample usage:
(define (num-divisors a)
(let ((count 0)
(divisor 1))
(while (< divisor a)
(if (= (remainder a divisor) 0)
(set! count (+ count 1)))
(set! divisor (+ divisor 1)))
count))
The while loop can be translated as:
(let *iter* ()
(if <predicate>
(begin
<body>
(*iter*))))
For the sake of completeness, here is the full translation of the above example using this template:
(define (num-divisors a)
(let ((count 0)
(divisor 1))
(let *iter* ()
(if (<= divisor a)
(begin
(if (= (remainder a divisor) 0)
(set! count (+ count 1)))
(set! divisor (+ divisor 1))
(*iter*))))
count))
Exercise 4.10
The previous exercise nicely illustrates the possibility to change a syntax without modifying eval or apply. By introducing those two loops (both of them are syntactic sugars) the code mirrors an imperative programming style (especially the last example with classical assignments to variables). Another small change of a syntax was demonstrated in part b of exercise 4.2.
Exercise 4.11
See the file chapter4/exercise4.11.rkt. Only procedures related to frames (inside section 4.1.3) have been altered, as expected.
Exercise 4.12
See the file chapter4/exercise4.12.rkt. Notice that the procedures set-variable-value!, define-variable!, and lookup-variable-value are now expressed as single calls to our new abstractions. There is no more code duplication.
Exercise 4.13
See the file chapter4/exercise4.13.rkt. The following list enrolls the major design choices for this special form:
- It removes only the binding in the first frame of the environment. This limits the danger of unforeseen side-effects caused by pruning away some symbol from the enclosing environment(s). Moreover, this decision keeps deletion of symbols in symmetry with creation of new bindings for variables (these also alter only the current environment).
- Removing an unknown symbol has no effect.
- It is impossible to judge whether a removal is safe in all circumstances, so there is no attempt to prevent mistakes (for example, removing a symbol referenced from other places).
- Unbinding a variable does not imply completely reclaiming the matching memory. We will just set the name & value of the symbol to
nullinstead of fully making the corresponding items from the lists (variable names and values) amenable for garbage collection. This will keep the implementation simple.
Exercise 4.14
The main problem with Louis's approach is the mixup of two different realms: Scheme and our metacircular evaluator. Even though they interpret the same programming language, they belong to separate domains. Let us see what happens when we try to "bridge" these two domains by using map as a primitive procedure. Enter the next expression:
(map (lambda (x) (* x x)) '(1 2 3 4))
The evaluator will spill out an error message instead of printing (1 4 9 16). If you look into the eval procedure, then you will see that the arguments to map are first evaluated inside our evaluator. The lambda expression is converted and tagged with procedure. Only as a last step we execute the built-in apply procedure. Nonetheless, map gets confused with what it receives (read footnote 21 in the SICP book).
Exercise 4.15
The reasoning here applies the proof by contradiction technique. We can have two outcomes from executing (try try): halted and running forever. Let us see the implications:
- If the program halts, then
halts?wrongly judged thattrywill never halt. - If the program enters an infinite loop, then
halts?wrongly assumed thattrywill halt.
In both cases, we reach a contradiction. This means that the initial assumption about the existence of such a procedure halts? is incorrect.
Exercise 4.16
See the file chapter4/exercise4.16.rkt (contains all parts). The make-procedure is a better place to put our scanning routine. A procedure is defined only once, and used many times later. Therefore, it is better to transform the body during construction time.
Exercise 4.17
The environment structures when definitions are interpreted sequentially (left side) and scanned out (right side) look like as follows:
global +-----------------------+ global +--------------------------+
------>| | ------>| |
+-----------------------+ +--------------------------+
^ ^
| |
E1 +-----------------------+ E1 +--------------------------+
------>| <vars> | ------>| <vars> |
| u: <e1> | +--------------------------+
| v: <e2> | ^
+-----------------------+ |
E2 +--------------------------+
------>| u: '*unassigned* -> <e1> | both set! execute
| v: '*unassigned* -> <e2> | in E2
+--------------------------+
An extra frame is due to the placement of <e3> inside an internal procedure's body, which is created by let. A correct program would never try to use an uninitialized variable, so the fact that <e1> and <e2> may refer to each other makes no difference.
To avoid an extra frame, the custom apply procedure would need to be expanded with an environment bootstrapping step. Besides extending the compound procedure's environment with its parameters, it would be also augmented with definitions set to some special value (similarly to our scanning solution). Consequently, the procedure's body would be evaluated with forward declarations already in place.
Exercise 4.18
The solve procedure will not work if internal definitions are scanned out as shown in this exercise. If they are scanned out as shown in the text, then it will work. The streams y and dy are mutually referencing each other. The y's first value is y0, which is needed by dy to provide its first value back to y, and so forth. In this case, via delayed execution (recall that delay is a special form) and careful orchestration, the program is correct. Unfortunately, if we restrict the visibility (by setting both variables to a special marker), then it would be impossible to evaluate the matching definitions, nor initiate the stream processing.
Exercise 4.19
I prefer Alyssa's viewpoint (as implemented in exercise 4.16). This is a most conservative alternative, which prevents confusing program constructs via ambiguous cross references. The example from the previous exercise is different; the solve procedure was carefully crafted and explicit in its intention. Eva'a notion (and footnote 26 from text) is not quite friendly in regard to maintenance of large code bases. Difficult simultaneous definitions are incomprehensible, and should be avoided regardless whether there is some efficient mechanism to support them.
One way to implement Eva's desire is to have a multi-pass based procedure application mechanism. This would work in principle as given in exercise 4.17, but instead of eagerly marking all variables as uninitialized, they would be evaluated. Those whose evaluation succeeds would be set to their final value. The cycle would continue until no progress can be made. At this point either all of them would be properly settled, or an error discovered (for a truly impossible case).
Exercise 4.20
Part a
See the file chapter4/exercise4.20.rkt. The letrec->let and our previous scan-out-defines are sharing couple of procedures, which are exposed to both of them.
Part b
The environment structures when using letrec (left side) and let (right side) look like as follows:
global +-----------------------+ global +-----------------------+
------>| f: ... | ------>| f: ... |
+-----------------------+ +-----------------------+
^ ^
| |
E1 +-----------------------+ E1 +-----------------------+
------>| x: 5 | ------>| x: 5 |
| even?: ... | +-----------------------+
| odd?: ... | ^ ^ ^
+-----------------------+ | | |
^ ^ E3 +-------+ | E2 +------------+
| | ------>| n | | ------>| even?: ... |
E2 +-------+ E3 +-------+ +-------+ | | odd?: ... |
------>| n | ---->| n | | +------------+
+-------+ +-------+ |
|
E4 +-------+
------->| n |
+-------+
As an illustration, here is a sequence of interactions with the Scheme interpreter (notice the different error messages with letrec and let):
> (define (test-letrec) (letrec ((u v) (v u)) 'ok))
> (test-letrec)
. . v: undefined;
cannot use before initialization
>
> (define (test-let) (let ((u v) (v u)) 'ok))
> (test-let)
. . v: undefined;
cannot reference an identifier before its definition
This difference is understandable if you consider the above environment diagrams.
Exercise 4.21
Part a
The program outputs 3628800, which is indeed 10!. Below is the snippet for calculating Fibonacci numbers in a similar fashion:
((lambda (n)
((lambda (fib)
(fib fib n))
(lambda (f k)
(if (< k 2)
k
(+ (f f (- k 1)) (f f (- k 2)))))))
10)
This will print 55, which is the 10th Fibonacci number. I suggest that you read the article The Why of Y to get more insight about the Y operator.
Part 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
You just need to copy over your solution from exercise 4.6, and add the following line (for example, after testing for cond) to the analyze procedure:
((let? exp) (analyze (let->combination exp)))
Exercise 4.23
When a sequence has just one expression, then the execution procedure produced by the program in the text will simply invoke the analyzed expression. Alyssa's program would call the internal execute-sequence procedure with a single element list, check that there are no more elements, and invoke the first analyzed expression.
With two expressions, the original program would directly invoke the following procedure encompassing the analyzed expressions:
(lambda (env) (proc1 env) (proc2 env))
Allyssa'a variant would perform two iterations over the list to invoke these procedures.
Exercise 4.24
The best way to notice the difference is to measure execution time for recursive procedures (like the factorial as mentioned in the SICP book). There is no performance gain for procedures that are invoked only once during the life time of a program. At any rate, the speedup is significant.
Exercise 4.25
In applicative-order Scheme, if we attempt to evaluate (factorial 5), then we will enter an infinite loop. This will not happen in case of normal-order evaluation.
Exercise 4.26
See my Solutions Guide for the Instructor's Manual of SICP (exercises M4.2-M4.4) for an example how to fully implement unless as a macro in an applicative-order language. Of course, every macro is a special form. Having unless available as an ordinary procedure may be sometimes handy. For example, it could be used to implement a selector (alternator) between elements of two collections (see a code excerpt here).
Exercise 4.27
The values printed are given below (in the same order as asked in this exercise):
- 1 - The variable
wis defined as(id (id 10)). Its return value is actually a thunk(id 10)(represented as an argumentx). Nonetheless, during the execution of the body of the procedureid(with lazy argumentx) it does incrementcountonce. - 10 - This is the result we get by forcing the thunk
(id 10)to execute. - 2 - In the previous step, the counter was again incremented by one, so we get 2 here.
Exercise 4.28
This is what the textbook says: "We still evaluate the operator, because apply needs the actual procedure to be applied in order to dispatch on its type (primitive versus compound) and apply it." The need for forcing arises when we want to apply a procedure passed as an argument inside the body of our procedure. Recall that all arguments are tagged with 'thunk, and our custom apply would throw an error, if we try to directly use such a lazy argument.
Exercise 4.29
Any recursive procedure where an argument (or many of them) is evaluated more once inside a body would run much more slowly without memoization than with memoization. This is especially true, if evaluating the argument itself is expensive.
The responses when the evaluator memoizes are 100 and 1. When it does not then they are 100, and 2.
Exercise 4.30
Part a
Ben is right due to a combined effects of the following rules:
- Our
evalprocedure evaluates the operator (see exercise 4.28), and procedure invocations inside a sequence will always be triggered (standard behavior ofevalfor an expression, which is a procedure call). - Any application of a primitive procedure (like
displayin this case) will force the evaluation of its arguments.
All in all, both procedures inside a sequence will run, and the (car items) expression will be triggered when applying display.
Part b
The values of (p1 1) and (p2 1) with the original eval-sequence are (1 2) and 1, respectively. Cy's variant will result in the same behavior of p1 and p2, and the output will be (1 2) and (1 2).
Part c
The actual-value is calling force-it, which simply returns the original expression if it is not a thunk (or evaluated thunk). All the rest performs as explained in part a.
Part d
Cy's approach correctly enforces side-effects, when evaluating a sequence (all steps in a sequence, except the last one, are useful for their side-effects). Furthermore, the lazy evaluation strategy should preserve the semantics of a normal-order language, so I prefer Cy's version (see also footnote 32).Of course, this cannot be achieved at this moment with memoization (see also the next exercise).
Exercise 4.31
See the file chapter4/exercise4.31.rkt (contains all parts). The solution is based on tagging the thunks with 'memo and 'non-memo, depending on whether memoization is needed or not. The custom apply procedure must extract the called procedure's parameters, and pass it down while evaluating the arguments of the call. The delay-it and force-it procedures have been augmented, too.
Exercise 4.32
The major differences are enrolled below:
- Even the first element of a stream is delayed. This renders obsolete the need to manually sprinkle
delaystatements. - With delayed lists we have solved the missing link between lists and streams. Handling them in the same fashion surely benefits maintenance.
The paper Why Functional Programming Matters contains many examples of lazy evaluation including lazy trees. See also footnoe 41 from the textbook.
Exercise 4.33
See the file chapter4/exercise4.33.rkt. The code is based on the original lazy evaluator rather than the version developed in exercise 4.31 (look at the modified text-of-quotation procedure). It assumes that you have entered the new definitions of cons, car and cdr, as defined in the textbook. If you now evaluate (car (car (cdr (cdr '(a b (c d)))))) you will get c.
Exercise 4.34
See the file chapter4/exercise4.34.rkt. This exercise builds upon the previous one. The following major changes have been made:
- The built-in
cons,car, andcdrprocedures are now available asscheme-cons,scheme-car, andscheme-cdr, respectively. - The custom
cons,car, andcdrprocedures are inserted into the evaluator at startup. A lazy pair/list is tagged with'lazy-pair. - The procedure
user-printhandles the printing of all sorts of objects including lazy pairs/lists. It incorporates the material from the Instructor's Manual for the SICP book. The parameterncontrols the maximum number of printed elements (to protect against infinite structures).