The introduction to Lisp follows. Additional
information about this book, along with access to software, is available
Understanding Symbol Manipulation
This book is about Lisp, a programming language that takes its
name from List Processing. The book has three parts,
each written to accomplish a particular purpose:
This brief chapter describes what symbol manipulation is all
about, indicates why symbol manipulation is important, and
explains why Lisp is the right symbol-manipulation language to
- The purpose of Part One is to help you learn about symbol
manipulation and basic Lisp programming.
- The purpose of Part Two is to introduce you to some more
advanced Lisp programming ideas.
- The purpose of Part Three is to excite you about what you can do
Symbol Manipulation Is Like Working with Words and
Everything in a computer is a string of binary digits, ones and
zeros, that everyone calls bits. From one perspective, sequences
of bits can be interpreted as a code for ordinary decimal digits.
But from another perspective, sequences of bits can be
interpreted as a code for wordlike objects and sentencelike
A symbol-manipulation program uses symbolic expressions to
remember and work with data and procedures, just as people use
pencil, paper, and human language to remember and work with data
and procedures. A symbol-manipulation program typically has
procedures that recognize particular symbolic expressions, tear
existing ones apart, and assemble new ones.
- In Lisp, the fundamental things formed from bits are
wordlike objects called atoms.
- Groups of atoms form sentencelike objects called lists.
Lists themselves can be grouped together to form higher-level
- Atoms and lists collectively are called symbolic
expressions, or more succinctly, expressions. Working
with symbolic expressions is what symbol manipulation using Lisp is
Two examples of symbolic expressions follow. The parentheses mark
where lists begin and end. The first is a description of a structure
built out of children's blocks. The second is a description of a
(arch (parts lintel post1 post2)
(lintel must-be-supported-by post1)
(lintel must-be-supported-by post2)
(lintel a-kind-of wedge)
(post1 a-kind-of brick)
(post2 a-kind-of brick)
(post1 must-not-touch post2)
(post2 must-not-touch post1))
(mit (a-kind-of university)
(location (cambridge massachusetts))
(founder (william barton rogers)))
Certainly these are not scary. Both just describe something
according to some conventions about how to arrange symbols. Here is
another example, this time expressing a rule for determining whether
some animal is a carnivore:
((? animal) has pointed teeth)
((? animal) has claws)
((? animal) has forward eyes)
((? animal) is a carnivore))
What we see is just another way of expressing the idea that an
animal with pointed teeth, claws, and forward-pointing eyes is
probably a carnivore. To use such a rule, a program must take it
apart, determine if the patterns involving teeth, claws, and eyes
are compatible with what is known about a particular animal in a
database, and if they are compatible, add the conclusion that the
animal is a carnivore to the database. All this is done by
LISP Helps Make Computers Intelligent
These days, there is a growing armamentarium of programs that
exhibit what most people consider intelligent behavior. Nearly
all of these intelligent programs, or seemingly intelligent programs, are
written in Lisp. Many have great practical importance. Here
are some examples:
Consequently, people who want to know about computer intelligence
need to understand Lisp.
- Expert problem solvers. One of the first Lisp programs did
calculus problems at the level of university freshmen. Another
early program did geometric analogy problems of the sort found in
intelligence tests. Since then, newer programs have configured
computers, diagnosed infections of the blood, understood
electronic circuits, evaluated geological formations, planned
investments, scheduled factories, designed fasteners, invented
interesting mathematics, and much more. All are written in
- Commonsense reasoning. Much of human thinking seems to involve a
small amount of reasoning using a large amount of knowledge.
Representing knowledge means choosing a vocabulary of symbols and fixing
some conventions for arranging them. Good representations make just the
right things explicit. Lisp is the language in which most research
on representation is done.
- Learning. Much work has been done on the learning of concepts
by computer, and certainly most of what has been done also rests on
progress in representation. Lisp again dominates.
- Natural-language interfaces. There is a growing need for
programs that interact with people in English and other natural
languages. Practical systems have been built for recovering
information from databases that are difficult to use otherwise.
- Education and intelligent support systems. To interact comfortably
with computers, people must have computers that know what people know
and how to tell them more. No one wants a long-winded explanation once
they know a lot. Nor does anyone want a telegramlike explanation when
just beginning. Lisp-based programs are beginning to make user
models by analyzing what the user does. These programs use the models
to trim or elaborate explanations.
- Speech and vision. Understanding how people hear and see has
proved fantastically difficult. It seems that we do not know
enough about how the physical world constrains what ends up on
our ear drums and retinas. Nevertheless, progress is being made
and much of it is made in Lisp, even though a great deal of
straight arithmetic-oriented programming is necessary. To be
sure, Lisp has no special advantages for arithmetic-oriented
programming. But at the same time, Lisp has no disadvantages
for arithmetic either.
LISP Promotes Productivity and Facilitates Education
Lisp is an important language
even when computer intelligence is not involved. Here are some
Given all these examples, it is no surprise that the following is
accepted by nearly everyone:
- Applications programming. Talented programmers find that Lisp
can increase their productivity enormously, enabling them to write
big programs much faster and far less expensively. This can have
dramatic effects on the way big programs are developed. The old
way was to start with multiyear periods of specification,
followed by multiyear periods of implementation, leading to
systems that produce disappointed, cranky users. The new way is
to have prototypes up in a few months, with specification and
implementation evolving together, with users constantly helping
to shape the final result.
- Systems programming. Lisp machines are high-powered
workstations programmed from top to bottom in Lisp. The
operating system, the user utility programs, the editors, the
compilers, and the interpreters are all written in Lisp,
demonstrating Lisp's power and versatility.
- Computer science education. Lisp facilitates procedure
abstraction and data abstraction, thereby emphasizing two
supremely important programming ideas. And because Lisp is a
superb implementation language, Lisp is a good language with
which to build interpreters and compilers for a variety
of languages, including Lisp itself.
- All computer scientists and computer engineers must understand the power
of symbol manipulation in general. Most computer scientists and engineers
should understand Lisp in particular.
LISP Is the Right Symbol-Manipulation Language To Learn
There are too many programming languages. Fortunately, however,
only a few are for symbol manipulation, and of these Lisp is
the most used. After Lisp is understood, most of the other
symbol-manipulation languages are easy to learn.
Why has Lisp become the most used language for symbol
manipulation, and lately, much more? All of the following
arguments have adherents:
Happily, Lisp is an easy language to learn. A few hours of
study is enough to understand amazing programs. Previous
exposure to some other programming language is not necessary.
Indeed, such experience can be something of a handicap, for there
can be a serious danger of developing a bad accent: other
languages do things differently, and procedure-by-procedure
translation leads to awkward constructions and poor programming
- The interaction argument. Lisp is oriented toward programming
at a terminal with rapid response. All procedures and all data can be
displayed or altered at will.
- The environment argument. Lisp has been used by a community
that needed and got the best in editing and debugging tools. For more
than two decades, people at the world's largest artificial intelligence
centers have created sophisticated computing environments around
Lisp, making a combination that is unbeatable for writing big,
- The evolution argument. CommonLisp is built on more than
twenty years of continuous experiment and refinement.
Consequently, Lisp has just the right features.
- The uniformity argument. Lisp procedures and Lisp data
have the same form. One Lisp program can use another as data. One
Lisp program even can create another and use it.
One reason Lisp is easy to learn is that its syntax is
extremely simple. Curiously, Lisp's present syntax has
strange roots. John McCarthy, Lisp's inventor, originally
used a sort of old Lisp, which is about as hard to read as old
English. At one point, however, he wished to use Lisp to do a
piece of mathematics that required both procedures and data to
have the same syntactic form. The resulting form of Lisp
quickly caught on.
COMMON LISP Is the Right LISP To Learn
The Lisp used throughout this book is CommonLisp. We use
CommonLisp because it is modern, powerful, and widely
available. CommonLisp also is the accepted standard for
commercial use. Do not be confused by references to other,
strangely-named Lisps. Most are either obsolete dialects or
CommonLisp with company-specific extensions.
Lately, CommonLisp has been extended to include features for
object-oriented programming via CLOS, the COMMON LISP
Object System. Several
chapters in this book explain how CLOS makes CommonLisp
Beware of False Myths
There is no perfect computer language, and to be sure, Lisp
has defects. Many of the original defects have been fixed, even
though some people mistakenly cite them even today. Among the
most pervasive and unfortunate myths are the following:
In fact this was true at one time. This historical problem has
been corrected by the development of good programs for
translating the stuff programmers produce into the instructions
that a computer can execute directly, without further
decomposition. Said another way, the problem has been corrected
by the development of good Lisp compilers.
In fact this also was true at one time. In the old days, Lisp
was used strictly in research, where interaction is at a premium
and high speed for fully debugged application-oriented programs
is less important. Today, however, excellent Lisp compilers
have been developed to support the growing commercial demand for
- Myth: Lisp is slow at crunching numbers.
Actually, this is not a myth. Some are. But that is only because
Lisp makes it possible to create programs that are big enough to
know a lot.
- Myth: Lisp programs are big.
A few years ago, getting started with Lisp required a
million-dollar commitment. Today, on the low end, excellent
Lisp systems for personal computers start at only a few
hundred dollars, and on the high end, even the fanciest Lisp
systems running on Lisp-oriented workstations cost well under
a hundred thousand dollars.
- Myth: Lisp programs require expensive computers.
In fact the parentheses problem goes away as soon as you learn
how to use a Lisp editing program that helps you put things
down on an editing screen properly. No one finds the following
to be particularly clear:
- Myth: Lisp is hard to read and debug because of all the parentheses.
(defun fibonacci (n) (if (or (= n
0) (= n 1)) 1 (+ (fibonacci (-
n 1)) (fibonacci (- n 2)))))
But the equivalent, formatted version is fine after a little experience:
(defun fibonacci (n)
(if (or (= n 0) (= n 1))
(+ (fibonacci (- n 1))
(fibonacci (- n 2)))))
Lisp-oriented editors make it easy to produce the formatted
version as it is written.
Lisp earned its bad reputation by being in the company of some
hard-to-read books in its youth. Now there are many good ones,
each with its own distinguishing features.
- Myth: Lisp is hard to learn.
- Symbol manipulation is like working with words and sentences.
- Lisp helps make computers intelligent.
- Lisp promotes productivity and facilitates education.
- Lisp is the right symbol-manipulation language to learn.
- CommonLisp is the right Lisp to learn.
- Beware of false myths. Lisp is an easy-to-learn,
fast-running, productivity-multiplying language, well-suited to many
applications both in and outside of Artificial Intelligence.