Answers to the Final Review Sheet

1. A

2. Part 1) (compound-procedure (x) ((* x x)) <procedure-env>)
   Part 2) 10

3. (define useless-square
      (let ((prev #f))
          (lambda (x)
               (if (not prev)
                   (set! prev (* x x)))
               prev)))

4. Let's call (bar 10)
   LEXICAL SCOPE: 10   DYNAMIC SCOPE: 20

   foo
   LEXICAL SCOPE: 20  DYNAMIC SCOPE: 100


5. For the sake of argument, let's assume that let works in the evaluators
   Part 1) ERROR, ERROR, VALUE, ERROR
   Part 2) ERROR, ERROR, ERROR, ERROR

6. Part 1) FASTER
   Part 2) SAME

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

8. a) (define (last lst)
         (if (null? (cdr lst))
             (car lst)
             (last (cdr lst))))
   b) (define (butlast lst)
         (if (or (null? lst) (null? (cdr lst)))
             '()
             (cons (car lst) (butlast (cdr lst)))))

      (define (trimmed lst)
         (if (null? lst)
         '()
         (butlast (cdr lst))))


   c) (define (coolerize lst)
         (if (or (null? lst) (null? (cdr lst)))
             lst
             (list (car lst) (coolerize (trimmed lst)) (last lst))))

9. (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)))))



10. (define (smallest-containing-tree tree x y)
      (if (and (tree-member? x tree) (tree-member? y tree))
          (let ((candidate-forest
                 (filter (lambda (x) x)
                         (map (lambda (child)
                                (smallest-containing-tree child x y)) (children tree)))))
            (or (and (not (null? candidate-forest)) candidate-forest) tree))
          #f))

11. (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)))))

12. (define (square-nums exp)
       (cond ((null? exp) '())
             ((pair? (car exp))
              (append (list (square-nums (car exp))) (square-nums (cdr exp))))
             ((number? (car exp))
              (cons (square (car exp)) (square-nums (cdr exp))))
             (else
              (cons (car exp) (square-nums (cdr exp))))))

13. (define (demorganize exp)
       (cond ((null? exp) '())
             ((not-and-exp? (car exp))
              (append (list (not-and->or-not (car exp))) (demorganize (cdr exp))))
             (else
              (cons (car exp) (demorganize (cdr exp))))))

    (define (not-and->or-not exp)
       (demorganize (cons 'or (map (lambda (subexp)
                                      (list 'not subexp))
                                   (cdadr exp)))))


14. (define (updated table name new-value)
       (cond ((null? table) (list (list name new-value)))
             ((eq? (caar table) name)
              (cons (list name new-value) (cdr table)))
             (else
              (cons (car table) (updated (cdr table) name new-value)))))

    (define (updated! table name new-value)
       (cond ((null? table) (list (list name new-value)))
             ((eq? (caar table) name)
              (set-car! (cdar table) new-value))
             ((null? (cdr table))
              (set-cdr! table (list (list name new-value))))
             (else
              (updated! (cdr table) name new-value)))
       table)

15. a. (a b c)
    b. (a c)
    c. ERROR

16. a) Envdraw
    b) 14

17. (f 2) --> (3 6 (2 4) (1 4))
    (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))

18. (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)))