Chapter 4 - Mastering the Essentials

We've explored the fundamental concepts of Lisp through the twelve lessons of Chapter 3. If you feel that you have a very strong grasp of these fundamentals, or if you've worked with Lisp before, you may want to skim the remainder of this chapter.

We'll review some of the material from Chapter 3 using a hands-on approach. Along the way, you'll learn some new techniques that have had to wait until all of the fundamentals had been introduced; if you're a beginner and haven't read Chapter 3, go back and read it before you try to do the exercises in this chapter.

You should have access to a Lisp development system as you work through this chapter. As you read this chapter, please take the time to run the examples using your Lisp system. This will give you a chance to learn how your Lisp system responds to input, including any mistakes you may make. (If you don't make any mistakes in transcribing the examples, you should get adventurous and try to modify some of the examples.) Appendix A lists several commercial, shareware, and free Lisp systems for Macintosh, DOS, and Windows computers.

Hands-on! The "toploop"

You interact with the Lisp system through a built-in piece of code called the toploop, which repeats three simple steps for as long as you run the Lisp system:

1. Read an expression (you provide the expression).
2. Evaluate the expression just read.
3. Print the result(s) of the evaluation.

This is also called the "read-eval-print" loop. Some Lisp systems evaluate the expression using a Lisp interpreter; modern systems use a compiling evaluator, which first compiles the expression to machine code then executes the code. A compiling evaluator is also an incremental compiler, so named because it can compile a program in increments of one expression.

The toploop also provides a minimal user interface -- a prompt to indicate that it's ready to read a new expression -- and a way to gracefully catch any errors you might make.

If you were to write the Lisp code for a toploop, it would look something like this:

(loop
   (terpri)
   (princ 'ready>)
   (print (eval (read))))

NOTE 1: (terpri) prints a blank line.

NOTE 2: (loop ...) executes its forms in order, then repeats -- we'll see more of LOOP in Chapter 5.

NOTE 3: (eval ...) returns the result of evaluating a form. This is one of the few legitimate uses of EVAL -- you should beware of Lisp code that uses EVAL for reasons other than evaluating arbitrary Lisp expressions provided at runtime.

In fact, you can type this into your Lisp system and temporarily run your own toploop on top of Lisp's toploop. Try it! You'll see your system's prompt replaced with READY>. Every valid Lisp form you type will be read, evaluated, and printed by your toploop. Depending upon your Lisp system, this may happen as soon as the expression is completed -- either by a space or a matching parenthesis or double quote mark -- or you may have to press the RETURN or ENTER key.

Your Lisp session may look like the following, where ? is the Lisp system's prompt for input:

? (loop
     (terpri)
     (princ 'ready>)
     (print (eval (read))))

READY>(+ 1 2 3)

6
READY>(cons 1 (cons 2 (cons 3 nil)))

(1 2 3)
READY>

There are two ways to get out of your toploop. One is to abort, typically using a special keystroke or a menu command -- consult your Lisp system's manual. The other way is to enter an erroneous expression -- such as (+ 'A 1) -- at the READY> prompt, which will put you into the Lisp debugger.

In Lisp, the debugger is accessed via a "break loop." This behaves just like a toploop, but accepts additional commands to inspect or alter the state of the "broken" computation. Break loops vary widely among Lisp systems. The manual will describe the break loop. Check also under the manual's index entries for "debugger."

Spotting and avoiding common mistakes

"I entered a Lisp expression, but nothing happened." The most common cause of this problem is missing a matching delimiter -- typically a right parenthesis or double-quote -- somewhere in your expression. Unlike some development systems which process your input each time you enter a line of code, Lisp waits for you to enter a complete expression before attempting to process anything. What happens if you enter the following code in your system?

? (defun bad-1 ()
     (print "This is a bad function definition)
     (print "But I'll try it anyway..."))

Looks good, huh? All the parentheses match, and you press the ENTER key that one last time, and... Nothing. The string argument to the first print statement is missing a closing double-quote, turning the rest of your input into part of the string. You'll do this more than once (trust me), so the best thing to do is to consult your Lisp system manual to find out how to edit the pending input so you can add the missing double-quote to what you've already typed.

Here's another bit of code that will make your Lisp system appear to sleep:

? (defun factorial (n)
     (cond ((<= n 0)  1)
           (t (* n (factorial (- n 1)))))

Again, a quick glance shows nothing amiss. But count the parentheses and you'll find that lefts outnumber rights by one. When you press the final enter key, the read part of Lisp's read-eval-print loop still needs one more right parenthesis before it can finish its job and pass your expression to the evaluator.

Both of these situations can be avoided if your Lisp system has an editor that matches delimiters as you type. In some systems, this matching momentarily flashes the left delimiter as you type the matching right delimiter. Or your system might flash or highlight the matching delimiter of whatever you have under the cursor; some systems even highlight the entire intervening expression. Again, check your manual -- this feature is essential to comfortable Lisp programming.

"I get confused about when to use '." This is a really common problem for people just learning to program, but it manages to puzzle the occasional experienced (non-Lisp) programmer as well. The rule is simple:

If you want a name to stand for a value, don't quote it.

If you want a name to stand for its symbol, quote it.

There are a few exceptions to the rule, all having to do with self-evaluating symbols. These symbols always represent themselves. They are:

T
NIL

and keyword symbols. A keyword symbol is any symbol that begins with a : character, for reasons that will become clear when we look at packages in Chapter 31. A keyword symbol always evaluates to itself, thus:

? :foo
:FOO
? :some-long-but-nondescript-keyword-symbol
:SOME-LONG-BUT-NONDESCRIPT-KEYWORD-SYMBOL

It usually doesn't hurt to quote a self-evaluating symbol. For example, NIL is identical to 'NIL. Adding the quote is a matter of style and preference.

Time for a pop quiz! What's wrong with the following code?

? (defun factorial (n)
     (cond ((<= 'n 0)  1)
           (t (* 'n (factorial (- 'n 1))))))

Right. The 'N expressions are wrong, because we want the value of the symbol (a number which varies with execution of the function), and not the symbol itself.

Defining simple functions

(defun function-name (argument-names ...)
   function-body )

For example:

? (defun quadratic-roots (a b c)
    "Returns the roots of a quadratic equation aX^2 + bX + c = 0"
    (let ((discriminant (- (* b b) (* 4 a c))))
      (values (/ (+ (- b) (sqrt discriminant)) (* 2 a))
              (/ (- (- b) (sqrt discriminant)) (* 2 a)))))
QUADRATIC-ROOTS

? (quadratic-roots 1 2 4)
#c(-1.0 1.7320508075688772)
#c(-1.0 -1.7320508075688772)

? (quadratic-roots 2 -16 36)
#c(4.0 1.4142135623730951)
#c(4.0 -1.4142135623730951)

? (quadratic-roots 1 4 4)
-2
-2

? (quadratic-roots 1 -14 49)
7
7

? (quadratic-roots 1 8 4)
-0.5358983848622456
-7.464101615137754

? (quadratic-roots 1 4 -5)
1
-5

? (documentation 'quadratic-roots 'function)
"Returns the roots of a quadratic equation aX^2 + bX + c = 0"

             /--------
       +    /  2
   - b -  \/  b  - 4ac
 ----------------------
          2a

If you've ever solved this problem in a computer language that doesn't support complex number arithmetic, you've had to find a way to signal the caller when the roots are imaginary (i.e. when the discriminant is less than zero). Lisp just does the right thing: the square root of a negative number is a complex number:

? (sqrt -1)
#c(0 1)

? (values 2 nil)
2
NIL

So you think about only having one value in the VALUES form:

? (values 3)
3

? (values)

? (values 4 (values))
4
NIL

A little reflection convinces you that you can't get VALUES to return nothing for something, so you consider having two separate returns. This yields the following function:

? (defun quadratic-roots-2 (a b c)
    "Returns the roots of a quadratic equation aX^2 + bX + c = 0.
Returns only one value if the roots are coincident."
    (let ((discriminant (- (* b b) (* 4 a c))))   ; zero if one root
      (cond ((zerop discriminant)
             ;; coincident roots -- return one value
             (/ (+ (- b) (sqrt discriminant)) (* 2 a)))
            (t
             ;; two distinct roots
             (values (/ (+ (- b) (sqrt discriminant)) (* 2 a))
                     (/ (- (- b) (sqrt discriminant)) (* 2 a)))))))
QUADRATIC-ROOTS-2

? (quadratic-roots-2 1 -14 49)
7

? (quadratic-roots-2 1 4 -5)
1
-5

NOTE: ZEROP is a predicate (hence the P suffix) that is true when its numeric argument is zero. Writing (ZEROP n) is the same as writing (= n 0).

? (documentation 'quadratic-roots-2 'function)
"Returns the roots of a quadratic equation aX^2 + bX + c = 0.
Returns only one value if the roots are coincident."

A lambda list can have a number of additional features. We'll look at two of these here, and the rest in Chapter 21.

If you want to make a function that takes one or more optional arguments, use the &OPTIONAL keyword followed by a list of parameter names, like this:

? (defun silly-list-1 (p1 p2 &optional p3 p4)
    (list p1 p2 p3 p4))
SILLY-LIST-1

? (silly-list-1 'foo 'bar)
(FOO BAR NIL NIL)

? (silly-list-1 'foo 'bar 'baz)
(FOO BAR BAZ NIL)

? (silly-list-1 'foo 'bar 'baz 'rux)
(FOO BAR BAZ RUX)

If you supply fewer than the number of required parameters (to the left of &OPTIONAL in the example above), or more than the total number of required plus optional parameters, you'll get an error:

? (silly-list-1 'foo)
Error: Not enough arguments.

? (silly-list-1 'foo 'bar 'baz 'rux 'qup)
Error: Too many arguments.

? (defun silly-list-2 (p1 p2 &rest p3)
    (list p1 p2 p3))

? (silly-list-2 'foo 'bar)
(FOO BAR NIL)

? (silly-list-2 'foo 'bar 'baz)
(FOO BAR (BAZ))

? (silly-list-2 'foo 'bar 'baz 'bob 'tom 'don)
(FOO BAR (BAZ BOB TOM DON))

? (defun silly-list-3 (p1 p2 &optional p3 p4 &rest p5)
    (list p1 p2 p3 p4 p5))
SILLY-LIST-3

? (silly-list-3 'foo 'bar)
(FOO BAR NIL NIL NIL)

? (silly-list-3 'foo 'bar 'baz)
(FOO BAR BAZ NIL NIL)

? (silly-list-3 'foo 'bar 'baz 'bob)
(FOO BAR BAZ BOB NIL)

? (silly-list-3 'foo 'bar 'baz 'bob 'tom)
(FOO BAR BAZ BOB (TOM))

? (silly-list-3 'foo 'bar 'baz 'bob 'tom 'don)
(FOO BAR BAZ BOB (TOM DON))

Using global variables and constants

? (defun set-foo-globally (x)
    (setq foo x))
SET-FOO-GLOBALLY

? foo
Error: unbound variable FOO

? (set-foo-globally 3)
3

? foo
3

? (defun set-foo-globally (x)
    (setq foo x))
Warning: undeclared free variable FOO, in SET-FOO-GLOBALLY.
SET-FOO-GLOBALLY

My Lisp system warns me about free variables in function definitions because they could be a symptom of a typographical error:

? (setq *olympic-year* 1996)
1996

? (defun set-next-olympic-year ()
    (setq *olympic-year* (+ *olmpic-year* 2)))
Warning: undeclared free variable *OLMPIC-YEAR*, in SET-NEXT-OLYMPIC-YEAR.
SET-NEXT-OLYMPIC-YEAR

There are two more ways to define global variables in Lisp:

? *var1*
Error: unbound variable

? (defvar *var1* 1)
*VAR1*

? *var1*
1

? (defvar *var1* 2)
*VAR1*

? *var1*
1

? (defparameter *a-var* 3)
*A-VAR*

? *a-var*
3

? (defparameter *a-var* 4)
*A-VAR*

? *a-var*
4

DEFPARAMETER sets a global value each time it is used. Although the effect is the same as a SETQ form, the DEFPARAMETER is preferable because it gives implicit documentation as a defining form (in Lisp, any form that begins with DEF is most likely a defining form), and because it allows you to add documentation to the variable:

? (defparameter *a-var* 3 "The number of things I have to do today.")
*A-VAR*

? (documentation '*a-var* 'variable)
"The number of things I have to do today."

In the examples above, we've started following the convention of making global variable names begin and end with an asterisk. When you read other programmers' Lisp code, you'll see that they follow this convention. They'll expect you to do the same.

DEFCONSTANT is similar to DEFVAR and DEFPARAMETER, except that it defines a name which is known globally and has a constant value. This means that anywhere you read a name which was defined in a DEFCONSTANT form, you can substitute the value given by the DEFCONSTANT form. It also means that you can't redefine the named constant, not even by using another DEFCONSTANT form with a different value.

Some Lisp programmers give constants names which begin and end with plus signs. It's helpful to name constants in a distinctive way so you don't inadvertently try to use the name for another purpose. Once a name has been defined constant, you can't even use it for a seemingly innocuous use, such as a parameter in a lambda list or LET binding.

Defining recursive functions

You need to follow two simple rules of thumb to make recursive functions work. These rules suggest the structure of a recursive function -- it must behave appropriately according to its current inputs:

1. One case must not make a recursive call.
2. Other cases must reduce the amount of work to be done in a recursive call.

(defun factorial (n)
  (cond ((zerop n) 1)
        (t (* n (factorial (1- n))))))

Let's work through another simple recursive definition. The length of an empty list is zero. The length of a non-empty list is one plus the length of the list reduced by one element. These two statements state exactly what is required by our rules of thumb, above. The first statement gives the answer for a list of known length -- the trivial case of an empty list. The second statement gives the answer for a list of unknown length in terms of the answer for a list of reduced length. Here's how it translates into code:

? (defun my-length (list)
    (cond ((null list) 0)
          (t (1+ (my-length (rest list))))))
MY-LENGTH

? (my-length '(a b c d))
4

Note the similarities between FACTORIAL and MY-LENGTH. The base case is always the first in the COND because it must be tested before the recursive case -- otherwise, the recursive function calls would never end.

If you want to visualize how recursive calls work, you can use you Lisp system's TRACE macro:

? (trace my-length)
NIL

? (my-length '(a b c d))
; Calling (MY-LENGTH (A B C D)) 
;  Calling (MY-LENGTH (B C D)) 
;   Calling (MY-LENGTH (C D)) 
;    Calling (MY-LENGTH (D)) 
;     Calling (MY-LENGTH NIL) 
;     MY-LENGTH returned 0
;    MY-LENGTH returned 1
;   MY-LENGTH returned 2
;  MY-LENGTH returned 3
; MY-LENGTH returned 4
4

NOTE: Your Lisp compiler may internally optimize the recursive calls to MY-LENGTH so you don't see them using TRACE. If this happens, you may be able to disable the optimization by evaluating the form (DECLAIM (OPTIMIZE (SPEED 0) (DEBUG 3))), then re-evaluating the (DEFUN MY-LIST ...) form.

Tail recursion

; Normal recursive call 

(defun factorial (n)
  (cond ((zerop n) 1)
        (t (*      ; * is the last function called 
            n
            (factorial (- n 1))))))

; Tail-recursive call 

(defun factorial-tr (n)
  (factorial-tr-helper n 1))

(defun factorial-tr-helper (n product)
  (cond ((zerop n) product)
        (t 
         ; factorial-tr-helper is the last function called 
         (factorial-tr-helper (- n 1) (* product n)))))

Because FACTORIAL-TR-HELPER is the last function executed in the recursive call, this is a tail-recursive call. Compare this to the recursive call in the FACTORIAL function, where the result is used by * to produce the function's value. A recursive call is tail-recursive only if it is the very last function executed in the recursive invocation.

With all that explanation out of the way, you're probably wondering "What good is tail-recursion? For the factorial calculation, it only seemed to complicate the code." The answer is in two parts: what Lisp can do for you, and what Lisp can do to you in the presence of tail-recursion.

Some Lisp compilers can optimize tail-recursive calls. To understand the benefits of such an optimization, let's first look at what a compiler must do for a normal function call: it must generate code to evaluate the arguments and push them on a stack (where they can be found by the called function), save the address in the code to which control will return after the recursive call, and finally call the function. One implication of this code sequence is that a function which makes a lot of recursive calls (as FACTORIAL will do for large value of N) will use a lot of stack space -- normally a limited resource.

A compiler that optimizes tail-recursive calls will generate code to perform the following operations for a tail-recursive call: evaluate the arguments and replace the old argument values with those just calculated, and then jump to the beginning of the function. Note that this code does not use any additional stack space, and it invokes the function with a jump instead of a call instruction -- this is a less expensive operation on all computers.

So, that's the answer to the first question, "What can Lisp do for me if I write a tail-recursive function call?" You get more efficient code -- if the compiler performs that optimization; it is not required to do so, but the better ones do.

Tail recursion optimization sounds like a good thing. It must be -- it produces faster code -- but it it may confuse you during debugging. The debugger normally displays each function call by looking at the stack frame created at entry to the function. So if you happen to break in the middle of a recursive function, you'd expect to see a stack frame for each recursive call:

 
? (defun broken-factorial (n)
    (cond ((= n 0) 1)
          ((= n 1) (break))
          (t (* n (broken-factorial (- n 1))))))
BROKEN-FACTORIAL

? (broken-factorial 6)
; Break: While executing: BROKEN-FACTORIAL

> (backtrace)
1: (BROKEN-FACTORIAL 1)
2: (BROKEN-FACTORIAL 2)
3: (BROKEN-FACTORIAL 3)
4: (BROKEN-FACTORIAL 4)
5: (BROKEN-FACTORIAL 5)
6: (BROKEN-FACTORIAL 6)
7: ... more stack frames, unrelated to BROKEN-FACTORIAL ... 
> (abort)
; Return to top level

? (defun broken-tr-factorial (n)
    (broken-tr-factorial-1 n 1))
BROKEN-TR-FACTORIAL

? (defun broken-tr-factorial-1 (n v)
    (cond ((= n 0) v)
          ((= n 1) (break))
          (t (broken-tr-factorial-1 (- n 1) (* n v)))))
BROKEN-TR-FACTORIAL

? (broken-tr-factorial 6)
; Break: While executing: BROKEN-TR-FACTORIAL-1

> (backtrace)
1: (broken-tr-factorial-1 1)
2: ... more stack frames, unrelated to BROKEN-TR-FACTORIAL ... 

The compiler also noticed that BROKEN-TR-FACTORIAL calls BROKEN-TR-FACTORIAL-1 and immediately returns its value. This is just another tail-recursive call. The compiler arranged to build the stack frame using the value provided for the call to BROKEN-TR-FACTORIAL and the constant 1; there was no need to generate a stack frame for BROKEN-TR-FACTORIAL.

I mention all of this because you may think that your compiler is broken the first time you encounter a backtrace with "missing" frames. Compilers that do tail recursion usually give you a way to disable that optimization; consult the manual for details. You're probably better off, however, learning to recognize tail recursion, and how to read backtraces in the presence of this optimization. Some code which relies on tail recursion could break (by overflowing the stack) if you disable the optimization.

Exercises in naming

Most Lisp programmers follow a few naming conventions to identify the names that certain roles. Global variables are almost always written with a leading and trailing *, for example:

*next-id*
*home-directory*
*software-version*

+initial-allocation-count+
+maximum-iteration-limit+

pi
most-positive-fixnum
least-negative-short-float

%open-file-id
%structure-slot-names
$reserve_heap
_call-event-handler
@frame-marker

If you don't define a constant using a DEFCONSTANT form, the compiler can not guarantee that its value will remain constant. Even worse is the requirement that a constant name be neither assigned (through a SETQ form, for example) nor bound (in a LET form or as the name of a function parameter, for example). If you don't define your constants using DEFCONSTANT, the compiler has no way to enforce these requirements.

Lexical binding, and multiple name spaces

(defun funny (funny)
  "funny..."
  (if (zerop funny)
    :funny
    (list
     (cons funny 
           (let ((funny funny))
             (setq funny (1- funny))
             (funny funny))) 
     funny)))

1. function name
2. function argument
3. a word in the documentation string
4. a constant in the keyword package
5. a new lexical variable

Is this hard to follow? Yes. As a rule of thumb, you should be shot if you write code that looks like this. I, on the other hand, get to do this because it's instructive -- the lesson here is that there are a number of different namespaces in Lisp.

And what happens when you invoke this bizarre function? This:

? (funny 3)
((3 (2 (1 . :FUNNY) 1) 2) 3)

? (funny 0)
:funny

? (defun foo () 1)
FOO
    
? (defun baz ()
    (flet ((foo () 2)
           (bar () (foo)))
      (values (foo) (bar))))
BAZ
    
? (baz)
2
1

? (defun raz ()
    (labels ((foo () 2)
             (bar () (foo)))
      (values (foo) (bar))))
RAZ

? (raz)
2
2

1. define function FOO to return 1
2. define function BAZ, which
   1. defines function FOO locally to return 2
   2. defines function BAR locally to call FOO
   3. calls FOO and BAR, and returns their values
3. call BAZ, which returns the values 2 and 1
4. define function RAZ, which
   1. defines function FOO locally to return 2
   2. defines function BAR locally to call FOO
   3. calls FOO and BAR, and returns their values
5. call RAZ, which returns the values 2 and 2

BAZ defines its local functions inside an FLET form, which does not allow reference to the functions it defines. So the FOO called by BAR inside BAZ is actually the global FOO, which returns 1. The FOO defined inside the FLET form is never referenced by BAZ.

RAZ defines its local functions inside a LABELS form, within which functions defined may refer to themselves or each other. Thus, the FOO called by BAR inside RAZ is the one defined inside the LABELS form, which returns 2. The globally defined FOO is shadowed by the FOO named in the LABELS form.

In both cases, FOO is lexically apparent at two places: globally, and within the local defining form (FLET or LABELS). For something to be lexically apparent, or lexically scoped, means that its definition can be determined by reading the program.

In BAZ, I know that the local definition of FOO is not visible within BAR, so the global definition must be referenced. (If there was an enclosing form within BAZ which defined a local function FOO, that would be referenced rather than the global definition -- again, because it's lexically apparent to the caller.)

In RAZ, I know that the local definition of FOO is visible to BAR, so this is used instead of the global definition. Even if there was an enclosing form that defined another FOO locally within RAZ, it would -- from the viewpoint of BAR -- be shadowed by the FOO defined in the LABELS form.

Reading, writing, and arithmetic

Most elementary programming texts include a simple program to demonstrate the "input, process, output" approach. Our example in Lisp reads a series of numbers, adds them, and prints the sum when we enter a special token instead of a number:

(defun simple-adding-machine-1 ()
  (let ((sum 0)
        next)
    (loop
      (setq next (read))
      (cond ((numberp next)
             (incf sum next))
            ((eq '= next)
             (print sum)
             (return))
            (t
             (format t "~&~A ignored!~%" next))))
    (values)))

(SIMPLE-ADDING-MACHINE-1)
3
5
FOO
FOO ignored!
11
=

19

What if we wanted to read inputs from a file, and write to another file? One way is to bind the standard input and output streams to files, and continue to use SIMPLE-ADDING-MACHINE-1:

(let ((*standard-input* (open "infile.dat" :direction :input))
      (*standard-output* (open "outfile.dat" :direction :output)))
  (declare (special *standard-input* *standard-output*))
  (simple-adding-machine-1)
  (close *standard-input*)
  (close *standard-output))

A better way to write this kind of code uses WITH-OPEN-FILE:

(with-open-file (in-stream "infile.dat" :direction :input)
  (with-open-file (out-stream "outfile.dat" :direction :output)
    (let ((*standard-input* in-stream)
          (*standard-output* out-stream))
      (declare (special *standard-input* *standard-output*))
      (simple-adding-machine-1))))

The technique of rebinding the standard input and output streams can be very handy if you have to redirect input and output for a program you didn't write, don't want to rewrite, or can't get the source code to. If you're writing a program from scratch, you might want to plan for it to be used either with the standard streams or streams (perhaps attached to files) provided by the caller:

(defun simple-adding-machine-2 (&optional (in-stream *standard-input*)
                                          (out-stream *standard-output*))
  (let ((sum 0)
        next)
    (loop
      (setq next (read in-stream))
      (cond ((numberp next)
             (incf sum next))
            ((eq '= next)
             (print sum out-stream)
             (return))
            (t
             (format out-stream "~&~A ignored!~%" next))))
    (values)))

(with-open-file (in-stream "infile.dat" :direction :input)
  (with-open-file (out-stream "outfile.dat" :direction :output)
    (simple-adding-machine-1 in-stream out-stream)))

To close out this section, let's take a brief look at arithmetic. Lisp has an extensive repertoire of mathematical functions, consult a reference book for details. Chapter 3, Lesson 10 covered numbers very briefly. Now, we're going to look at how and when numbers get converted automatically from one type to another.

The simplest rule is that of floating point contagion, an ominous-sounding term which means, "If you use a floating point number in a calculation, the result will be a floating point number."

The next rule involves floating point components of complex numbers. A complex number has a real part and an imaginary part, read (and printed) by Lisp as #C(real-part imaginary-part), where real-part and imaginary-part are any kind of Lisp number except for another complex number. If either part is a floating point number, then Lisp converts both parts to floating point numbers.

If you reduce the imaginary part of a complex number to zero, you get the non-complex value of the real part.

Ratios are read and printed as numerator/denominator, where numerator and denominator are always integers. The advantage of a ratio is that it is exact -- (/ 1.0 3) is a floating point number which is very close to (but not exactly) one-third, but 1/3 (or (/ 1 3)) is exactly one-third.

A ratio whose numerator is exactly divisible by its denominator will be reduced to an integer -- again, this is an exact number.

And finally, an integer is just an integer. If an integer gets too large to fit the machine's representation, Lisp converts it to a bignum -- the number of digits is limited only by the computer's memory.

Just to make sure you understand all of this, try adding some numbers of different types to see whether you can invoke all of the conversions described above.

Other data types

Here's the code:

(defvar *checks* (make-array 100 :adjustable t :fill-pointer 0)
  "A vector of checks.")

(defconstant +first-check-number+ 100 
  "The number of the first check.")

(defvar *next-check-number* +first-check-number+ 
  "The number of the next check.")

(defvar *payees* (make-hash-table :test #'equal) 
  "Payees with checks paid to each.")

(defstruct check
  number date amount payee memo)

(defun current-date-string ()
  "Returns current date as a string."
  (multiple-value-bind (sec min hr day mon yr dow dst-p tz)
                       (get-decoded-time)
    (declare (ignore sec min hr dow dst-p tz))
    (format nil "~A-~A-~A" yr mon day)))

(defun write-check (amount payee memo)
  "Writes the next check in sequence."
  (let ((new-check (make-check 
                    :number *next-check-number*
                    :date (current-date-string)
                    :amount amount
                    :payee payee
                    :memo memo)))
    (incf *next-check-number*)
    (vector-push-extend new-check *checks*)
    (push new-check (gethash payee *payees*))
    new-check))

(defun get-check (number)
  "Returns a check given its number, or NIL if no such check."
  (when (and (<= +first-check-number+ number) (< number *next-check-number*))
    (aref *checks* (- number +first-check-number+))))

(defun void-check (number)
  "Voids a check and returns T.  Returns NIL if no such check."
  (let ((check (get-check number)))
    (when check
      (setf (gethash (check-payee check) *payees*)
            (delete check (gethash (check-payee check) *payees*)))
      (setf (aref *checks* (- number +first-check-number+)) nil)
      t)))

(defun list-checks (payee)
  "Lists all of the checks written to payee."
  (gethash payee *payees*))

(defun list-all-checks ()
  "Lists all checks written."
  (coerce *checks* 'list))

(defun sum-checks ()
  (let ((sum 0))
    (map nil #'(lambda (check)
                 (when check
                   (incf sum (check-amount check))))
         *checks*)
    sum))

(defun list-payees ()
  "Lists all payees."
  (let ((payees ()))
    (maphash #'(lambda (key value)
                 (declare (ignore value))
                 (push key payees))
             *payees*)
    payees))

? (write-check 100.00 "Acme" "T-1000 rocket booster")
#S(CHECK :NUMBER 100 :DATE "1996-11-3" :AMOUNT 100.0 :PAYEE "Acme" :MEMO "T-1000 rocket booster")

? (write-check 50.00 "Acme" "1 gross bungee cords")
#S(CHECK :NUMBER 101 :DATE "1996-11-3" :AMOUNT 50.0 :PAYEE "Acme" :MEMO "1 gross bungee cords")

? (write-check 300.72 "WB Infirmary" "body cast")
#S(CHECK :NUMBER 102 :DATE "1996-11-3" :AMOUNT 300.72 :PAYEE "WB Infirmary" :MEMO "body cast")

? (list-checks "Acme")
(#S(CHECK :NUMBER 101 :DATE "1996-11-3" :AMOUNT 50.0 :PAYEE "Acme" :MEMO "1 gross bungee cords")
 #S(CHECK :NUMBER 100 :DATE "1996-11-3" :AMOUNT 100.0 :PAYEE "Acme" :MEMO "T-1000 rocket booster"))
T

? (get-check 101)
#S(CHECK :NUMBER 101 :DATE "1996-11-3" :AMOUNT 50.0 :PAYEE "Acme" :MEMO "1 gross bungee cords")

? (sum-checks)
450.72

? (list-all-checks)
(#S(CHECK :NUMBER 100 :DATE "1996-11-3" :AMOUNT 100.0 :PAYEE "Acme" :MEMO "T-1000 rocket booster")
 #S(CHECK :NUMBER 101 :DATE "1996-11-3" :AMOUNT 50.0 :PAYEE "Acme" :MEMO "1 gross bungee cords")
 #S(CHECK :NUMBER 102 :DATE "1996-11-3" :AMOUNT 300.72 :PAYEE "WB Infirmary" :MEMO "body cast"))

? (list-payees)
("WB Infirmary" "Acme")

? (void-check 101)
T

? (list-checks "Acme")
(#S(CHECK :NUMBER 100 :DATE "1996-11-3" :AMOUNT 100.0 :PAYEE "Acme" :MEMO "T-1000 rocket booster"))
T

? (list-all-checks)
(#S(CHECK :NUMBER 100 :DATE "1996-11-3" :AMOUNT 100.0 :PAYEE "Acme" :MEMO "T-1000 rocket booster")
 NIL
 #S(CHECK :NUMBER 102 :DATE "1996-11-3" :AMOUNT 300.72 :PAYEE "WB Infirmary" :MEMO "body cast"))

? (sum-checks)
400.72

Simple macros

But with a little more work we can write a macro that will write our save and restore functions. Then we can use this macro not only for our check writing program, but also for any program which keeps its state in global variables.

First take a look at the finished macro, then we'll dissect it:

(defmacro def-i/o (writer-name reader-name (&rest vars))
  (let ((file-name (gensym))
        (var (gensym))
        (stream (gensym)))
    `(progn
       (defun ,writer-name (,file-name)
         (with-open-file (,stream ,file-name
                                  :direction :output :if-exists :supersede)
           (dolist (,var (list ,@vars))
             (declare (special ,@vars))
             (print ,var ,stream))))
       (defun ,reader-name (,file-name)
         (with-open-file (,stream ,file-name
                                  :direction :input :if-does-not-exist :error)
           (dolist (,var ',vars)
             (set ,var (read ,stream)))))
       t)))

The expanded macro is generated by the ` form. The form is returned as the macro's expansion, then evaluated. Substitutions take place for symbols following , or ,@. Everything else appears literally in the expanded macro.

The expansion of DEF-I/O is a PROGN form containing two DEFUN forms. We wrap the DEFUNs like this because a macro's expansion can only be a single form, and we need to have this macro define two functions.

The macro defines a writer function which loops over the list of the VARS specified in the macro call, printing each in turn to a named output file. The reader function loops over the names of the VARS, reading values from an input file and assigning the values to the named variables. Note that SET evaluates its first argument; this lets us use a variable to contain the name of the variable to which we want to assign a value.

Here's how the macro expands to create load and save functions for our check writer program:

? (pprint (macroexpand '(def-i/o save-checks load-checks (*checks* *next-check-number* *payees*))))
(PROGN (DEFUN SAVE-CHECKS (#:G2655)
            (WITH-OPEN-FILE (#:G2657 #:G2655 :DIRECTION :OUTPUT :IF-EXISTS :SUPERSEDE)
              (DOLIST (#:G2656 (LIST *CHECKS* *NEXT-CHECK-NUMBER* *PAYEES*))
                (DECLARE (SPECIAL *CHECKS* *NEXT-CHECK-NUMBER* *PAYEES*))
                (PRINT #:G2656 #:G2657))))
          (DEFUN LOAD-CHECKS (#:G2655)
            (WITH-OPEN-FILE (#:G2657 #:G2655 :DIRECTION :INPUT :IF-DOES-NOT-EXIST
                             :ERROR)
              (DOLIST (#:G2656 '(*CHECKS* *NEXT-CHECK-NUMBER* *PAYEES*))
                (SET #:G2656 (READ #:G2657))))))

? (def-i/o save-checks load-checks (*checks* *next-check-number* *payees*))
T

? (save-checks "checks.dat")
NIL

? (makunbound '*checks*)
*CHECKS*

? (makunbound '*next-check-number*)
*NEXT-CHECK-NUMBER*

? (makunbound '*payees*)
*PAYEES*

? *PAYEES*
Error: Unbound variable.

? (load-checks "checks.dat")
NIL

? *PAYEES*
("WB Infirmary" "Acme")

Reader macros

Here's the code:

(set-macro-character #\$
                     #'(lambda (stream char)
                         (declare (ignore char))
                         (round (* 100 (read stream)))))

The rounding step ensures that the amount is a whole number. Binary floating point numbers can not precisely represent all decimal fractions. For example, (* 100 9.95) yields 994.9999999999999 and (* 100 1.10) yields 110.00000000000001 on my Lisp system.

? $9.95
995

? $-7.10
-710

(defstruct (check
            (:print-function
             (lambda (check stream depth)
               (declare (ignore depth))
               (format stream "#S(CHECK NUMBER ~S DATE ~S AMOUNT $~,2,-2F PAYEE ~S MEMO ~S)"
                       (check-number check)
                       (check-date check)
                       (check-amount check)
                       (check-payee check)
                       (check-memo check)))))
  number date amount payee memo)

? (make-check :amount $9.95)
#S(CHECK NUMBER NIL DATE NIL AMOUNT $9.95 PAYEE NIL MEMO NIL)