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 /noncircular/ list structure. If
circularity is ruled out, then in order for (SETCDR! (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 '() '()))
(setcar! x x)
(setcdr! x x)
With this singlepair 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 AMBlike 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
(defineclass (Tree datum children)
(method (treemap! fn)
(set! datum (fn datum))
(foreach (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 mytree 'datum)
rather than (datum mytree). 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 FOREACH
to ask each child to run its TREEMAP! method.
It's okay, but not ideal, to use MAP instead of FOREACH, because MAP
constructs an unnecessary list duplicating the existing CHILDREN list.
Since no return value is specified, it's okay to return whatever FOREACH
returns, but it's also okay to say something like 'OKAY after the call
to FOREACH.
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! somefunction)
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 nonOOP 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 nonOOP 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 FIRSTTREE and RESTOFTREES, but since OOP is more
commonly used for sequential programming, a more common approach would be
to use FIRSTTREE and NEXTTREE; 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 FOREACH 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 nonOOP Tree.
1 (set! children (map ...)).
0 other, including tree/forest confusion.
2 points for everything else: the instantiation variables, the
DEFINECLASS 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 (listbutlast lst)
(if (null? (cddr lst))
(cons (car lst) '())
(cons (car lst) (listbutlast (cdr lst)))))
(define (pairup fn lst)
(map fn (listbutlast 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 listbutlast:
(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 typechecking 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)
(vectorref pair 1))
(define (cdr pair)
(vectorref pair 2))
(define (pair? thing)
(and (vector? thing)
(= (vectorlength thing) 3) ; we didn't insist on checking length
(eq? (vectorref thing 0) 'pair)))
(define (setcar! pair value)
(vectorset! pair 1 value))
(define (setcdr! pair value)
(vectorset! pair 2 value))
The implementation of PAIR? above depends on the lefttoright 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 (vectorref 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. VECTORCDR 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 SETCAR!/SETCDR!. 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. Reallife 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 (consstream 1
(consstream 2
(consstream 3
(addstreams s1 ones)))))
Another approach was to use the INTEGERS stream to generate two more streams
(define ints2 (streamcdr integers))
(define ints3 (streamcdr 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 roundrobin  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 threeway
interleave:
(define (interleave3 a b c)
(consstream (streamcar a)
(consstream (streamcar b)
(consstream (streamcar c)
(interleave3 (streamcdr a)
(streamcdr b)
(streamcdr c))))))
or the more elegant
(define (interleave3 a b c)
(consstream (streamcar a)
(interleave3 b c (streamcdr a))))
and then create the desired stream this way:
(define s1 (interleave3 integers ints2 ints3))
A common wrong solution was
(define s1 (consstream (streamrange 1 3) (addstreams s1 ones)))
This would generate a stream of streams, not a stream of numbers, and so
the addstreams would fail. Better was
(define s1 (appendstreams (streamrange 1 3) (addstreams s1 ones)))
but this fails for a different reason: appendstreams 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 addstreams solution, we gave one point for
recognizing that three explicit consstream calls are required, and two points
for getting the addstreams [or (mapstreams + ...)] right. For the threeway
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 wordcounting example you were
shown, in that the mapper generates keys whose KVVALUE is 1 and then the
reducer is just +. But it's also a little like the patternmatching
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? (kvvalue kvp))
(list (makekvpair (kvkey kvp) 1))
'()))
+
0
"/chungnotes")
One common alternative, which we accepted, gives nonexercise lines a value
of 0, instead of filtering them out:
(mapreduce (lambda (kvp)
(list (makekvpair (kvkey kvp)
(if (exercise? (kvvalue kvp)) 1 0))))
+
0
"/chungnotes")
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
kvpairs 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 kvpairs 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 nonexercises, one for making the correct kvpair,
and one for putting it in a singleton list.
11. Nondeterministic evaluator
Here's the easy way:
(define (anelementsatisfying pred lst)
(let ((elt (anelementof lst)))
(require (pred elt))
elt))
If you didn't remember ANELEMENTOF from the book, you'd end up reinventing
it, like this:
(define (anelementsatisfying lst)
(let ((elt ((if (null? lst)
(amb)
(amb (car lst) (anelementsatisfying pred (cdr lst)))))))
(require (pred elt))
elt))
or reinventing FILTER, like this:
(define (anelementsatisfying pred lst)
(cond ((null? lst) (amb))
((pred (car lst))
(amb (car lst) (anelementsatisfying pred (cdr lst))))
(else (anelementsatisfying pred (cdr lst)))))
Some students who didn't remember anelementsatisfying 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, plausiblelooking solution that doesn't actually backtrack at all
was this:
(define (anelementsatisfying pred lst)
(cond ((null? lst) (amb))
((pred (car lst)) (CAR LST)) ; wrong here!
(else (anelementsatisfying 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 TRYAGAIN, 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 (doubledelement elt lst)
(cond ((null? lst) '())
((equal? (car lst) elt)
(cons elt (cons elt (doubledelement elt (cdr lst)))))
(else (cons elt (doubledelement 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 (doubledelement ?elt () ()))
(rule (doubledelement ?elt (?elt . ?cdr1) (?elt ?elt . ?cdr2))
(doubledelement ?elt ?cdr1 ?cdr2))
(rule (doubledelement ?elt (?car . ?cdr1) (?car . ?cdr2))
(and (not (same ?elt ?car))
(doubledelement ?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 (doubledelement ?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 nonbasecase rules into a single
rule with OR in its body, but it's pretty complicated because the two rules
have differentlength 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 nearmisses, 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 (fastgrad tree)
(if (null? (children tree))
(list (datum tree))
(cons (datum tree)
(accumulate shorter (map fastgrad (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 basecase 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 deeplist of paths:
(define (allpaths tree)
(if (leaf? tree)
(list (list (datum tree)))
(map (lambda (path) (cons (datum tree) path))
(flatmap allpaths (children tree)))))
The unusual base case value is needed because each path is a list, and
allpaths therefore has to return a list of lists. Given allpaths, we
can then pick the shortest:
(define (fastgrad tree)
(accumulate shorter (allpaths tree)))
The most efficient way would be a breadthfirst 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 FINDPLACE procedure (as used in lecture to find a city
within the world tree) generates the path to that leaf node. But using
FINDPLACE undoes the efficiency gain of BFS, because FINDPLACE uses a
depthfirst 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 treerecursive 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)))
(oehelp odds odds evens evens nums)))
Since ODDEVEN! calls OEHELP using the same argument twice, for both ODDS
and EVENS, you have to understand why. You get two hints: the formal
parameters of OEHELP (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 (oehelp odds oddlast evens evenlast nums)
(cond ((null? nums)
(setcdr! oddlast (cdr evens))
(setcdr! evenlast '())
(cdr odds))
((odd? (car nums))
(setcdr! oddlast nums)
(oehelp odds nums evens evenlast (cdr nums)))
(else
(setcdr! evenlast nums)
(oehelp 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 SETCAR!. 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 SETCAR!? 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 moveelementsrightward loop similar to some of the vector programming
examples we've seen. But using SETCDR!, 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 SETCAR! 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 oddnumbers list or the
evennumbers 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
(setcar! something (cdr somethingelse))
or
(setcdr! something (car somethingelse))
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
(setcdr! oddlast (car nums))
probably because they were thinking "I want ODDLAST to point to the /first/
of the notyetrepositioned 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
(setcdr! 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 OEHELP has to have exactly the form
(oehelp odds oddlast evens evenlast nums)
so, for example, instead of saying
(oehelp odds nums evens evenlast (cdr nums))
they said
(set! oddlast nums)
(set! nums (cdr nums))
(oehelp 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 (setcdr! something (car somethingelse)).
15. Metacircular evaluator
EVALINENV is a special form, so we know that we have to modify MCEVAL
by adding a COND clause to test for it:
...
((evalinenv? exp) (evalevalinenv exp env))
...
and provide the usual mechanism for recognizing a special form:
(define (evalinenv? exp)
(taggedlist? exp 'evalinenv))
The point of the EVALINENV form is to evaluate its first argument in
some particular environment:
(mceval (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 (evalevalinenv exp env)
(mceval (cadr exp)
(procedureenvironment (mceval (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 EVALINENV expression:
(define eieexpr cadr)
(define eieproc caddr)
(define (evalevalinenv exp env)
(mceval (eieexpr exp)
(procedureenvironment (mceval (eieproc 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 (evalinenv 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 LOOKUPVARIABLEVALUE instead of MCEVAL. 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:
(evalinenv (set! counter 0)
(let ((counter 0)) (lambda () ...)))
Worse than that was to invent an adhoc association list of procedure names
and values  that's what the environment is for!
A couple of people used MAKEPROCEDURE to turn the given expression into a
thunk, with a remembered environment borrowed from the given procedure, and
then used MCAPPLY to invoke the thunk. This could be made to work, but
it's a needless complication.
Scoring:
1 point for the COND clause in MCEVAL.
2 points for EVALINENV?.
2 points for (MCEVAL (CADDR EXP) ENV).
1 point for PROCEDUREENVIRONMENT.
2 points for (MCEVAL (CADR EXP) ...).
2 to 4 points if the code you add breaks something else, but that was rare.