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 defined in exercise-tests.lisp. 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.

Chapter 2

Recursion bundle

Exercise Name: Ex 2-4+7+8+9

Function names: greater, has-list-p, print-dots, get-a-count, summit

Send the code for exercises 4, 7, 8, and 9 in one submission.

Some exercises ask for multiple solutions. Submit all requested versions. Use the same required function name for each version. Be careful when testing that each version was tested separately. Most Lisp editors have a way to evaluate a single function definition in a file.

For Exercise 2-9, explain why each solution fails, in terms a novice would understand not Lisp jargon, and fix each solution. Don't give an entirely different answer. That would not help a novice learn.

Even though the instructions say to use only what you've seen so far, use COND rather than IF, if you have an if-then-else-if chain, and use DO if you have a loop that calculating a value, be it a list, sum, or boolean.

See "The Point of DO" on page 89 and How do you DO? for examples of how simple DO loops can be, without any assignment or RETURNs in the body of the DO.

Chapter 3

Exercise name: Ex 3-2

Not in a bundle -- don't submit

Function names: stable-union, stable-intersection, stable-set-difference

Names like 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: sort and 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 l1, if any, or in l2, if any. Don't worry about handling keyword arguments.

Avoid redundant code. Avoid needless CONSing or list scanning.

Exercise name: Ex 3-3

Not in a bundle -- don't submit

Function name: 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 the 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.

Exercise name: Ex 3-5

Not in a bundle -- don't submit

Function name: position+

Here is why the example returns (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.

Exercise name: Ex 3-8

Recursion bundle

Function names: show-dots, show-list.

Define 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 for examples.

Define 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.

Exercise name: Ex 3-9

Recursion bundle

Function name: longest-path

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.

Chapter 5

Exercise name: Ex 5-5

Not in a bundle -- don't submit

Function name: preceders

Do as specified. Put both versions in the same submission.

Exercise name: Ex 5-6

Not in a bundle -- don't submit

Function name: intersperse

Put both versions in the same submission.

NOTE: (intersperse '- '(a)) should return (a) and (intersperse '- '()) should return ().

Avoid inefficiencies. There are two easy traps to fall into:

Exercise name: Ex 5-7

Not in a bundle -- don't submit

Function name: diff-by-one-p

Define four versions, all with the same name. The fourth should use every. Put all four versions in the same submission.

return-from makes more sense than return in part c.

Exercise name: Ex 5-8

Values bundle

Function name: max-min

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, and the key point is to get both values in one scan through the list.

Don't use subseq to create subvectors. This is expensive. Don't call length on every iteration either. This is unnecessary. It also limits the generality of maxmin.

Instead, define max-min to take the keywords :start and :end, just like the other sequence functions do. With:start and :end, your code should be more efficient than code with subseq and multiple calls to length, and more flexible at the same time. Think about what other keyword arguments would provide similar efficiency and flexibility.

Exercise name: Ex 5-9

Recursion bundle

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)

to be

