Common Lisp Tips

PAIP lessons

Paradigms of AI Programming is a great book for learning Common Lisp. Peter Norvig wrote a retrospective on the book and included this list of 52 important lessons:

• Use anonymous functions. [p. 20]
• Create new functions (closures) at run time. [p. 22]
• Use the most natural notation available to solve a problem. [p. 42]
• Use the same data for several programs. [p. 43]
• Be specific. Use abstractions. Be concise. Use the provided tools. Don’t be obscure. Be consistent. [p. 49]
• Use macros (if really necessary). [p. 66]
• There are 20 or 30 major data types; familiarize yourself with them. [p. 81]
• Whenever you develop a complex data structure, develop a corresponding consistency checker. [p. 90]
• To solve a problem, describe it, specify it in algorithmic terms, implement it, test it, debug and analyze it. Expect this to be an iterative process. [p. 110]
• AI programming is largely exploratory programming; the aim is often to discover more about the problem area. [p. 119]
• A general problem solver should be able to solve different problems. [p. 132]
• We must resist the temptation to belive that all thinking follows the computational model. [p. 147]
• The main object of this book is to cause the reader to say to him or herself “I could have written that”. [p. 152]
• If we left out the prompt, we could write a complete Lisp interpreter using just four symbols. Consider what we would have to do to write a Lisp (or Pascal, or Java) interpreter in Pascal (or Java). [p. 176]
• Design patterns can be used informally, or can be abstracted into a formal function, macro, or data type (often involving higher-order functions). [p. 177]
• Use data-driven programming, where pattern/action pairs are stored in a table. [p. 182]
• Sometimes “more is less”: its easier to produce more output than just the right output. [p. 231]
• Lisp is not inherently less efficient than other high-level languages - Richard Fateman. [p. 265]
• First develop a working program. Second, instrument it. Third, replace the slow parts. [p. 265]
• The expert Lisp programmer eventually develops a good “efficiency model”. [p. 268]
• There are four general techniques for speeding up an algorithm: caching, compiling, delaying computation, and indexing. [p. 269]
• We can write a compiler as a set of macros. [p. 277]
• Compilation and memoization can yield 100-fold speed-ups. [p. 307]
• Low-level efficiency concerns can yield 40-fold speed-ups. [p. 315]
• For efficiency, use declarations, avoid generic functions, avoid complex argument lists, avoid unnecessary consing, use the right data structure. [p. 316]
• A language that doesn’t affect the way you think about programming is not worth knowing - Alan Perlis. [p. 348]
• Prolog relies on three important ideas: a uniform data base, logic variables, and automatic backtracking. [p. 349]
• Prolog is similar to Lisp on the main points. [p. 381]
• Object orientation = Objects + Classes + Inheritance - Peter Wegner [p. 435]
• Instead of prohibiting global state (as functional programming does), object-oriented programming breaks up the unruly mass of global state and encapsulates it into small, manageable pieces, or objects. [p. 435]
• Depending on your definition, CLOS is or is not object-oriented. It doesn’t support encapsulation. [p. 454]
• Prolog may not provide exactly the logic you want [p. 465], nor the efficiency you want [p. 472]. Other representation schemes are possible.
• Rule-based translation is a powerful idea, however sometimes you need more efficiency, and need to give up the simplicity of a rule-based system [p. 509].
• Translating inputs to a canonical form is often a good strategy [p. 510].
• An “Expert System” goes beyond a simple logic programming system: it provides reasoning with uncertainty, explanations, and flexible flow of control [p. 531].
• Certainty factors provide a simple way of dealing with uncertainty, but there is general agreement that probabilities provide a more solid foundation [p. 534].
• The strategy you use to search for a sequence of good moves can be important [p. 615].
• You can compare two different strategies for a task by running repeated trials of the two [p. 626].
• It pays to precycle [p. 633].
• Memoization can turn an inefficient program into an efficient one [p. 662].
• It is often easier to deal with preferences among competing interpretations of inputs, rather than trying to strictly rule one interpretation in or out [p 670].
• Logic programs have a simple way to express grammars [p. 685].
• Handling quantifiers in natural languiage can be tricky [p. 696].
• Handling long-distance dependencies in natural language can be tricky [p. 702].
• Understanding how a Scheme interpreter works can give you a better appreciation of how Lisp works, and thus make you a better programmer [p. 753].
• The truly amazing, wonderful thing about call/cc is the ability to return to a continuation point more than once. [p. 771].
• The first Lisp interpreter was a result of a programmer ignoring his boss’s advice. [p. 777].
• Abelson and Sussman (1985) is probably the best introduction to computer science ever written [p. 777].
• The simplest compiler need not be much more complex than an interpreter [p. 784].
• An extraordinary feature of ANSI Common Lisp is the facility for handling errors [p. 837].
• If you can understand how to write and when to use once-only, then you truly understand macros [p. 853].
• A word to the wise: don’t get carried away with macros [p. 855].

