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.
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
LOOPin 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
EVALfor 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."
"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
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:
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))))))
'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.
FACTORIALfunction (above) and a function or two in Chapter 3, Lesson 7. To review, a function is defined as follows:
(defun function-name (argument-names ...) function-body )The
...)is called a lambda list. Names in this list are bound to values when the function is called. The body of the function may refer to these names; identical names appearing elsewhere in your program (that is, outside the function body) are irrelevant to the function. Also, if your function changes the binding of an argument inside the function, the caller does not receive the changed value. The proper way to return values from a Lisp function is to return them as the value of the function.
? (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 -5The
QUADRATIC-ROOTSfunction shows how to use a documentation string. The first form in the function body is a string. This does not affect the function result, but it is recorded by the Lisp system for later reference:
? (documentation 'quadratic-roots 'function) "Returns the roots of a quadratic equation aX^2 + bX + c = 0"This function also shows how we can return two values from a function. You recognize the formula for the roots of a quadratic equation:
/-------- + / 2 - b - \/ b - 4ac ---------------------- 2aThis tells you that the equation has two solutions (which may be coincident in some cases). In Lisp it's a simple matter to return both values at once using the form
(VALUES value-1 value-2).
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)Suppose that you wanted
QUADRATIC-ROOTSto only return one value if the roots are coincident. Thinking that maybe you can return something special as the second value of the
VALUEform, you try
? (values 2 nil) 2 NILBut that doesn't work, because
NILis a value like any other in Lisp, and does not get special treatment like a nil pointer would, for example, in another language.
So you think about only having one value in the
? (values 3) 3Sure enough, that works. So why not
(VALUES value-1 some-form-that-returns-nothing)? Like this:
? (values) ? (values 4 (values)) 4 NILUnfortunately, this doesn't do what you expect; the outer
VALUESform expects a value from its second argument,
(VALUES), and substitutes
NILfor the missing value. This is one of the important rules of multiple values. The other rule is that forms which receive multiple values (see Chapter 3, Lesson 9) substitute
NILfor a missing value.
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
ZEROPis a predicate (hence the
Psuffix) that is true when its numeric argument is zero. Writing
(ZEROP n)is the same as writing
(= n 0).
QUADRATIC-ROOTS-2has a two-line documentation string. The newline is part of the string:
? (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."Also note the use of comments to describe the two return choices. In Lisp, a comment begins with a semicolon and continues until the end of the line. By convention, comments on a line of their own within a function body are indented to the same level as the rest of the code and prefixed by two semicolons. A comment on the same line as code only has one semicolon (again, by convention).
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)The optional parameters default to NIL when the call does not supply a value. Peek ahead to Chapter 21 to see how to change the default value of an optional parameter.
If you supply fewer than the number of required parameters (to the
&OPTIONAL in the example above), or more than
the total number of required plus optional parameters, you'll get an
? (silly-list-1 'foo) Error: Not enough arguments. ? (silly-list-1 'foo 'bar 'baz 'rux 'qup) Error: Too many arguments.If you want to have an indefinite number of parameters, you can name one parameter to receive a list of all the "extras" using the
&RESTsymbol in the lambda list, like this:
? (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))The
&RESTparameter must follow all of the required parameters. You can combine
&OPTIONALparameters, observing the following order:
? (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))
SETQto define global variables. You can do this using a top-level form, as in Lesson 3, or from within a function, such as this:
? (defun set-foo-globally (x) (setq foo x)) SET-FOO-GLOBALLY ? foo Error: unbound variable FOO ? (set-foo-globally 3) 3 ? foo 3Depending upon your Lisp system, you may have seen a warning message when you defined
? (defun set-foo-globally (x) (setq foo x)) Warning: undeclared free variable FOO, in SET-FOO-GLOBALLY. SET-FOO-GLOBALLYThis is not an error -- the function does what we want. But
FOOis said to be free because the function does not create a binding for
FOO. Variable bindings are created by lambda lists (the function's argument list) and by
LETforms (see Lesson 6), among others.
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-YEARHere, I misspelled the second instance of my global variable
*OLYMPIC-YEAR*, and the compiler warned me. Notice that I didn't get a warning for the correctly spelled
*OLYMPIC-YEAR*because I had defined it globally in a top-level
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
DEFVARsets a global value only the first time -- in other words, the variable must not have a value in order for
DEFVARto have an effect. This is useful for a variable that needs to have an initial value, but shouldn't be reset if you re-evaluate the
DEFVARform (as you might if you reload the file containing the
DEFVARin addition to other code).
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
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."You can also add a documentation string to a
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
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
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
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:
FACTORIALfunction that we've already used in several examples, and see how it follows these rules:
(defun factorial (n) (cond ((zerop n) 1) (t (* n (factorial (1- n))))))This function has two cases, corresponding to the two branches of the
COND. The first case says that the factorial of zero is just one -- no recursive call is needed. The second case says that the factorial of some number is the number multiplied by the factorial of one less than the number -- this is a recursive call which reduces the amount of work remaining because it brings the number closer to the terminating condition of the first
CONDclause. (For clarity, I've assumed that the number initially given to
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
NULLis true for an empty list, so the first
CONDclause returns zero for the empty list. The second
CONDclause gets evaluated (if the first clause if skipped) because its condition is
T; it adds one to the result of the recursive call on a list which is one element shorter (a list consists of its
FIRSTelement and the
RESTof the list.)
Note the similarities between
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
If you want to visualize how recursive calls work, you can use you
? (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 4Here, you can clearly see the recursive calls upon lists of decreasing length, the terminating call with the empty list (
NIL), and the returns each adding one to the length of a shorter list.
NOTE: Your Lisp compiler may internally optimize the recursive calls to
MY-LENGTHso 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.
; 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)))))
FACTORIAL-TR-HELPER, passing the original argument,
N, plus an additional argument used as the initial value of an accumulator for the product which will become the value of the factorial calculation.
FACTORIAL-TR-HELPERcalls itself recursively, decrementing
Nin the process (this moves the calculation closer to its terminating condition,
(ZEROP N)) and at the same time multiplying the product by the current value of
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
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
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 ...So what happened to all the recursive calls in
BROKEN-TR-FACTORIAL-1? For that matter, what happened to the call to
BROKEN-TR-FACTORIAL? The compiler did tail recursion elimination in
BROKEN-TR-FACTORIAL-1, replacing function calls with jumps. The function only generated one stack frame, then the tail-recursive calls replaced the values in that frame for subsequent calls.
The compiler also noticed that
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
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.
#. Furthermore, the name can't be a number in the current number base, as set by
*READ-BASE*. Thus, FACE is a name when
*READ-BASE*is 10, but a number when
*READ-BASE*is 16 (or higher).
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*Other conventions vary somewhat among Lisp programmers. It is fairly common to see the name of a constant written with a leading and trailing
+, such as:
+initial-allocation-count+ +maximum-iteration-limit+However, Lisp itself does not follow this convention for constants defined by the language:
pi most-positive-fixnum least-negative-short-floatLisp programmers tend to set aside certain characters as prefixes for names of functions which use implementation-dependent features of the Lisp implementation, or which which are otherwise considered "dangerous" because they violate abstraction. The
%character is most often seen in this role, but others are used -- you should be aware that any name which starts with a non-alphabetic character may have some special significance to the programmer who wrote the code:
%open-file-id %structure-slot-names $reserve_heap _call-event-handler @frame-markerDon't forget to use the proper forms (described earlier in this chapter ) to declare global variables and constants. Many Lisp compilers will let you get away with using a SETQ form to define global variables. Although this is convenient for debugging purposes, you should not rely on this behavior in your final program, as it is not guaranteed to work in all implementations.
If you don't define a constant using a
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
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
(defun funny (funny) "funny..." (if (zerop funny) :funny (list (cons funny (let ((funny funny)) (setq funny (1- funny)) (funny funny))) funny)))Here are the five roles played by this one name:
FUNNY, there are different values according to its use and position in the code. First, there is its value as a function object -- this is created by the
DEFUNform and called recursively inside the
LETform. Next, the value of the actual parameter is passed in a call to the function and bound to this name. Then, there's the constant value of the keyword, appearing as the consequent return value of the
IFform. And finally, inside the
LETform, a new binding is created (by the
LETform) and its value changed (by the
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) :funnyNow consider the following Lisp session:
? (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 2This is pretty subtle, but it's worth understanding because this is fairly common practice. Here's what happened:
FOOto return 1
FOOlocally to return 2
BARlocally to call
BAR, and returns their values
BAZ, which returns the values 2 and 1
FOOlocally to return 2
BARlocally to call
BAR, and returns their values
RAZ, which returns the values 2 and 2
RAZostensibly do the same thing, they return different values.
BAZ defines its local functions inside an
FLET form, which does not allow reference to the
functions it defines. So the
FOO called by
BAZ is actually the global
FOO, which returns 1. The
FLET form is never referenced by
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
RAZ is the one defined inside
LABELS form, which returns 2. The globally defined
FOO is shadowed by the
FOO named in the
In both cases,
FOO is lexically apparent at two places:
globally, and within the local defining form (
LABELS). For something to be lexically apparent, or
lexically scoped, means that its definition can be determined by
reading the program.
BAZ, I know that the local
FOO is not visible within
BAR, so the global definition must be referenced. (If
there was an enclosing form within
BAZ which defined a
FOO, that would be referenced rather than
the global definition -- again, because it's lexically apparent to the
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
-- be shadowed by the
FOO defined in the
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)))Our
SIMPLE-ADDING-MACHINE-1works like this:
(SIMPLE-ADDING-MACHINE-1) 3 5 FOO FOO ignored! 11 = 19
SIMPLE-ADDING-MACHINE-1gets its input via the keyboard, and writes output to the screen. This happens because
Tas the second argument to
FORMATis the same as specifying the standard output stream -- the screen.
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
(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))This is almost, but not quite, satisfactory. We bind the standard input and output streams to newly opened files, process the data, and close the files. We use
LETto temporarily bind the standard streams to files; upon leaving the
*STANDARD-OUTPUT*regain their original values. The problem lurking in this piece of code is that an abnormal exit -- an error or a deliberate interrupt -- can cause one or both of the
CLOSEcalls to be skipped.
A better way to write this kind of code uses
(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))))This does exactly the same thing, except that a file opened by
WITH-OPEN-FILEis guaranteed to be closed upon exiting the form, whether the exit is normal or not. We'll take a look at how this is possible in Chapter 9.
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)))If you want to use
SIMPLE-ADDING-MACHINE-2with the keyboard and screen, call it without any arguments. To call it with file streams, do this:
(with-open-file (in-stream "infile.dat" :direction :input) (with-open-file (out-stream "outfile.dat" :direction :output) (simple-adding-machine-2 in-stream out-stream)))We don't have to rebind the standard input and output streams as we did to redirect I/O for
SIMPLE-ADDING-MACHINE-1. This leaves the standard streams free other purposes -- such as reporting progress or interacting with the user.
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
), 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 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)) 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.
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))And here's an example of how it works:
? (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.72In about a page of code, we've built a simple check-writing application with efficient data structures to store checks and payees. We also have basic I/O facilities without any additional effort on our part. And thanks to garbage collection, we don't have to worry at all about storage deallocation or memory leaks.
*PAYEES*, all we really have to do is to use
READto reload them at a later time.
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 initial
LETform defines symbols that will appear in the expanded macro. Each symbol is created by
(GENSYM)so that no other symbol can possibly be the same. This avoids a problem which could arise if we wrote a macro using a particular symbol as a variable, then called the macro with an argument having the same name as one of the symbols in the expansion.
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
Everything else appears literally in the expanded macro.
The expansion of
DEF-I/O is a
DEFUN forms. We wrap the
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
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))))))And here's how we would use the macro, and the functions it defines, to save and restore the state information for our program:
? (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")
$10.95into the corresponding number of pennies.
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,This says to set
(* 100 9.95)yields
(* 100 1.10)yields
110.00000000000001on my Lisp system.
$to be a macro character which, when encountered by the reader, calls
READto get a number and return the nearest whole number after multiplying by 100. It's used like this:
? $9.95 995 ? $-7.10 -710Now that you can enter dollar amounts directly, you may want to modify the check-writing application to print amounts in whole cents as dollars and cents. To do this, you would redefine the
CHECKstructure with a custom print function, as follows:
(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)Then, the
$reader macro and the
CHECKprint function for its
AMOUNTslot complement each other perfectly:
? (make-check :amount $9.95) #S(CHECK NUMBER NIL DATE NIL AMOUNT $9.95 PAYEE NIL MEMO NIL)