COMMON LISP:
A Gentle Introduction
to Symbolic Computation

---

COMMON LISP:
A Gentle Introduction
to Symbolic Computation
David S. Touretzky
Carnegie Mellon University
The Benjamin/Cummings Publishing Company,Inc.
Redwood City, California • Fort Collins, Colorado • Menlo Park, California
Reading, Massachusetts• New York • Don Mill, Ontario • Workingham, U.K.
Amsterdam • Bonn • Sydney • Singapore • Tokyo • Madrid • San Juan

---

Sponsoring Editor: Alan Apt
Developmental Editor: Mark McCormick
Production Coordinator: John Walker
Copy Editor: Steven Sorenson
Text and Cover Designer: Michael Rogondino
Cover image selected by David S. Touretzky
Cover: La Grande Vitesse, sculpture by Alexander Calder
Copyright (c) 1990 by Symbolic Technology, Ltd.
Published by The Benjamin/Cummings Publishing Company, Inc.
This document may be redistributed in hardcopy form only, and only for
educational purposes at no charge to the recipient. Redistribution in
electronic form, such as on a web page or CD-ROM disk, is prohibited.
All other rights are reserved. Any other use of this material is prohibited
without the written permission of the copyright holder.
The programs presented in this book have been included for their
instructional value. They have been tested with care but are not
guaranteed for any particular purpose. The publisher does not offer any
warranties or representations, nor does it accept any liabilities with
respect to the programs.
Library of Congress Cataloging-in-Publication Data
Touretzky, David S.
Common LISP : a gentle introduction to symbolic computation /
David S. Touretzky
p. cm.
Includes index.
ISBN 0-8053-0492-4
1. COMMON LISP (Computer program language) I. Title.
QA76.73.C28T68 1989
005.13’3–dc20 89-15180
CIP
ISBN 0-8053-0492-4
ABCDEFGHIJK - DO - 8932109
The Benjamin/Cummings Publishing Company, Inc.
390 Bridge Parkway
Redwood City, California 94065

---

To Phil and Anne

---

Preface
This book is about learning to program in Lisp. Although widely known as
the principal language of artificial intelligence research—one of the most
advanced areas of computer science—Lisp is an excellent language for
beginners. It is increasingly the language of choice in introductory
programming courses due to its friendly, interactive environment, rich data
structures, and powerful software tools that even a novice can master in short
order.
When I wrote the book I had three types of reader in mind. I would like to
address each in turn.
• Students taking their first programming course. The student could
be from any discipline, from computer science to the humanities.
For you, let me stress the word gentle in the title. I assume no
prior mathematical background beyond arithmetic. Even if you
don’t like math, you may find you enjoy computer programming.
I’ve avoided technical jargon, and there are lots of examples. Also
you will find plenty of exercises interspersed with the text, and the
answers to all of them are included in Appendix C.
• Psychologists, linguists, computer scientists, and other persons
interested in Artificial Intelligence. As you begin your inquiry into
AI, you will see that almost all research in this field is carried out
in Lisp. Most Lisp texts are written exclusively for computer
science majors, but I have gone to great effort to make this book
accessible to everyone. It can be your doorway to the technical
literature of AI, as well as a quick introduction to its central tool.
• Computer hobbyists. Prior to about 1984, the Lisps available on
personal computers weren’t very good due to the small memories
of the early machines. Today’s personal computers often come
with several megabytes of RAM and a hard disk as standard
vii

---

