;; Summer 1995  CS 61A
;; Midterm #2 Solutions

;; Question 1 [5 points total]: Scheme Expressions and Box-and-Pointer Diagrams
;; ============================================================================
;; The goal of this question was to test your understanding of list
;; structures and of how the Scheme interpreter prints them.
;; 
;; > (list (mickey mouse))
;; This produces an error because mickey and mouse are
;; unbound variables.
;; ERROR
;; 
;; > (cons '(computer science) '(is fun!))
;; ((computer science) is fun!)
;;            +---+---+                +---+---+   +---+---+
;;            |   |   |                |   |   |   |   |  /|
;;  --------> | | |  ----------------->| | | ----->| | | / |
;;            | | |   |                | | |   |   | | |/  | 
;;            +-|-+---+                +-|-+---+   +-|-+---+ 
;;              |                        |           |       
;;              |                        |           |       
;;              V                        V           V       
;;            +---+---+   +---+---+     is          fun!     
;;            |   |   |   |   |  /|   
;;            | | | ----->| | | / |
;;            | | |   |   | | |/  |
;;            +-|-+---+   +-|-+---+
;;              |           |
;;              |           |
;;              V           V
;;          computer      science
;; 
;; 
;; > ((lambda (x) (list x x)) (quote happy))
;; The key point here is that (quote happy) is the same as 'happy,
;; and evaluating (list 'happy 'happy) gives:
;; (happy happy)
;;            +---+---+   +---+---+    
;;            |   |   |   |   |  /|   
;;  --------->| | | ----->| | | / |
;;            | | |   |   | | |/  |
;;            +-|-+---+   +-|-+---+
;;              |           |
;;              |           |
;;              V           V
;;            happy       happy
;; 
;; 
;; > (cdr '(1 (2 (3))))
;; The cdr of this list gives a list of ONE item [that one item
;; being the list (2 (3))]. So the answer is:
;; ((2 (3)))
;;            +---+---+
;;            |   |  /|
;;  --------> | | | / |
;;            | | |/  | 
;;            +-|-+---+ 
;;              |       
;;              |       
;;              V       
;;            +---+---+   +---+---+
;;            |   |   |   |   |  /|   
;;            | | | ----->| | | / |
;;            | | |   |   | | |/  |
;;            +-|-+---+   +-|-+---+
;;              |           |
;;              |           |
;;              V           V
;;              2         +---+---+      
;;                        |   |  /| 
;;                        | | | / | 
;;                        | | |/  | 
;;                        +-|-+---+ 
;;                          |
;;                          |       
;;                          V       
;;                          3
;; 
;; > (list '(car (cons 1 2)) 10)
;; The quote before (car (cons 1 2)) makes everything inside the
;; parentheses a symbol, including car and cons. The answer is:
;; ((car (cons 1 2)) 10)
;;            +---+---+   +---+---+
;;            |   |   |   |   |  /|
;;  --------> | | |  ---->| | | / |
;;            | | |   |   | | |/  | 
;;            +-|-+---+   +-|-+---+ 
;;              |           V      
;;              |          10     
;;              V          
;;            +---+---+   +---+---+
;;            |   |   |   |   |  /|   
;;            | | | ----->| | | / |
;;            | | |   |   | | |/  |
;;            +-|-+---+   +-|-+---+
;;              |           |
;;              |           |
;;              V           V
;;             car      +---+---+    +---+---+   +---+---+
;;                      |   |   |    |   |   |   |   |  /|
;;                      | | |  ----->| | | ----->| | | / |
;;                      | | |   |    | | |   |   | | |/  |
;;                      +-|-+---+    +-|-+---+   +-|-+---+
;;                        |            |           |        
;;                        |            |           |                         
;;                        V            V           V        
;;                       cons          1           2
;; 
;; 
;; SCORING: (1 point per expression)
;;   -0.5 pt for incorrect scheme printout
;;   -0.5 pt for incorrect box-and-pointer diagram, unless it matches
;;           the (incorrect) scheme printout
;;   -1 pt for saying ERROR if there wasn't one


;; Question 2 [7 points total]: Flip-tree
;; ======================================
;; The goal of this question was to test your understanding of
;; manipulating tree structures and of representing data using message
;; passing.
;; 
;; Part A. (4 pts)
;; ---------------
(define (flip-tree tree)
  (cond ((empty-tree? tree) the-empty-tree)
        (else (make-tree (entry tree)
                         (flip-tree (right-branch tree))
                         (flip-tree (left-branch tree))))))

;;SCORING:
;;  + 1 pt. for correct base case
;;  + 2 pts. for correct tree recursion
;;  + 1 pt. for respecting the abstraction barrier (but -2 for multiple
;;          violations) 
;;
;; Some common errors:
;;
;;  - Using the leaf case as the base case, i.e. 
;;
;;       (and (empty-tree? (left-branch tree))
;;            (empty-tree? (right-branch tree)))
;;
;;    This not only fails when the original tree is the-empty-tree, but
;;    also causes problems with nodes with a single branch.  Although
;;    this can be made to work with some extra tests, it's easier to let
;;    the recursion "bottom out" at the empty trees which are the
;;    "branches" of the leaves.
;;
;;  - Getting the data abstraction mostly right, but using () instead of
;;    the-empty-tree.  This is part of the abstraction barrier as well.
;;
;;  - Recursing on only one branch, e.g. from thinking about binary
;;    search trees.  This problem required the entire tree to be
;;    traversed, not just one path to a leaf.

;; Part B. (3 pts)
;; ---------------
(define (make-tree value left right)
  (lambda (m)
    (cond ((eq? m 'entry) value)
          ((eq? m 'left-branch) left)
          ((eq? m 'right-branch) right)
          (else (error "Unrecognized message:" m)))))

(define (entry tree)
  (tree 'entry))

(define (left-branch tree)
  (tree 'left-branch))

(define (right-branch tree)
  (tree 'right-branch))

;;SCORING:
;;  3 pts. if perfect
;;  2 pts. for small error, but correct notion of message passing
;;  1 pt. for having some idea, but clearly misunderstanding how message
;;        passing works
;;  0 pts. for having no idea
;;
;; Common errors:
;;
;; - Getting make-tree entirely right, but failing to have the selectors
;;   pass messages correctly to their arguments.  A common form of this was
;;
;;        (define (entry tree)
;;          ((make-tree (car tree) (cadr tree) (caddr tree))
;;           'entry))
;;
;;   This is doomed to fail, since tree is a procedure (being itself the
;;   result of a call to make-tree).
;;
;; - Giving only one argument "tree" to make-tree, and returning e.g.
;;   (car tree) from the lambda expression when an 'entry message is
;;   received.


;; Question 3 [6 points total]: Generic Operators and Coercion
;; ===========================================================
;; The goal of this question was to test your understanding of how the
;; data-directed implementation of generic operators and coercion
;; works. It involved applying the same ideas from the last two exercises
;; of Homework #4.
;; 
;; Part A.
;; -------
;; Here, OPERATE-2 gets called once, and it immediately finds +NUMBER to
;; add the two numbers together.
;; 
;; (number . 7) 
;; SUM = 1
;; 
;; Part B.
;; -------
;; OPERATE-2 gets called twice -- in the first invocation, one argument
;; is an (integer) number, and the other is a complex number. The integer
;; gets coerced to a complex number, and OPERATE-2 is called again. This
;; time, it finds +COMPLEX. +COMPLEX calls +C (with the contents of the
;; complex numbers, i.e., with the COMPLEX tag removed). +C makes a new
;; complex number after getting the REAL-PART and IMAG-PART of each
;; number. There are four calls total to REAL-PART and IMAG-PART, and
;; each of these calls makes a call to OPERATE to find the
;; REAL-PART-RECTANGULAR or IMAG-PART-RECTANGULAR procedures.
;; Even with the code written on the whiteboard, many students treated +C
;; as a black-box and said that SUM = 2.
;; 
;; (complex rectangular 15 . 4)
;; SUM = 6
;; 
;; Part C.
;; -------
;; OPERATE-2 gets called once for the ADD. OPERATE gets called twice
;; for the MAGNITUDE (this is what happens in exercise 2.51 of the text).
;; 
;; (number . 17.0)
;; SUM = 3
;; 
;; SCORING (2 points each part):
;;   -0.5 pts for incorrect numerical answer
;;   -0.5 pts for correct numerical answer but wrong Scheme printout
;;   -1.0 pt  for incorrect sum
;;   We did not penalize for making the exact same Scheme printout error
;;   twice. Common errors included not putting a dot between NUMBER and 7,
;;   writing just "7", or adding extra quotes or parentheses to the printout.



;; Question 4 [5 points total]: A more forgiving doctor program
;; ============================================================
;; The goal of this question was to test your understanding of iterating
;; through a list and of making a small change to the doctor program.
;; 
;; this is what we wanted:
(define (repeated? item item-list)
  (define (iter item-list count)
    (cond ((>= count 3) #t)
	  ((null? item-list) #f)
          ((equal? item (car item-list))
               (iter (cdr item-list) (1+ count)))
          (else (iter (cdr item-list) count))))
  (iter item-list 0))

;; SCORING:
;; 5 pts. for any working solution
;; 4 pts. for "almost" working solution, with minor mistake
;;        (e.g. "off-by-one" errors)
;; 3 pts. for basically right, but with multiple minor mistakes or one
;;        bigger mistake (e.g. infinite loop)
;; 2 pts. for some idea, using recursion
;; 1 pt. for some idea, without recursion
;; 0 pts. for blank page
;;
;; Common errors:
;;
;; - "Off-by-one" errors: e.g. returns #t iff there are 4 or more
;;   occurences (or 2 or more), instead of 3 or more.
;;
;; - Thinking that the expression (1+ count) somehow magically changes
;;   the value of count, rather than just returning count+1.  This is a
;;   serious conceptual error about functional programming, but if the
;;   program worked under this false assumption only 1 point was lost.
;;
;; - Correct definition of helper procedure, but missing call to it.
;;
;; - Missing one of the base cases (e.g. never returns #t).
;;
;; - Sometimes returning a number instead of #t or #f.
;;
;; - Changing code outside of repeated?.
;;
;; - One common bug which is fairly subtle was to have the two base cases
;;   in the helper function switched.  This will incorrectly return #f in
;;   the special case that the third occurence of item is at the very end
;;   of the list.


;; Question 5 [6 points total]: Composing a list of functions
;; ==========================================================
;; The goal of this question was to test your understanding of
;; higher-order procedures and of manipulating list structures.
;; 
;; We want to apply the procedures in order from right to left, but
;; taking the car of the list of procedures gives us the leftmost one
;; first. Thus, we defer applying that procedure until we have applied
;; all the procedures in the rest of the procs list to n.
;; 
;; Either of these is the desired solution:
(define (compose-funcs procs)
  (lambda (n)
    (if (null? procs)
        n
        ((car procs) ((compose-funcs (cdr procs)) n)))))

(define (compose-funcs procs)
  (if (null? procs)
      (lambda (n) n)
      (lambda (n)
        ((car procs) ((compose-funcs (cdr procs)) n)))))


;; Some students realized that by reversing the list of procedures,
;; they could implement an iterative solution to compose-funcs:
(define (compose-funcs procs)
  (lambda (n)
    (define (iter curr-procs result)    
      (if (null? curr-procs)
          result
          (iter (cdr curr-procs) ((car curr-procs) result))))
    (iter (reverse procs) n)))
    
;; SCORING:
;;   -2 pts -- each significant error (up to -4 pts)
;;             The most common errors were in the recursive call:
;;             -- not applying (compose (cdr procs)) to n
;;             -- trying to somehow cons the car and cdr of the the procs list 
;;             -- applying the procs to () or to (lambda (x) x) 
;;   -1 pt  -- minor error (up to -2 pts)
;;             The most common errors were:
;;             -- not working with an empty list of procedures
;;             -- passing the wrong argument name
;;    
;; There were too many different answers to categorize, but basically the
;; scores came out like this:
;;   6 pts -- perfect solution
;;   5 pts -- works, but minor error
;;   4 pts -- will work with one significant change
;;   3 pts -- applies procedures in wrong order, or significant + minor error
;;   2 pts -- two significant errors, or just bits and pieces of a solution
;;   1 pts -- a bit or piece of the solution
;;   0 pts -- clearly didn't know how to solve problem