;; PROBLEM 1:  100, -15, 45, -10, -5, -30, 25

;; PROBLEM 2.

#|
Which of the following interactions will execute faster, slower, or
the same in the analyzing evaluator than in the original MCE?

i)
     > (define (gauss-recur n)
	 (if (= n 1)
	     1
	     (+ n (gauss-recur (- n 1)))))
     > (gauss-recur 1000)

GAUSS-RECUR is a recursive procedure for computing the sum of all
the integers from 1 to n, making n procedure calls in the process.
Since it gets called 1000 times in this interaction, its body must
be evaluated 1000 times.  This is *faster* in the analyzing
evaluator, because the work of determining the meaning of the
expressions in the body is done only once.

In the original metacircular evaluator, much work is involved in
determining the kind of expression being evaluated.  EVAL has to
ask whether the expression is a number or a variable or a list
starting with QUOTE or a list starting with SET!, etc.	In the case
of GAUSS-RECUR, EVAL has to do this not only for the IF, but also
for two of the subexpressions and *their* subexpressions, and so on.
When the evaluator finally gets to the point where it makes the
recursive call, it starts over with the body of GAUSS-RECUR, as if
it has never seen it before.

The analyzing evaluator still has to do all of this work, but it
does it once, when GAUSS-RECUR is defined, instead of every time
GAUSS-RECUR is called.	It figures out ahead of time that the body
contains an IF and that the predicate expression wants to call a
procedure named `=', among other things.  It packages its
discoveries into a fast underlying Scheme procedure that takes an
environment and produces the result of the expression in that
environment.  When a recursive call is made, the same underlying
Scheme procedure is reused, and the slow process of dissecting
the original code is not repeated.

ii)
     > (define (gauss n)
	 (/ (* (+ n 1) n) 2))
     > (gauss 1000)

GAUSS, given a positive integer, computes the same result as GAUSS-
RECUR through the use of a mathematical trick.	Contrary to what
some people thought, this program is *not* faster in the analyzing
evaluator.  As explained above, the analyzing evaluator saves time
by avoiding repeated work, specifically the work of analyzing a
given expression more than once.  But there is no repeated work
here; GAUSS is called only once!  If we called GAUSS more than once,
then we could save some time.

So is this interaction slower if we analyze the expressions, or is
its running time unchanged?  The answer we expected was SAME, which
is almost true.	 It turns out that the analyzing evaluator has a
trivial amount of overhead for making those fast underlying Scheme
procedures, potentially making it slightly slower.  We accepted
either SLOWER or SAME for this question.

|#

;; PROBLEM 3: 1	 2  5  12  29  70  169

;; PROBLEM 4.
(define cxr-stream
  (cons-stream car
	       (cons-stream cdr
			    (interleave
			     (stream-map
			      (lambda (fn) (compose car fn)) cxr-stream)
			     (stream-map
			      (lambda (fn) (compose cdr fn)) cxr-stream)))))

;; PROBLEM 5.

#|
(a) The define statement goes into an infinite loop.  When we evaluate 
    stream-accumulate, we will go into the else clause, and have to call 
    stream-accumulate again on the stream-cdr of integers, which does the 
    same thing again.  The problem is, NOTHING IS DELAYED.
      
(b) The define statement is fine (since stream-accumulate is delayed).	
    But when you call stream-cdr on bar, then you will wait a very long time
    for the answer.
      
(c) So the question is, does THIS delay anything?  It looks like it does.  
    If the combiner uses cons-stream, then it seems that we will delay the 
    evaluation of y, which is the next call to accumulate.  Alas, that is 
    making the same mistake as believing new-if would work.  Whereas 
    cons-stream is a special form, the combiner is NOT, and so it will 
    evaluate both of its arguments --- including the call to accumulate ---
    before evaluating its body.	 So the problem persists.
|#

;; PROBLEM 6.

(define (catch-cheaters v)
  (define (compare v1 v2 n idens)
	(cond ((= n (vector-length v1))
		   (>= idens (/ n 2)))
		  ((equal? (vector-ref v1 n) (vector-ref v2 n))
		   (compare v1 v2 (+ n 1) (+ idens 1)))
		  (else (compare v1 v2 (+ n 1) idens))))
  (define (iterate v i)
	(cond ((= (+ i 1) (vector-length v))
		   #f)
		  ((compare (vector-ref v i) (vector-ref v (+ i 1)) 0 0)
		   i)
		  (else (iterate v (+ i 1)))))
  (iterate v 0))

;; PROBLEM 7.
#|
	       APPLICATIVE				LAZY
At Point A     + 0 Times     * 1 Time			+ 0 Times     * 1 Time
At Point B     + 1 Time	     * 0 Times			+ 0 Times     * 0 Times
At Point C     + 0 Times     * 0 Times			+ 1 Time      * 0 Times
At Point D     + 0 Times     * 0 Times			+ 0 Times     * 0 Times
|#

;; PROBLEM 8.
;; (a)	50
;; (b)	3
;; (c)	10

;; PROBLEM 9.
(define (unique? . args)
  (cond ((or (null? args) (null? (cdr args))) #t)
	((member (car args) (cdr args)) #f)
	(else
	 (apply unique? (cdr args)))))

(define (magic-square)
  (let
      ((r1c1 (amb 1 2 3 4 5 6 7 8 9))
       (r1c2 (amb 1 2 3 4 5 6 7 8 9))
       (r1c3 (amb 1 2 3 4 5 6 7 8 9))
       (r2c1 (amb 1 2 3 4 5 6 7 8 9))
       (r2c2 (amb 1 2 3 4 5 6 7 8 9))
       (r2c3 (amb 1 2 3 4 5 6 7 8 9))
       (r3c1 (amb 1 2 3 4 5 6 7 8 9))
       (r3c2 (amb 1 2 3 4 5 6 7 8 9))
       (r3c3 (amb 1 2 3 4 5 6 7 8 9)))
    (require (unique? r1c1 r1c2 r1c3 r2c1 r2c2 r2c3 r3c1 r3c2 r3c3))
    (require (= (+ r1c1 r1c2 r1c3)
		(+ r2c1 r2c2 r2c3)
		(+ r3c1 r3c2 r3c3)
		(+ r1c1 r2c1 r3c1)
		(+ r1c2 r2c2 r3c2)
		(+ r1c3 r2c3 r3c3)
		(+ r1c1 r2c2 r3c3)
		(+ r1c3 r2c2 r3c1)))
    (list (list r1c1 r1c2 r1c3)
	  (list r2c1 r2c2 r2c3)
	  (list r3c1 r3c2 r3c3))))

;; PROBLEM 10.
;; Though a lot of the answers below are the same, an important aspect of the
;; question is to realize *where* the next choice is made, if a previous
;; choice led to a failure.  Remember that you *always* go back to the last
;; time you had to make a choice.

#|
(a)  1, 2, 3
(b)  (1 2 3)
(c)  1, 2, 3
(d)  1, 2, 3
(e)  2, 3, 1, 4
(f)  f, i
|#

;; PROBLEM 11.
(assert! (rule (rotate-forward (?first . ?rest) ?what)
	       (append ?rest (?first) ?what)))

;;; For rotate-backward, we need some help.
(assert! (rule (last (?first) ?first)))
(assert! (rule (last (?first . ?rest) ?last)
	       (last ?rest ?last)))
(assert! (rule (butlast (?first) ())))
(assert! (rule (butlast (?first . ?rest) ?result)
	       (and (append (?first) ?x ?result)
		    (butlast ?rest ?x))))

;; Now we can write rotate-backward:
(assert! (rule (rotate-backward ?lst ?result)
	       (and (butlast ?lst ?bl)
		    (last ?lst ?last)
		    (append (?last) ?bl ?result))))

;;; Alternatively (and elegantly),
(assert! (rule (rotate-backward ?x ?y)
	       (rotate-forward ?y ?x)))