CS325 Graham Chapter 3 Notes

Page 36

our-copy-list is a very important function to understand. The recursive pattern it uses is the basis for most recursive list-transforming functions.

But be careful about the predicate you use to test for the end of the list. The code as written is:

(defun our-copy-list (lst)
      (cond ((atom lst) lst)
        (t (cons (car lst) (our-copy-list (cdr lst))))))

What happens if you call (our-copy-list 12)? The real copy-list signals an error, but the above definition returns 12.

The standard pattern for traversing a list is to use null to test for the end of the list. That is what you should use for your code, unless something special is required.

In the case of our-copy-list, the actual specification says that dotted lists, e.g., (a b c . d), need to be allowed, but not atoms by themselves. It's left as an exercise to the reader on how to fix the above code to implement the correct behavior.

compress on page 37, which uses the predicate consp, is another example of this. The function will return inputs like 12 and A without error.

When should you allow non-lists and when should you signal an error? A good rule of thumb is:

• A CDR-recursive function that loops down the elements of a list should reject a non-list input. Examples of such functions are count, copy-list, reverse, and find.
• A CAR-CDR recursive function that operates on all elements of a list, no matter how nested, should accept and process a non-list input. Examples of such functions are copy-tree, subst, and equal.

It's not worth doing extra work to check to make sure a list is properly formed, but it's trivial and cheap to use the appropriate predicate to catch most problems.

Page 37

compr and n-elts are both terrible function names. The former suggests nothing at all, except a confusing similarity to compress, and the latter suggests that it generates a list of N elements, not a pair of the form (number element).

Names like compr, compress2, recursive-compress are typical names that programmers generate when at a loss for how to name a function. They're all terrible.

Here's an important rule for names:

Name a function by the task it does, not how it does it, nor how it relates to another function.<

If you follow the Cardinal Rule of Functions, then generating a good name should not be hard. Just name it for the single task that it does.

If two functions do similar tasks, they usually differ by the kind of arguments they take, e.g., compress-list versus compress-string. If they do the same thing to the same arguments, then why are there two functions?

In this particular case, compr's primary task is not "compress a list." It's "given an object and a list, collect a run for the given object." The run collected is returned in the form of a pair of the form (length object).

Unfortunately, compr has a secondary task, which is to recursively repeat this process with the remainder of the list. This is a common problem with recursive code. It mixes control structure with tasks and that makes it harder to name. The best we can do is probably something like scan-and-compress.

Or we could use generated lists.

Page 38

Note Graham's comment in the text that list-of is unnecessary. Common Lisp already has a function make-list that does the same thing. To make a list of three ho's, you'd write:

(make-list 3 :initial-element 'ho)

This uses a keyword argument. See page 44.

There's a much more interesting use for the name list-of in the Lisp exercises.

Page 39

In this class, we'll use require rather than load, so you would load the list compression code with

(require "compress")

The advantages of require over load are:

• if compress.lisp has already been loaded, it won't be loaded again
• if your Lisp uses some extension other than "lisp", you don't have to change anything, because require generates the appropriate extension automatically.

The disadvantages of require are

• it was underspecified in the Common Lisp reference manual, so different implementations do different things
• because of these differences, require was temporarily dropped from Common Lisp, so some implementations don't have it
• like loop, it has a religious aspect; the battle is between:
  • the centralists, who favor defining all module dependencies in one place with defsystem, and
  • the decentralists, who favor defining what a module depends on in the module

Unfortunately for the centralists, there is no Common Lisp standard for defsystem. Unfortunately for the decentralists, most implementations of require are pretty weak.

A very commonly used non-standard centralist package is ASDF (Another System Definition Facility), modeled after defsystem.

Page 52

bfs is a terrible name, because it says how it works, not what it does. Also, the nested let's might be better done as a subfunction, e.g.,

(defun breadth-first-search (end queue net)
      (if (null queue)
          nil
          (expand-queue end (car queue) (cdr queue) net)))

    (defun expand-queue (end path queue net)
      (let ((node (car path)))
        (if (eql node end)
            (reverse path)
            (breadth-first-search end
                                  (append queue
                                          (new-paths path node net))
                                  net))))