viii
Common Lisp: A Gentle Introduction to Symbolic Computation
equipment. They run full implementations of the Common Lisp
standard, and provide the same high-quality tools as the Lisps in
university and industrial research labs. The ‘‘Lisp Toolkit’’
sections of this book will introduce you to the advanced features of
the Common Lisp programming environment that have made the
language such a productive tool for rapid prototyping and AI
programming.
This current volume of the ‘‘gentle introduction’’ uses Common Lisp
throughout. Lisp has been changing continuously since its invention 30 years
ago. In the past, not only were the Lisp dialects on different machines
incompatible, but programs written in one dialect would often no longer run in
that same dialect a few years later, because the language had evolved out from
under them. Rapid, unconstrained evolution was beneficial in the early days,
but demand for a standard eventually grew, so Common Lisp was created. At
present, Common Lisp is the de facto standard supported by all major
computer manufacturers. It is currently undergoing refinement into an official
standard. But Lisp will continue to evolve nonetheless, and the standard will
be updated periodically to reflect new contributions people have made to the
language. Perhaps one of those contributors will be you.
DAVID S. TOURETZKY
PITTSBURGH, PENNSYLVANIA

---

Note to Instructors
Much has been learned in the last few years about how to teach Lisp
effectively to beginners: where they stumble and what we can do about it. In
addition, the switch to Common Lisp has necessitated changes in the way
certain topics are taught, especially variables, scoping, and assignment. This
version of the ‘‘gentle introduction’’ has been completely revised for Common
Lisp, and includes several new teaching tools that I believe you will find
invaluable in the classroom. Let me share with you some of the thinking
behind this book’s novel approach to Lisp.
GRAPHICAL NOTATION
The first two chapters use a graphical box-and-arrow notation for describing
primitive functions and function composition. This notation allows students to
get comfortable with the basic idea of computation and the three fundamental
data structures—numbers, symbols, and lists—before grappling with side
issues such as the syntax of a function call or when to use quotes. Although
sophisticated Lispers profit from the realization that programs are data, to the
beginner this is a major source of confusion. The box-and-arrow notation
makes programs and data visually distinct, and thereby eliminates most syntax
errors. Another advantage of this notation is its lack of explicit variables; the
inputs to a function are simply arrows that enter the function definition from
outside. Since there is no computer implementation of function box notation,
the first two chapters are designed to be covered rapidly using just pencil and
paper. This also shelters the student temporarily from another source of
frustration—learning the mechanics of using an actual machine, editing
expressions, and coping with the debugger.
Readers who are familiar with other programming languages can flip
through Chapter 1 in a minute or so, read the summary at the end, and then
skim Chapter 2 to pick up the basic list manipulation primitives.
ix

---

x
Common Lisp: A Gentle Introduction to Symbolic Computation
In Chapter 3 the student is introduced to standard EVAL notation; the
concepts of quoting and named variables follow fairly naturally. Now he or
she is ready to discard paper and pencil for a real computer (and is probably
eager to do so), whereas at the start of the course this might have been viewed
with trepidation.
OTHER FEATURES
Three other unique features of the book first appear in Chapter 3: evaltrace
notation, Lisp Toolkit sections, and a comprehensive graphical representation
for Lisp data structures, including function objects and the internal structure of
symbols.
Evaltrace notation shows step-by-step how Lisp expressions are evaluated,
how functions are applied to arguments, and how variables are created and
bound. The different roles of EVAL and APPLY, the scoping of variables,
and the nesting of lexical contours can all be explained graphically using this
notation. It makes the process of evaluation transparent to the student by
describing it in a visual language which he or she can remember and use.
The Lisp Toolkit sections introduce the various programming aids that
Common Lisp provides, such as DESCRIBE, INSPECT, TRACE, STEP, and
the debugger. There are also two tools unique to this book; their source code
appears in Appendices A and B, and is available on diskette from the
publisher. The first tool, SDRAW, draws cons cell diagrams. It is part of a
read-eval-draw loop that has proven invaluable for teaching beginners to
reason about cons cell structures, particularly the differences among CONS,
LIST, and APPEND. The second tool, DTRACE, is a tracing package that
generates more detailed output than most implementations of TRACE, and is
therefore more useful for teaching beginners.
Finally, the graphical representation of Lisp data structures—particularly
the internal structure of symbols with their name, function, value, plist, and
package cells—helps students understand the true nature of Lisp interpreters
and highlights the distinctions between symbols, functions, variables, and print
names.
ORGANIZATION OF LATER CHAPTERS
Applicative operators are introduced in Chapter 7, where the student also
learns about lexical closures. In Chapter 8, the dragon stories that were a
popular feature of the previous version have been retained, but they are now
backed up with a new device—recursion templates—that helps beginners
analyze recursive functions to extract the essence of the recursive style. Since

