Below are exercises, often modified or extended, from Graham.
Warning: many of the exercises suggest terrible names for the functions
to define. Use the function names given in the exercise descriptions below.
These are the names used by the unit tests
When inventing your own names, ignore Graham's examples and use the
principles of good naming.
Feel free to define subfunctions when they make the code clearer. In fact, you will be critiqued for not defining subfunctions when appropriate. Some students think the phrase "define a function" means "define just one function." That's not true in Lisp or anywhere else. That terminology is just how programmers describe the API (application program interface) for the public function that other code will call.
Quick jump to notes for Chapter 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12
Send the code for exercises 4, 7, 8, and 9 in one submission.
Even though the instructions say to use only what you've seen so far, use
if, where appropriate.
new-xxx are always a bad idea. "New" says nothing
about what the function does. And how long can something stay "new?"
The term "stable" is used in computer science
to refer to sorting algorithms that don't mess up the order of elements any
more than they have to. Common Lisp provides two sorting functions:
stable-sort to capture this difference.
Define stable versions of the three major
set functions: union, intersection, and difference.
These should work like the built-in versions (see Graham's glossary),
but items in the result
should have the same relative ordering they have in
if any, or in
l2, if any. Don't worry about handling
Avoid redundant code. Avoid needless CONSing or list scanning.
occurrences (yes, that is how you spell it)
It's very inefficient to do this by creating a new list of count pairs every
time you count a new element. Instead, keep a list of
(item . count)
pairs, initially empty. For each element in the input list, update this list
of pairs, where updating means incrementing the counter in the appropriate pair,
if one exists, otherwise adding a new pair.
To increment the count, use
(INCF (CDR pair)) which increments
CDR of a pair.
NOTE: it's OK to get "a little too long" from the Lisp Critic on this, though there are many reasonably short solutions.
In case you're not sure why the return value is (7 6 3 7): The first element is 7 (the first element of the original list) + 0 (the position of the first element, counting from 0), the second element is 5 (from the original list) plus position 1, the third element is 1 plus position 2, and the last element is 4 plus position 3.
show-dots as described in Graham. This is a simple function
and should have simple code. Look at the test cases in exercises-tests.lisp
show-list to act like Lisp's PRINT, except that it should
print square brackets instead of parentheses. (Printing to a string and replacing
parentheses doesn't count.)
Both functions should be able to print any S-expression, including atoms.
There are two problems with this exercise as given. First, Graham's phrase "the longest finite path" makes no sense if you allow cycles in the network, as he does and should. There are an infinite number of finite paths when the network has cycles.
We could say "find the longest path with no cycles," but consider asking for the longest path from node A to node A. This has a cycle, but it's asking a reasonable question: what is the longest round-trip tour from A?
So, define your function to find the longest path with no internal cycles, i.e., no node repeated except possibly the first and last nodes.
The second problem is that
looking for longest paths means that Graham's breadth-first
BFS function is not appropriate. Why? Because
breadth-first search has to build
a queue of alternatives, and such a queue is only worth doing
if it lets you stop before you've tried all possibilities.
There's no way to find the longest path without trying all possibilities. Therefore, there is no point to keeping a queue. Depth-first search would work just fine and is more efficient..
Define a recursive
longest-path function that uses depth-first
search to explore all paths without internal cycles, one at a time.
That is, there will be a variable with the current
path, and perhaps another with the best path, but no list of all paths.
rotate-array to create a new array and copy the
elements from the old array into it. This can be done pretty simply
with a pair of nested
dotimes and a formula that maps (x, y)
in the old array into a position in the new array.
In Lisp, for obscure historical reasons, destructive versions
of functions start with the letter "n" as in
should be a version of
rotate-array that modifies and returns the original array. The
trick is to notice that every element participates in a 4-step
circular rotation. For example, in a 5x5 array, the element at (0, 0)
goes to (0, 4) which goes to (4, 4) which goes to (4, 0) which goes
to (0, 0). (In odd-sized arrays, the center element doesn't move.)
The formula for what goes where is not hard to figure out and similar
to the one needed for the easy version of this exercise.
Common Lisp has a very handy special form,
takes N "places" (variables, aref's, whatever), and "rotates" the
values in those places 1 position.
(rotatef x y), for
rotatef to implement the 4-step rotations that
nrotate-array needs in a concise fashion. Don't rotate any
element more than once!
Send code for exercises 2 and 6 in one submission.
Do as specified.
The specification "in order from greatest to least" is a bit confusing. Is this assuming a particular ordering predicate was used to build the tree?
In any case, define
return the elements of a binary search tree in the reverse order of
appear in the tree. So
a tree with 1, 2 and 3 would return
(3 2 1).
Your solution should only do N conses (not counting internal CONSes out of your control) to produce an N-element result. Hint: there's a BST function to make this fairly simple. The code code for Graham's binary search tree is in bst.lisp. Send only your code, not Graham's.
Do as specified. Put both versions in the same submission.
Put both versions in the same submission.
(intersperse '- '(a)) should return
(intersperse '- '()) should return
Avoid inefficiencies. There are two easy traps to fall into:
Define four versions, all with the same name. The fourth should
every. Put all four versions in the same submission.
return-from makes more sense than
return in part
Don't worry about using just one function, if more would make the code clearer or more efficient. Only one recursive function is needed though.
subseq to create subvectors. This is
expensive. Don't call
length on every iteration either. This
is unnecessary. It also limits the generality of
max-min to take the keywords
:end, just like the other sequence functions do. With
:end, your code should be more efficient than code with
and multiple calls to
length, and more flexible at the same time.
Think about what other keyword arguments would provide similar efficiency and
Define both versions as specified. Put both versions in the same submission.
Important: In order for the test cases to tell if your code is indeed stopping immediately when a path is found, it needs to know what you put on the queue. For this to happen, change:
(defun bfs (end queue net) (if (null queue)
(defun bfs (end queue net) (if (empty-queue-p queue)
empty-queue-p is defined in exercise-tests.lisp. It works like null but also checks what's in the queue.
To pass the tests, you must also fix the code to handle cycles in the graph. Graham's code will find a path if one exists, no matter what, but will go into an infinite loop if no path exists and there are cycles in the graph.
finder function is not great Common Lisp. Run the Critic
on it and see.
Furthermore, it has a serious bug, as noted on the errata page at his web site.
Therefore, part of your job here is to reimplement the code to work correctly (pass the test cases) and be in good Common Lisp style.
bin-search so that
(bin-search object vector :key key-fn :start start :end end)
uses binary search to find an item in vector whose
key-fn item) value is equal to object. For example,
> (bin-search 8 #((1 a) (3 b) (5 c) (7 d) (8 e) (10 f)) :key #'car :start 3 :end 5) (8 E)
The search should go from start (inclusive) to end (exclusive). All parameters should take their usual values. In particular, in Lisp, C++, Java and elsewhere, the end of a sequence is the first index past the last element. Graham uses the index of the last element, which makes his arithmetic more complicated. With the standard value you can test for the end case and calculate the midpoint without a range calculation.
Do not define a
:test parameter. A
makes little sense here, because the code takes a vector previously sorted using
<, and that implicitly defines an equality predicate.
You should not need a helper function, just a recursive
Send code for exercises 5, 6, 7 and 8 in one submission.
The parameter to
be optional. If omitted, it should reset the internal data to its initial state.
(memoize function) should take one argument that is
itself a function of one argument, e.g.,
memoize should return a new function object, i.e., closure. The closure
should call function when it gets new argument values, and return
whatever function returns. When passed previously seen
equal values, the closure should return the previous answer without
calling function. If the closure is called with no arguments,
it should clear its internal table of argument values, and start over.
See the test cases in exercise-tests.lisp for examples.
Exercise 7-1 is good practice for this exercise, but only send Exercise 7-2.
Instead of making a list of the expressions in a file, define
(map-stream function stream)
to apply function to every Lisp expression in stream. It
(map-file function pathname)
to apply function to every Lisp expression in the file
named by pathname, and return
nil. These functions
can be very useful for checking code files, collecting the names of
functions defined in a file, and so on.
There are test cases only for
Do as specified. Currently, there are no test cases for this exercise.
To do this exercise, you need Graham's buffer and stream-subst code. The book version of the buffer code has an error. Use this version instead. Here's the stream-subst code, which you'll be changing.
stream-subst as described for Exercise 7-5, but
the wildcard character should be specifiable with a
keyword parameter, with the default
stream-subst as described for Exercise 7-6.
Change the code so that the pattern
old can be a sequence. (This
is a very easy change.)
Strings are sequences but so are lists and simple one-dimensional arrays.
By allowing non-string sequences, we can specify patterns with non-character
elements. In particular, you should change
so that the elements
digits, alphabetics, alphanumerics, and any characters, respectively, e.g.,
#(:digit :alpha :digit) would match any subsequence
of a digit, letter, and digit.
To simplify writing tests, exercise-tests.lisp
string-subst to use strings as input
and output streams for
file.lisp. They have Graham's code, with
defpackage forms. You need to edit those
defpackage forms. To test, load the files and run
Note that if you get things wrong, you typically need to reload ring.lisp and file.lisp, in that order.
Submit only the defpackage forms you wrote. Don't send Graham's code.
Henley is the random text generator in Figures 8.2 and 8.3. It generates poems based on word pairs found in an existing text. Page vi of the book has a poem by Henley, based on the word pairs in Milton's Paradise Lost.
The ostensible goal of this exercise is to define
(henley-p string) to return true
if and only if
string could have been generated
by generate-text. Hint: a better way to think of this is
that henley-p returns false if it can prove generate-text
could not have created the text.
The secondary goal is to take advantage of this exercise to incrementally improve the original code. While you personally will never write poor code (right?), you will often encounter it. It's not a good investment of time to clean up bad code. There's no benefit if no new functionality results. But, when you have to modify a stretch of code to fix a bug or add new features, then you should clean up the code you're working on so that future maintenance will be easier. A standard rule of thumb is that the next stretch of code that needs maintenance will be in or near the stretch that was just maintained. So clean up pays off.
Get the Henley code (Figures 8.2 and 8.3) from graham.lisp, and put it in the file henley.lisp. Make sure it compiles without error. (You might see a warning about see being undefined. That's because it's embedded in a let, which triggers some warnings. This should be harmless.)
Second, download the plain text file version of Milton's Paradise Lost from Project Gutenberg, and save it in paradise-lost.txt. Open it with your Lisp editor or any text editor and
Start Lisp, compile and load Henley, and
(read-text paradise-lost-pathname), to read
and process the entire poem. This should take just a few seconds, if Henley
Now try several calls to
(generate-text number) with
numbers like 10 and 20 and 50. You should see different Milton-like text
produced each time.
generate-text to be iterative.
In Scheme, you can count on tail-recursion optimization.
In Common Lisp, this is possible but not guaranteed.
Making the code iterative
will also allow you to drop the optional
henley-p function will need to read a stream
of words, just like
read-text. Never copy and paste code to do
this. Refactor the part you want to reuse into a more general function.
In this case, define
(read-stream stream function)
to be a general version of
read-text. It should apply
function to every "word" in the text in
stream. Note that a "word" here means a word or
a punctuation character.
read-text to call
read-text to return the number of
entries in *words*, so that you can see if it actually
Recompile and reload henley.lisp, re-read paradise-lost.txt and confirm that generate-text still produces reasonable output.
(henley-p string) as described before.
henley-p takes a string, not a file.
henley-p should call
Unless you were very keen-eyed during clean-up, you should get a test failure. There's a bug in Graham's code. Find it and fix it. Don't create repeated code.
You should also test
henley-p on some random output from
generate-text. Here's an easy way to capture the printed
generate-text in a string, suitable for passing to
(setq str (with-output-to-string (*standard-output*) (generate-text 20)))
with-output-to-string is described in the book glossary.
Page 113 discusses rebinding global variables. In this case,
we temporarily rebind the global standard output stream
variable to a string stream, so that any call to (format t ...)
goes there instead of the terminal.
Submit for review all the code you changed. Briefly note what you changed and why. Do not submit functions you didn't change.
Do Exercise 8-5 first, because you need the predicate it defines to test your solution to this exercise.
It's not too difficult to use the existing hashtable to find a word that can precede a given word, and hence generate backwards from an initial word to the start of a sentence. But this is expensive and doesn't have the random generation statistical propertes of Henley.
A better approach is to create an equivalent hashtable for going backwards, using the data in the existing hashtable. Then generating in either direction is basically a matter of which hashtable you're using.
To test your code, feed the output of your generator into your Henley tester. It should always return true.
Define your function to take the number of cents and an optional list of the
available coins, largest to smallest, e.g.,
(make-change 72 '(25 10 1)).
The default list should be
(25 10 5 1).
You can assume that the coins are such that the simple greedy algorithm will get the answer with the fewest coins. For a more challenging exercise that doesn't make this assumption, after you do this, try make-best-change.
Graham says that
min have opposite signs.
This makes no sense. It should say that
(funcall f max) and
f min) have opposite signs.
Also, students frequently misunderstand the use of
epsilon. What Graham means (and what is usually intended) is
that you stop approximating when
epsilon of each other.
Finally, my best solution requires two functions, one to check the initial values and handle some special cases that have no solution or an exact solution, and another to do the actual solving. The style critic calls the first a little too long, the latter somewhat too long.
Do as specified.
See the challenge exercises for challenges based on exercises in this chapter.
Send code for exercises 3 and 5 in one submission.
Note that the test case Graham gives for
rules out using a function. If you don't see why, try running
the example with this definition:
(defun nth-expr (n &rest l) (nth (1- n) l))
However, that one test case still allows for a macro that evaluates all expressions, catching any errors. We'll take the interpretation that
nth-expr n exp1 exp2 exp3 ...)
should evaluate only
Here's a test case that your code has to handle correctly. Only one thing should print and it'll be clear if you're right.
(let ((n 3) (x "lose") (y "win")) (nth-expr n (format t "You ~S!" x) (format t "You ~S!" x) (format t "You ~S!" y) (format t "You ~S!" x) ))
This exercise requires you to understand how variable bindings work, but the answer is quite short. Your macro needs to work for both lexical and special variables.
Note the name change: Graham's name does not suggest the close connection
between this macro and
doublef correctly handles generalized references.
Send code for exercises 1 and 5 in one submission.
Do as specified.
Send all the queue functions in one submission.
Queues in Lisp are easy and useful, but Graham left out one essential function,
and should have made
make-queue more convenient. Define
to return true if a queue is empty. Redefine
(make-queue arg1 arg2
... to return a queue initialized with the items given, if any.
As far as I can tell, you need to do Exercise 7 first, before doing Exercise 6, so submit both as one submission.
For all the circular list exercises, make sure you set the global variable
*PRINT-CIRCLE*to true first! This tells Lisp to use a special printing algorithm that handles circular lists. Note that what Lisp prints can be typed in to make a circular list too. It's not just an output format.
As you might expect, by chapter 12, a simple question doesn't mean a simple answer. Graham should've said more.
First, for Exercise 7, something like
(eq l (cdr l))
won't work. This only catches a 1-element cdr-circular list, not lists like
(let ((l (list 1 2 3))) (nconc l l))
(let ((l (list 1 2 3))) (nconc l (cddr l)))
The obvious solution is to keep a list of every CDR and return true if you find the same list twice before hitting NIL. The problem with this solution is that it requires potentially large amounts of CONSing. If you assume a top-level circularity only in the final CDR, you can trade more pointer following to avoid CONSing.
Start a loop with two variables -- a "turtle" that CDR's down the list and a rabbit that CDDR's. That means the rabbit goes twice as fast as the turtle. If the list is CDR-circular, eventually the rabbit and turtle will bump into each other. If the list is not circular, the rabbit will hit NIL.
After you have CDR-circular lists working, then you can do Exercise 6. Careful! Make sure you test this thoroughly. It's easy to write a version that says false when it should say true.
Make sure your function works for regular lists too.
Graham's definition of CAR-circular on page 209 says "the loop passes through the car of some cons." This is pretty open, so I'm defining this problem to be much more general than CDR-circular. In fact, it's comparable to what Lisp has to do when printing with *PRINT-CIRCLE* set to true. All the solutions I've seen keep a stack of sublists.
My exercise-tests.lisp include both CAR-circular and CDR-circular lists, and, in some cases, both. If you believe one of the tests is wrong, email me. Before doing so, draw the test case in box and arrow notation, as shown in the figures in Chapter 12. If there is a loop that goes through the CAR side of a box, then it's CAR-circular.
Comments? Send mail to Chris Riesbeck.