Homework 6 solutions

1.
(define (eval-or exp env)
  (cond ((null? exp) 'nay)
        ((not (eq? (car exp) 'nay)) (car exp))
        (else (eval-or (cdr exp) env))))

(define (or-exp? exp)
  (eq? (car exp) 'or))

Then, add this to the cond for mc-eval, before
the list? exp condition

((or-exp? exp) (eval-or exp env))

2.
SICP 4.6
(BH)
;; 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.
)

3.
SICP 4.14
BH explanation
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.

(define (mce-map proc L)
  (if (null? L)
      '()
      (cons (mc-apply proc (list (car L)))
            (mce-map proc (cdr L)))))

Then we can install this primitive in the list of primitives:

(define the-global-frame
  (cons (list '+ '- '/ '* 'car 'cdr 'cons 'null? 'nil 'yell 'square 'factorial
               '=   '<    'list 'map)
        (list + - / * car cdr cons new-null? nil yell square factorial
              new-= new-<  list mce-map))

4.
(define (eval-and-set! var val)
  (if (symbol? var)
      (set-variable-value! var val the-global-env)
      (error "not a symbol")))

Note that the evaluator evaluates var and val before calling
the eval-and-set! primitive.
And we can install this the same way as map:

(define the-global-frame
  (cons (list '+ '- '/ '* 'car 'cdr 'cons 'null? 'nil 'yell 'square 'factorial
               '=   '<    'list 'eval-and-set!)
        (list + - / * car cdr cons new-null? nil yell square factorial
              new-= new-<  list eval-and-set!))

5.
(BH)
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.

6.
(BH)
SICP 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.

7.

4.25  UNLESS in normal vs. applicative order
(BH)
In ordinary (applicative order) Scheme, this version of FACTORIAL
will be an infinite loop, because the argument subexpression
(* n (factorial (- n 1))) is evaluated before UNLESS is called,
whether or not n is 1.

In normal order Scheme it'll work fine, because the argument
subexpressions aren't evaluated until they're needed.  What
will actually happen is that each use of the special form IF
within UNLESS will force the computation of (= n 1), but
no multiplications will happen until the evaluator tries to
print the result.  In effect, (factorial 5) returns the thunk
        (lambda () (* 5 (* 4 (* 3 (* 2 (* 1 1))))))
and that gets evaluated just in time to print the answer.


4.26  Normal order vs. special forms
(BH)
For Ben's side of the argument we must implement UNLESS as a
derived expression:

(define (unless->if exp)
  (make-if (unless-predicate exp)
	   (unless-consequent exp)
	   (unless-alternative exp)))

(define unless-predicate cadr)
(define unless-alternative caddr)
(define unless-consequent cadddr)

Notice that we reversed the order of the last two subexpressions in
the call to make-if.

Then we just add a clause
        ((unless? exp) (eval (unless->if exp) env))
to the ordinary metacircular evaluator, or
        ((unless? exp) (analyze (unless->if exp)))
to the analyzing evaluator.

For Alyssa's side of the argument, we need a case in which it's useful to
have a Scheme special form available as an ordinary procedure.  The only
thing we can do with ordinary procedures but not with special forms is use
them as arguments to higher-order procedures.  An example using UNLESS will
be a little strained, so first we'll look at a more common situation
involving a different special form, namely AND.  We'd like to be able to say

(define (all-true? tf-list)
  (accumulate and tf-list))

Now, here's the strained example using UNLESS:  Suppose we have a list of
true-false values and we'd like to add up the number of true ones.  Here's a
somewhat strange way to do it:

(define zero-list (cons 0 '()))
(set-cdr! zero-list zero-list)

(define one-list (cons 1 '()))
(set-cdr! one-list one-list)

(define (howmany-true tf-list)
  (apply + (map unless tf-list zero-list one-list)))

Zero-list is an infinite list of zeros; one-list is an infinite list
of ones.  We make use of the fact that MAP's end test is that its
first argument is empty, so MAP will return a list the same size as
the argument tf-list.  For example, if tf-list is
        (#t #t #f #t)
then map will return
        (1 1 0 1)
created, in effect, this way:
        (list (unless #t 0 1)
	      (unless #t 0 1)
	      (unless #f 0 1)
	      (unless #t 0 1))
And so + will return 3, the number of trues in the list.

4.27
count ---> 1 ; When we do (define w (id (id 10))). it calls the outer id,
             ; but thunks its argument, (id 10). It increments count in
             ; the body and returns x which evaluates to the thunk for (id 10),
             ; which is assigned to w.
w ---> 10 ; The evaluator forces the thunk for (id 10), which was assigned
          ; to above, which increments count for a second time, and returns 10
count ---> 2 ; so by this time count has been incremented twice, and so it
             ; evaluates to 2.

8.
SICP 4.32  Lazy trees
(BH)

One possibility is to use doubly-lazy lists as an alternative to
interleaving, when dealing with a naturally two-dimensional problem.
For example, to get pairs of integers, we could say

(define (pairs a b)
  (cons (map (lambda (x) (cons (car a) x)) b)
	(pairs (cdr a) b)))

Then we could use this data structure with two-dimensional versions
of the usual higher order procedures.  For example:

(define (2dfilter pred s)
  (if (null? s)
      '()
      (cons (filter pred (car s))
	    (2dfilter pred (cdr s)))))


4.33  Quoted lazy lists
(BH)

Instead of
        ((quoted? exp) (text-of-quotation exp))
we need a more complicated treatment to turn the ordinary lists
of the underlying Scheme into lazy lists.

        ((quoted? exp) (process-quotation (text-of-quotation exp) env))

(define (process-quotation quoted env)
  (if (pair? quoted)
      (lazy-cons (process-quotation (car quoted) env)
		 (process-quotation (cdr quoted) env)
		 env)
      quoted))

(define (lazy-cons x y env)
  (make-procedure '(m) (list (list 'm x y)) env))

or alternatively

(define (lazy-cons x y env)
  (apply (lookup-variable-value 'cons env)
	 (list x y)))

This lazy-cons is the below-the-line equivalent of the above-the-line
CONS on page 409.

9.

SICP 4.35
(define (an-integer-between low high)
  (if (> low high)
      (choose)
      (choose low (an-integer-between (+ low 1) high))))

SICP 4.36 all Pythagorean triples
(BH)
Replacing an-integer-between with an-integer-starting-from won't
work because the AMB that provides the value for K will never fail,
and so I and J will always be 1 forever.

To make this work, we note that K must always be larger than I or J,
so I and J can be restricted to finite ranges if we choose a value
for K first:

(define (a-pythgorean-triple)
  (let ((k (an-integer-starting-from 1)))
    (let ((i (an-integer-between 1 (- k 1))))
      (let ((j (an-integer-between i (- k 1))))
	(require (= (+ (* i i) (* j j)) (* k k)))
	(list i j k)))))

10.
SICP 4.42 liars
(BH)
(define (liars)
  (define (onetrue? x y)
    (if x (if y #f #t) y))
  (let ((betty (amb 1 2 3 4 5))
	(ethel (amb 1 2 3 4 5))
	(joan (amb 1 2 3 4 5))
	(kitty (amb 1 2 3 4 5))
	(mary (amb 1 2 3 4 5)))
    (require (distinct? (list betty ethel joan kitty mary)))
    (require (onetrue? (= kitty 2) (= betty 3)))
    (require (onetrue? (= ethel 1) (= joan 2)))
    (require (onetrue? (= joan 3) (= ethel 5)))
    (require (onetrue? (= kitty 2) (= mary 4)))
    (require (onetrue? (= mary 4) (= betty 1)))
    (list (list 'betty betty) (list 'ethel ethel) (list 'joan joan)
	  (list 'kitty kitty) (list 'mary mary))))

As in the multiple dwelling puzzle, this program can be made much more
efficient by checking for distinct values as we go along instead of
after all values have been assigned:

(let ((betty (amb 1 2 3 4 5))
      (ethel (amb 1 2 3 4 5)))
  (require (distinct? (list betty ethel)))
  (let ((joan (amb 1 2 3 4 5)))
    (require (distinct? (list betty ethel joan)))
    ...