CS 61A Fall 1997 Final exam solutions
1. Applicative/normal order.
Applicative order means we evaluate the argument subexpression first, so
(square (inc)) ==> (square 6) ==> 36
Normal order means we pass the argument expression to the procedure, so
(square (inc)) ==> (* (inc) (inc)) ==> (* 6 7) ==> 42
Scoring: 1 point each, or 1 point for 42 and 36 (in the wrong order).
2. Order of growth.
If f is Theta(g), then f+g is Theta(f): True.
Handwavy explanation: f is Theta(g) means that f(x) is close to a*g(x)
for some constant a. Then f(x)+g(x) is close to f(x) + (1/a)*f(x),
which is (1 + 1/a)*f(x), which is a constant times f(x), which makes it
Theta(f).
More formal proof: f is Theta(g) means that for large enough x,
a*g(x) < f(x) < b*g(x)
This implies that g is Theta(f), because
(1/b)*f(x) < g(x) < (1/a)*f(x)
So what about f(x) + g(x)?
(1 + 1/b)*f(x) < f(x) + g(x) < (1 + 1/a)*f(x)
So f+g is Theta(f) as desired.
Note on notation: Many people write f=Theta(g) for "f is Theta(g)" but
there really is no equality involved, and Prof. Hilfinger won't let you
use the equal sign next semester! Instead he uses the "is an element of"
symbol that sort of looks like a greek epsilon, taking Theta(g) as the
set of all functions that are Theta(g).
Scoring: 1 point for True, 0 points for False!
3. Tree searching
You saw the code for breadthfirst search in lecture:
(define (bfs tree pred)
(define (helper tasks)
(cond ((null? tasks) #f)
((pred (datum (car tasks))) (datum (car tasks)))
(else (helper (append (CDR TASKS) (CHILDREN (CAR TASKS)))))))
(helper (list tree))) ;  
For breadthfirst search, we want to see the alreadyqueued tasks
(which include the siblings of the node we're looking at right now)
*before* we see the children of this node. That's why we append
those two sets of tasks in the order seen above.
For depthfirst search, we still want to see all the nodes eventually,
but we want to see the children of this node first. So we want to have
the same tasks in the list for the recursive call, but in the other order:
(define (dfs tree pred)
(define (helper tasks)
(cond ((null? tasks) #f)
((pred (datum (car tasks))) (datum (car tasks)))
(else (helper (append (CHILDREN (CAR TASKS)) (CDR TASKS))))))
(helper (list tree))) ;  
Most of the errors on this question were either wild guesses (e.g., answers
containing LEFTBRANCH and RIGHTBRANCH) or wild data abstraction violations
(e.g., (CHILDREN TASKS)  tasks is a forest, not a tree).
Scoring: 2 points if correct; 1 point if correct but swapped (depth before
breadth) or if one of the two is correct. (That latter is a generous point,
since it probably means you copied the depthfirst version from your
lecture notes without understanding it. But at least you came to lecture. :)
4. DDP according to Ben.
This was a subtle question, definitely requiring thought rather than just
memorizing or pattern matching.
First, a note on epistemology  the philosophy of knowledge. *All* category
names have fuzzy boundaries! Wittgenstein, in his book _Philosophical
Investigations_, discusses the example of the word "game." Clearly baseball
is a game; it has players, rules, winners, losers; it's played for fun;
etc. Is solitaire a game? It has only one player. Is daydreaming a game?
It has no rules, but is an activity carried out for fun. Is baseball a game
in the professional leagues, where the players do it for money rather than
mainly for pleasure? And so on.
Even so, it's useful to have a word "game" that means *roughly* the same
thing to everyone, and that clearly includes some things (baseball for fun)
and clearly excludes others (an elephant).
Similarly, it's not surprising that Ben can find rough edges in the concept
of "data directed programming." We may want to let him include some things
not ordinarily considered in those terms, but if we let him include *all*
procedures, then the name has become meaningless  "data directed program"
just means "program." So we should tell Ben he's very clever, but we
should avoid extending the concept that far.
Ben is right, though, that most procedures *do* act differently for different
arguments. Why isn't that good enough?
To answer, we have to look at another idea with fuzzy boundaries: "program"
versus "data." One of the themes of the entire course has been precisely
that this distinction, which most programmers consider strict and absolute,
is actually just as fuzzy as any other. It is often useful to think of
a program as data (as in a compiler) or of data as a program (as in a
formal language description). Even so, just as in the case of games, there
are things that are *clearly* programs, and other things that are *clearly*
not programs. For example, (define (square x) (* x x)) is a program, and
3 isn't a program. (Except, by the way, in a fully objectoriented language
such as Smalltalk!)
So I'd like to say that a datadirected program is one that looks to its
argument(s) for an *algorithm*  for a *program*  and not merely for
passive data. We should recognize that there will be fuzzy cases, but we
should nevertheless bravely insist that the whole point of having a name
"data directed" is to make this distinction.
Now we're ready to answer the question.
In part (a), we'll accept any program that takes a *program* as argument
to be supporting Ben's view. There are two main examples: higher order
procedures (such as MAP) and EVAL, which takes a Scheme program as argument.
Any procedure that doesn't have that property is a good answer for (b).
Note that the datadirected example in SICP does *not* take a program as
an argument! Instead, it uses a table full of programs as a sort of
implicit argument  a global variable, rather than part of the OPERATE
procedure itself.
A common wrong answer for (a) was a program whose behavior depends on
the type of its argument. Examples are + (which adds integers differently
from nonintegers) and FIRST (which treats sentences differently from
words). But these are classic examples of "conventional style" programming,
in which the algorithms for the different data types are built into the
procedure itself. To add a new type would require editing the procedure
definition.
Another common wrong answer for (a) was messagepassing dispatch procedures.
Here, too, the argument is merely the *name* of a method; the methods
themselves are built into the dispatch procedure.
On the other hand, the ASK procedure in the OOP system, which takes
objects as arguments, does rely on the argument to contain the method
knowledge. But ASK is just a special case of a higher order procedure,
noted earlier as the standard correct response for part (a).
We gave half credit for IF or COND. These do take Scheme expressions
as arguments, but they're not *procedures* at all; they're special forms.
And it can be argued that they don't really evaluate the Scheme
expression arguments, but merely choose one to be evaluated by EVAL.
In part (b), a common wrong answer was a procedure that involves mutation,
because the procedure's result does not depend *only* on its arguments.
But that's not what Ben was claiming  he's not saying that every procedure
is functional. He's saying that the arguments *affect* the behavior; it's
okay if other things affect it too.
We gave half credit for a constant function such as (lambda (x) 3), or
for a function with no arguments at all. These do indeed fail Ben's test,
but they're trivial degenerate cases, like a circle with radius zero.
They don't give much insight into the merits of Ben's view.
5. OOP questions.
(a) What should inherit from both THING and PLACE? Well, THINGs can
move around from place to place, and PLACEs can be moved into or out from.
The best example of something with those characteristics is a VEHICLE,
which people can enter, and then move from one place to another.
People gave many specific kinds of vehicles, ranging from the prosaic CAR
to the scatological PORTAPOTTY. All are equivalent for our purposes.
We also accepted CONTAINERs, which can hold things and can be moved around.
Essentially,
container : thing :: vehicle : person
Aren't you glad you took the SAT so you had practice with this sort of
thing?
We did not accept HOUSE or other such stationary places, even though people
argued that they can be owned, as things can be. That's true, but (alas,
in this capitalist world) all places can be owned, even old growth redwood
forests. So, if we want to model ownership of places, I think we would
add that capability to the PLACE class, rather than have OWNABLEPLACE
inherit from THING and then have to teach the PERSON and PLACE classes
that certain THINGs aren't movable. But we did accept TENT, which is
a *moveable* dwelling.
The most common serious misunderstanding was to confuse "inherit from"
with "have as a characteristic." A sample wrong answer in that
category: "PERSON, because a person is in a PLACE and can own THINGs."
One class inherits from another only if it *behaves like* that other.
(b) Implement pairs in oop.
What it means to implement a data type is to provide constructors,
selectors, and mutators as needed. Here's the shortest good answer:
(defineclass (pair car cdr)
(method (setcar! x)
(set! car x))
(method (setcdr! x)
(set! cdr x)))
This solution takes advantage of the fact that defineclass automatically
provides methods for the object's state variables, so there are implicit
CAR and CDR methods.
To make the implementation look exactly like the standard Scheme one,
we'd add some syntax procedures:
(define (cons a b)
(instantiate pair a b))
(define (car p) (ask p 'car))
(define (cdr p) (ask p 'cdr))
(define (setcar! p x) (ask p 'setcar! x))
(define (setcdr! p x) (ask p 'setcdr! x))
But that really isn't necessary, because in a pure OOP language as
recommended by Ingalls, we'd use the OOP notation for everything,
rather than the global procedure notation.
Many people wanted to implement list constructors such as APPEND as methods,
but that's not necessary. Lists are an abstract data type built on top of
pairs, and APPEND can be written in terms of (our rewritten) pair primitives.
Some people made a pair class with no instantiation variables, and instead
gave it a CONS method that set instance variables. That's somewhat missing
the idea; the job of CONS is to create a new pair, and instantiation
variables let us model that straightforwardly. I expect these people
thought there had to be a method named after every Scheme pairrelated
function, but it's perfectly fine to say (instantiate pair ...) when you
want a pair. After all, you have to instantiate the class anyway, before
you could use the CONS method!
An even worse case of not getting the point is to write methods in the
PAIR class that take a pair as an argument! For example:
(method (setcar! p x)
(set! (ask p 'car) x))
This is doubly awful, first because it doesn't understand that the object
is implicit in any use of any method, and second because of trying to use
the SET! special form with a first argument that isn't a symbol.
Scoring: 1 point for each part.
6. Environment diagram.
KONS is a procedure defined in the global environment. So, what environment
do we extend whenever KONS is called? Always the global environment, no
matter how confusing the context of the call might be. So the answer must
be A or B, in which each call to KONS extends the same environment.
(Note: Even in a dynamically scoped Scheme, this example would have both
new frames extend the global environment. It's only if a call to KONS
happened *in the body of* some procedure that the frame might extend
another environment.)
To what is P bound? Is it the KONS procedure, or is it a particular
pair created by KONS? Obviously the latter. So the answer must be B or D.
The intersection of these shows that B is the correct diagram.
Scoring: all or nothing.
7. Mutation.
Here is the original value of P, before mutation:
> XX>XX
  \
XX 3 4
 \
1 2
In the mutated version, the thing that used to point to 2 should now
point to the pair (3 . 4):
> XX+>XX
 /  \
XX+ 3 4

1
The changed pointer is the CDR of a pair, so we have to SETCDR! it.
Which pair? The one pointed to by the CAR of P.
(setcdr! (car p) (cdr p))
There is no SETCADR! in Scheme.
Scoring: all or nothing.
8. Synchronization.
In (a), different synchronizers are used for the two threads, so
they are not protected from each other. This can give an incorrect
result. Here's one incorrect sequence of events:
Thread 1 reads x = 5.
Thread 2 reads x = 5.
Thread 2 sets x to (* 5 2) = 10.
Thread 1 sets x to (+ 5 1) = 6.
The correct possibilities are thread 1 first, so 5 > 6 > 12, and
thread 2 first, so 5 > 10 > 11.
This can't deadlock, because the two threads never want the same
synchronizer.
In (b), incorrect results are impossible, because both threads must
have synchronizer S to run (along with T, but never mind that for now),
so the two can't be in progress at overlapping times. But deadlock
is possible:
Thread 1 gets S.
Thread 2 gets T.
Now thread 1 waits forever for T, while thread 2 waits forever for S.
Scoring: one point each.
9. Turn special forms into primitives.
This was apparently a difficult problem for most students. It shouldn't
have been, since the proposed modification to the evaluator was so
similar to one you supposedly understand from the Logo project.
Part (a) is about a *difference* between the proposed Scheme
specialprimitives and Logo procedures. In Logo, except for the
special form TO, all procedures take evaluated arguments, even
the ones corresponding to Scheme special forms. The arguments to
IF, for example, are evaluated, in Logo, before being sent to APPLY
along with the IF primitive itself.
In Scheme, however, we must ensure that for a specialprimitive,
the arguments are not evaluated by EVAL before they are passed along
to APPLY. This situation is somewhat like what happens in the
normal order Scheme variation: for a specialprimitive, EVAL must
refrain from calling LISTOFVALUES before calling APPLY.
What we're doing, though, is not exactly like normal order. In
the normal order Scheme, we are deferring evaluation of something
we know will be evaluated eventually. (Remember that in normal
order Scheme the deferred evaluation is only for arguments to
userdefined procedures, whereas here it's primitives  some of
them  whose arguments aren't evaluated.) In a special form,
some arguments are never evaluated, such as the symbol used as
the first argument to DEFINE or SET!. It is the argument
expression itself, not a promise to evaluate that expression later,
that DEFINE needs.
We also accepted "EVAL must pass ENV to APPLY as an additional
argument." This is certainly true, although not in the sense
of (APPLY PROC ARGS ENV). Rather, we include env among the
args that APPLY will pass to the specialprimitive:
(APPLY PROC (CONS ENV ARGS))
We didn't accept answers that restated the first line of part (a),
about removing tests for special forms. There were also some wildly
wrong answers, e.g., ones that seemed to think the PRIMITIVEPROCEDURES
list is part of EVAL (again restating part of the question, but this
time a completely irrelevant part).
The best answer to part (b) is: Specialprimitives are first class.
We accepted anything derived from that fact:
* The names of specialprimitives can be rebound.
* Specialprimitives can be arguments to higher order functions.
* You can make a list of specialprimitives.
We didn't accept "more efficient" or "less efficient." This eliminates
some tests from EVAL, but it adds a test to APPLY (to see which kind
of primitive this is), and we have to wrap a type tag around the
primitive to mark it as special. The effect on timing will be quite
subtle, probably not noticeable.
"Dynamic scope" is also wrong. This was a good guess, because we are
passing ENV to apply, but APPLY isn't using the environment as the
one to extend with a new frame. That only happens when calling a
userdefined procedure! Instead, the calling environment is given as
an argument to specialprimitives  that is, to the equivalent of
real Scheme's special forms, which already affect the caller's
environment!
"Uservisible environments" and "userdefinable special forms" are both
also wrong. Those are related features that *could* be added to Scheme,
but the proposed feature does not provide useraccessible ways to
capture the environment or to create a new specialprimitive. (It's
worth noting that existing real Scheme implementations do allow
userdefinable special forms, called "macros," which act like regular
special forms  for example, they're not first class. Some versions
of Scheme also have firstclass environments. Those things don't
require this proposed modification.)
Is this a good idea? Why doesn't Scheme do it this way? One reason
is that fast implementations of Scheme compile the special forms
in specific ways, not like general procedure calls, rather like
the way compilers for Clike languages handle IF statements and so on.
(So the "more efficient" answers for part (b) are especially wrong if
you think about compiling!) Otherwise, though, I don't think there's
any strong reason it couldn't work.
Scoring: one point each.
10. Nondeterministic evaluator.
The program returns a value when the CDR of its argument is a word  that
is, not another pair, and not the empty list. In other words, this program
is looking for improper lists. So first it finds the F in (D E . F), then
it finds the I in (H . I). There are no other improper lists in the example,
so the third attempt prints "no more values." (We didn't worry about the
exact text of the message.)
A common set of wrong answers was C, F, I. This is what you get if
you scan the argument for close parentheses. But the C is not the
CDR of anything! It's the second element of a list, so it's the CAR
of the second pair in the list.
Another really strange set of wrong answers was no value, then C, then
no value again. This is a deep misunderstanding of how backtracking
works in the nondeterministic evaluator. You don't see "no more values"
until there are no more values to be found! Once you get that message,
it won't do any good to ask again.
Scoring: We accepted F and I in either order, and any text in the
third slot indicating a failure. The only onepoint solution had
(F) and (I) instead of F and I, missing the fact that the procedure
returns (CAR X) and not simply X.
11. Multiplying in logic.
(a) Zero times anything is zero.
(rule (times () ?y ()))
Most everyone got this. The funniest wrong answer was
(rule (times () ?y ?y)) ;; WRONG!!!
which I guess was a mindless copying of the base case for plus.
Folks, logic programming is *about* pattern matching, but that
doesn't mean that *you* should pattern match instead of thinking!
(b) First of all, what's the mathematics we're trying to model?
It's this:
(x+1) * y = (x * y) + y
This is how we can get a problem about a nonzero multiplicand
reduced toward a problem matching the base case, by using a problem
with a smaller x.
In the query system notation we're using, x+1 is represented as (a . ?x)
because if X is a list of that many copies of the letter A, then X+1
is a list of that many plus one copies. In Scheme we'd say (CONS 'A X).
(rule (times (a . ?x) ?y ?product)
(and (times ?x ?y ?xy)
(plus ?xy ?y ?product)))
I've used the name ?XY for clarity, but don't think the query system
understands it as anything but an arbitrary name!
Common errors:
(?A . ?X) instead of (A . ?X). We want actual copies of the actual letter
A, not some unknown variable.
Getting the fields of the PLUS in the rule body in the wrong order,
e.g., (PLUS ?PRODUCT ?Y ?XY).
Thinking that the (A . B) notation can be used to represent APPEND,
rather than CONS:
(rule (times (a . ?x) ?y (?y . ?xy)) ;; WRONG!!
(times ?x ?y ?xy))
This has the basic idea, but misunderstands the notation.
We gave all of the above one point (out of two for part (b)) for otherwise
correct solutions.
By the way, many people felt the need to write another base case for
multiplying by one:
(rule (times (a) ?y ?y))
which is fine, but unnecessary. Believe in zero!
The really awful mistake was to try to use composition of functions.
There aren't any functions in logic programming:
(rule (times (a . ?x) ?y (plus ?y (times ?x ?y)))) ;; WAY WRONG!!!
Scoring: One point for (a), two for (b).
12. Automating abstract data types.
In part (a) the only difficulty is understanding what a selector is;
in part (b) people who don't understand tree recursion had trouble.
(a) Selectors for a sequential type.
(define (select field type)
(lambda (thing)
(if (eq? field (car type))
(car thing)
((select field (cdr type)) (cdr thing)))))
This is the most straightforward solution, I think. It's also possible
to push the LAMBDA inside the IF:
(define (select field type)
(if (eq? field (car type))
car
(lambda (thing) ((select field (cdr type)) (cdr thing)))))
One of the joys of teaching is that occasionally I'm surprised by a student's
solution more elegant than what I'd thought up, such as the following:
(define (select field type)
(if (eq? field (car type))
car
(compose (select name (cdr type)) cdr)))
Isn't that nice? It works entirely by manipulating known functions,
without ever applying any of them to an argument (like THING in the
earlier versions).
Many students managed to complicate the program by first computing a
numeric position within the list, and then calling LISTREF or NTH or
something like that. This can work, but what's the point? It just
makes the program take twice as long, and be twice as hard to read or
debug. It's almost always the wrong thing to use numbers in
navigating a list structure.
Similarly, some people constructed lists of the words CAR and CDR repeated,
and then wrote a procedure to interpret those lists (an example of
datadirected programming, I guess), but why bother? You can get away
with such complexity in the relatively trivial part (a), but when you
try it in part (b), the result is unreadable. (This question took us
longer to grade than any three other questions!)
And while I'm complaining, iterative code (using helper procedures
with extra arguments to collect partial results) is always harder to
read and to debug than straightforward recursive code.
Very bad solutions didn't return a procedure at all. (These included
some very complicated procedures that ended up returning the FIELD
argument.) Don't confuse these with the elegant one earlier that
doesn't explicitly use LAMBDA, but *does* return a procedure!
Extra especially bad solutions are ones that had LEFTBRANCH or
RIGHTBRANCH or BINARYTREE built into them. Folks, every year in
the exam solutions I have a paragraph like this one ranting about
the fact that procedures are supposed to be general methods, and the
examples in the question are just examples. The same students who
diligently pore through the old solutions to find a procedure that
seems to have a shape similar to the one in this year's question never
seem to read those paragraphs!
>>> HEY!!! NEXT YEAR'S BAD STUDENTS!!!! READ THAT!!!! <<<
(b) Selectors for a treestructured type.
Here's a pretty straightforward solution:
(define (select field type)
(cond ((null? type) #f)
((eq? field (car type)) car)
((pair? (car type))
(if (eq? field (caar type))
car ;;; NOT CAAR!
(let ((sub (select field (cdar type))))
(if sub
(lambda (thing) (sub (car thing))) ;;; NOT JUST SUB!
(lambda (thing) ((select field (cdr type))
(cdr thing)))))))
(else (lambda (thing) ((select field (cdr type)) (cdr thing))))))
We can also make an elegant nevercallaselector version:
(define (select field type)
(cond ((null? type) #f)
((eq? field (car type)) car)
((pair? (car type))
(if (eq? field (caar type))
car
(let ((sub (select field (cdar type))))
(if sub
(compose sub car)
(compose (select field (cdr type)) cdr)))))
(else (compose (select field (cdr type)) cdr))))
One subtle point to notice: In part (a), there was no error checking;
the procedure assumes that it will find the field name somewhere. But
in part (b), we have to try recursive subproblems that might fail, so
there is a test for that, returning #F. On success SELECT returns a
procedure, so this #F can't be mistaken for a field name or value that
happens to be #F.
The crucial point is that in a treestructured problem your procedure
is sometimes going to have to do recursion on the CAR *and also* on
the CDR, not recursion on the CAR *or* on the CDR. So this would be
wrong:
(define (select field type) ;; WRONG!
(cond ((null? type) #f)
((eq? field (car type)) car)
((pair? (car type))
(if (eq? field (caar type))
car
(LAMBDA (THING) ((SELECT FIELD (CDAR TYPE)) (CAR THING)))))
(else (lambda (thing) ((select field (cdr type)) (cdr thing))))))
This (quite common) version notices that the first field specification
is a list, and therefore commits itself to finding the desired field
within that list. But maybe not! We still must be prepared to examine
(CDR TYPE).
There were some clever ways to check both possibilities without
needing the LET in my solution. But they either used iterative style
or constructed lists of CARs and CDRs, so I won't show them here.
There were also some failed attempts to try both car and cdr without
using LET. Some just had two expressions not connected:
((pair? (car type)) ;; wrong!
(select field (car type))
(select field (cdr type)))
and the like. Others tried a sequence of events:
((pair? (car type)) ;; wrong!
(begin (select field (car type))
(select field (cdr type))))
Some people tried to use MAP to look at all the subproblems in parallel.
It's possible to make that work, but in general the efforts were not
successful. At best, you end up with a list containing a bunch of #F
values and one procedure somewhere in the middle, and then you have to
go through that list again to pull out the procedure. At worst, you
forget to return a procedure at all.
Scoring: 3 points for each part, more or less on the scale
3 correct
2 has the idea
1 has an idea
0 other
Specific scores for common problems:
Doesn't return a procedure: at most 1.
Example (or a fixed size) built in: zero zero zero!!!!
Gratuitous SET!: subtract 1 from score.
In part (b), correct except for the special handling of the first
field name in a sublist: 2.
In (b), a solution that works only two levels deep: 1.
No tree recursion at all: 0.
Uses BEGIN (or SEQUENCE): 0.
13. Infinite Hanoi stream.
The most obvious approach is to try to generalize from the finite case.
You can't, of course, say (HANOISTREAM INFINITY). Instead of recursion
to smaller streams, as in HANOISTREAM, you have to start with a small
example and try to make it bigger in each recursion. The goal is something
like this:
(makebigger () 1) >
(makebigger (1) 2) >
(makebigger (1 2 1) 3) >
(makebigger (1 2 1 3 1 2 1) 4) > etc.
Here's the attempted code:
(define (makebigger stream num)
(makebigger (streamappend stream (consstream num stream))
(+ num 1)))
(define hanoi (makebigger theemptystream 1)) ; wrong!
But of course this won't work. The recursion in MAKEBIGGER isn't
delayed (by happening in the second argument to a CONSSTREAM) so
the program really does loop forever with no result.
There were five general categories of solution to this problem.
First category (three correct solutions):
We know how to make finite Hanoi streams. The problem points out
that the infinite Hanoi stream has any particular finite Hanoi
stream as a leading substring. So for example, the infinite stream
(1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 1 2 1 ...)
starts with
(1 2 1 3 1 2 1)
which is (hanoistream 3). So, the Nth element of the infinite
Hanoi stream is also the Nth element of any finite Hanoi stream
whose length is at least N. The simplest such finite stream to
choose is (hanoistream N), whose length is always at least N.
So...
(define (nthhanoielement n)
(streamnth n (hanoistream n)))
(define (streamnth n stream)
(if (= n 1)
(streamcar stream)
(streamnth ( n 1) (streamcdr stream))))
(define hanoi (streammap nthhanoielement integers))
Second category (four correct solutions):
The idea of computing a function that finds the Nth number in the
stream, and mapping that function over the integers, is nice and
simple. But the NTHHANOIELEMENT above takes time Theta(2^N) for
each element. By choosing a smaller argument to HANOISTREAM, we
can get that down to Theta(N), but why can't we calculate the
Nth number directly, instead of building a stream each time?
If N is odd, (HANOINUMBER N) should be 1.
If N is divisible by 2 but not by 4, (HANOINUMBER N) must be 2.
If N is divisible by 4 but not by 8, the number is 3.
And so on... We must find the largest power of 2 that's a factor
of N.
(define (hanoinumber n)
(if (odd? n)
1
(+ 1 (hanoinumber (/ n 2)))))
(define hanoi (streammap hanoinumber integers))
Third category (three correct solutions):
One way to characterize the infinite Hanoi stream is that it's
(streamappend (hanoistream 3) (everythingstartingwith4))
(1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 1 2 1 ...)
(1 2 1 3 1 2 1) (4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 1 2 1 ...)
Since the first argument to streamappend is finite, this is a reasonable
thing to try to compute. The second argument has a funny asymmetrical
shape, though. (Remember that there's more than one 4 in the infinite
stream, but we're singling out the first one as special.) What's in that
right part? It's
* The number 4
* then another copy of (hanoistream 3)
* and then (everythingstartingwith5).
(4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 1 2 1 ...)
4 (1 2 1 3 1 2 1) (5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 1 2 1 ...)
Clearly instead of picking a specific number such as 4, we need a general
function for the right part starting with any number.
(define (rightpart n)
(consstream n
(streamappend (hanoistream ( n 1))
(rightpart (+ n 1)))))
In particular, if we take n=1, the left part is empty, so we can
forget about it:
(define hanoi (rightpart 1))
Fourth category (two correct solutions):
Let's look at the infinite Hanoi stream again.
(1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 1 2 1 ...)
Every other number is 1, so let's think about interleaving ONES with
something:
(1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...)
( 2 3 2 4 2 3 2 5 2 3 2 4 2 3 2 6 2 ...)
In that second stream, every other number is 2, so if we had a TWOS stream
we could interleave it with something else:
( 2 2 2 2 2 2 2 2 2 ...)
( 3 4 3 5 3 4 3 6 ...)
But in *that* new stream, every other number is 3... A pattern emerges.
First we need a way to make an infinite stream of all the same N, for
any N:
(define (nstream n)
(consstream n (nstream n)))
At this point it's easy to make a mistake, as follows:
(define (badhanoisubstream n)
(interleave (nstream n)
(badhanoisubstream (+ n 1))))
(define hanoi (badhanoisubstream 1)) ;;; wrong!
The problem is that INTERLEAVE is an ordinary procedure, not a special
form, so it doesn't delay its second argument as CONSSTREAM does.
If you run this program it'll loop forever without returning a stream.
There are two ways to solve this. One is to use explicit delays:
(define (hanoisubstreamdelayed n)
(interleavedelayed (nstream n)
(delay (hanoisubstream (+ n 1)))))
(define hanoi (hanoisubstreamdelayed 1))
The other solution is to rearrange the order so that we use an
explicit CONSSTREAM in the definition:
(define (hanoisubstream n)
(consstream n
(interleave (hanoisubstream (+ n 1))
(nstream n))))
(define hanoi (hanoisubstream 1))
Note that interchanging the order of the arguments to interleave
is necessary to counteract the extra N at the beginning.
Fifth category (two correct solutions):
As in the fourth category, we notice that ones are interleaved with
nonones:
(1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...)
( 2 3 2 4 2 3 2 5 2 3 2 4 2 3 2 6 2 ...)
Subtract 1 from every element of that second stream, and what do you get?
( 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 ...)
Hey! It's the infinite Hanoi stream! With this insight we don't even
have to write a procedure; we can use an implicit recursion based on
the stream's name.
Again we have to be careful either to use INTERLEAVEDELAYED or to start
with an explicit CONSSTREAM:
(define hanoi (consstream 1 (interleave (streammap + hanoi ones)
ones)))
Scoring: Two points for a correct solution. There were three basic
categories of incorrect solution:
(a) Ones that would work in a normalorder Scheme, namely the ones
we had to fix with explicit DELAYs: one point, because the math is
correct and it's a Scheme deficiency that gets in the way.
(b) Streams of streams, e.g., ((1) (2 1) (3 1 2 1) (4 1 2 1 3 1 2 1) ...)
(c) Wrong sequences, e.g., (1 2 1 2 1 2 1 2 ...)
No points for (b) or (c).