---

Note to Instructors
xi
some instructors prefer to teach recursion before applicatives, these two
chapters have been written so that they may be covered in either order.
The book promotes a clean, side-effect-free style of programming for the
first eight chapters. Chapter 9 discusses i/o. Chapter 10 provides a unified
picture of assignment that includes ordinary variables, generalized variables,
and destructive sequence operations. Chapter 11 covers iteration, and shows
how DO and DO* can be used to construct substantial iterative expressions
with no explicit assignments. Chapter 12 introduces structures, and Chapter
13 covers arrays, hash tables, and property lists. The final chapter, Chapter
14, is devoted to macros and compilation. It also explains the difference
between lexical and dynamic scoping. Evaltrace diagrams clarify the
semantics of macros and special variables.
EMPHASIS ON SIMPLICITY
Because Common Lisp is such a complex language, there are a few places
where I have chosen to simplify things to better meet the needs of beginners.
For example, the 1+ and 1- functions are banished from this book because
their names are very confusing. Also, the book relies almost exclusively on
EQUAL because this is the most useful equality predicate. EQ, EQL,
EQUALP, and = are mentioned in advanced topics sections, but not used very
much. In a few places I have chosen to write a function slightly less concisely
rather than introduce one of the more obscure primitives like PUSHNEW.
And I make no attempt to cover the most advanced features, such as multiple
values or the package system.
Some people prefer to teach Scheme in introductory courses because it is
so much smaller than Common Lisp. But one can easily teach the subset of
Common Lisp that is equivalent to Scheme, so language size isn’t really an
issue for beginners. A more compelling argument is that there is a certain
style of applicative programming, making heavy use of lexical closures, that
can be expressed more elegantly in Scheme syntax. But there are also areas
where Common Lisp is superior to Scheme, such as its support for user-
defined macros, its elegant unification of lists and vectors into a sequence
datatype, and its use of keyword arguments to greatly extend the utility of the
sequence functions. The combination of tremendous power, extensive
manufacturer support, and a built-in object-oriented programming facility
make Common Lisp the only ‘‘industrial strength’’ Lisp. Although this book
does emphasize a side-effect-free, applicative approach to programming with
which Scheme afficionados will feel quite at home, it does so in purely
Common Lisp style.

---

xii
Common Lisp: A Gentle Introduction to Symbolic Computation
This book has been carefully designed to meet the needs of beginning
programmers and non-computer science students, but the optional advanced
topics sections at the end of each chapter provide enough enrichment material
to hold the interest of junior and senior computer science majors. For
advanced undergraduates, Guy L. Steele Jr.’s Common Lisp: The Language
(published by Digital Press) would be a useful companion to the introduction
provided here. For beginners, Common Lisp: The Reference, by Franz, Inc.
(published by Addison-Wesley) is a more suitable reference work.

---

Document Outline

• Preface vii
• Note to Instructors ix
• Acknowledgements xiii
• 1. Functions and Data
  • 1.1. Introduction
  • 1.2. Functions On Numbers
  • 1.3. Three Kinds of Numbers
  • 1.4. Order Of Inputs Is Important
  • 1.5. Symbols
  • 1.6. The Special Symbols T and NIL
  • 1.7. Some Simple Predicates
  • 1.8. The EQUAL Predicate
  • 1.9. Putting Functions Together
    • 1.9.1. Defining ADD0
    • 1.9.2. Defining ADD1
    • 1.9.3. Defining TWOP
    • 1.9.4. Defining ONEMOREP
  • 1.10. The NOT Predicate
  • 1.11. Negating A Predicate
  • 1.12. Number of Inputs to a Function
  • 1.13. Errors
  • Advanced Topics
  • 1.14. The History of Lisp