(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.

Chapter 6

Exercise name: Ex 6-2

Not in a bundle -- don't submit

Graham's 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.

Redefine 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 (funcall 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 :test parameter 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 bin-search.

Exercise name: Ex 6-5+6+7+8

Not in a bundle -- don't submit

Function names: my-remove-if, greatest-arg, bigger-arg, memoize

Send code for exercises 5, 6, 7 and 8 in one submission.

The parameter to greatest-arg and bigger-arg should be optional. If omitted, it should reset the internal data to its initial state.

Instead of frugal, define (memoize function). (memoize function) should take one argument that is itself a function of one argument, e.g., (memoize #'sqrt). 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 name: Generalized BFS

Recursion bundle

Function names: bfs, shortest-path

Test cases: use the shortest-path tests, as described below.

BFS in Exercise 5-9 is a terrible name for a function to find paths in a graph, but it's not a bad abbreviation for a function to do breadth-first state space search.

State space search formalizes solving many problems as starting with some initial state S, and trying different actions that lead to new states, until you find a state that satisfies some goal predicate P. The solution is a list of states, called a path, showing the states from the final goal backward to the initial state.

Generalize the BFS function to do simple breadth-first state space search. Define (bfs paths pred gen) to take three arguments:

bfs should avoid cycles, i.e., it should not add a state to any path twice. The gen function does not need to handle that case.

The code for bfs should not need to change very much, from your breadth-first code in Exercise 5-9. Try using the version that didn't need non-local exits. The code will manage the queue of paths the same way. Replace the steps that test for done and that generate new states to use the functions passed in. It should not reverse the final answer.

Test by redefining shortest-path to call the new bfs with the appropriate lambda closures to search a graph. No other new functions should be needed. shortest-path should take the same parameters as before. Test your code with (run-tests shortest-path).

Note that shortest-path will need to reverse the value returned by the generalized bfs.

Exercise: Iterative Deepening Search

Recursion bundle

Function names: ids, dls, shortest-path

Test cases: use the shortest-path tests, as described below.

Simple breadth-first search on large very bushy networks is impractical. If there are dozens or hundreds of branches, the queue quickly grows to 1000s of elements. But if you're looking for an optimal solution, e.g., the shortest path, what else can you do?

One answer that seems at first glance to be even more worse than breadth-first search is this:

The iterative deepening algorithm seems like it will be too expensive because step 2 will repeat all the work done in step 1, step 3 will repeat step 2 and so on.

However, while this repeated work does happen, the combinatorics of trees, specifically that there as many or more nodes at layer N than in the entire tree above layer N, turns out to make the total runtime cost of this algorithm very competitive with BFS , with much smaller memory costs. The same idea can be applied to more intelligent search algorithms.

Define the function ids (iterative deepening search) to take the same arguments as bfs. ids should repeatedly call a depth-first search function -- call it dls for depth-limited search -- that does a simple depth-first search to find an extension of path. dls should take an additional parameter n, and should

dls should not need a queue. dls should avoid cycles, i.e, it should not add states already in path.

There is one tricky point. If you look at the algorithm as described on Wikipedia and elsewhere, it has a problem: it loops forever if there is no solution!

One option would be to pass a depth-limit parameter to ids to tell it when to stop trying. This is useful to have. It's necessary for both ids and bfs if infinitely long paths are possible. But it's not a general or satisfying approach when infinitely long paths are not possible.

bfs can handle searches that fail as long as there there no infinite paths, because, eventually, nothing new can be added to the queue, and all options have been explored.

To do the same thing, ids and dls need to be able to distinguish two kinds of search failure:

If all the depth-first searches have true failure at depth N, then there's no point to going any deeper.

Implement ids and dls, and any subfunctions you need. Test by defing shortest-path to call ids and confirm that all tests pass, including those where search fails. Your code should be efficient and clean, including the handling of the two kinds of failure.

Chapter 7

Exercise name: Ex 7-2

Text bundle

Function names: map-file, map-stream

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 should return nil. Define (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 map-stream.

Exercise name: Ex 7-4

Not in a bundle -- don't submit

Do as specified. Currently, there are no test cases for this exercise.

Exercise name: Ex 7-5+6

Text bundle

Function name: stream-subst

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.

Extend stream-subst as described for Exercise 7-5, but the wildcard character should be specifiable with a :wildcard keyword parameter, with the default +, e.g.,

Then extend 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 stream-subst so that the elements :digit, :alpha, :alphanumeric and :wild match 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 defines string-subst to use strings as input and output streams for stream-subst.

Chapter 8

Exercise name: Ex 8-4

Trie bundle

Download ring.lisp and file.lisp. They have Graham's code, with empty defpackage forms. You need to edit those defpackage forms. To test, load the files and run the following:

(run-tests ring-package)

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.

Exercise name: Ex 8-5

Text bundle, Legacy code bundle

Function names: read-stream, henley-p

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.

Setup and test Henley

Get the Henley code (Figures 8.2 and 8.3) from graham.lisp, and put it in the file henley.lisp. Put (in-package :cs325-user) at the top as with other exercise code.

Compile and load the code. 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 call (read-text paradise-lost-pathname), to read and process the entire poem. This should take just a few seconds, if Henley is compiled.

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.

Clean up Henley

There are a number of ways to clean up the Henley code.

Change 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 argument prev.

Get rid of the DEFUN inside LET. Such definitions are a pain to maintain. it also means you have no way, short of reloading the whole form, to reset SEE back to start. The better approach is to define a MAKE-SEE that returns a closure that does what SEE did. Then any time you want a fresh "SEE" function, you just call (MAKE-SEE).

Refactor the code to operate on a stream. That will make it more flexible, e.g., you can test it on other kinds of streams, like string streams.

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, as defined by Graham, i.e., a symbol for a word or punctuation character.

Redefine read-text to call read-stream appropriately. Change read-text to return the number of entries in *words*, so that you can see if it actually loaded anything.

Clean up the do in read-stream so that the Lisp Critic is happy. An easy change is to replace if and progn with cond. A more important change is to refactor the do so that the do loop just handles character input until the stream is empty. It calls another function -- with no loop in it -- that manages adding a character to a buffer and possibly outputing a token.

Recompile and reload henley.lisp, re-read paradise-lost.txt and confirm that generate-text still produces reasonable output.

Define henley-p

Define (henley-p string) as described before. Note that henley-p takes a string, not a file. henley-p should call read-stream appropriately.

Do (run-tests henley-p).

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 your generate-text. Here's an easy way to capture the printed output of generate-text in a string, suitable for passing to henley-p

(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.

Exercise name: Ex 8-6

Not in a bundle -- don't submit

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.

Chapter 9

Exercise name: Ex 9-2

Values bundle, Number bundle

Function name: make-change

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.

Exercise name: Ex 9-5

Number bundle

Function name: solve

Graham says that max and min have opposite signs. This makes no sense. It should say that (funcall f max) and (funcall 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 max and min are within 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.

Exercise name: Ex 9-6

Values bundle

Function name: horner

Do as specified.

See the challenge exercises for challenges based on exercises in this chapter.

Chapter 10

Macro bundle

Exercise name: Ex 10-3+5

Send code for exercises 3 and 5 in one submission.

Note that the test case Graham gives for nth-expr 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 n and expN.

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)
            ))

Exercise name: Ex 10-6

Macro bundle

Function name: preserve

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.

Exercise name: Ex 10-8

Macro bundle

Function name: doublef

Note the name change: Graham's name does not suggest the close connection between this macro and incf.

Make sure doublef correctly handles generalized references.

Chapter 11

Exercise name: Ex 11-1+5

Not in a bundle -- don't submit

Send code for exercises 1 and 5 in one submission.

Exercise name: Ex 11-2

Not in a bundle -- don't submit

Do as specified.

Chapter 12

Exercise name: Ex 12-3+4+5

Not in a bundle -- don't submit

Function names: make-queue, empty-queue-p, copy-queue, enqueue-front, requeue-front

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 empty-queue-p to return true if a queue is empty. Redefine (make-queue arg1 arg2 ... to return a queue initialized with the items given, if any.

Exercise name: Ex 12-6+7

Not in a bundle -- don't submit

Function names: circular-member-p, cdr-circular-p

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))

or

  (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.

Exercise name: Ex 12-8

Not in a bundle -- don't submit

Function name: car-circular-p

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.