*

1 files changed, 1008 insertions, 0 deletions

diff --git a/js/games/nluqo.github.io/~bh/61a-pages/Solutions/week12 b/js/games/nluqo.github.io/~bh/61a-pages/Solutions/week12
new file mode 100644
index 0000000..7b8c5a3
--- /dev/null
+++ b/js/games/nluqo.github.io/~bh/61a-pages/Solutions/week12
@@ -0,0 +1,1008 @@
+CS 61A       Week 12 solutions
+
+LAB EXERCISES
+=============
+
+3.  Why doesn't make-procedure call eval?
+
+Because none of the arguments to lambda should be evaluated.
+In particular, the expressions that make up the body of the procedure are
+not evaluated until the procedure is *invoked*!
+
+
+4.1, left-to-right
+
+(define (list-of-values exps env)       ;; left to right
+  (if (no-operands? exps)
+      '()
+      (let ((left (eval (first-operand exps) env)))
+	(cons left (list-of-values (rest-operands exps) env)))))
+
+(define (list-of-values exps env)       ;; right
+  (if (no-operands? exps)
+      '()
+      (let ((right (list-of-values (rest-operands exps) env)))
+	(cons (eval (first-operand exps) env) right))))
+
+
+4.2, Louis reordering
+
+(a)  The trouble is that APPLICATION? cheats.  The book has
+
+(define (application? exp) (pair? exp))
+
+It really should be something like
+
+(define (application? exp)
+  (and (pair? exp)
+       (not (member (car exp) '(quote set! define if lambda begin cond)))))
+
+They get away with the shorter version precisely because EVAL doesn't
+call APPLICATION? until after it's checked for all the possible special
+forms.  Louis (quite reasonably, I think) wants to rely on APPLICATION?
+behaving correctly no matter when it's called.
+
+(b)  All we are changing is the syntax of an application, so we
+change the procedures that define the "application" abstract data type.
+These are on page 372 of the text.  The new versions are:
+
+(define (application? exp)
+  (tagged-list? exp 'call))
+
+(define (operator exp) (cadr exp))
+
+(define (operands exp) (cddr exp))
+
+
+4.4 AND and OR special forms
+
+The book suggests two solutions: make them primitive special forms
+or make them derived expressions.  We'll do both.
+
+As primitive special forms:
+
+Change the COND clause in EVAL by adding
+
+  (cond ...
+	((and? exp) (eval-and exp env))
+	((or? exp) (eval-or exp env))
+	...)
+
+(define (eval-and exp env)
+  (define (iter tests)
+    (cond ((null? tests) #t)
+	  ((null? (cdr tests)) (eval (car tests) env))
+	  ((true? (eval (car tests) env)) (iter (cdr tests)))
+	  (else #f)))
+  (iter (cdr exp)))
+
+(define (eval-or exp env)
+  (define (iter tests)
+    (if (null? tests)
+	#f
+	(let ((result (eval (car tests) env)))
+	  (if (true? result)
+	      result
+	      (iter (cdr tests))))))
+  (iter (cdr exp)))
+
+Now for the derived expression technique.  Modify the COND clause
+in EVAL this way instead:
+
+  (cond ...
+	((and? exp) (eval (and->if (cdr exp)) env))
+	((or? exp) (eval (or->if (cdr exp)) env))
+	...)
+
+(define (and->if exps)
+  (cond ((null? exps) #t)
+	((null? (cdr exps)) (car exps))
+	(else (make-if (car exps)
+		       (and->if (cdr exps))
+		       #f))))
+
+(define (or->if exps)
+  (if (null? exps)
+      #f
+      (make-if (car exps)
+	       (car exps)
+	       (or->if (cdr exps)))))
+
+This version is elegant but has the disadvantage that you end up
+computing the first true value twice.
+
+
+4.5  Cond => notation
+
+(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 "..."))
+	    (IF (COND-ARROW-CLAUSE? FIRST)
+		(LIST (MAKE-LAMBDA '(COND-FOO)
+				   (MAKE-IF 'COND-FOO
+					    (LIST (COND-ARROW-DOER FIRST)
+						  'COND-FOO)
+					    (EXPAND-CLAUSES REST)))
+		      (COND-PREDICATE FIRST))
+		(make-if (cond-predicate first)
+			 (sequence->exp (cond-actions first))
+			 (expand-clauses rest)))))))
+
+(define (cond-arrow-clause? clause)
+  (and (pair? clause)
+       (= (length clause) 3)
+       (eq? (cadr clause) '=>)))
+
+(define (cond-arrow-doer clause)
+  (caddr clause))
+
+This may be a little confusing.  What it does is to turn a clause like
+
+        (test => recipient)
+
+into
+
+        ((lambda (cond-foo)
+	   (if cond-foo
+	       (recipient cond-foo)
+	       <expanded-rest-of-clauses>))
+	 test)
+
+Using the name cond-foo here is a kludge, because what if the user
+has used the same name for some other purpose within the clause?
+The right thing would be to generate an otherwise-untypable symbol
+each time.  But this is complicated enough already.
+
+By the way, this is really trying to do
+
+        (let ((cond-foo test))
+	  (if ...))
+
+but we don't yet have LET in the metacircular Scheme.
+
+It might be easier to do this by abandoning the whole idea of
+cond->if and just implementing cond directly.
+
+
+5b.  In Logo there are no internal definitions; all procedures are global.
+So we need a situation with two procedures, one of which calls the other:
+
+to outer :var
+inner
+end
+
+to inner
+print :var
+end
+
+? outer 23
+23
+
+To see that this result is different from what would happen with lexical
+scope, try the same example in Scheme:
+
+(define (outer var)
+  (inner))
+
+(define (inner)
+  (print var))
+
+> (outer 23)
+Error -- unbound variable: var
+
+(Or you could define a global variable var whose value is something other
+than 23, and then (outer 23) would print that other value.
+
+
+5c.
+
+Logo " is like Scheme ' -- it's the quoting symbol.  But in Logo it is used
+only with words, not with lists, and there is no QUOTE special form which the
+quotation character abbreviates.
+
+Logo [ ] are like '( ) in Scheme -- the brackets both delimit and quote a
+list.  But within a list, brackets are used to delimit sublists, and don't
+imply an extra level of quotation, so Logo [a [b c] d] means '(a (b c) d),
+not '(a '(b c) d).  So, how do you get the effect of Scheme's ( ) without
+quotation?  In Scheme that means to call a procedure; in Logo you don't
+need any punctuation to call a procedure!  You just give the procedure name
+and its arguments.  But in Logo you *can* use parentheses around a procedure
+call just as you would in Scheme.
+
+Logo : means that you want the value of the variable whose name follows the
+colon.  In Scheme the name by itself means this -- if you want the value of
+variable X, you just say X.  The reason this doesn't work in Logo is that
+in Logo procedures aren't just another data type, and a procedure name isn't
+just the name of a variable whose value happens to be a procedure.  (In other
+words, Logo procedures are not first-class.)  In Logo there can be a procedure
+and a variable with the same name, so FOO means the procedure and :FOO means
+the variable.
+
+
+HOMEWORK
+========
+
+4.3  data-directed eval
+
+The table itself could be done in several ways; perhaps the easiest
+is to use the built-in table from chapter 2.  So we say:
+
+(put 'quote 'eval text-of-quotation)
+(put 'define 'eval eval-definition)
+(put 'set! 'eval eval-assignment)
+
+Where the original eval does something other than (foo exp env) we
+have to write an interface procedure.  For example:
+
+(define (eval-lambda exp env)
+  (make-procedure (lambda-parameters exp) (lambda-body exp) env))
+
+(put 'lambda 'eval eval-lambda)
+
+
+(define (eval exp env)
+  (cond ((self-evaluating? exp) exp)
+	((variable? exp) (lookup-variable-value exp env))
+	(else (let ((form (get (operator exp) 'eval)))
+		 (if form       	;; IT'S A SPECIAL FORM
+		     (form exp env)	;; SO form IS THE PROCEDURE TO CALL
+		     (apply (eval (operator exp) env)
+			    (list-of-values (operands exp) env) ))))))
+
+The first two COND clauses deal with atomic expressions: numbers (which
+are self-evaluating) and symbols (which represent variables).  If the
+expression is neither of those, then it's a list, and we look at its
+CAR.  We look that up in the table; if we find it, the expression is a
+special form, and we invoke the particular procedure that knows about
+that special form.  Otherwise, it's a regular procedure.
+We're neglecting various kinds of errors that might occur with mal-formed
+input.
+
+We also have to rewrite text-of-quotation so that it accepts an extra
+input, the environment, even though it doesn't need it:
+
+(define (text-of-quotation exp env)
+  (cadr exp))
+
+And we have to write a new "front end" to cond->if:
+
+(define (eval-cond exp env)
+  (eval (cond->if exp) env))
+
+and put that in the table.
+
+It would also be possible to include the atomic expressions in the
+general data-directed mechanism by assigning them implicit types just as
+we assigned Scheme numbers an implicit type in exercise 2.78, page 193:
+
+(define (expression-type exp)
+  (cond ((self-evaluating? exp) '(() SELF-EVALUATING))
+	((symbol? exp) '(() SYMBOL))
+	((pair? exp) (car exp))
+	(else (error "Unknown expression type" exp))))
+
+(define (eval exp env)
+  (let ((handler (get (expression-type exp) 'eval)))
+    (if handler
+	(handler exp env)
+	(apply (eval (operator exp) env)
+	       (list-of-values (operands exp) env)))))
+
+(put '(() self-evaluating) 'eval (lambda (exp env) exp))
+(put '(() symbol) 'eval lookup-variable-value)
+
+The reason for using (() SYMBOL) instead of just SYMBOL as the type tag
+is that otherwise we'd get in trouble if an expression tried to call a
+procedure named SYMBOL.  These type tags aren't valid Scheme expressions,
+so they shouldn't get us in trouble.
+
+
+4.6  Implementing LET   
+
+;; In eval's big cond we put
+
+	((let? exp) (eval (let->combination exp) env))
+
+;; Now for the guts of the problem:
+
+(define (let->combination exp)
+  (cons (make-lambda (let-formals exp)
+		     (let-body exp))
+	(let-actuals exp)))
+
+;; And now for the data abstraction stuff:
+
+(define (let? exp)
+  (tagged-list? exp 'let))
+
+(define (let-formals exp)
+  (map car (cadr exp)))
+
+(define (let-actuals exp)
+  (map cadr (cadr exp)))
+
+(define (let-body exp)
+  (cddr exp))
+
+
+Please note that this problem becomes MUCH easier if you ruthlessly separate
+the semantics (let->combination) from the mickey mouse work of extracting
+the syntactic components.  I actually wrote this in the order in which it
+appears here; in essence I solved the problem completely before I thought at
+all about syntactic issues.
+
+
+4.7 Implementing Let*
+
+(define (let*->nested-lets exp)
+  (if (null? (let-bindings exp))
+      (make-let '() (let-body exp))
+      (make-let (list (car (let-bindings exp)))
+		(list (make-let* (cdr (let-bindings exp))
+				 (let-body exp))))))
+
+(define (let-bindings exp)
+  (cadr exp))
+
+(define (make-let bindings body)
+  (cons 'let (cons bindings body)))
+
+(define (make-let* bindings body)
+  (cons 'let* (cons bindings body)))
+
+I'm cheating slightly by using LET-BODY for a LET* expression instead
+of inventing a whole new abstract data type.  In principle someone
+might want to change Scheme so that the syntax of LET* looks different
+from the syntax of LET.
+
+
+4.10 new syntax
+
+Okay, let's make the syntax of IF look like it does in those other bad
+languages.  (After all, any change we make to Scheme's syntax *has* to make
+it worse!)  The new syntax will be (if ... then ... else ...).
+
+(define (if? exp)
+  (and (tagged-list? exp 'if)
+       (eq? (caddr exp) 'then)
+       (or (= (length exp) 4)
+	   (eq? (list-ref exp 4) 'else))))
+
+(define (if-predicate exp) (cadr exp))
+
+(define (if-consequent exp) (cadddr exp))
+
+(define (if-alternative exp) (list-ref exp 5))
+
+Of course you can do lots of other changes too, so if you're copying
+last semester's answers next semester, the reader will be suspicious
+if you come up with this choice!  :-)
+
+
+4.11  changed frame representation
+
+(define (make-frame variables values)
+  (attach-tag 'frame (map cons variables values)))
+
+(define (frame-variables frame)
+  (map car (contents frame)))
+
+(define (frame-values frame)
+  (map cdr (contents frame)))
+
+(define (add-binding-to-frame! var val frame)
+  (set-cdr! frame (cons (cons var val) (contents frame))))
+
+As explained in footnote 14 on page 378, the procedures lookup-variable-value,
+set-variable-value!, and define-variable! aren't just above-the-line users of
+the frame ADT, because the latter two use SET-CAR! to modify frames.
+Lookup-variable-value could actually work exactly as written, but the others
+have to be changed, and that one should also be changed, to use ASSOC in
+their SCAN internal procedures.  Basically these will look like the table
+procedures from chapter 3:
+
+(define (lookup-variable-value var env)
+  (define (env-loop env)
+    (DEFINE (SCAN ALIST)
+      (LET ((RESULT (ASSOC VAR ALIST)))
+	(IF RESULT
+	    (CDR RESULT)
+	    (ENV-LOOP (ENCLOSING-ENVIRONMENT ENV)))))
+    (if (eq? env the-empty-environment)
+	(error "Unbound variable" var)
+	(let ((frame (first-frame env)))
+	  (SCAN (CONTENTS FRAME)))))
+  (env-loop env))
+
+(define (set-variable-value! var val env)
+  (define (env-loop env)
+    (DEFINE (SCAN ALIST)
+      (LET ((RESULT (ASSOC VAR ALIST)))
+	(IF RESULT
+	    (SET-CDR! RESULT VAL)
+	    (ENV-LOOP (ENCLOSING-ENVIRONMENT ENV)))))
+    (if (eq? env the-empty-environment)
+	(error "Unbound variable -- SET!" var)
+	(let ((frame (first-frame env)))
+	  (SCAN (CONTENTS FRAME)))))
+  (env-loop env))
+
+(define (define-variable! var val env)
+  (let ((frame (first-frame env)))
+    (DEFINE (SCAN ALIST)
+      (LET ((RESULT (ASSOC VAR ALIST)))
+	(IF RESULT
+	    (SET-CDR! RESULT VAL)
+	    (ADD-BINDING-TO-FRAME! VAR VAL FRAME))))
+    (SCAN (CONTENTS FRAME))))
+
+If I hadn't attached a tag to the frames, this would be harder.
+I wouldn't be able to have an add-binding-to-frame! procedure
+because there wouldn't be anything in an empty frame to mutate.
+Instead, define-variable! would have to get more complicated.
+
+
+4.13  make-unbound   
+
+First, about the design issues:  I see three possibilities.  You can
+require that the symbol be bound in the current environment and remove
+that binding only; you can remove the nearest single binding; or you can
+remove all bindings of that symbol.  Perhaps the best solution in any case
+where it's not obvious what the right semantics is would be to provide
+all three versions: unbind-this-frame, unbind-nearest, and unbind-all.
+That way the user can decide for herself what best suits the application
+at hand.  Failing that, I vote for the second choice: removing the nearest
+binding.  Here's why.  First of all, the third version can be written in
+terms of the second:
+
+(define (unbind-all sym)
+  (cond ((bound? sym)
+	 (unbind-nearest sym)
+	 (unbind-all sym))
+	(else '())))
+
+(This assumes we have a predicate bound? that returns true if there is
+an accesible binding for the symbol.  If we provide any form of unbinding
+we should probably provide that too.)  But the second can't be written in
+terms of the third.  So if we're only having one we should have the more
+flexible one.  I rule out the first (current frame only) because I can
+easily imagine wanting to write a procedure like
+
+(define (cleanup)
+  (make-unbound 'a)
+  (make-unbound 'b)
+  (make-unbound 'c))
+
+that removes global variables at the end of a computation, but this
+wouldn't be possible under the first option.  (Why not?)
+
+I have also implicitly decided another design question: should this be
+a special form that requires an unevaluated symbol, like set!, or should
+it be an ordinary procedure whose actual parameter is evaluated?  In
+order to make things like unbind-all (above) work, it should be an ordinary
+procedure.  (What I want to get unbound is the actual argument to
+unbind-all, not the symbol "sym" itself.)  Then again, I think set! should
+be an ordinary procedure, too, so perhaps you're asking the wrong person.
+
+Trouble is, we can't REALLY make make-unbound an ordinary procedure
+because it has to have access to the environment.  If Scheme were
+dynamically scoped, any procedure in the evaluator could just make a
+free reference to "env" to get the current user environment, but as it
+is we have to have eval treat make-unbound specially.  So we'll make 
+it a special form but still have it evaluate everything.
+
+(define (eval-make-unbound exp env)
+  (define (unbind-in-frame sym frame)
+    (define (remove-not-first-binding vars vals)
+      (if (eq? sym (cadr vars))
+	  (begin (set-cdr! vars (cddr vars))
+		 (set-cdr! vals (cddr vals)))
+	  (remove-not-first-binding (cdr vars) (cdr vals))))
+    (if (eq? sym (car (frame-variables frame)))
+	(begin (set-car! frame (cdr (frame-variables frame)))
+	       (set-cdr! frame (cdr (frame-values frame))))
+	(remove-not-first-binding (frame-variables frame)
+				  (frame-values frame))))
+  (define (env-iter sym env)
+    (cond ((eq? env the-empty-environment) 'okay)
+	  ((memq sym (frame-variables (first-frame env)))
+	   (unbind-in-frame sym (first-frame env)))
+	  (else (env-iter sym (enclosing-environment env)))))
+  (env-iter (eval (cadr exp) env) env))
+
+This is rather messier than one might wish, because if the binding in
+question is the first one in a frame, we have to remove it differently from
+if it's not the first in a frame.  In the first case we mutate the header
+pair of the frame; in the second case we splice elements out of two lists.
+Had this evaluator been written with unbinding in mind, they might have
+picked a different data structure.  Env-iter looks for the first frame in
+which the symbol is bound, then unbinds it in that frame.  Unbind-in-frame
+first checks the first binding specially, then uses remove-not-first-binding
+to check the other bindings.
+
+Strictly speaking, I should have made mutators for the frame
+abstraction.  The obvious choice would be set-frame-variables! and
+set-frame-values!, but actually that only makes sense if we know that
+the frame is represented as two parallel lists.  If the frame is
+represented as an a-list, as in exercise 4.11, then a better choice
+would be set-frame-bindings!.  So the really right thing, to keep
+the abstraction barrier solid, is to have a mutator frame-remove-binding!
+that would be like the unbind-in-frame part of the code above.  It would
+be different for different representations, but would have the same
+effect above the abstraction barrier.
+
+Finally, we have to modify eval, adding
+
+  ((make-unbound? exp) (eval-make-unbound exp env))
+
+to the big cond.
+
+(define (make-unbound? exp)
+  (tagged-list? exp 'make-unbound))
+
+
+
+4.14 why doesn't map work?
+
+This question is about level confusion.  Let's talk about meta-Scheme,
+the one implemented by the metacircular evaluator, and under-Scheme, the
+regular Scheme in which the MCE is written.
+
+Eva defines MAP in meta-Scheme.  In particular, when MAP tries to invoke
+a meta-Scheme procedure for each element of the list, it's doing a
+meta-Scheme invocation.
+
+Louis uses the MAP that's defined in under-Scheme.  When he calls MAP,
+he is giving it a meta-Scheme procedure as its first argument, but it's
+expecting an under-Scheme procedure.  From the point of view of under-Scheme,
+a meta-Scheme procedure isn't a procedure at all -- it's a list whose car
+is the word PROCEDURE.
+
+
+4.15 the halting problem
+
+This is the most famous problem in automata theory, the most elegant proof that
+some things can't be done no matter how sophisticated our computers become.
+The proof was first given using the "Turing machine," an abstract machine
+that's used only for proving theorems.  But the same idea works in any
+formal system that's capable of representing a procedure as data; the key
+element of the proof is the fact that the hypothetical HALTS? is a
+higher-order function.
+
+Suppose that (HALTS? TRY TRY) returns #T.  Then when we call (TRY TRY)
+it says, after argument substitution,
+
+        (if (halts? try try)
+	    (run-forever)
+	    'halted)
+
+But this will run forever, and so (TRY TRY) runs forever, and so
+(HALTS? TRY TRY) should have returned #F.
+
+Similarly, suppose that (HALTS? TRY TRY) returns #F.  Then (TRY TRY)
+turns into the same IF expression shown above, but this time the
+value of that expression is the word HALTED -- that is, it halts.
+So (HALTS? TRY TRY) should have returned #T.
+
+
+4.22  LET in analyzing evaluator
+
+This is easy, given the hint about 4.6.  We don't have to change the
+procedure LET->COMBINATION we wrote for that exercise; since it deals
+entirely with the expression, and not with the values of variables,
+all of its work can be done in the analysis phase.  All we do is
+change this COND clause in EVAL:
+
+	((let? exp) (eval (let->combination exp) env))
+
+to this COND clause in ANALYZE:
+
+	((let? exp) (analyze (let->combination exp)))
+
+
+4.23  Efficiency of analyze-sequence
+
+For a sequence with just one expression, the book's version does the
+following analysis:  First, the body of analyze-sequence is the LET.
+Suppose that the result of analyzing the one expression is PROC.
+Then the variable PROCS will have as its value a list whose only
+element is PROC.  That's not null, so (still in the analysis part)
+we call (LOOP PROC '()).  In LOOP, since (in this case) REST-PROCS
+is null, LOOP just returns PROC.  So if the analysis of EXP gives
+PROC, then the analysis of (BEGIN EXP) also gives PROC.
+
+In the same one-expression case, Alyssa's version returns
+	(lambda (env) (execute-sequence (list PROC) env))
+So every time this execution procedure is called, execute-sequence
+will check that (cdr procs) is empty, which it is, and then
+calls PROC with the environment as its argument.  This test of
+(null? (cdr procs)) is done for every execution, whereas in the
+book's version it was done just once.
+
+How about the two-expression case.  Suppose that the analysis of
+EXP1 gives PROC1, and the anaylsis of EXP2 gives PROC2.  The book's
+version will call, in effect, (loop PROC1 (list PROC2)).  This
+in turn calls (sequentially PROC1 PROC2), which returns
+	(lambda (env) (PROC1 env) (PROC2 env))
+as the execution procedure.  (There is a recursive call to LOOP,
+but it doesn't change the result, because this time the second
+argument is null.)
+
+Alyssa's version makes the execution procedure be
+	(lambda (env) (execute-sequence (list PROC1 PROC2) env)))
+which in effect means
+	(lambda (env)
+	  (cond ((null? (list PROC2)) ...)
+		(else (PROC1 env)
+		      (cond ((null? '()) (PROC2 env)) ...))))
+Each time this is executed, we do two unnecessary checks for
+the nullness of a list -- unnecessary because we already knew
+while doing the analysis how many expressions are in the sequence.
+
+
+4.24  How fast?
+
+Hint:  You'll get the most dramatic results when an expression
+is evaluated over and over, i.e., with a recursive procedure.
+
+
+
+2.  Type checking
+
+When we define a procedure, we don't even look at the parameter
+list; it's just stored as part of the procedure.  That doesn't
+need to be changed.  When do we have to check the type?  We do it
+when we're invoking a procedure, as part of the process of
+binding names to values.  This happens in extend-environment
+and make-frame.  The only change to extend-environment is that it
+has to supply the environment that we're extending to make-frame,
+because make-frame will have to look up the type predicates:
+
+(define (extend-environment vars vals base-env)
+  (if (= (length vars) (length vals))
+      (cons (make-frame vars vals BASE-ENV) base-env)
+      (if (< (length vars) (length vals))
+	  (error "Too many arguments supplied" vars vals)
+	  (error "Too few arguments supplied" vars vals))))
+
+Make-frame, which was trivial before this change, now has some
+real work to do:
+
+(define (make-frame variables values BASE-ENV)
+  (DEFINE (TYPE-CHECK VAR VAL)
+    (IF (AND (PAIR? VAR)
+	     (NOT (APPLY (EVAL (CAR VAR) BASE-ENV)
+			 (LIST VAL))))
+	(ERROR "WRONG ARGUMENT TYPE" VAL)))
+  (DEFINE (SCAN VARS VALS)
+    (COND ((NULL? VARS) #T)
+	  (ELSE (TYPE-CHECK (CAR VARS) (CAR VALS))
+		(SCAN (CDR VARS) (CDR VALS)))))
+  (SCAN VARIABLES VALUES)
+  (cons (JUST-NAMES variables) values))
+
+(DEFINE (JUST-NAMES VARS)
+  (COND ((NULL? VARS) '())
+	((PAIR? (CAR VARS))
+	 (CONS (CADAR VARS) (JUST-NAMES (CDR VARS))))
+	(ELSE (CONS (CAR VARS) (JUST-NAMES (CDR VARS))))))
+
+Another approach would be to try to modify the procedure as it's being
+created (therefore, in make-procedure, called from eval) so that the type
+checks become part of the procedure's body.  This can be done, but it's
+quite tricky to get it right.  For example, in what environment should the
+names of the type predicates be looked up?
+
+It's a real misunderstanding of the problem to write a solution in which
+specific type predicates such as INTEGER? are built into the evaluator.
+If there's a type checking system, it should work for user-defined types
+as well as for primitive types.  For example, I should be able to say
+that an argument must be a prime number, or must be a three-letter word.
+
+  
+
+Extra for Experts
+=================
+
+4.16
+
+(a)
+
+(define (lookup-variable-value var env)
+  (define (env-loop env)
+    (define (scan vars vals)
+      (cond ((null? vars)
+             (env-loop (enclosing-environment env)))
+            ((eq? var (car vars))
+             (LET ((RESULT (car vals)))			  ;; ***
+	       (IF (EQ? RESULT '*UNASSIGNED*)		  ;; ***
+		   (ERROR "UNBOUND VARIABLE" (CAR VARS))  ;; ***
+		   RESULT)))				  ;; ***
+            (else (scan (cdr vars) (cdr vals)))))
+    (if (eq? env the-empty-environment)
+        (error "Unbound variable" var)
+        (let ((frame (first-frame env)))
+          (scan (frame-variables frame)
+                (frame-values frame)))))
+  (env-loop env))
+
+
+(b)
+
+(define (scan-out-defines body)
+  (cond ((null? body) '())
+	((definition? (car body))
+	 (list	  ; body is a list of expressions, we make one-element list
+	  (cons 'let
+		(cons (make-let-variables (definitions body))
+		      (append (make-setbangs (definitions body))
+			      (non-definitions body))))))
+	(else body)))
+
+(define (definitions body)
+  (cond ((null? body) '())
+	((definition? (car body))
+	 (cons (car body) (definitions (cdr body))))
+	(else '())))
+
+(define (non-definitions body)
+  (cond ((null? body) '())
+	((definition? (car body))
+	 (non-definitions (cdr body)))
+	(else body)))
+
+(define (make-let-variables definitions)
+  (map (lambda (def)
+	 (list (definition-variable def) '(quote *unassigned*)))
+       definitions))
+
+(define (make-setbangs definitions)
+  (map (lambda (def)
+	 (list 'set! (definition-variable def) (definition-value def)))
+       definitions))
+
+
+(c)  It should be in make-procedure, because then the scanning is done only
+once, when the procedure is created, rather than every time the procedure
+is called.  (On the other hand, if Scheme printed procedures in a way that
+showed the body, the user might wonder why the body isn't what s/he wrote.)
+
+(define (make-procedure parameters body env)
+  (list 'procedure parameters (scan-out-defines body) env))
+
+
+4.17
+
+The extra frame is created by the LET we introduced into the procedure body.
+The frame itself would matter only if some expressions were evaluated in the
+outer frame rather than the inner one.  But there are no such expressions,
+except for the (QUOTE *UNASSIGNED*) ones we put in the LET, and those don't
+depend on the environment for their values.
+
+We could do it without the extra frame by scanning
+
+(lambda (args...)
+  (define u e1)
+  (define v e2)
+  ...)
+
+into
+
+(lambda (args)
+  (define u '*unassigned*)
+  (define v '*unassigned*)
+  (set! u e1)
+  (set! v e2)
+  ...)
+
+and continuing to use the sequential version of internal DEFINE already in the
+metacircular evaluator.  (This may seem to have no benefit at all, but it does,
+because the local variables U and V are bound before the expressions E1 and E2
+are evaluated, so we can be sure they won't refer to global variables.)
+
+
+4.18 
+
+You can't actually experiment with this question unless you define DELAY
+and CONS-STREAM as special forms in the metacircular evaluator.
+
+The SOLVE procedure would work using the scan-out approach of 4.16, but not
+using the version proposed in this exercise.  The body of SOLVE would be
+
+	(let ((y '*unassigned*) (dy '*unassigned*))
+	  (let ((gensym1 (integral (delay dy) y0 dt))
+		(GENSYM2 (STREAM-MAP F Y)))
+	    (set! y gensym1)
+	    (set! dy gensym2)
+	    y)
+
+In the line in capital letters, stream-map is an ordinary procedure, so its
+argument expressions are evaluated before stream-map is called.  One of the
+arguments is Y, whose value at this point is *unassigned*, so an error will
+result.  This is consistent with the definition of LETREC in the Scheme
+standard.  (Internal DEFINE is defined by the standard to be equivalent to
+LETREC.  See page 16 of the standard, in the course reader, section 5.5.2.
+Then see pages 11-12 for the discussion of LETREC, especially the last
+paragraph of that section.)
+
+
+4.19
+
+This is answered in the footnote: the authors support Alyssa.
+
+One possible way to get what Eva wants is to use the approach of exercise
+4.16, but instead of giving an error if one of the SET! expressions fails,
+move it to the end of the line, so you keep trying until every variable has a
+value or until no further progress can be made.  So in this example it'd be
+
+	(let ((b '*unassigned*) (a '*unassigned*))
+	  (set!-ignoring-errors b (+ a x))
+	  (set!-ignoring-errors a 5)
+	  (if (unassigned? b) (set! b (+ a x)))
+	  (if (unassigned? a) (set! a 5))
+	  (+ a b))
+
+using pseudo-special-forms SET!-IGNORING-ERRORS and UNASSIGNED? that aren't
+defined but whose meanings should be obvious.  You'd have to repeat the IF
+expressions as many times as you have variables, to be sure that any
+dependency order would work.
+
+Even so, an expression such as
+
+	(define (f x)
+	  (define a (+ b 3))
+	  (define b (+ a 4))
+	  (+ a b))
+
+won't work no matter how many times you try the assignments.
+
+
+4.20
+
+(a)
+
+(define (letrec? exp)
+  (tagged-list? exp 'letrec))
+
+(define (letrec->let exp)
+  (cons 'let
+	(cons (map (lambda (var) (list var '(quote *unassigned*)))
+		   (let-formals exp))
+	      (append (map (lambda (var val) (list 'set! var val))
+			   (let-formals exp)
+			   (let-actuals exp))
+		      (let-body exp)))))
+
+Then add a cond clause to EVAL:
+
+	((letrec? exp) (eval (letrec->let exp) env))
+
+
+(b) In the correct version, after transforming the LETREC as on page 389,
+we have
+
+(define (f x)
+  (let ((even? '*unassigned*) (odd? '*unassigned*))
+    (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>))
+
+Evaluating that gives
+
+    global env:  F -> procedure P1
+
+    procedure P1: params (x), body (let ...), global env
+
+When evaluating (F 5), we add
+
+    E1: X -> 5, extends G
+
+The LET expands to a LAMBDA and an invocation:
+
+    procedure P2: params (even? odd?),  body (set! ...)...,  env E1
+
+    E2: EVEN? -> *unassigned*,  ODD? -> *unassigned*,  extends E1
+
+With E2 as the current environment we evaluate the two SET! expressions,
+which create procedures (because of the LAMBDA expressions inside them) and
+change the bindings in E2:
+
+    procedure P3: params (n),  body (if (= n 0) true (odd? ...)),  env E2
+    procedure P4: params (n),  body (if (= n 0) false (even? ...)),  env E2
+
+    E2: EVEN? -> procedure P3,  ODD? -> procedure P4,  extends E1
+
+Note that P3 and P4 are created in E2, so they have access to the bindings
+for EVEN? and ODD?.
+
+Then we evaluate the remaining expression in the body of F, which can use
+EVEN? and ODD? successfully.
+
+By contrast, Louis wants us to evaluate
+
+(define (f x)
+  (let ((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>))
+
+This time, when evaluating (F 5), we still add
+
+    E1: X -> 5, extends G
+
+The LET expands to a LAMBDA and an invocation with procedures as arguments:
+
+    ((lambda (even? odd?) <rest of body>)
+     (lambda (n) (if (= n 0) true (odd? (- n 1))))
+     (lambda (n) (if (= n 0) false (even? (- n 1)))))
+
+The three LAMBDA expressions give us
+
+    procedure P2: params (even? odd?),  body <rest of body>,  env E1
+    procedure P3: params (n),  body (if (= n 0) true (odd? ...)),  env E1
+    procedure P4: params (n),  body (if (= n 0) false (even? ...)),  env E1
+
+We can then invoke P2 with P3 and P4 as its arguments:
+
+    E2: EVEN? -> procedure P3,  ODD? -> procedure P4,  extends E1
+
+In this environment we evaluate <rest of body>.  Suppose it's a simple
+expression: (EVEN? X).  First we evaluate the subexpressions.  In E2 we
+find the binding EVEN? -> P3.  There's no binding for X in frame E2, but
+it extends E1, where we find X -> 5.  Now we invoke P3 by making a new
+environment:
+
+    E3: N -> 5, extends E1
+
+Note that E3 extends E1, not E2, because E1 is where P3 was created.
+
+With E3 as the current environment we evaluate the body of P3, which is
+
+    (if (= n 0) true (odd? (- n 1)))
+
+We easily evaluate (= N 0) and get the answer #F.  We then try to evaluate
+
+    (odd? (- n 1))
+
+But there is no binding for ODD? in E3, including the frames it extends.
+That's why LET instead of LETREC isn't sufficient.
+
+
+4.21
+
+We've actually seen this idea before, in the Extra for Experts in week 2.
+
+(a) FIB without DEFINE/LETREC
+
+((lambda (n)
+   ((lambda (fib) (fib fib n))
+    (lambda (fb k)
+      (if (< k 2)
+	  k
+	  (+ (fb fb (- k 1))
+	     (fb fb (- k 2)))))))
+ 10)
+
+
+(b) EVEN?/ODD? ditto
+
+(define (f x)
+  ((lambda (even? odd?)
+     (even? even? odd? x))
+   (lambda (ev? od? n)		; This is EVEN?
+     (if (= n 0) true (OD? EV? OD? (- N 1))))
+   (lambda (ev? od? n)		; This is ODD?
+     (if (= n 0) false (EV? EV? OD? (- N 1))))))