CS 61A Fall 1994 Midterm 2 solutions 1. Box & pointer diagrams > (cons (append '(a b) '(c d)) '(e f)) ((A B C D) E F) Many people said ((a b c d) . (e f)) but Scheme never prints the sequence ". (" in representing a list structure. In the picture below, the starred pair is the one created by the CONS invocation. *********** *+---+---+* +---+---+ +---+---+ *| | |* | | | | | /| --------->*| | | ----------->| | | ----->| | | / | *| | | |* | | | | | | |/ | *+-|-+---+* +-|-+---+ +-|-+---+ ***|******* | | | V V | | E F | V +---+---+ +---+---+ +---+---+ +---+---+ | | | | | | | | | | | /| | | | ----->| | | ----->| | | ----->| | | / | | | | | | | | | | | | | | | |/ | +-|-+---+ +-|-+---+ +-|-+---+ +-|-+---+ | | | | V V V V A B C D > (list (cons 'a 'b) (list 'c 'd) 'e) ((A . B) (C D) E) +---+---+ +---+---+ +---+---+ | | | | | | | | /| ---------> | | | ----->| | | ----->| | | / | | | | | | | | | | | |/ | +-|-+---+ +-|-+---+ +-|-+---+ | | | | | V | | | | E V V +---+---+ +---+---+ +---+---+ | | | | | | | | /| | | | | | | | | ----->| | | / | | | | | | | | | | | | |/ | +-|-+-|-+ +-|-+---+ +-|-+---+ | | | | V V V V A B C D > (caaddr '((a b c d e) (f g h i j) (l m n o p) (q r s t u))) L (cdr '((a b c d e) (f g h i j) (l m n o p) (q r s t u))) ===> ((f g h i j) (l m n o p) (q r s t u)) (cdr '((f g h i j) (l m n o p) (q r s t u))) ===> ((l m n o p) (q r s t u)) (car '((l m n o p) (q r s t u))) ===> (l m n o p) (car '(l m n o p)) ===> L The box and pointer diagram for this is just -----> L We accepted "you can't have a box and pointer diagram with no pairs" and we accepted a single box around the L, but we didn't accept anything with a pair above the L. > (cons 'a (cdr '(((b))))) (A) (cdr '(((b)))) is the empty list, so this is equivalent to (cons 'a '()). +---+---+ | | /| ---------> | | | / | | | |/ | +-|-+---+ | | V A Scoring: one point each, all or nothing. 2. Deep lists. (define (deep-list? obj) (cond ((null? obj) #t) ((atom? obj) #f) ((or (atom? (car obj)) (deep-list? (car obj))) (deep-list? (cdr obj))) (else #f))) A deep list must be a list, so it can't be a non-null atom. If the list is empty, then (trivially) all of its members satisfy the condition given. If the list isn't empty, we look at its first element. That element must be either a deep list or a non-pair (that is, an atom). If either of those criteria is met, we make sure the rest of the list is a deep-list. The crucial idea here is that this is a tree recursive problem. In other words, we aren't just looking at each element of a sequence of elements; instead, we're looking at the elements, and at elements of the elements, and at elements of elements of elements, and so on, to any depth. It's a two-dimensional problem. Therefore, any correct solution must use car/cdr recursion, or the equivalent higher-order function: (define (deep-list? obj) (and (list? obj) (null? (filter (lambda (element) (not (or (atom? element) (deep-list? element)))) obj)))) Scoring: Standard BH 5-point scale. Having the idea means using tree recursion. Typical part-credit answers: 4 right except for base cases 3 tree recursion, but bad logic (e.g., always true) 2 checks elements, but not elements of elements 1 any recursion By the way, many people seem to think that PAIR? and LIST? are mutually exclusive. A list is either the empty list or *a pair* whose cdr is a list. Some people were confused by the recursive definition: a deep list has deep lists as elements. (See also the recursive definition of "list" in the previous paragraph.) Recursive definitions are just like recursive procedures: There must be a base case. For lists, the base case is the empty list. For deep lists, the base case is having atoms as elements. 3. Time of day ADT. (define (time-print-form time) (word (hour time) ': (two-digit (minute time)) (category time))) (define (two-digit num) (if (< num 10) (word 0 num) num)) (define (24-hour time) (+ (* (hour time) 100) (minute time) (if (equal? (category time) 'pm) 1200 0))) (define (make-time hr min cat) (+ (* hr 100) min (if (equal? cat 'pm) 1200 0))) (define (hour time) (if (>= time 1200) (- (div time 100) 1200) (div time 100))) (define (minute time) (remainder time 100)) (define (category time) (if (>= time 1200) 'pm 'am)) The most common serious errors were writing a non-function in part (a) and rewriting make-time with the wrong number of arguments in part (c). These errors were the ones that gave rise to the most complaints about harsh grading, but I really think they're about crucial issues in the course. Part (a) says, "Write a FUNCTION time-print-form that takes a time as its argument and RETURNS a word of the form 3:07pm." In week 7 of the course you should know what it means for a function to return a value! Some people said they were confused by the fact that the word "print" is part of the function's name, but a "print form" is the form in which we want things to be printed; computing the print form of a time doesn't mean that we should actually print it! Maybe the print form will be used as part of a larger sentence that we'll want to print later. Part (c) says, "Now we decide to change the *internal* representation of times to be a number in 24-hour form. BUT WE WANT THE CONSTRUCTOR AND SELECTORS TO HAVE THE SAME INTERFACE SO THAT PROGRAMS USING THE ABSTRACT DATA TYPE DON'T HAVE TO CHANGE." That means that the arguments to make-time must be the same things they were all along: an hour (in 12-hour time), a minute, and a category (am/pm). Many people returned 3:7pm instead of 3:07pm in part (a), because they thought that it would be sufficient to say something like (time-print-form (make-time 3 07 'pm)) The trouble is that Scheme interprets 07 as the number 7; Scheme doesn't remember exactly how you typed the number. This was a minor error. Many people, in part (c), changed the internal representation to something other than a number, e.g., a list of two numbers. I've spoken with four students who didn't understand why this was wrong, and I asked them to read the first sentence of part (c), and they said "... representation of times to be in 24-hour form." And I said, "No, read it again." On the third or fourth try they'd finally read the words "a number." Sigh. Typical errors and scores: 4 3:7pm 3 changes internal form to (15 7) instead of 1507 2 printing in (a) or wrong args in (c), as above 1 glimmers of using the abstraction 4. Fix message passing for dyadic operators (define (make-rectangular x y) (define (dispatch m) (cond ((eq? m 'real-part) x) ((eq? m 'imag-part) y) ((eq? m 'magnitude) (sqrt (+ (square x) (square y)))) ((eq? m 'angle) (atan y x)) ((EQ? M 'ADD) (LAMBDA (Z) (MAKE-RECTANGULAR (+ X (REAL-PART Z)) (+ Y (IMAG-PART Z))))) (else (error "Unknown op -- make-rectangular" m)))) dispatch) The lines in capital letters are the only changes. It's okay to use the book's +c procedure instead of calling make-rectangular: ((eq? m 'add) (lambda (z) (+c dispatch z))) and it's okay to use (z 'real-part) instead of (real-part z). (That's not a violation of data abstraction because we're writing make-rectangular, the constructor for the ADT, and it has to know how complex numbers are implemented!) Having the idea means that make-rectangular accepts an ADD message for which it returns a function of another complex number. Common errors included giving make-rectangular extra arguments and giving dispatch extra arguments. Probably that's because you didn't understand the significance of all the parentheses in (define (+complex z1 z2) ((z1 'add) z2))