Stylish Common Lisp

The Tutorial on Good Lisp Programming Style by Peter Norvig and Kent Pitman is full of useful tips for Common Lisp programmers.

Touching a file

To create an empty file, like the Unix touch command does, you might try something like this:

;; BOGUS
(close (open "foo.txt" :direction :output 
             :if-does-not-exist :create 
             :if-exists :append))

open has a :direction option specifically for this purpose, though:

(open "foo.txt" :direction :probe :if-does-not-exist :create)

If “foo.txt” does not exist, it will be created. The stream returned is already closed. The spec says this:

[:probe causes] the creation of a “no-directional” file stream; in effect, the file stream is created and then closed prior to being returned by open.

Reading floats

When the reader sees a number like “3.0” with no exponent marker, the reader will convert it into a single-float by default. You can change what float type is used for conversion by changing *read-default-float-format* to another float type.

For example:

* (/ 22.0 7.0)
3.142857

* (setf *read-default-float-format* 'double-float)
DOUBLE-FLOAT

* (/ 22.0 7.0)
3.142857142857143

The printer will also omit exponent markers if the float type of the number being printed matches *read-default-float-format*.

Redirecting output

Got a function that writes to *standard-output* but you really want to redirect it somewhere else? You can bind the *standard-output* special variable in all the macros that create temporary streams.

For example, to return the output as a string:

* (with-output-to-string (*standard-output*) 
    (print-marketing-report))
"Source,Hits
twitter,243
google,805
direct,47
"

To write it out to a file:

* (with-open-file (*standard-output* #p"file.txt" :direction :output)
    (print-marketing-report))
NIL

Swapping places

The naive way to swap the values of two places, a and b, is something like this:

;; BOGUS
(setf temp a)
(setf a b)
(setf b temp)

psetf (parallel setf) can do it in one form:

(psetf a b b a)

But rotatef is best:

(rotatef a b)

Pluralization

The ~P format directive can do simple pluralization.

* (format nil "You have ~D goat~:P." 42)
"You have 42 goats."

* (format nil "You have ~D goat~:P." 1)
"You have 1 goat."

* (format nil "You have ~D fl~@:P." 42)
"You have 42 flies."

* (format nil "You have ~D fl~@:P." 1)
"You have 1 fly."

Irregular plurals are more complicated:

(format nil "You have ~D ~:*~[mice~;mouse~:;mice~]." n)

(Thanks to stassats for the flies and mice.)

string output streams

get-output-stream-string doesn’t just return the string accumulated so far in a string-stream. It also resets the accumulation, so you can use the same stream multiple times for separate results. Here’s a simple string splitter:

(defun split (string &optional (split-character #\Space))
  (let ((result '())
        (stream (make-string-output-stream)))
    (loop for char across string
          if (char= char split-character)
          do (push (get-output-stream-string stream) result)
          else
          do (write-char char stream))
    (push (get-output-stream-string stream) result)
    (nreverse result)))

It could be used like this:

* (split "The quick brown fox.")
("The" "quick" "brown" "fox.")

I learned about this technique from an Erik Naggum post.

Discarding output

Unix shell nerds discard unwanted output by redirecting it to /dev/null. The equivalent in Common Lisp is the empty broadcast stream returned by a call to make-broadcast-stream with no arguments.

For example, if you have some code that normally prints to *standard-output*, but you want that output discarded, you can do something like this:

(let ((*standard-output* (make-broadcast-stream)))
  (app:noisy-code))