Final Examination Review Solutions ================================== THE METACIRCULAR EVALUATOR ---------------------------------------------------- 1. 3 STk's and MCE's environment are completely separate. You cannot modify STk's environment from MCE 2. Part 1) (compound-procedure (x) ((* x x)) ) You can find quote as a bound variable in the environment Part 2) 10 The quote special form takes precedence here. 3. a) apply We want to change how environments are extended. That's handled in apply. b) We chose to change extend-environment. c) (define (extend-environment vars vals base-env) (if (null? vars) ; Use the base environment. Don't make a new frame base-env [Rest of the old extend-environment])) THE ANALYZING EVALUATOR ------------------------------------------------------- The left procedure is performs FASTER in the analyzing evaluator. The right procedure has the SAME performance in the analyzing evaluator. STREAMS ----------------------------------------------------------------------- 1. 1 2 5 12 29 70 169 2. a) The define statement goes into an infinite loop. When we evaluate stream-accumulate, we’ll 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’ll delay the evaluation of y, which is the next call to accumulate. Alas, that’s 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. THE LAZY EVALUATOR ------------------------------------------------------------ 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 THE NONDETERMINISTIC EVALUATOR ------------------------------------------------ (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)))) THE LOGIC EVALUATOR ----------------------------------------------------------- (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 (assert! (rule (rotate-backwards ?x ?y) (rotate-forward ?y ?x))) LEXICAL AND DYNAMIC SCOPE ----------------------------------------------------- Run the scheme on in env draw. For dynamic, ignore the right bubbles. Procedure frames extend the current frame in dynamic scope. Scheme: (bob says hello) Dynamic: (sam says hello) TOPICS IN THE PAST ------------------------------------------------------------ 1. (define (tree-member? x tree) (or (eq? x (datum tree)) (forest-member? x (children tree)))) (define (forest-member? x forest) (cond ((null? forest) #f) ((tree-member? x (car forest))) (else (forest-member? x (cdr forest))))) 2. (define (num-sum exp) (cond ((null? exp) 0) ((pair? (car exp)) (+ (num-sum (car exp)) (num-sum (cdr exp)))) ((number? (car exp)) (+ (car exp) (num-sum (cdr exp)))) (else (num-sum (cdr exp))))) 3. a. (a b c) b. (a c) c. ERROR 4. It's much easier to understand what's going on if you draw the environment diagram! For a better picture of what's going on, type this into envdraw. (define foo (let ((L (list 1))) (lambda (a) (let ((M (cons a L))) (lambda (b) (set! L (cons (+ a 1) L)) (set! a (+ a 2)) (set-car! (cdr M) (+ 3 (cadr M))) (set! b (+ b 4)) (list a b L M)))))) > (define f (foo 1)) > (f 2) (3 6 (2 4) (1 4)) > (define g (foo 2)) > (g 1) (4 5 (3 5 4) (2 5 4)) > (f 2) (5 6 (4 3 5 7) (1 7)) > (g 1) (6 5 (5 4 3 8 7) (2 8 7)) 5. (define-class (job desc work-to-do) (class-vars (number-of-jobs 0)) (instance-vars (id #f)) (initialize (set! id number-of-jobs) (set! number-of-jobs (+ number-of-jobs 1))) (method (do-work work) (if (< (- work-to-do work) 0) '(but you are already done!) (set! work-to-do (- work-to-do work)))) (method (done?) (= work-to-do 0)))