Lisp

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/CummingsPublishing 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 thisbook 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 Iwrote 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 computerprogramming. 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 iscarried 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 memoriesof 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...