CS 61A Spring 2005 Final exam solutions 1. True/False The length of the list returned by MAP is always equal to the length of its second argument. TRUE. This was meant to be an easy one. The point is to distinguish MAP from FILTER, which by design typically returns a list smaller than the argument, and from EVERY, which, because of its flattening effect, often returns a *longer* sentence: > (map (lambda (x) (se x x)) '(a b c d)) ((a a) (b b) (c c) (d d)) > (every (lambda (x) (se x x)) '(a b c d)) (a a b b c c d d) Since MAP can return a structured list, it uses the structure to preserve the one-for-one element count. (define j (list (se 'hello 'dolly) (se 'goodbye 'holly))) (append j (map (lambda (k) (every first k)) j)) This expression contains a data abstraction violation. FALSE. J is a list, so MAP is correct; each element K is a sentence, so EVERY is correct. (As for FIRST, it's the only possibility, since its argument is a word each time.) Of the conventional, data-directed and message-passing paradigms, message-passing is the closest in spirit to object-oriented programming. TRUE. OOP is all about sending messages to objects. We can use the substitution model of evaluation, instead of the environment model, when none of the procedures use assignment or mutation. TRUE. It's mutation that requires us to keep track of sets of local variables. (Some people did raise a question about internal defines, but technically, even those are okay, since they can be treated as a kind of LET (look up LETREC in the reference manual).) Dynamic scoping makes it easier than lexical scoping to tell what value a variable will have just by reading the text of the program. FALSE. Dynamic scope does have its own virtues, I think, but this is not one of them. Lexical scope means you can figure out which variable is meant just from the text of the program -- you find a declaration whose scope surrounds the appearance of the name. With dynamic scope, you have to know which procedure calls which other procedure, which might be different for different calls to the same procedure. In the lazy evaluator, compound procedures do not need to remember what environment they were created in (the "procedure environment"). FALSE. The lazy evaluator is still lexically scoped. It's in the Logo interpreter, which is dynamically scoped, that procedures don't have to remember where they were created. The following could result in deadlock: (define s1 (make-serializer)) (define s2 (make-serializer)) (parallel-execute (s1 (s2 (lambda () 'airbag))) (s1 (s2 (lambda () 'treefingers)))) FALSE. Since S1 is the outer serializer in both threads, at most one of the threads can get through that first hurdle at a time. It's only if the serializers were used in different orders that a deadlock could happen. (If the inner lambda expressions called other procedures, then *those* procedures might cause a deadlock, but that can't happen since we see everything they do.) Scoring: Two points each. 2. What will Scheme print / box & pointer (let ((x (list 61 'a))) (append x (cons x x))) The only slightly complicated part here is knowing how APPEND works. X is the list (61 A), and APPEND makes a copy of its first argument but with the cdr of its last pair pointing to the second argument. So we have --->XX---->XX---->** | | || V V VV 61 A XX---->X/ | | V V 61 A The pair shown above as ** is the one generated by CONS. Its car and its cdr point to the same pair, the one just below it, which is the head of the list X. (Note, when an arrow points to a pair, it points to the entire pair, even though in the picture one arrowhead seems to point to the left half and one to the right half.) One error some people made in the diagram was to make two new pairs for another copy of (61 a) for the CONS, so that each side of the pair made by CONS would have its own distinct list. But CONS only makes a single new pair! (It's the one marked ** in the picture above.) APPEND does copy its first argument, but not its second, because of the way it calls CONS to do its job: (define (append a b) (if (null? a) b (cons (car a) (append (cdr a) b)))) If you start from the beginning and just follow the CDRs of the spine, you'll see that this is a list of five elements, the third of which is the list X. So the print form is (61 a (61 a) 61 a) (let ((x (list 61 'a))) (set-car! x (cdr x)) x) Here X is originally the list (61 A), but we replace its car (its first element) with its cdr (which is the list (A)). So we end up with this: +------+ | V --->XX---->X/ | V A It's still a two-element list: ((a) a) Some people drew a correct diagram for this, then crossed it out and drew an incorrect one with three pairs! Scoring: One point per diagram, one point per print form. 3. Higher order function. There are several ways to do this. For example: (define (evencount sent) (count (keep even? (every count sent)))) (define (evencount sent) (count (keep (lambda (wd) (even? (count wd))) sent))) (define (evencount sent) (accumulate + 0 (every (lambda (wd) (if (even? (count wd)) 1 0)) sent))) The second way requires only one higher order function (keep), but does need a lambda expression to specify the more complicated filtering predicate. I like the first way, which uses two higher order functions, but is expressed entirely in terms of primitives. The third way uses accumulate instead of the outer call to count, at the cost of having to generate a list of ones and zeros as an intermediate result. Some people wrote solutions making a local variable with initial value 0, then using a for-each to iterate over the words in the sentence, and using set! to add 1 to their variable for each even-count word. You can get that to work, but please don't. You should be able to solve an easy functional problem like this one using purely functional techniques; get over that 12-year-old BASIC programming mindset in which every problem has to be solved by looping and incrementing variables. Scoring: The "standard four-point scale," which is 4 correct 3 has the idea 2 has an idea 0 other Here are some specific cases: applying LENGTH rather than COUNT to a word: 3 (KEEP EVEN? SENT): 2 (ACCUMULATE + (KEEP ...)): 2 MAP instead of KEEP: 2 missing or misplaced LAMBDA: 1 ACCUMULATE of one-argument function: 0 using recursion: 0 4. Streams. As usual with interleave problems, I like to draw the elements this way: ____ seed ____ ____ ____ ____ ____ (word 'c w) ____ ____ ____ ____ (word w 'd) The first three elements are easy to fill in: A ____ seed CA ____ ____ ____ ____ ____ (word 'c w) AD ____ ____ ____ ____ (word w 'd) Now that we know three elements of the complete stream, we can compute three elements of each of the interleaved substreams: A ____ seed CA CCA CAD ____ ____ ____ ____ ____ (word 'c w) AD CAD ADD ____ ____ ____ ____ (word w 'd) Now that we know seven elements of the complete stream, we can compute seven elements of each of the interleaved substreams, but we don't need that many: A ____ seed CA CCA CAD CCCA CCAD ____ ____ ____ ____ ____ (word 'c w) AD CAD ADD CCAD ____ ____ ____ ____ (word w 'd) Reading this from left to right, we end up with A CA AD CCA CAD CAD ADD CCCA CCAD CCAD The most common wrong answer was to stream-map the given function over only its own half of the stream FOO, as if the problem were (define s1 (cons-stream 'a (stream-map (lambda (w) (word 'c w)) s1))) (define s2 (cons-stream 'a (stream-map (lambda (w) (word w 'd)) s2))) (define foo (stream-cdr (interleave s1 s2))) This gives A CA AD CCA ADD CCCA ADDD etc. Other mistakes were to think that the letter W should be part of the result, not paying attention to the difference between variable names and quoted data, or, similarly but even more strangely, thinking the letters FOO should be in the result. Scoring: One point for the first three elements, one point for the next four elements, one point for the last three. For each point you have to get all of them, and we do *not* compute the implications of early errors; we just compare your answers against the correct ones. 5. List mutation, circular lists (not really a stream question!) We intended this question as an easy equivalent of "what will Scheme print" for circular lists, since people had trouble with mutation on midterm 3. We didn't worry about the exact format of the result of SHOW-STREAM, as long as you got the elements right. You were not required to draw diagrams; we looked only at what you said would be the printed result. (define y (let ((x (list 1 2))) (set-cdr! x x) x)) (define s (list->stream y)) (show-stream s 10) ++ V| y--->XX ...>X/ | | V V 1 2 The second pair is disconnected by the set-cdr! and does not form part of the result. So this is (1 1 1 1 1 1 1 1 1 1 ...) (define y (let ((x (list 1 2))) (set-cdr! (cdr x) x) x)) (define s (list->stream y)) (show-stream s 10) +-------+ V | y--->XX---->XX | | V V 1 2 This time both pairs are part of the result, and both elements are repeated forever: (1 2 1 2 1 2 1 2 1 2 ...) (define y (let ((x (list 1 2))) (set-cdr! (cdr x) (cdr x)) x)) (define s (list->stream y)) (show-stream s 10) ++ V| y--->XX---->XX | | V V 1 2 This time it's only the second element that repeats: (1 2 2 2 2 2 2 2 2 2 ...) Scoring: One point each. 6. Environment diagrams. If you start by looking at the four possible diagrams, you'll see that they represent the four possibilities for two yes/no questions in combination: * Is FOO defined in the global environment? (Yes in A and B.) * Does frame E2 extend frame E1? (Yes in B and D.) (define (foo x) (+ x 1)) (let ((x 2)) (foo x)) Here FOO is clearly globally defined, so it has to be A or B. The LET creates frame E1. Since FOO's right bubble points to G, the call (FOO X) must extend G, as in A or C. So the answer is A. (let ((x 2)) (define (foo x) (+ x 1)) (foo x)) Here FOO is defined inside a LET, so it has to be C or D. Since FOO's right bubble points to E1, the call (FOO X) extends E1, as in B or D. So the answer must be D. (define (foo x) (let ((x 2)) (+ x 1))) (foo 2) Here FOO is again defined globally, so it's A or B. But this time it's the (FOO 2) that creates frame E1, and frame E2 is created by the LET, which happens inside E1, so E2 extends E1, as in B or D. So the answer is B. Scoring: One point each. Most people got D for the second one; the common error was to exchange A and B. 7. Order of growth. (a) (FACTORIAL N) involves N recursive calls, each of which takes constant time for one call to each of =, *, and -. So it's Theta(N). (b) (CHOOSE N K) involves three calls to FACTORIAL, plus two constant-time arithmetic operations (/ and *). Since K is less than N, we can just pretend all three calls are (FACTORIAL N) for a pessimistic estimate, so this is still Theta(N). (Some people said Theta(3N), which is of course fine, since constant factors are unimportant in Theta notation.) (c) (SUBSETS N) involves N calls to HELPER, each of which requires a call to CHOOSE plus a few constant-time operations. Since each call to CHOOSE is Theta(N), the total is Theta(N^2). Almost everyone got (a) and (b); most people got (c), too, but a fairly common wrong answer was Theta(2^N). I'm not sure where this came from. (It *would* take Theta(2^N) time to *list* all the subsets, since there are 2^N of them. But we're just asking how many there are.) By the way, this is a good example of a problem in which a little math beats a lot of programming skill; since the value of (SUBSETS N) is just 2^N, it can be computed in constant time if we just call the primitive EXPT instead of using the algorithm shown here. Scoring: 2 points each. (If you're wondering why this problem was worth 6 points when the environment one was only worth 3, it's because an earlier draft of the test had a more complicated environment question with four expressions and six pictures, and when we made the late decision to simplify the problem, I didn't rearrange the points carefully!) 8. Trees in OOP I still don't understand why people found this one so difficult, and came up with so many convoluted wrong answers. Let's first review how size-counting and mapping work for regular trees: (define (size tree) (accumulate + 1 (map size (children tree)))) (define (treemap fn tree) (make-tree (fn (datum tree)) (map (lambda (child) (treemap fn child)) (children tree)))) Note in both cases that it's (MAP ... (CHILDREN TREE)), not TREEMAP, since (children tree) is a forest, not a tree. Using 1 as the base case for the accumulate (representing the top-level node itself) is a trick you might not think of, in which case you'd say (+ 1 (accumuulate + 0 ...)) which would be fine too. Now, what we are doing is changing the representation of trees (a/k/a nodes) so that instead of a pair (cons datum children), we use an object. How do objects work? Instead of calling functions with the object as argument, like (FOO OBJ), we send the object a message, (ASK OBJ 'FOO). And instead of creating a new one with a constructor like MAKE-TREE, we use INSTANTIATE. So, knowing all that, the transformation to OOP is really straightforward: (define-class (node datum children) (method (size) (accumulate + 1 (map (lambda (c) (ask c 'size)) children))) (method (map fn) (instantiate node (fn datum) (map (lambda (child) (ask child 'map fn)) children)))) Wherever I have CHILDREN or DATUM, you could say (ASK SELF 'CHILDREN) or (ASK SELF 'DATUM), but it's not necessary within a method of the same class. See? It's exactly the same structure. What were all the people thinking who asked if the children of an oop-tree should also be oop-trees? Of *course* they should! The whole power of the idea of trees comes from the fact that each subtree works exactly the way the whole tree works. It would be bizarre to have a tree in which one node is represented differently from the other nodes. The softhearted TAs decided to announce this on the board during the exam, but it shouldn't have been necessary. A few notes on various complications in your solutions: * Some people were worried that having a method named MAP would prevent the use of the primitive MAP procedure, so they rewrote MAP with a different name. This is a reasonable fear, but as it turns out, the OOP system doesn't define procedures named after the messages. The messages are just part of a COND structure looking roughly like this: (cond ((eq? msg 'size) (lambda () ...)) ((eq? msg 'map) (lambda (fn) ...)) ...) So the method functions are anonymous. * There's no excuse for a SET! anywhere in this problem, since you were not asked to write mutator methods for tree nodes. Computing the size and computing a new tree with a function mapped over the nodes of the old tree are purely functional problems. I was astonished at the complicated code some of you managed to write, none of which worked, involving things like class or instance variables starting at 1 and incremented for each child node. Some such solutions would work provided that there is only one tree in the world, or provided that you only ask for a tree's size once. Pfui. * There's also no excuse for using CAR or CDR on a node -- this would be a data abstraction violation even for regular trees, and won't work at all for a tree represented as an object, i.e., a procedure. You can use CAR and CDR on forests, if you write recursive helper functions that take forests as arguments instead of doing it the easy way with MAP. * Many people added extraneous base case tests. Every tree has at least one node -- this is especially obvious in the OOP version, since a nodeless tree couldn't be asked to carry out these node-based methods! And MAP is perfectly happy to deal with an empty list, so you don't have to worry about leaf nodes as a special case. But we didn't take off for these if you didn't break the important parts. * There's no variable named TREE in this class. There's a variable named NODE, but it's the class, not any particular instance. So, no (DATUM TREE) or (CHILDREN NODE). * I get a little angry when you try to avoid thinking about the problem you were given by converting it (often with great difficulty) into some other kind of problem, so we tended not to give the benefit of the doubt in assigning part credit to solutions involving things like (length (flatmap (lambda (x) x) tree)) ; wrong! or (treemap fn (make-tree datum children)) ; wrong! Besides being wrong-headed and intellectually lazy, these putative solutions don't work. FLATMAP's domain is deep lists, not trees; MAKE-TREE would have to be applied to every child node, too, not just to the top-level node. But don't bother working out the details of why these solutions fail, just stop thinking in this reductionist style in the first place. Scoring: We graded this by subtracting points from 8, with the special cases of zero points for totally incoherent solutions and for constructing old-style trees with (MAKE-TREE DATUM CHILDREN). -4 for (+ 1 (length children)) [because it doesn't count grandchildren] -2 for (children tree), (children node), etc. -2 for no ASK in SIZE; -2 for no ASK in MAP. -2 for no INSTANTIATE in MAP. -2 for incorrect algorithm in SIZE (e.g., missing toplevel node) -2 for incorrect algorithm in MAP (e.g., calling FN on trees not DATUMs) -2 for FLATMAP -2 for infinite recursion, e.g., (ASK SELF 'SIZE) -1 for ASK or INSTANTIATE attempted but wrong notation (-1 each time) -1 for FOR-EACH instead of MAP -1 for (ASK NODE 'DATUM) This list is not exhaustive, but covers the most common errors. 9. Nondeterministic make-change Here's the COUNT-CHANGE we're starting from: (define (count-change amount denoms) (cond ((= amount 0) 1) ((or (< amount 0) (null? denoms)) 0) (else (+ (count-change amount (cdr denoms)) (count-change (- amount (car denoms)) denoms))))) The main difference in our version is that instead of reporting the *number* of solutions, we must report the *actual* solutions. So, in the two base cases, the 1 is replaced by one actual solution, and the 0 is replaced by an indication that there are no solutions. In the ELSE clause, the two arguments to + represent two alternative ways to generate the desired change; the + will be replaced by an AMB whose alternatives construct those two ways. What is the one actual solution for (= AMOUNT 0)? What coins do you use to make zero cents? You don't use a zero-cent coin; there's no such thing. You use an empty set of coins, which we represent as the empty list. How do you indicate that there are no solutions? This is what it means for a computation to fail; we indicate it with (AMB). In the ELSE clause, what does the subexpression (count-change amount (cdr denoms)) represent? It means that we are not using any coins of denomination (car denoms), and still have the entire amount to make out of the other coins. This will be just (make-change amount (cdr denoms)) in our new program. But the subexpression (count-change (- amount (car denoms)) denoms) is more interesting. It means that we *are* using at least one coin of size (car denoms). So when we are constructing an actual set of coins used, we must include (car denoms) in the list, along with whatever set is needed to make the smaller amount after subtracting it from AMOUNT: (cons (car denoms) (make-change (- amount (car denoms)) denoms)) Here's the whole program: (define (MAKE-change amount denoms) (cond ((= amount 0) '()) ((or (< amount 0) (null? denoms)) (AMB)) (else (AMB (MAKE-change amount (cdr denoms)) (CONS (CAR DENOMS) (MAKE-change (- amount (car denoms)) denoms)))))) (We didn't take off points for forgetting to change the name to make-change.) This is the best solution; it gives each possible combination of coins exactly once. But some students came up with another solution that we accepted even though it counts, e.g., (1 3 3) and (3 1 3) as separate combinations of coins: (define (make-change amount denoms) (cond ((= amount 0) '()) ((< amount 0) (amb)) (else (let ((coin (an-element-of denoms))) (cons coin (make-change (- amount coin) denoms)))))) Several students had variants of this version. AN-ELEMENT-OF is given in the text; it's not good enough to say (AMB DENOMS), which would have only one possible value, the entire list of denominations; nor can you say (APPLY AMB DENOMS), although that's closer, because AMB is a special form, not a procedure. Although I don't think anyone actually did it, the problem of multiple versions of the same set of coins can be solved by modifying this solution slightly: (define (make-change amount denoms) (cond ((= amount 0) '()) ((< amount 0) (amb)) (else (let ((coin (an-element-of denoms))) (cons coin (make-change (- amount coin) (member coin denoms))))))) This says that if AN-ELEMENT-OF chooses a certain coin, only coins from that one to the end of the DENOMS list are eligible to come after it in an answer. So, in the (1 3) example from the exam, the program can't cons a 3 in front of a list containing a 1. This may be the most elegant solution. The second version doesn't need a base case check for (null? denoms) because that's built into an-element-of. Scoring: One point for each of the two base cases; the ELSE clause is graded on the standard four-point scale. In particular: Mixing up the two subexpressions in the AMB in the else clause, e.g., consing onto the wrong one, or throwing in an extra CONS, at most 3 points. No CONS, or the CONS outside the AMB (so that a coin is consed onto both recursive calls), at most 2 points. No AMB, 0 points. If you're still having trouble understanding the solution, you might want to examine the following non-AMB variant, which returns a list of *all* the ways to make the desired change: (define (make-change amount denoms) (cond ((= amount 0) '(())) ((or (< amount 0) (null? denoms)) '()) (else (APPEND (make-change amount (cdr denoms)) (MAP (LAMBDA (ANS) (CONS (CAR DENOMS) ANS)) (make-change (- amount (car denoms)) denoms)))))) The big change is in the ELSE clause, in which AMB is changed to APPEND to combine two lists of answers, and (car denoms) has to be consed onto *each answer* in a list-of-answers, which is why the MAP is needed. Each base case is changed, too; the first one returns *a list containing* the one empty-list answer; in the second, since there are no answers, it returns an empty list-of-answers. 10. Tree traversal. This should have been much easier than it apparently was. You've seen many tree-node-counting procedures such as (define (count-nodes tree) (accumulate + 1 (map count-nodes (children tree)))) (define (count-leaves tree) (accumulate + (if (leaf? tree) 1 0) (map count-leaves (children tree)))) (define (count-numbers tree) (accumulate + (if (number? (datum tree)) 1 0) (map count-numbers (children tree)))) What we wanted was just a generalization of that to an arbitrary test: (define (count-property pred tree) (accumulate + (if (pred tree) 1 0) (map (lambda (child) (count-property pred child)) (children tree)))) Many of you didn't want to use ACCUMULATE. If you just ignored the ACCUMULATE you got at most 5 points. Some people managed to accommodate the ACCUMULATE without really using it, by saying (accumulate (lambda (element result-so-far) (your-function element)) 0 (list tree)) which indeed applies your-function to the tree. We didn't take off for this, although it's not exactly in the spirit of the problem. It's possible, but more complicated, to do the recursion in the first (function) argument to ACCUMULATE rather than in the last (data) argument: (define (count-property pred tree) (accumulate (lambda (element result-so-far) (+ (count-property pred element) result-so-far)) (if (pred tree) 1 0) (children tree))) This is fine, but many people who tried it failed, because they didn't quite get how the function argument to accumulate is called. Its two arguments are (in this case) of different types; the first is an element of the data list, while the second is of whatever type the function itself returns. This isn't a problem with a function like +, whose domain and range are the same (namely numbers). But your function has to take a tree as (its first) argument and return a number, so the second argument must also be a number. People tried functions of two numbers (which would be correct if the third argument to ACCUMULATE were a list of numbers, as in our preferred solution), or functions of two trees. Even worse was to give ACCUMULATE a one-argument function, rather than a two-argument functionn, as its first argument -- trying to turn ACCUMULATE into MAP, basically. Since we told you that we meant the version of ACCUMULATE on page 116 of the text, many people found ENUMERATE-TREE on the same page. This was unfortunate, since what the book calls a "tree" is not a datum/children tree at all, but a deep list. So their ENUMERATE-TREE is what I'd call DEEP-FLATTEN. Solutions based on this error tended to score between 3 and 5 points, depending exactly how ENUMERATE-TREE was used. Scoring: One point for using + either as the first argument to accumulate or in some equivalent way. Two points for the (if (pred tree) 1 0) either as the second argument or in some equivalent way; of those two points, one was for converting the true/false result from PRED into a number, and the other was for applying PRED to TREE rather than to (DATUM TREE), which is important in order for the LEAF? example to work. (You can always put DATUM in the PRED argument if you want it, as in (lambda (tree) (number? (datum tree))) but you can't undo a DATUM in count-property itself.) The remaining four points were for the third argument, in our solution, or the equivalent in more complicated solutions, on the standard four-point scale. In particular, both (map pred (children tree)) and (map count-property (children tree)) lost two points. Solutions doing deep-list manipulation instead of datum/children tree manipulation generally got zero of these four points. 11. Logic programming. (a) PREFIX. There were two basic approaches to this problem. The one we expected was this: (assert! (rule (prefix ?list ()))) (assert! (rule (prefix (?car . ?cdr1) (?car . ?cdr2)) (prefix ?cdr1 ?cdr2))) The first rule says that the empty list is a prefix of any list. The second says that a nonempty prefix must start with the first element of the big list, and that its cdr must be a prefix of the big list's cdr. Note that it's "()" and not "'()" for the empty list. Although our query evaluator uses the Scheme reader to turn parentheses into list structure, it does *not* use the Scheme EVAL, and so there's no issue of quoting versus evaluating any part of a query, assertion, or rule. Nothing is evaluated in the Scheme sense. Putting (QUOTE ()) in a rule means that the query must have an element exactly matching that, quote and all. But we didn't take off for this small mistake. Another mistake for which we didn't take off points was to have a set of rules that handle every case except for (PREFIX () ()), which should be true. The usual way to get into this trouble was to try to make a single rule handle all cases, like this: (assert! (rule (prefix (?car . ?cdr1) ?list2) ; NOT QUITE RIGHT (or (same ?list2 ()) (and (same ?list2 (?car . ?cdr2)) (prefix ?cdr1 ?cdr2))))) The problem is that the conclusion of this rule requires that list1 be a pair, not the empty list. The other approach uses APPEND, which allows a single rule: (assert! (rule (prefix ?big ?small) (append ?small ?other ?big))) This says that a prefix appended to some other stuff must give the big list. (b) SUBLIST. The answer we expected was this: (assert! (rule (sublist ?big ?small) (prefix ?big ?small))) (assert! (rule (sublist (?car . ?big) ?small) (sublist ?big ?small))) The first rule says that any prefix is a sublist. Sublists that aren't prefixes must also be sublists of ?BIG with its car removed, which is what the second rule says. There are also a few APPEND-based answers for this one: (assert! (rule (sublist ?big ?small) (and (append ?left ?smallright ?big) (prefix ?smallright ?small)))) or (assert! (rule (sublist ?big ?small) (and (append ?left ?small ?leftsmall) (prefix ?big ?leftsmall)))) or (assert! (rule (sublist ?big ?small) (and (append ?left ?small ?leftsmall) (append ?leftsmall ?right ?big)))) These rules are all essentially similar; they divide ?BIG into three pieces, here called ?LEFT, ?SMALL, and ?RIGHT. ?SMALL is the one we're trying to verify as a sublist of ?BIG. Variables ?LEFTSMALL and ?SMALLRIGHT combine two of these three pieces. Many had variants of these rules with bunches of unnecessary SAME clauses, I guess because you think every piece of a computation has to have its own name. This is bad style, but harmless. Many other people had extra rules for unnecessary base cases, such as (SUBLIST ?BIG ()). That one isn't quite harmless, because it leads to duplication of answers, but we didn't take off for it. Another error, for which we did take off points, was to write rules that work only if the sublist is either a prefix of the big list or a prefix of the cdr of the big list -- in other words, there could be only one extra list element before the beginning of the sublist. Scoring: Three points each. One point off for missing base case in (a). No points off for redundant rules that don't lead to infinite loops, e.g., (SUBLIST ?BIG ()). One point off for forgetting that the big list, which is the *left* element of PREFIX and SUBLIST, is the *right* element of APPEND. Zero points for rules whose bodies are about variables other than the ones in the conclusion: (rule (prefix ?x ?y) ; HUH? (prefix (?a . ?b) (?a . ?c))) Zero points for part (b) if the rules are the same as the PREFIX rules in part (a)! The same rules can't have two different meanings. Zero points for any solution using composition of functions, such as (rule (prefix (append ?x ?y) ?x)) ; VERY WRONG! 12. Add streams to evaluator. There are three key points to understand here: * The car must be evaluated when CONS-STREAM is done. * The cdr must be evaluated when STREAM-CDR is done. * The environment to evaluate the cdr must be in the stream. It doesn't matter exactly how you represent a stream, as long as it includes the three pieces evaluated-car, unevaluated-cdr, and env. I'm going to use a tagged list: (STREAM car cdr env) So in mc-eval we have: (cond ... ((cons-stream? exp) (LIST 'STREAM (EVAL (CADR EXP) ENV) (CADDR EXP) ENV)) ...) Note that we can use ENV here because it's an argument to mc-eval. In the primitive procedure list we have (list ... (list 'stream-car CADR) (list 'stream-cdr (LAMBDA (S) (MC-EVAL (CADDR S) (CADDDR S)))) ...) Again, the selectors here will depend on the constructor used in mc-eval. (Note that you have no choice about the *selectors* used in mc-eval, since they are selecting from a cons-stream expression, whose format you are stuck with, not from your own internal data structure.) The key thing is that mc-eval evaluates the first argument to cons-stream, but it's stream-cdr that evaluates the second one. It's worth noting that one way to include an unevaluated expression and the current environment in a data structure is to construct a metacircular thunk (a metacircular Scheme procedure with no arguments): (list 'stream (mc-eval (cadr exp) env) (MAKE-PROCEDURE '() (CADDR EXP) ENV)) The empty list above is the formal parameter list for the thunk. In this case, to evaluate the cdr-expression when stream-cdr is called, you say (mc-apply (caddr s) '()) instead of calling mc-eval (since mc-apply will itself call mc-eval on the body of this thunk). Another way to do it, although I find this kludgy, is to create an *STk* thunk, because it will preserve the current STk environment, from within mc-eval, including the current value of mc-eval's variable ENV, which has the metacircular environment we're trying to preserve: (list 'stream (mc-eval (cadr exp) env) (LAMBDA () (MC-EVAL (CADDR EXP) ENV))) or (list 'stream (mc-eval (cadr exp) env) (DELAY (MC-EVAL (CADDR EXP) ENV))) In this case we have to call the generated STk procedure from stream-cdr: ((caddr s)) or (force (caddr s)) I'm less fond of this solution because, unlike the others, it wouldn't work if we were writing a Scheme interpreter in a language other than Lisp or one of its intellectual children (so that we'd have the ability to create a procedure and pass it around as data). Note that (LAMBDA () (CADDR EXP)) or (DELAY (CADDR EXP)) is incorrect; if you make an STk thunk, it has to include the evaluation of the cdr with the correct environment as part of what it promises. Some people recognized the need to delay evaluation until stream-cdr is called, but didn't think to include the environment among the saved data. They used the-global-environment, used a nonexistent (in that context) variable ENV, or just called mc-eval with only one argument. Typically, the-global-environment solutions got three points, and the others two points, depending on what else was wrong. Scoring: We subtracted points from 6 as follows: -1 for selectors in stream-car and stream-cdr not matching the constructor of the saved stream in mc-eval. -2 for not evaluating the car in mc-eval. -2 for not evaluating the cdr in stream-cdr. -2 for not saving the environment. Most wrong solutions lost both the evaluate-cdr points and the save-env points for the same mistake, since this was the central issue in the problem. In some cases we assigned -1 for a not-quite-right attempt to do one of the 2-point tasks. (Using the-global-environment is an example, getting -1 for eval-cdr and -2 for save-env.)