Midterm 3 Review Answers Problem 1 ---------- So the key thing here that I'm trying to emphasize is that you SHOULDN't be doing set-cdr! or set-car! on an atom! BAD! So here are the box-and-pointer diagrams for the following expressions a) +---- this pair is changed | v +---+---+ +---+---+ +---+---+ x-->| | ---->| | ---->| | | +-|-+---+ +-|-+---+ +-|-+-|-+ v v v v 1 2 3 1 (1 2 3 . 1) b) +---- this pair is changed | v +---+---+ +---+---+ +---+---+ +---+---+ x-->| | ---->| | ---->| | ---->| | / | +-|-+---+ +-|-+---+ +-|-+---+ +-|-+---+ v v v v 1 2 () 4 (1 2 () 4) c) +---- this pair is changed | v +---+---+ +---+---+ +---+---+ +---+---+ x-->| | ---->| | ---->| | ---->| | / | +->+-|-+---+ +-|-+---+ +-|-+---+ +-|-+---+ | v v | v | 1 2 | 4 + -------------------------+ (1 2 (1 2 (1 2 .... d) +---+---+ +---+---+ x-->| | ---->| | / | +-|-+---+ +-|-+---+ v v surfin safari This errors due to the fact that you cannot set-cdr! of the word safari! Rememember ONLY pairs can be mutated! e) (after the set-car! x 'monty-python-and-the) x ------>+---+---+ +---+---+ +---+---+ monty -->| | ---->| | ---->| | / | +-|-+---+ +-|-+---+ +-|-+---+ | v v v holy grail monty-python-and-the (after set! x (cons 'super-monkey (cdr x))) +---+---+ +---+---+ +---+---+ x -->| | ---->| | ---->| | / | +-|-+---+ +-|-+---+ +-|-+---+ | v v v holy grail super-monkey +---+---+ +---+---+ +---+---+ monty -->| | ---->| | ---->| | / | +-|-+---+ +-|-+---+ +-|-+---+ | v v v holy grail monty-python-and-the (after let statement) y -->+---+---+ x -->| | / | +-|-+---+ v super-monkey (python monty)--> (super-monkey) monty --> (monty-python-and-the holy grail) Problem 2 ---------- a) The reason for having more than one serializer is to avoid inefficiency Consider bank accounts, our favorite example. Although it is correct to have one serializer (only one person in the world can use an ATM at a time), that approach would be inefficient. If, on the other had, we have one serializer per account, we still get correct answers, but multiple people can access different accounts at the same time. The other choices, deadlock and fairness, make no sense; you can't have deadlock with just one serializer. b) In a, the only interesting event is where moo gets set to 4. In b, we need to consider three events: read moo, read moo a second time, and set moo. So in the unserialized version, (parallel-execute a b), there are four possible interleavings: (1): answer is 16 (2): answer is 12 (3): answer is 9 (4): answer is 4 a: store moo b: load moo b: load moo b: load moo b: load moo a: store moo b: load moo b: load moo b: load moo b: load moo a: store moo b: store moo b: store moo b: store moo b: load moo a: store moo In (ii), we use the same serializer to protect both a and b, so their executions cannot overlap. We don't know whether a or b comes first, but we do know that they don't happen at the same time. That leaves us with the "correct" answers, 4 and 16 In (iii), we are using two different serializers. This is wrong because we want to protect only one resource. Since s1 doesn't know about s2 and vise versa, we get the same answers as in (i). In (iv), we have some extra serializers thrown in, but we at least still have s1 on the outside. Provided that there is no deadlock, we will still get 4 and 16 as in (ii). In (i)-(iii), it is pretty clear that there is no deadlock, because a and b aren't competing for two or more serializers. In (iv), it turns out that deadlock is also impossible. You might think a ould get s2 and b could get s3, then each could wait for the other, but notice that both procedures are protected by s1 first! Neither can attempt to use s2 or s3 until s1 has been called, so they can't try to enter s2 or s3 at the same time. If it had been (parallel-execute (s2 (s3 (s1 a))) (s3 (s2 (s1 b)))), then we could end up with deadlock. Problem 3 ---------- Draw them in EnvDraw to see the solutions! Problem 4 ---------- There were three main categories of correct solution to this problem: 1. Rearrange the CDRs in a single step. 2. Rearrange the CDRs in N steps (rotatin one position per step). 3. Rearrange the CARs in N steps. (In principle you could rearrange the CARs in one set, but that would require a lot of extra temporary memory and would be quite complicated.) Rearranging the CDRs means that each pair points to the same list member it did originally, but the pairs themselves are in a different order within the list. Rearranging the CARs means that the spine of the list remains in its original order, but each pair points to a different list member from its original one. Here are examples of each technique: (define (list-rotate! n seq) (if (= n 0) seq (let ((oldend ((repeated cdr (- (length seq) 1)) seq)) (newend ((repeated cdr (- n 1)) seq)) (newstart ((repeated cdr n) seq))) (set-cdr! oldend seq) (set-cdr! newend '()) (newstart)))) (define (list-rotate! n seq) ;; Rearrange CDRs in N steps. (define (last-pair seq) (if (null? (cdr seq)) seq (last-pair (cdr seq)))) (if (= n 0) seq (let ((newstart (cdr seq))) (set-cdr! (last-pair seq) seq) (set-cdr! seq '()) (list-rotate! (- n 1) newstart)))) (define (list-rotate! n seq) ;; Rearrange CARs in N steps (define (rotate-values seq firstvalue) (if (null? (cdr seq)) (set-cdr! seq firstvalue) (sequence (set-car! seq (cadr seq)) (rotate-values (cdr seq) firstvalue)))) (if (= n 0) seq (sequence (rotate-values seq (car seq)) (list-rotate! (- n 1) seq)))) What are the advantages of the different techniques? Of course on a test you just do whichever you can do most easily, but supposed you ahd this problem in real life. The one-step CDR solution is the most efficient, because it is O(n) instead of O(n^2) like the others. (In an N-step solution, each step must traverse the entire list and is therefore O(n), and there are n steps.) The CAR solution has the advantage that the rearranged list has the same pair at its head, so any variables that were bound to this list earlier still point to the entire (rotated) list. I can't think of any particular advantage to the N-step CDR solution. (In the one-step solution, if you didn't remember about REPEATED you could of course implement a cdr-n-times procedure yourself, but REPEATED sure makes it easy and elegant, doesn't it?) (By the way, the one-step solution can be made even more efficient by finding all the interesting pairs in a single traversal of the list like this: (let* ((newend ((repeated cdr (- n 1)) seq)) (newstart (cdr newend)) (oldend (last-pair newstart))) ...) but I thought the version I gave earlier would be easier to understand. Note that this new version uses LET*, not LET, so taht the three values are computed sequentially, each using the one before it.) The really crucial point to understand in this problem was that in any pair of a list, the CAR points to a MEMBER of the list, while the CDR points to a SUBLIST of the list. These are two different kinds of thing! Any solution that said (set-car! ... (cdr ...)) or (set-cdr! ... (car ...)) had to be wrong, because swapping CARs and CDRs makes for an ill-formed list. (Some of these wrong solutions were copying the solution of an entirely different problem from a previous exam having to do with association lists, in which some pairs have both car and cdr pointing to a symbol, and it makes sense to swap them. It's really, really pathetic to copy some program you don't understand as a solution to a problem you also don't understand. Even if you do get a point or two part credit on the exam, do you really want to spend the rest of your life trying to survive in a job you don't understand at all, hoping every day that you boss and co-workers won't find out? But some of these wrong solutions really were honest efforts to solve this problem; for those people there's some hope, provided you come to understand what this paragraph is saying.) A few people CDRed all the way down to the end of the list in order to find an empty list to use in their solution. I presume this is because you were afraid that you'd lose points for saying '() because that would allocate pairs. Nope -- the empty list isn't a pair, and doesn't occupy any space. It's perfectly okay to use '() in this problem. On the other hand, some people wanted to use the queue abstraction from the text in this problem, and got in trouble. The worst trouble (zero points) was for simply applying queue selectors and mutators to SEQ, which is not a queue! It's a list; they're different. But almost as bad (one point) was to turn the list into a queue by allocating a header pair for it; the problem said in boldface, "do not allocate new pairs"! Speaking of allocating new pairs, solutions that used CONS or APPEND (not APPEND!, which is okay) or LIST were obviously wrong, but you should understand by now why using BUTLAST also allocates new pairs, besides being a data abstraction violation. Problem 5 ---------- (a) Fill in missing blanks to define the TA class. (define-class (ta name) (INSTANCE-VARS (TIME-LEFT 8)) (method (help time) (cond ((= 0 TIME-LEFT) ;; *If we use (ask self ’name) (SE NAME ’(IS ASLEEP))) ;; instead of name throughout ((> time TIME-LEFT) ;; Q1b help messages differ (SE NAME ’(CANNOT HELP THAT LONG))) (else (SET! TIME-LEFT (- TIME-LEFT TIME)) (SE NAME ’(HELPS FOR) TIME ’HOURS))))) (b) Predict the output from the following interaction: > (define my-head-ta (instantiate head-ta ’alex)) > (ask my-head-ta ’name) =) alex > (ask my-head-ta ’help 3) =) (head-ta-alex helps for 3 hours) > (ask my-head-ta ’help 3) =) (tired-alex helps for 3 hours) ;; *see above > (ask my-head-ta ’name) =) tired-alex > (ask my-head-ta ’help 3) =) (head-ta-alex helps for 3 hours) > (ask my-head-ta ’help 3) =) (tired-tired-alex helps for 3 hours) ;; *same (c) Complete the definition of the help-session class below. Use proper OOP style. (define-class (help-session) (INSTANCE-VARS (TAS ’())) (METHOD (ADD TA) (SET! TAS (APPEND TAS (LIST TA)))) (METHOD (TOTAL-HOURS) ;; has to be a method!!!! (ACCUMULATE + 0 (MAP (LAMBDA (TA) (ASK TA ’TIME-LEFT)) TAS))) (method (help time) (if (> time (ASK SELF ’TOTAL-HOURS)) ’(sorry that is asking too much) (ASK SELF ’HELP-HELPER TIME TAS))) (method (help-helper time TAS-LEFT) (if (= time 0) ’() (let ((time-this-ta-takes (min time (ASK (CAR TAS-LEFT) ’TIME-LEFT)))) (let ((time-remaining (- time time-this-ta-takes))) (CONS (ASK (CAR TAS-LEFT) ’HELP TIME-THIS-TA-TAKES) (ASK SELF ’HELP-HELPER TIME-REMAINING (CDR TAS-LEFT)))))))