Section notes: Week 2

CS 164, Fall 2005

Follow-up from last time

There are several minor differences between Scheme and Common Lisp. There are also more fundamental differences, many of which are reflected in the relative sizes of the language. Scheme is a small language: the specification for Scheme is fifty pages, including the table of contents, bibliography, and index. In contrast, the Common Lisp specification is over a thousand pages. In part because of its small size, Scheme is very clean: there are no mostly-redundant features in the language, and no extra bits that are hard to implement but are rarely used. But size has its advantages, and the Common Lisp control structures and data types that Scheme doesn't have can be very useful.

In many language families, newer dialects are larger than older dialects. C begets C++; Fortran 77 begets Fortran 95; Awk begets Perl. In many cases, the new features provided in newer versions of a language provide welcome relief from deficiencies (or perceived deficiences) in related older dialects. On the other hand, it can be dangerous to make a big new system in order to fix the problems in a smaller, older system; see Fred Brooks' discussion of the second system effect in The Mythical Man-Month.

Quote and sharp-quote

We've already mentioned some differences between Common Lisp and Scheme: Common Lisp uses setf rather than set!, and Common Lisp predicates end with a p rather than with a ?. Common Lisp functions are defined with defun rather than with define, and the parentheses around the arguments are arranged differently. There are a variety of Common Lisp facilities that standard Scheme doesn't have (macros, libraries, fancy data structures), and there is one Scheme facility that Common Lisp lacks (call/cc). Perhaps the difference that causes the most confusion, however, is Common Lisp's two-namespace system, and the difference between quote and sharp-quote.

When you want to pass a literal list, which you haven't evaluated, you do it by quoting the list with ', like this:

  '(1 2 3)

If you want to pass around functions, you do it with the #', like this:

  (mapcar #'1+ '(1 2 3))

In Scheme you would never need #', because Scheme has only one name space. In Common Lisp, you can use the same symbol to simultaneously refer to an ordinary value (the symbol-value) and a function (the symbol-function). If you are the type of programmer who enjoys obfuscated code contests, it may amuse you to use this namespace distinction to write perverse codes like:

  (let ((x 2))
    (defun x (x) (+ x x))
    (x x))

Usually, good taste prevents people from writing such code.

Common Lisp features

• Control structures
  • if, cond, when, unless
  • do, dolist, dotimes
  • map, mapcar, mapcan, maphash
  • loop (a language unto itself)
• Data structures
  • All things cons (lists, assoc lists, trees, sets)
  • Symbols
  • Arrays
  • Hash tables and property lists
  • Structs (defstruct)
  • Classes
  • Lots of different intrinsic types
• Flexible function definition
  • Optional arguments
  • Keyword arguments
  • values / multiple-value-bind
• World's coolest macro system
• Flexible input system (read macros)
• Large standard library

Practice Lisping

1. What do you expect as the output from the following code?

     (setf *alist* '((a . 1) (b . 2) (c . 3)))
     (setf *new-pair* '(a . 2))
     (push *new-pair* *alist*)
     (print (assoc 'a *alist*))
     (setf (cdr (assoc 'a *alist*)) 42)
     (print (assoc 'a *alist*))
     (print *new-pair*)
   

2. A prefix-sum operation takes a list of numbers x[i] and returns a list of numbers y[i] = sum_{j = 1 .. i} x[i]. How many ways can you think to write prefix-sum in Common Lisp?
3. The management of Acme Programming Widgets has decided to change their terminology. Write a function that will take a sentence from Acme's old documentation (as a list of words) and an assoc list of (old-word . new-word) pairs, and will return a sentence in which all the old words have been replaced by their new equivalents.
4. Extend the previous idea by writing a Mad Libs program: rather than replacing an old word by a pre-determined new word, you will replace an old word by a randomly selected new word of the appropriate type (noun, verb, etc). You may assume the existence of a choose-random function which returns a randomly selected element from a list.
5. How would your sentence rewriter have to change if you wanted to replace one phrase with another, rather than replacing single words?
6. In an introductory Lisp programming course, the students are allowed to form teams of two. Unfortunately, the instructor suffered a catastrophic hard drive failure, and so has lost the list of registered partners. Help the instructor by writing a program to read a list of (programmer program) lists and return a list of sets of programmers with identical programs.
7. How might the previous program change if the instructor wanted to find all the programmers who had written structurally identical programs, which differ only in the choice of variable and function names?

Question for next time

In C/C++, the preprocessor is frequently separated from the rest of the C compiler; in fact, you can invoke the preprocessor alone through the standalone program cpp. Which aspects of C lexical structure must the preprocessor know about, and which can it ignore? How closely do you think the preprocessor ought to be coupled to the rest of the compiler, and why?