;; 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)))