The introduction to Lisp follows. Additional information about this book, along with access to software, is available via http://www.ai.mit.edu/people/phw/Books/

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:

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 with Lisp.

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 learn.

Symbol Manipulation Is Like Working with Words and Sentences

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 objects.

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 lists.
Atoms and lists collectively are called symbolic expressions, or more succinctly, expressions. Working with symbolic expressions is what symbol manipulation using Lisp is about.

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.

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 certain university.


(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))
     (phone 253-1000)
     (schools (architecture
               business
               engineering
               humanities
               science))
     (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: (identify6 ((? 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 manipulating symbols. 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: 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 Lisp. 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. Consequently, people who want to know about computer intelligence need to understand Lisp. LISP Promotes Productivity and Facilitates Education Lisp is an important language even when computer intelligence is not involved. Here are some examples: 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. Given all these examples, it is no surprise that the following is accepted by nearly everyone: 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: 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, complicated programs. 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. 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 practice. 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 more powerful. 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: Myth: Lisp is slow at crunching numbers. 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. Myth: Lisp is slow. 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 Lisp programs. Myth: Lisp programs are big. 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 require expensive computers. 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 is hard to read and debug because of all the parentheses. 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: (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)) 1 (+ (fibonacci (- n 1)) (fibonacci (- n 2))))) Lisp-oriented editors make it easy to produce the formatted version as it is written. Myth: Lisp is hard to learn. 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. Highlights 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.