CS 61A Solutions: Midterm III Summer 2002 Question 1: Stream Warm-up [ 6 Points ] Strangely, after doing this problem nobody reported feeling warmer ... Probably the cleanest solution to this problem is one that uses mutual recursion: (define (wave-maker low high) (define (ascend from) (cons-stream from (if (= from high) (descend high) (ascend (+ from 1))))) (define (descend from) (cons-stream from (if (= from low) (ascend low) (descend (- from 1))))) (ascend low)) There were many others. Grading: 6 points if perfect. 4.5 points if goes into an infinite loop or creates a stream of just the ascending values, but shows significant understanding. 3 points if solution is a stream of streams. 2 points if able to generate ascending and descending streams, but not link them into a single stream. 0 points if solution uses lists. Question 2: Conc-urrrrrwin-cy [ 10 Points ] Most of these questions were all-or-nothing. a. Does INC-LIST! have cuncurrency issues? Yes it does. To get the full 3 points on this problem, you needed to provide us with a specific example, such as: the expression (set-car! lst (+ (car lst) 1)) might each grab the same value for (car lst) but one will finish after the other, overwriting the value stored by the earlier SET-CAR!. b. Kurt's solution does not solve the problem because it creates a new mutex for each invocation of INC-LIST!. Since each invocation has its own mutex, each invocation has a green light. The situation is no better than having no mutex at all. This part was worth 3 points. c. To correct the problem, the INC-LIST! function needs to be given a single mutex that persists from call to call -- a local state variable: (define inc-list! (let ((my-mutex (make-mutex))) (lambda (lst n) (my-mutex 'acquire) (cond ((= n 0) 'ok) (else (inc-list-by-one! lst) (inc-list! lst (- n 1)))) (my-mutex 'release)))) We were dissapointed that no one felt the urge to shout "Urrrrrrrwin-cy" during the midterm. Question 3: Mutable Structures [ 12 Points ] a. (define (filter! pred lst) (cond ((null? (cdr lst)) 'ok) ((pred (cadr lst)) (filter! pred (cdr lst))) (else (set-cdr! lst (cddr lst)) (filter! pred lst)))) Grading: 6 points total. +1 recursive structure +1 mutation +2 checking the CADR +2 correctly skipping elements that do not satisfy the predicate -1 incorrect recursive calls -1 setting the CARs to things not in the argument list Mutation was required. Solutions that created any new pairs received no credit. b. The assumption we made in Part a was that the first element of our input list will always satisfy the predicate. Even if the predicate returns false for the first element, it is still possible to write filter!, provided the predicate returns true for at least one element of the list. If that is the case, then it will be possible to move around the cars of the list to create a correctly filtered list without changing the external pointer. The real problem arises if the predicate returns false for *every* element of the list (such as (lambda (x) #f)). Then the list should be set to the null list, but that is impossible with the way lists are implemented in scheme. Grading: 3 points total. +3 if correct +2 saying that an external pointer cannot be changed +1 saying you can't change the first element +1 for saying "yes" if explanation shows significant insight c. Despite what the test said, the only functions we wanted you to define were NEW-LIST and NEW-NULL?. The only condition was that the following must work: (define a (new-list 1 3 5)) (filter! even? a) (new-null? a) ==> returns #t To do this, all you need to do is attach a dummy (a sentinel) as the first list node. This way, that pesky first pair is never an issue since any external pointers point to it, even if the entire (new) list is (new) null. (define (new-list . args) (cons '*new-list* args)) (define (new-null? new-list) (null? (cdr new-list))) Notice that the new list datatype is defined in terms of the old CONS, NULL? and CDR functions. Grading: 3 points total. +1 for new-list +1 for new-null? +1 consistency with FILTER! Question 4: MCEs Ouch! [ 12 Points ] Most students lost a lot of points on this question, partly due to the way we graded it. We decided to award 4 points each for parts A, B and C. No points were awarded for correct answers to parts D and E, but one point was deducted for incorrect answers to parts D and E. a. Ilya's Attempt. This does not work for two main reasons. The first is the same one as in Exercise 4.14 of the homework: we're mixing representations of procedures. The MAP in underlying Scheme will crash when trying to apply a metacircular Scheme procedure. To get full credit on this problem, you needed to state what exactly goes wrong. Merely noting that underlying Scheme and metacircular Scheme represent procedures differently got you close -- but not cigar! Another reason this does not work, as a few students pointed out, is that we should not be calling MC-EVAL on the list of arguments to MAP. We should have said (eval-sequence (caddr exp) env). Most people got this one. b. Jane's Attempt. This does not work because all primitives are applied with the APPLY-IN-UNDERLYING-SCHEME function, which is just an alias for APPLY. As with part a, APPLY expects an STk procedure as its first argument. It will crash when trying to apply a list. c. Greg's Attempt. He tried, he tried ... but it still is no good! Although parts of a metacircular Scheme procedure should be quoted, the environment should not be. Here, MAP-PROCEDURE returns a quoted list, which means each element of it -- including the-global-environment -- is quoted. Full credit was given for answers that specifically stated that the-global-environment should not be quoted. Answers saying that Greg needed to use LIST or the MAKE-PROCEDURE function were not specific enough, so they received partial credit. A common mistake was to say that this addition of MAP works. However, even if the- global-environment had not been quoted, this would not work for a very subtle reason: this is a change in SETUP-ENVIRONMENT, which is called to turn the-global- environment into something useful in the MCE function. At the moment when SETUP- ENVIRONMENT is called, the-global-environment is the empty list. So the environment that this MAP function would point to is the empty environment, meaning that this MAP would never be able to access anything bound in the global environment. In fact, if you perform this addition and then try (map (lambda (x) (* x x)) '(1 2 3 4)) the first error you'll get is, "Unbound variable: null?". Strangely, if you call MCE twice, this MAP will work (assuming you do not quote the-global-environment). Why? d. Jeff's Attempt. This will work. The difference is that the environment -- initial-env in this case -- is not quoted. Besides that, initial-env is the correct environment in which to add stuff that you want to be bound when MCE starts. The MCE function calls SETUP-ENVIRONMENT like so: (set! the-global-environment (setup-environment)). This means that from here on the-global-environment has whatever initial-env does because initial-env is the return value of SETUP-ENVIRONMENT. Just like the primitive procedures and the variables true, false and import are bound in intial-env yet are accesible in the-global-environment, so will be Jeff's MAP. A common wrong answer was saying that we should be binding MAP in the-global- environment, not in initial-env. Binding MAP in the-global-environment, however, does not work, as explained above. e. Erwin's Attempt. This works fine also because we're binding MAP in the-global- environment *after* it has been set-banged to initial-env. This means that MAP can safely point to the-global-environment as it is no longer null. f. Greg's Second Attempt. This part was on the back, in invisible ink, so everybody missed it and we decided not to grade it. It worked, too.