CS 61A Fall, 2008 Final exam solutions 1. Higher order functions > (map (lambda (x) (x 3)) '(number? pair? even?)) ERROR The quoted list is a list of symbols (words), not a list of procedures. So the error is the attempt to call the /word/ NUMBER? as if it were a procedure. > (map (lambda (x) (x 3)) (list number? pair? even?)) (#T #F #F) The call to LIST makes a list of three procedures -- LIST itself is not part of the list! So the three elements of the result are the values of (NUMBER? 3), (PAIR? 3), and (EVEN? 3). Too many people put quotation marks in front of the result. Earlier in the semester we were more lenient about this, but we think that by the end of the semester you should know the difference between an expression and a value. Scoring: 2 points each, all or nothing. 2. Pairs, lists, abstract data types The FIRST procedure can be defined by (DEFINE FIRST CAR): FALSE The domain of FIRST is words and sentences. CAR is how you find the first word of a sentence, but finding the first letter of a word is more complicated (and beyond the scope of the course). (PAIR? X) false implies (LIST? X) false: FALSE Every /nonempty/ list is a pair, but the empty list isn't. Scoring: 2 points each, all or nothing. 3. LIst mutation We accepted two answers to this question: one pair, and four pairs. The question we /intended/ to ask was about /non-circular/ list structure. If circularity is ruled out, then in order for (SET-CDR! (CDDAR X) 'CS61A) to work, X has to be a pair; the CAR of X has to be a pair; the CDR of (CAR X) has to be a pair; and the CDDR of (CDAR X) has to be a pair. So there must be at least four pairs: x ---->X* | V *X---->*X----->** In this picture every box containing a component that doesn't have to be a pair is shown as an asterisk (*). But several students noticed that the problem can also be solved with a single pair whose car and cdr point to itself: (define x (cons '() '())) (set-car! x x) (set-cdr! x x) With this single-pair structure, any number of CARs and CDRs can be composed and the result is still the same pair X. Scoring: 2 points, all or nothing. 4. Trees and data abstraction SAN is the first word of the datum of the second child of MYTREE: (first (datum (cadr (children mytree)))) The most common errors were forgetting DATUM or using CAR instead of FIRST. Some people interpreted the question as meaning "write a procedure that can be applied to any Tree, but which, when applied to MYTREE, gives the answer SAN." That's what you should do if a problem says "for example" and gives an example tree, but this problem was quite explicit about wanting only an answer for this particular tree. But we accepted such procedures if they actually work. Scoring: There are four parts to the answer. All four correct, 5 points; three correct, 4 points; two correct, 2 points; one correct, 1 point; zero, 0. Minus one point for extra components. (CAR (CDR ...)) instead of CADR is okay but still counts as one component. Getting two components of the answer in the wrong order counts as one error, not two. Writing a procedure that says (BEGIN (... (car forest)) (... (cdr forest))) (trying for an AMB-like ability to choose by magic whichever node has the "San" in it) lost two points; you can't return more than one value! The value of the first expression would just be ignored. 5. Trees in OOP language (define-class (Tree datum children) (method (treemap! fn) (set! datum (fn datum)) (for-each (lambda (child) (ask child 'treemap! fn)) children))) Since we're representing Trees as OOP objects, we don't need selector functions for the datum and children; instead they're just instantiation variables, as the problem says. If we wanted to examine the datum or children of an object from outside the object, we'd say (ask my-tree 'datum) rather than (datum my-tree). But inside the object we just say DATUM or CHILDREN to get the desired value. Since we are mutating the tree, there's no need to instantiate any extra Tree objects, We use SET! to change the datum of this node, and FOR-EACH to ask each child to run its TREEMAP! method. It's okay, but not ideal, to use MAP instead of FOR-EACH, because MAP constructs an unnecessary list duplicating the existing CHILDREN list. Since no return value is specified, it's okay to return whatever FOR-EACH returns, but it's also okay to say something like 'OKAY after the call to FOR-EACH. What you can't do, though, is (set! children (map (lambda (child) ...) children)) There are two problems here. One is that, even if it did what you thought, you wouldn't be following the specification, which says that you should mutate the existing tree. Instead this version creates /new/ child nodes, replacing the original ones. This matters because we'd like to be able to say something like (define france (cadr (children worldtree))) (ask worldtree 'treemap! some-function) and have the variable FRANCE still point to the same tree as (cadr (children worldtree)). But also, the (set! children ...) version doesn't do what it promises. The return value from the TREEMAP! method will be what SET! returns, namely the word OKAY. So the call to MAP will return a list (OKAY OKAY OKAY ...) instead of a forest! Too many people asked during the exam whether the children of an OOP Tree should be OOP Trees or regular non-OOP Trees. The whole point of the idea of trees is that every node of a tree has to be a tree also! That is, the structure of the tree is uniform; if you have two different kinds of tree, then every procedure has to be twice as long, with one algorithm for OOP trees and one for non-OOP trees. (This is true for any of the variants of the tree idea, so in particular it's true about Trees.) You only want one kind of Tree in your program. You weren't told to define a FOREST class; the CHILDREN of a Tree is still just a list of Trees, but of course those subtrees also use the OOP version. But we were happy to accept solutions that did invent OOP forests. (It's not obvious what messages a FOREST class should accept, by the way; that's why we didn't ask you to invent one. Since my instincts are functional, I'd be inclined to use FIRST-TREE and REST-OF-TREES, but since OOP is more commonly used for sequential programming, a more common approach would be to use FIRST-TREE and NEXT-TREE; the latter method would remember which tree it returned on the previous invocation and would return the one after it for the current invocation.) Speaking of forests, a particularly bad mistake was to confuse them with trees, saying something like (ASK CHILDREN 'TREEMAP! FN). You can ask an individual child something, but you can't ask the entire forest of children. Many people included unnecessary NULL? tests for the datum and/or children. We didn't take off for this, although we should have in the case of the datum, which can legitimately be an empty list -- you don't know that the empty list isn't in the domain of FN. For the children, the NULL? test doesn't hurt, but doesn't help either, since MAP and FOR-EACH are perfectly capable of dealing with empty lists. Similarly, (ASK SELF 'DATUM) or the same for the children is unnecessary but not incorrect. But (ASK TREE 'DATUM) is wrong -- TREE is the name of the class, not of this instance. And you can't use (ASK SELF 'DATUM) as the first argument to the SET! special form, which requires a symbol as its first argument. Scoring: 4 points for the TREEMAP! method: 4 correct. 3 trivial error (e.g., TREEMAP! instead of 'TREEMAP!) 2 (set! (ask self 'datum) ...) 1 correctly constructs a new OOP Tree. 1 correctly mutates a non-OOP Tree. 1 (set! children (map ...)). 0 other, including tree/forest confusion. 2 points for everything else: the instantiation variables, the DEFINE-CLASS notation, nothing extra included. 1 if flawed; 0 if very flawed. 6. Writing higher order functions (define (pairup fn lst) (if (null? (cdr lst)) '() (cons (fn (car lst) (cadr lst)) (pairup fn (cdr lst))))) This is basically MAP, except that FN takes the first /two/ elements as arguments, and the base case is different. This was meant to be really easy, as long as you learned chapter 1! The question said LST would be a "nonempty list," so there was no need to include a check for LST being empty. But we didn't take off for doing it. Many people said (append (list (fn ...)) (pairup ...)) instead of using CONS. Whenever you're tempted to write (APPEND (LIST X) Y), just say (CONS X Y) instead! But this wasn't an error, just an infelicity. A very elegant alternative solution uses the fact that MAP will accept functions of more than one argument, going through several argument lists in parallel. So you could do this: (define (list-butlast lst) (if (null? (cddr lst)) (cons (car lst) '()) (cons (car lst) (list-butlast (cdr lst))))) (define (pairup fn lst) (map fn (list-butlast lst) (cdr lst))) If LST is (a b c d), this is equivalent to (map fn '(a b c) '(b c d)), which generates exactly the pairings we want. By the way, STk allows the lists used as arguments to MAP to be of different lengths, so in STk you don't have to bother inventing list-butlast: (define (pairup fn lst) ; nonstandard STk extension (map fn lst (cdr lst))) A few people wrote iterative and/or sequential solutions. Some of them worked, some didn't, but they all violated the spirit of the whole course, which is to be able to use the most appropriate programming paradigm for any problem, instead of trying to make all problems fit one paradigm. Scoring: 3 correct. 2 base case wrong, word/sentence functions, LIST instead of CONS, CDR instead of CADR, or (CDDR LST) in recursive call. 1 just does MAP, or result is backwards (because of an iterative solution). 0 other, including building + (from the example) into the solution, using BEGIN (or an implicit BEGIN) instead of CONS, or mutating the argument list. 7. Pairs as vectors This should have been easy if you know how vectors work; the only slight subtlety is that the constructor includes a type tag as element 0 of the vector, so testing for that should be part of the PAIR? implementation. Also, the domain of type-checking predicates is /all possible values/, so PAIR? has to make sure its argument is a vector before looking at the elements of the vector. For example, (PAIR? 3) should return false, not give an error message. (define (car pair) (vector-ref pair 1)) (define (cdr pair) (vector-ref pair 2)) (define (pair? thing) (and (vector? thing) (= (vector-length thing) 3) ; we didn't insist on checking length (eq? (vector-ref thing 0) 'pair))) (define (set-car! pair value) (vector-set! pair 1 value)) (define (set-cdr! pair value) (vector-set! pair 2 value)) The implementation of PAIR? above depends on the left-to-right evaluation of the special form AND, so that if THING isn't a vector, the other two clauses won't be evaluated. Several people had this wrong attempt: (define (cdr pair) (vector 'pair (vector-ref pair 2))) ;wrong We think they were thinking that the CDR of a list has to be a list, and so they should tag it. But it's /pairs/ you're implementing. The cdr of a Scheme pair can be anything at all. If the cdr of the pair happens to be a list, then the pair itself is a list. Also, this tagged "pair" doesn't have two parts! It has only the PAIR tag and the actual cdr. So it's not a pair even though it confusingly claims to be. Other people had very long, complicated definitions of CDR. No doubt they were thinking of a comment in lecture to the effect that /if we wanted to/ we could define operations on vectors (of any length!) /analogous to/ the operations CONS, CAR, and CDR for lists. VECTOR-CDR would allocate a new vector one element smaller than the original and copy all but the first of the original elements into it. But, apart from the fact that I said we would never really do that, that exercise has nothing to do with /using/ vectors /to implement/ pairs. Scoring: 1 point for CAR/CDR; 1 point for PAIR?; 1 point for SET-CAR!/SET-CDR!. But making the same small mistake in the selectors and the mutators (e.g., using elements 0 and 1 instead of 1 and 2) only loses one point. 8. Real-life concurrency The trouble with technique 1 (acquiring the mutex as soon as the map is shown) is that there's no guarantee the user will actually select a seat quickly, or at all. The user could go eat dinner, and nobody else would be able to reserve seats. The trouble with technique 2 (not acquiring the mutex until the user actually chooses a seat) is that while the user was studying the map, someone else might have asked for a seat on the same flight, seen the same map, and chosen the same seat, so this user might end up getting an error message saying the seat is unavailable even though it was shown as available on the seat map. (This is in fact quite likely, since there's probably a lot of agreement among passengers as to which is the best seat, either the frontmost available aisle or the frontmost available window.) Technique 2 is what they really use, because the first undesirable result is a disaster, whereas the second is merely an annoyed customer. Several people thought the answers had to be one of "incorrect result," "deadlock," "inefficiency," or "unfairness." You could make a case for "inefficiency" as the answer for technique 1, although when I used that word in lecture it was to refer to a different problem, in which the same mutex is used to protect two independent variables, and two separate mutexes would give correct results with less serialization. In technique 1 the problem is worse than that, because the "critical section" depends on the response of a human being, so the delays are on human scale rather than computer scale of timing. But "no undesirable result" for technique 2 was a clear misunderstanding of the question, and "incorrect result" or "deadlock" was even worse. Some people suggested that two people could acquire the mutex at once, but the whole point of a mutex is that that can never happen. And how could it be a deadlock? There's only one mutex involved. Technique 2 is the correct technique for this situation, but it /still/ has an undesirable result -- an implicit promise to the user is sometimes not honored. Scoring: 2 points each, all or nothing. No credit for longwinded answers that propose two or more undesirable results, only one of which is correct. 9. Streams The first three elements of the stream are given explicitly, and then the rest can be computed easily: (define s1 (cons-stream 1 (cons-stream 2 (cons-stream 3 (add-streams s1 ones))))) Another approach was to use the INTEGERS stream to generate two more streams (define ints2 (stream-cdr integers)) (define ints3 (stream-cdr ints2)) and then interleave those three streams. It doesn't quite work to say (define s1 (interleave integers (interleave ints2 ints3))) ;wrong because the interleaving wouldn't be round-robin -- there'd be an element of INTEGERS every other space in S1, whereas INTS2 and INTS3 would turn up only once every four spaces. But you could write a procedure that does a three-way interleave: (define (interleave-3 a b c) (cons-stream (stream-car a) (cons-stream (stream-car b) (cons-stream (stream-car c) (interleave-3 (stream-cdr a) (stream-cdr b) (stream-cdr c)))))) or the more elegant (define (interleave-3 a b c) (cons-stream (stream-car a) (interleave-3 b c (stream-cdr a)))) and then create the desired stream this way: (define s1 (interleave-3 integers ints2 ints3)) A common wrong solution was (define s1 (cons-stream (stream-range 1 3) (add-streams s1 ones))) This would generate a stream of streams, not a stream of numbers, and so the add-streams would fail. Better was (define s1 (append-streams (stream-range 1 3) (add-streams s1 ones))) but this fails for a different reason: append-streams isn't a special form, so the attempt to use S1 before it's defined will fail, like Louis Reasoner's version of the PAIRS procedure. Scoring: In an attempt at the add-streams solution, we gave one point for recognizing that three explicit cons-stream calls are required, and two points for getting the add-streams [or (map-streams + ...)] right. For the three-way interleave, we gave three points for the correct one shown above, or two points for nested calls to INTERLEAVE. For other methods, the scale was 3 correct. 2 trivial error. 1 has the idea. 0 other. 10. Mapreduce This question is essentially the same as the word-counting example you were shown, in that the mapper generates keys whose KV-VALUE is 1 and then the reducer is just +. But it's also a little like the pattern-matching example in that only certain lines contribute to the result; for the other lines, the mapper must output the empty list: (mapreduce (lambda (kvp) (if (exercise? (kv-value kvp)) (list (make-kv-pair (kv-key kvp) 1)) '())) + 0 "/chung-notes") One common alternative, which we accepted, gives non-exercise lines a value of 0, instead of filtering them out: (mapreduce (lambda (kvp) (list (make-kv-pair (kv-key kvp) (if (exercise? (kv-value kvp)) 1 0)))) + 0 "/chung-notes") This is less efficient, though, because the reduce processes have more pairs than necessary to add up. A fairly common error was to omit the '() as the alternative in the IF, which lost the filtering point. Another alternative solution was to use the /exercise number/ as the value of kv-pairs created by the mapper, and then use MAX as the reducer. This assumes that the exercises are consecutively numbered, and that each topic starts with exercise number 1, so it's a less robust solution, but we accepted it. Another mistake was to have the mapper output exactly the same kv-pairs found in the input, and then to do all the work in the reducer. This can work, but it's a waste of the efficiency gains that are possible using mapreduce! Scoring: 1 point for reducing with + correctly. 3 for the mapper: one for filtering out the non-exercises, one for making the correct kv-pair, and one for putting it in a singleton list. 11. Nondeterministic evaluator Here's the easy way: (define (an-element-satisfying pred lst) (let ((elt (an-element-of lst))) (require (pred elt)) elt)) If you didn't remember AN-ELEMENT-OF from the book, you'd end up reinventing it, like this: (define (an-element-satisfying lst) (let ((elt ((if (null? lst) (amb) (amb (car lst) (an-element-satisfying pred (cdr lst))))))) (require (pred elt)) elt)) or reinventing FILTER, like this: (define (an-element-satisfying pred lst) (cond ((null? lst) (amb)) ((pred (car lst)) (amb (car lst) (an-element-satisfying pred (cdr lst)))) (else (an-element-satisfying pred (cdr lst))))) Some students who didn't remember an-element-satisfying tried to get around the need for it by imagining that AMB itself would select list elements, with expressions like (AMB LST) or (APPLY AMB LST) or (AMBEVAL (CONS 'AMB LST)). The first of these would just return the entire list; the second would fail because AMB is a special form, not a procedure, so can't be used with APPLY; the third would fail because AMBEVAL is an STk procedure, not an ambeval procedure! We gave these solutions 2 points. A few students returned the string "No more values" instead of using (AMB) to indicate failure. We gave these solutions 1 point, because they seem to indicate a profound misunderstanding of how backtracking happens in the evaluator. A common, plausible-looking solution that doesn't actually backtrack at all was this: (define (an-element-satisfying pred lst) (cond ((null? lst) (amb)) ((pred (car lst)) (CAR LST)) ; wrong here! (else (an-element-satisfying pred (cdr lst))))) This correctly returns the first list element satisfying the predicate. But that return isn't within an AMB, so if the user says TRY-AGAIN, the result will be an immediate "no more values" message. These got no points. Scoring: 3 correct. 2 small error, e.g., no base case. 1 constructs the list of all satisfiers (with or without FILTER), then returns one at a time with AMB. 0 even worse. 12. Logic programming First, here's how we'd write it in Scheme: (define (doubled-element elt lst) (cond ((null? lst) '()) ((equal? (car lst) elt) (cons elt (cons elt (doubled-element elt (cdr lst))))) (else (cons elt (doubled-element elt (cdr lst)))))) So there are three cases: the base case, finding the desired element as the car of the list, or finding something else as the car of the list. Each of these possibilities is handled in a separate rule: (rule (doubled-element ?elt () ())) (rule (doubled-element ?elt (?elt . ?cdr1) (?elt ?elt . ?cdr2)) (doubled-element ?elt ?cdr1 ?cdr2)) (rule (doubled-element ?elt (?car . ?cdr1) (?car . ?cdr2)) (and (not (same ?elt ?car)) (doubled-element ?elt ?cdr1 ?cdr2))) The (NOT (SAME ...)) is important; without it, we'd get two answers for every time the desired element is seen, once doubled and once not doubled. The improper list notation (?ELT ?ELT . ?CDR2) is equivalent to two nested dotted pairs, (?ELT . (?ELT . ?CDR2)). But there's no such thing as a dotted triple! So you can't say (?A . ?B . ?C) ;wrong! Also, the left side (the CAR) of a dotted pair is an /element/, not a sublist. Some people wanted to have a single rule like this: (rule (doubled-element ?elt (?a ?elt . ?b) (?a ?elt ?elt . ?c)) ...) ; wrong thinking that ?A could be any number of elements, but alas the notation isn't that versatile. Of course it's possible to combine the two non-base-case rules into a single rule with OR in its body, but it's pretty complicated because the two rules have different-length lists as the rightmost member of the relation, so very few people who tried it succeeded completely. Scoring: 1 point for the base case, all or nothing; 2 points for each of the other rules (with 1 point for near-misses, including the failure to use two distinct variables for CDR1 and CDR2 above). 13. Trees What we're after is the shortest path from the root node to a leaf node. The simplest way (although not the fastest) is to find recursively the shortest path for each child, and then choose the shortest of those: (define (fast-grad tree) (if (null? (children tree)) (list (datum tree)) (cons (datum tree) (accumulate shorter (map fast-grad (children tree)))))) (define (shorter a b) (if (< (length a) (length b)) a b)) There's a slight handwave in this solution; we've used the version of ACCUMULATE that doesn't take a base-case argument but instead requires a nonempty data list. It's not obvious what a good base case value would be to use with SHORTER; the first choice that occurred to most students, namely the empty list, doesn't work, because the empty list /is/ shorter than any legitimate path, so that's what ACCUMULATE will return! What you really want is a list with some /large/ number of elements. Since students are generally expected to graduate in eight semesters, no prerequisite chain can reasonably be longer than that, so the list (1 2 3 4 5 6 7 8 9 10 11 12) should be large enough for practical purposes. Some people just used TREE as the base case value instead of (LIST (DATUM TREE)). This works, because of the way Trees are represented as pairs, but it's a violation of data abstraction. An equally plausible way, which turns out to be less simple, is to find all the paths to leaf nodes, and pick the shortest. It's less simple because finding all the paths involves flattening a deep-list of paths: (define (all-paths tree) (if (leaf? tree) (list (list (datum tree))) (map (lambda (path) (cons (datum tree) path)) (flatmap all-paths (children tree))))) The unusual base case value is needed because each path is a list, and all-paths therefore has to return a list of lists. Given all-paths, we can then pick the shortest: (define (fast-grad tree) (accumulate shorter (all-paths tree))) The most efficient way would be a breadth-first search, but it's more complicated; you have to construct a queue of tasks, in which each task includes a node and the path above that node. A few students used an easier BFS technique in which a simple BFS finds the datum of the least deep leaf node, and then the FIND-PLACE procedure (as used in lecture to find a city within the world tree) generates the path to that leaf node. But using FIND-PLACE undoes the efficiency gain of BFS, because FIND-PLACE uses a depth-first traversal to find the desired datum. So you might as well use the simpler techniques shown above. There shouldn't be any mutation in the solution! Unless you are specifically required to mutate the tree itself, problems about trees are always /easier/ to solve using recursive functions rather than trying to accumulate partial results with repeated SET!ing of a result variable. Instead of inventing the procedure SHORTER above, some people tried to use (ACCUMULATE MIN ...). But this returns a number, the minimum depth, instead of what we need, which is a path. By the way, we didn't take off points for this, but many solutions we saw would take exponential time to run, because the recursive calls for children were done more than once each. When doing tree recursion, if you'll need the result of a recursive call more than once, use a LET to name the value from the recursive call. A few people tried to solve this problem using AMB. Unless you're told otherwise, you're supposed to solve programming problems in real Scheme, not the variants in Chapter 4! But in any case, AMB wouldn't work for this problem, because in order to find /the shortest/ path, you have to be thinking about all the paths at once, not generating each path as a separate computation. If you use AMB to choose a path, you can't compare it with a different path. We gave these solutions no points. Scoring: 8 correct. 7 trivial error. 5 has the idea. 2 has an idea. 0 other. We gave no grades other than these five possibilities. "Has the idea" required a tree-recursive path generation with no tree/forest confusions, some attempt to find the shortest, and returning a path rather than just the length of the path. "Has an idea" meant getting some of those requirements but not all of them. A few people wrote solutions for /binary/ trees, rather than for Trees. We graded these papers on the scale above, then subtracted three points. 14. List mutation When a question is a whole page long, it's a good idea to read the question several times before you start answering it! This question asks you to use a particular algorithm to solve the problem; understanding the algorithm (and understanding what a sentinel is) was part of the problem. (define (oddeven! nums) ; this procedure is given in the question (let ((odds (list 'odd)) (evens (list 'even))) (oe-help odds odds evens evens nums))) Since ODDEVEN! calls OE-HELP using the same argument twice, for both ODDS and EVENS, you have to understand why. You get two hints: the formal parameters of OE-HELP (ODDS and ODDLAST, EVENS and EVENLAST) and the box and pointer diagram of a recursive call, which should make it clear that ODDLAST is the spine pair containing the last number already known to be odd, and EVENLAST is the spine pair containing the last number known to be even. The code you write will mutate the cdrs of those pairs to add elements to ODDS and EVENS, and at the end, to splice the two together (removing the sentinel pairs): (define (oe-help odds oddlast evens evenlast nums) (cond ((null? nums) (set-cdr! oddlast (cdr evens)) (set-cdr! evenlast '()) (cdr odds)) ((odd? (car nums)) (set-cdr! oddlast nums) (oe-help odds nums evens evenlast (cdr nums))) (else (set-cdr! evenlast nums) (oe-help odds oddlast evens nums (cdr nums))))) That's it! The use of sentinels dramatically reduces the number of special cases (e.g., finding the /first/ odd number). Solutions that gave the correct result but didn't take advantage of the sentinels got 6 points. Since the desired result is a sequential list, the same size as the input, and with the same elements, you could imagine mutating either the CARs or the CDRs of the spine pairs to do the reordering. But in fact it would be much harder to do it using SET-CAR!. Consider this example: > (oddeven! (list 2 4 6 8 10 3 12 14)) (3 2 4 6 8 10 12 14) How would you get the 3 to the front using SET-CAR!? Since we don't want to change the order of appearance of the even numbers, you couldn't just exchange the 3 with the 2. Instead you'd have to move each of the first five even numbers one position rightward in the list. You'd have to write a move-elements-rightward loop similar to some of the vector programming examples we've seen. But using SET-CDR!, you just have to modify three pairs (the sentinel, the pair whose car is 10, and the pair whose car is 3), no matter how many even numbers came before the first odd number. (Some sorting algorithms work by exchanging the positions of two numbers at a time; that's the sort of situation in which SET-CAR! would be useful.) You've seen the technique of keeping pointers to both front and back of a list before, in the book's example of inserting into a queue. Since we want to put newly seen numbers at the /end/ of the odd-numbers list or the even-numbers list, it's ODDLAST or EVENLAST that we're going to mutate, not ODDS or EVENS, and it's ODDLAST or EVENLAST that will have a new value in each recursive call. Many, many people had expressions of the form (set-car! something (cdr something-else)) or (set-cdr! something (car something-else)) The CAR and the CDR of pairs in the spine of a list have two very different meanings! The CAR is an element; the CDR is a sublist. It's almost always wrong to mix them up. In particular, many people said (set-cdr! oddlast (car nums)) probably because they were thinking "I want ODDLAST to point to the /first/ of the not-yet-repositioned numbers." But that can't be right; the result wouldn't be a list at all. We gave these solutions at most 4 points. A very common mistake was to leave out the (set-cdr! evenlast '()) We only took off a point for it, but the result is actually pretty bad: if the last even number isn't the last number in the original list, the returned list will be circular, with the last spine pair pointing back to the odd number that originally came after it. Notice that there's no SET! in this program! Many students seem to think that the recursive call to OE-HELP has to have exactly the form (oe-help odds oddlast evens evenlast nums) so, for example, instead of saying (oe-help odds nums evens evenlast (cdr nums)) they said (set! oddlast nums) (set! nums (cdr nums)) (oe-help odds oddlast evens evenlast nums) This doesn't hurt, but it's unnecessary; it makes the program much harder to read; and it /does/ hurt if you happen to do the SET!s in the other order. You were told not to allocate new pairs in your solution. If you followed this rule until the base case, and then said (APPEND (cdr odds) (cdr evens)), you got 6 points; if you used CONS or LIST or APPEND in the recursive cases, you got at most 2 points. (It would be correct to use APPEND!, the mutating version of APPEND, in the base case.) Scoring: 8 correct. 7 trivial mistake. 6 has the idea. 6 implements ODDEVEN! w/o new pairs but not using sentinels. 4 does the right thing, then ruins it with extra mutation. 2 has an idea (e.g., mutation, but not in any coherent way). 0 other. The difference between "the idea" and "an idea" was often the point already mentioned about (set-cdr! something (car something-else)). 15. Metacircular evaluator EVAL-IN-ENV is a special form, so we know that we have to modify MC-EVAL by adding a COND clause to test for it: ... ((eval-in-env? exp) (eval-eval-in-env exp env)) ... and provide the usual mechanism for recognizing a special form: (define (eval-in-env? exp) (tagged-list? exp 'eval-in-env)) The point of the EVAL-IN-ENV form is to evaluate its first argument in some particular environment: (mc-eval (cadr exp) ) ; an excerpt One subtlety is that to find the environment, we look in a procedure, but that procedure is /the value of/ the second argument, which has to be evaluated in /the current/ environment. So here's the rest of it: (define (eval-eval-in-env exp env) (mc-eval (cadr exp) (procedure-environment (mc-eval (caddr exp) env)))) Of course it'd be better style, and more consistent with the code in the text, to invent selectors for the pieces of an EVAL-IN-ENV expression: (define eie-expr cadr) (define eie-proc caddr) (define (eval-eval-in-env exp env) (mc-eval (eie-expr exp) (procedure-environment (mc-eval (eie-proc exp) env)))) That's all there is to it! Other than forgetting to evaluate the caddr of the expression, the most common error was to think you were writing a new primitive procedure instead of a new special form, i.e., (define (eval-in-env exp proc) ...) with no indication of where the value of PROC comes from. Other people, who did recognize the need to find the procedure somewhere, invented complicated and usually wrong methods to find it. The least wrong was to call LOOKUP-VARIABLE-VALUE instead of MC-EVAL. The expression providing the procedure was indeed a variable in the example, but, as usual, it could be /any/ expression whose value is a procedure: (eval-in-env (set! counter 0) (let ((counter 0)) (lambda () ...))) Worse than that was to invent an ad-hoc association list of procedure names and values -- that's what the environment is for! A couple of people used MAKE-PROCEDURE to turn the given expression into a thunk, with a remembered environment borrowed from the given procedure, and then used MC-APPLY to invoke the thunk. This could be made to work, but it's a needless complication. Scoring: 1 point for the COND clause in MC-EVAL. 2 points for EVAL-IN-ENV?. 2 points for (MC-EVAL (CADDR EXP) ENV). 1 point for PROCEDURE-ENVIRONMENT. 2 points for (MC-EVAL (CADR EXP) ...). -2 to -4 points if the code you add breaks something else, but that was rare.