• 2. Lists
  • 2.1. Lists Are The Most Versatile Data Type
  • 2.2. What Do Lists Look Like?
  • 2.3. Lists of One Element
  • 2.4. Nested Lists
  • 2.5. Length of Lists
  • 2.6. NIL: The Empty List
  • 2.7. Equality of Lists
  • 2.8. FIRST, SECOND, THIRD, and REST
  • 2.9. Functions Operate On Pointers
  • 2.10. CAR and CDR
    • 2.10.1. The CDR of a Single-Element List
    • 2.10.2. Combinations of CAR and CDR
    • 2.10.3. CAR and CDR of Nested Lists
    • 2.10.4. CAR and CDR of NIL
  • 2.11. CONS
    • 2.11.1. CONS and the Empty List
    • 2.11.2. Building Nested Lists With CONS
    • 2.11.3. CONS Can Build Lists From Scratch
  • 2.12. Symmetry of CONS and CAR/CDR
  • 2.13. LIST
  • 2.14. Replacing the First Element of a List
  • 2.15. List Predicates
  • Advanced Topics
  • 2.16. Unary Arithmetic with Lists
  • 2.17. Nonlist Cons Structures
  • 2.18. Circular Lists
  • 2.19. Length of Nonlist Cons Structures
• 3. EVAL Notation
  • 3.1. Introduction
  • 3.2. The EVAL Function
  • 3.3. EVAL Notation Can Do Anything Box Notation Can Do
  • 3.4. Evaluation Rules Define the Behavior of EVAL
  • 3.5. Defining Functions in EVAL Notation
  • 3.6. Variables
  • 3.7. Evaluating Symbols
  • 3.8. Using Symbols and Lists as Data
  • 3.9. The Problem of Misquoting
  • 3.10. Three Ways to Make Lists
  • 3.11. Four Ways to Misdefine a Function
  • 3.12. More About Variables
  • Lisp on the Computer
  • 3.13. Running Lisp
  • 3.14. The Read-Eval-Print Loop
  • 3.15. Recovering From Errors
  • Lisp Toolkit: ED
  • Keyboard Exercise
  • Advanced Topics
  • 3.16. Functions of No Arguments
  • 3.17. The QUOTE Special Function
  • 3.18. Internal Structure of Symbols
  • 3.19. Lambda Notation
  • 3.20. Scope of Variables
  • 3.21. EVAL and APPLY
• 4. Conditionals
  • 4.1. Introduction
  • 4.2. The IF Special Function
  • 4.3. The COND Macro
  • 4.4. Using T as a Test
  • 4.5. Two More Examples of COND
  • 4.6. COND and Parenthesis Errors
  • 4.7. The AND and OR Macros
  • 4.8. Evaluating AND and OR
  • 4.9. Building Complex Predicates
  • 4.10. Why AND and OR are Conditionals
  • 4.11. Conditionals are Interchangeable
  • Lisp Toolkit: STEP
  • Advanced Topics
  • 4.12. Boolean Functions
  • 4.13. Truth Tables
  • 4.14. DeMorgan’s Theorem
• 5. Variables and Side Effects
  • 5.1. Introduction
  • 5.2. Local and Global Variables
  • 5.3. SETF Assigns a Value to a Variable
  • 5.4. Side Effects
  • 5.5. The LET Special Function
  • 5.6. The LET* Special Function
  • 5.7. Side Effects Can Cause Bugs
  • Lisp Toolkit: DOCUMENTATION and APROPOS
  • Keyboard Exercise
  • Advanced Topics
  • 5.8. Symbols and Value Cells
  • 5.9. Distinguishing Local from Global Variables
  • 5.10. Binding, Scoping, and Assignment
