MT3 Review Solution:

-- Environment Diagram
Use EnvDraw to verify

-- List Mutations
1.
The easiest way to do a problem like this is to use a LET in which
you give names to every relevant piece of the list structure.  Then,
inside the LET, you can mutate the pairs in any old order without
risk of error:

(define (make-alist! lst)
  (if (null? lst)
      'done
      (let ((car1 (car lst))
	    (cdr1 (cdr lst))
	    (car2 (cadr lst))
	    (cdr2 (cddr lst)))
	(set-car! lst cdr1)
	(set-cdr! lst cdr2)
	(set-car! cdr1 car1)
	(set-cdr! cdr1 car2)
	(make-alist! cdr2))))

But that's more work than is really needed.  If you're clever about
the order in which you do the mutation, you can get by with only one
temporary variable.  There are several such solutions; here's one:

(define (make-alist! lst)
  (if (null? lst)
      'done
      (let ((tmp (cddr lst)))
	(set-cdr! (cdr lst) (cadr lst))
	(set-car! (cdr lst) (car lst))
	(set-car! lst (cdr lst))
	(set-cdr! lst tmp)
	(make-alist! tmp))))


2.
(define (list-rotate! n seq)
  (define (one-round! l first-e)
    (if (null? (cdr l))
	(set-car! l first-e)
	(begin 
	  (set-car! l (cadr l))
	  (one-round! (cdr l) first-e))))
  (if (= n 0)
      seq
      (begin
	(one-round! seq (car seq))
	(list-rotate! (- n 1) seq))))

Notice that the following code is wrong!

(define (list-rotate! n seq)
  (if (= n 0)
      seq
      (begin 
	(let ((end (last-pair seq))
	      (old-first seq) 
	      (new-first (cdr seq)))
	  (set-cdr! end seq)
	  (set-cdr! old-first ())
	  (list-rotate! (- n 1) new-first)))))

(define (last-pair l)
  (if (null? (cdr l))
      l
      (last-pair (cdr l))))

Since the original variable does not point to the beginning of 
the mutated list. It still points to the first pair in the 
original list.

-- Vector
1.
(define (vector-lookup key)
  (define (iter index)
    (cond ((< index 0) #f)
 	  ((eq? key (vector-ref v-keys index))
		(vector-ref v-values index))
	  (else
		(iter (- index 1)))))
 (iter (- (vector-length v-keys) 1)))

2.
(define (vector-swap! v i j)
  (let ((temp (vector-ref v i)))
    (vector-set! v i (vector-ref v j))
    (vector-set! v j temp)))

(define (vector-reverse! v)
  (define (iter i j)
    (if (>= i j)
	v
	(begin (vector-swap! v i j)
	       (iter (+ i 1) (- j 1)))))
  (iter 0 (- (vector-length v) 1)))


-- Concurrency
1.  100, -15, 45, -10, -5, -30


2.  
a) Incorrect
b) Neither
c) Neither
d) Neither
e) Deadlock