David S. Touretzky - Common LISP: A Gentle Introduction to Symbolic Computation

Copyright

Copyright 2013 by David S. Touretzky

All rights reserved.

Bibliographical Note

This Dover edition, first published in 2013, is a revised republication of the work originally published by The Benjamin/Cummings Publishing Company, Inc., in 1990.

International Standard Book Number

eISBN-13: 978-0-4867-9170-8

Manufactured in the United States by Courier Corporation
49820401
www.doverpublications.com

To Phil and Anne

This book is about learning to program in Lisp. Although widely known as the principal language of artificial intelligence researchone of the most advanced areas of computer scienceLisp 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 dont like math, you may find you enjoy computer programming. Ive 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 werent very good due to the small memories of the early machines. Todays personal computers often come with several megabytes of RAM and a hard disk as standard 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 1989

This 2013 edition from Dover Publications includes roughly two dozen corrections to the original manuscript, and a few additions to the Further Readings section. With the arrival of ANSI Common Lisp as the official standard, and the availability of several good open source implementations, Lisp will remain an important language for years to come.

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 books novel approach to Lisp.

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 structuresnumbers, symbols, and listsbefore 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 frustrationlearning 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 to pick up the basic list manipulation primitives.

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

Three other unique features of the book first appear in : 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.