• 6. List Data Structures
  • 6.1. Introduction
  • 6.2. Parenthesis Notation vs. Cons Cell Notation
  • 6.3. The APPEND Function
  • 6.4. Comparing CONS, LIST, and APPEND
  • 6.5. More Functions on Lists
    • 6.5.1. REVERSE
    • 6.5.2. NTH and NTHCDR
    • 6.5.3. LAST
    • 6.5.4. REMOVE
  • 6.6. Lists as Sets
    • 6.6.1. MEMBER
    • 6.6.2. INTERSECTION
    • 6.6.3. UNION
    • 6.6.4. SET-DIFFERENCE
    • 6.6.5. SUBSETP
  • 6.7. Programming With Sets
  • 6.8. Lists As Tables
    • 6.8.1. ASSOC
    • 6.8.2. RASSOC
  • 6.9. Programming With Tables
  • Lisp Toolkit: SDRAW
  • Keyboard Exercise
  • Advanced Topics
  • 6.10. Trees
    • 6.10.1. SUBST
    • 6.10.2. SUBLIS
  • 6.11. Efficiency of List Operations
  • 6.12. Shared Structure
  • 6.13. Equality of Objects
  • 6.14. Keyword Arguments
• 7. Applicative Programming
  • 7.1. Introduction
  • 7.2. FUNCALL
  • 7.3. The MAPCAR Operator
  • 7.4. Manipulating Tables With MAPCAR
  • 7.5. Lambda Expressions
  • 7.6. The FIND-IF Operator
  • 7.7. Writing ASSOC With FIND-IF
  • 7.8. REMOVE-IF and REMOVE-IF-NOT
  • 7.9. The REDUCE Operator
  • 7.10. EVERY
  • Lisp Toolkit: TRACE and DTRACE
  • Keyboard Exercise
  • Advanced Topics
  • 7.11. Operating on Multiple Lists
  • 7.12. The FUNCTION Special Function
  • 7.13. Keyword Arguments to Applicative Operators
  • 7.14. Scoping and Lexical Closures
  • 7.15. Writing An Applicative Operator
  • 7.16. Functions That Make Functions
• 8. Recursion
  • 8.1. Introduction
  • 8.2. Martin and the Dragon
  • 8.3. A Function to Search for Odd Numbers
  • 8.4. Martin Visits The Dragon Again
  • 8.5. A Lisp Version of the Factorial Function
  • 8.6. The Dragon’s Dream
  • 8.7. A Recursive Function for Counting Slices of Bread
  • 8.8. The Three Rules of Recursion
  • 8.9. Martin Discovers Infinite Recursion
  • 8.10. Infinite Recursion in Lisp
  • 8.11. Recursion Templates
    • 8.11.1. Double-Test Tail Recursion
    • 8.11.2. Single-Test Tail Recursion
    • 8.11.3. Augmenting Recursion
  • 8.12. Variations on the Basic Templates
    • 8.12.1. List-Consing Recursion
    • 8.12.2. Simultaneous Recursion on Several Variables
    • 8.12.3. Conditional Augmentation
    • 8.12.4. Multiple Recursion
  • 8.13. Trees and CAR/CDR Recursion
  • 8.14. Using Helping Functions
  • 8.15. Recursion in Art and Literature
  • Lisp Toolkit: The Debugger
  • Keyboard Exercise
  • Advanced Topics
  • 8.16. Advantages of Tail Recursion
  • 8.17. Writing New Applicative Operators
  • 8.18. The LABELS Special Function
  • 8.19. Recursive Data Structures
• 9. Input/Output
  • 9.1. Introduction
  • 9.2. Character Strings
  • 9.3. The FORMAT Function
  • 9.4. The READ Function
  • 9.5. The YES-OR-NO-P Function
  • 9.6. Reading Files with WITH-OPEN-FILE
  • 9.7. Writing Files with WITH-OPEN-FILE
  • Keyboard Exercise
  • Lisp Toolkit: DRIBBLE
  • Advanced Topics
  • 9.8. Parameters to Format Directives
  • 9.9. Additional Format Directives
  • 9.10. The Lisp 1.5 Output Primitives
  • 9.11. Handling End-of-File Conditions
  • 9.12. Printing in Dot Notation
  • 9.13. Hybrid Notation
