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 breadth-first 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 breadth-first search, we want to see the already-queued 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 depth-first 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 LEFT-BRANCH and RIGHT-BRANCH) 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 depth-first 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 object-oriented language such as Smalltalk!) So I'd like to say that a data-directed 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 data-directed 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 non-integers) 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 message-passing 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 PORT-A-POTTY. 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 OWNABLE-PLACE 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: (define-class (pair car cdr) (method (set-car! x) (set! car x)) (method (set-cdr! x) (set! cdr x))) This solution takes advantage of the fact that define-class 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 (set-car! p x) (ask p 'set-car! x)) (define (set-cdr! p x) (ask p 'set-cdr! 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 pair-related 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 (set-car! 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 SET-CDR! it. Which pair? The one pointed to by the CAR of P. (set-cdr! (car p) (cdr p)) There is no SET-CADR! 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 special-primitives 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 special-primitive, 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 special-primitive, EVAL must refrain from calling LIST-OF-VALUES 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 user-defined 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 special-primitive: (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 PRIMITIVE-PROCEDURES 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: Special-primitives are first class. We accepted anything derived from that fact: * The names of special-primitives can be rebound. * Special-primitives can be arguments to higher order functions. * You can make a list of special-primitives. 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 user-defined procedure! Instead, the calling environment is given as an argument to special-primitives -- that is, to the equivalent of real Scheme's special forms, which already affect the caller's environment! "User-visible environments" and "user-definable special forms" are both also wrong. Those are related features that *could* be added to Scheme, but the proposed feature does not provide user-accessible ways to capture the environment or to create a new special-primitive. (It's worth noting that existing real Scheme implementations do allow user-definable special forms, called "macros," which act like regular special forms -- for example, they're not first class. Some versions of Scheme also have first-class 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 C-like 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 one-point 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 LIST-REF 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 data-directed 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 LEFT-BRANCH or RIGHT-BRANCH or BINARY-TREE 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 tree-structured 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 never-call-a-selector 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 tree-structured 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 (HANOI-STREAM INFINITY). Instead of recursion to smaller streams, as in HANOI-STREAM, you have to start with a small example and try to make it bigger in each recursion. The goal is something like this: (make-bigger () 1) --> (make-bigger (1) 2) --> (make-bigger (1 2 1) 3) --> (make-bigger (1 2 1 3 1 2 1) 4) --> etc. Here's the attempted code: (define (make-bigger stream num) (make-bigger (stream-append stream (cons-stream num stream)) (+ num 1))) (define hanoi (make-bigger the-empty-stream 1)) ; wrong! But of course this won't work. The recursion in MAKE-BIGGER isn't delayed (by happening in the second argument to a CONS-STREAM) 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 (hanoi-stream 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 (hanoi-stream N), whose length is always at least N. So... (define (nth-hanoi-element n) (stream-nth n (hanoi-stream n))) (define (stream-nth n stream) (if (= n 1) (stream-car stream) (stream-nth (- n 1) (stream-cdr stream)))) (define hanoi (stream-map nth-hanoi-element 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 NTH-HANOI-ELEMENT above takes time Theta(2^N) for each element. By choosing a smaller argument to HANOI-STREAM, 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, (HANOI-NUMBER N) should be 1. If N is divisible by 2 but not by 4, (HANOI-NUMBER 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 (hanoi-number n) (if (odd? n) 1 (+ 1 (hanoi-number (/ n 2))))) (define hanoi (stream-map hanoi-number integers)) Third category (three correct solutions): One way to characterize the infinite Hanoi stream is that it's (stream-append (hanoi-stream 3) (everything-starting-with-4)) (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 stream-append 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 (hanoi-stream 3) * and then (everything-starting-with-5). (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 (right-part n) (cons-stream n (stream-append (hanoi-stream (- n 1)) (right-part (+ n 1))))) In particular, if we take n=1, the left part is empty, so we can forget about it: (define hanoi (right-part 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 (n-stream n) (cons-stream n (n-stream n))) At this point it's easy to make a mistake, as follows: (define (bad-hanoi-substream n) (interleave (n-stream n) (bad-hanoi-substream (+ n 1)))) (define hanoi (bad-hanoi-substream 1)) ;;; wrong! The problem is that INTERLEAVE is an ordinary procedure, not a special form, so it doesn't delay its second argument as CONS-STREAM 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 (hanoi-substream-delayed n) (interleave-delayed (n-stream n) (delay (hanoi-substream (+ n 1))))) (define hanoi (hanoi-substream-delayed 1)) The other solution is to rearrange the order so that we use an explicit CONS-STREAM in the definition: (define (hanoi-substream n) (cons-stream n (interleave (hanoi-substream (+ n 1)) (n-stream n)))) (define hanoi (hanoi-substream 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 non-ones: (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 INTERLEAVE-DELAYED or to start with an explicit CONS-STREAM: (define hanoi (cons-stream 1 (interleave (stream-map + 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 normal-order 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).