• 10. Assignment
  • 10.1. Introduction
  • 10.2. Updating a Global Variable
  • 10.3. Stereotypical Updating Methods
    • 10.3.1. The INCF and DECF Macros
    • 10.3.2. The PUSH and POP Macros
    • 10.3.3. Updating Local Variables
  • 10.4. WHEN and UNLESS
  • 10.5. Generalized Variables
  • 10.6. Case Study: A Tic-Tac-Toe Player
  • Lisp Toolkit: BREAK and ERROR
  • Keyboard Exercise
  • Advanced Topics
  • 10.7. Do-It-Yourself List Surgery
  • 10.8. Destructive Operations on Lists
    • 10.8.1. NCONC
    • 10.8.2. NSUBST
    • 10.8.3. Other Destructive Functions
  • 10.9. Programming With Destructive Operations
  • 10.10. SETQ and SET
  • 11. Iteration and Block Structure
  • 11.1. Introduction
  • 11.2. DOTIMES and DOLIST
  • 11.3. Exiting the Body of a Loop
  • 11.4. Comparing Recursive and Iterative Search
  • 11.5. Building Up Results With Assignment
  • 11.6. Comparing DOLIST with MAPCAR and Recursion
  • 11.7. The DO Macro
  • 11.8. Advantages of Implicit Assignment
  • 11.9. The DO* Macro
  • 11.10. Infinite Loops with DO
  • 11.11. Implicit Blocks
  • Keyboard Exercise
  • Lisp Toolkit: TIME
  • Advanced Topics
  • 11.12. PROG1, PROG2, and PROGN
  • 11.13. Optional Arguments
  • 11.14. Rest Arguments
  • 11.15. Keyword Arguments
  • 11.16. Auxiliary Variables
• 12. Structures and The Type System
  • 12.1. Introduction
  • 12.2. TYPEP and TYPE-OF
  • 12.3. Defining Structures
  • 12.4. Type Predicates for Structures
  • 12.5. Accessing and Modifying Structures
  • 12.6. Keyword Arguments to Constructor Functions
  • 12.7. Changing Structure Definitions
  • Lisp Toolkit: DESCRIBE and INSPECT
  • Keyboard Exercise
  • Advanced Topics
  • 12.8. Print Functions for Structures
  • 12.9. Equality of Structures
  • 12.10. Inheritance from Other Structures
• 13. Arrays, Hash Tables, And Property Lists
  • 13.1. Introduction
  • 13.2. Creating an Array
  • 13.3. Printing Arrays
  • 13.4. Accessing and Modifying Array Elements
  • 13.5. Creating Arrays With MAKE-ARRAY
  • 13.6. Strings as Vectors
  • 13.7. Hash Tables
  • 13.8. Property Lists
  • 13.9. Programming With Property Lists
  • Array Keyboard Exercise
  • Hash Table Keyboard Exercise
  • Lisp Toolkit: ROOM
  • Advanced Topics
  • 13.10. Property List Cells
  • 13.11. More On Sequences
• 14. Macros and Compilation
  • 14.1. Introduction
  • 14.2. Macros as Shorthand
  • 14.3. Macro Expansion
  • 14.4. Defining a Macro
  • 14.5. Macros as Syntactic Extensions
  • 14.6. The Backquote Character
  • 14.7. Splicing With Backquote
  • 14.8. The Compiler
  • 14.9. Compilation and Macro Expansion
  • 14.10. Compiling Entire Programs
  • 14.11. Case Study: Finite State Machines
  • Lisp Toolkit: PPMX
  • Keyboard Exercise
  • Advanced Topics
  • 14.12. The &BODY Lambda-List Keyword
  • 14.13. Destructuring Lambda Lists
  • 14.14. Macros and Lexical Scoping
  • 14.15. Historical Significance of Macros
  • 14.16. Dynamic Scoping
  • 14.17. DEFVAR, DEFPARAMETER, DEFCONSTANT
  • 14.18. Rebinding Special Variables
• Appendix A. The SDRAW Tool
• Appendix B. The DTRACE Tool
• Appendix C. Answers to Exercises
• Glossary
• Further Reading
• Index I-

---