ANSI Common LISP (Paul Graham) (Z-Library)

ANSI Common Lisp

PRENTICE HALL SERIES UW§ IN ARTIFICIAL INTELLIGENCE Stuart Russell and Peter Norvig, Editors GRAHAM ANSI Common Lisp MUGGLETON Logical Foundations of Machine Learning RUSSELL & NORVIG Artificial Intelligence: A Modern Approach

ANSI Common Lisp Paul Graham An Alan R. Apt Book Prentice Hall, Upper Saddle River, New Jersey 07458

Library of Congress Cataloging-in-Publication Data Graham, Paul. ANSI common lisp. / Paul Graham. p. cm. "An Alan R. Apt book." Includes bibliographical references and index. ISBN 0-13-370875-6 1. COMMON LISP (Computer program language) I. Tide. QA76.73.C28G69 1996 005.13'3-dc20 95-45017 CIP Publisher: Alan Apt Production Editor: Mona Pompili Cover Designer: Gino Lee Copy Editor: Shirley Michaels Production Coordinator: Donna Sullivan Editorial Assistant: Shirley McGuire Cover Photo: Ed Lynch © 1996 by Prentice Hall, Inc. Upper Saddle River, NJ 07458 The author and publisher of this book have used their best efforts in preparing this book. These efforts include the development, research, and testing of the theories and programs to determine their effectiveness. The author and publisher shall not be liable in any event for incidental or consequential damages in connection with, or arising out of, the furnishing, performance, or use of these programs. All rights reserved. No part of this book may be reproduced, in any form or by any means, without permission in writing from the publisher. All trademarks are the property of their respective owners. Printed in the United States of America 20 ISBN 0-13-370875-6 Prentice-Hall International (UK) Limited, London Prentice-Hall of Australia Pty. Limited, Sydney Prentice-Hall of Canada, Inc., Toronto Prentice-Hall Hispanoamericana, S. A., Mexico Prentice-Hall of India Private Limited, New Delhi Prentice-Hall of Japan, Inc., Tokyo Prentice-Hall Asia Pte. Ltd., Singapore Editora Prentice-Hall do Brasil, Ltda., Rio de Janeiro •m

TORTM

Half lost on my firmness gains to more glad heart, Or violent and from forage drives A glimmering of all sun new begun Both harp thy discourse they march'd, Forth my early, is not without delay; For their soft with whirlwind; and balm. Undoubtedly he scornful turn'd round ninefold, Though doubled now what redounds, And chains these a lower world devote, yet inflicted? Till body or rare, and best things else enjoy'd in heav'n To stand divided light at ev'n and poise their eyes, Or nourish, lik'ning spiritual, I have thou appear. —Henley

Preface The aim of this book is to teach you Common Lisp quickly and thoroughly. It is really two books. The first half is a tutorial that explains, with plenty of examples, all the essential concepts of Lisp programming. The second half is an up-to-date summary of ANSI Common Lisp, describing every operator in the language. Audience ANSI Common Lisp is intended for both students and professional program­ mers. It assumes no prior knowledge of Lisp. Experience writing programs in some other language would be helpful, but not absolutely necessary. The book begins with the most basic concepts, and pays special attention to the points that tend to confuse someone seeing Lisp for the first time. This book could be used by itself as the textbook in a course on Lisp programming, or to teach Lisp as part of a course on artificial intelligence or programming languages. Professional programmers who want to learn Lisp will appreciate the direct, practical approach. Those who already use Lisp will find it a useful source of examples, and a convenient reference for ANSI Common Lisp. How to Use This Book The best way to learn Lisp is to use it. It's also more fun to learn a language by writing programs in it. This book is designed to get you started as quickly as possible. After a brief Introduction, vii

viii PREFACE • Chapter 2 explains, in 21 pages, everything you need to start writing Lisp programs. • Chapters 3-9 introduce the essential elements of Lisp programming. These chapters pay special attention to critical concepts like the role of pointers in Lisp, the use of recursion to solve problems, and the significance of first-class functions. For readers who want a thorough grounding in Lisp techniques, • Chapters 10-14 cover macros, CLOS, operations on list structure, opti­ mization, and advanced topics like packages and read-macros. • Chapters 15-17 sum up the lessons of the preceding chapters in three examples of real applications: a program for making logical inferences, an HTML generator, and an embedded language for object-oriented programming. The last part of the book consists of four appendices, which should be useful to all readers: • Appendices A-D include a guide to debugging, source code for 58 Common Lisp operators, a summary of the differences between ANSI Common Lisp and previous versions of the language,0 and a reference describing every operator in ANSI Common Lisp. The book concludes with a section of notes. The notes contain clarifications, references, additional code, and occasional heresies. Notes are indicated in the text by a small circle, like this.0 The Code Although it describes ANSI Common Lisp, this book has been designed so that you can use it with any version of Common Lisp. Examples that depend on newer features are usually accompanied by notes showing how they would be rendered in older implementations. All the code in this book is available online. You can find it, along with links to free software, historic papers, the Lisp FAQ, and a variety of other resources, at: h t tp : / /www.eecs .harvard .edu/on l i sp / The code is also available by anonymous FTP from: f t p : / / f t p . e e c s . h a r v a r d . e d u : / p u b / o n l i s p / Questions and comments can be sent to pgOeecs. harvard. edu.

PREFACE IX On Lisp Throughout this book I've tried to point out the unique qualities that make Lisp Lisp, and the new things that this language will let you do. Macros, for example: Lisp programmers can, and often do, write programs to write their programs for them. Lisp is the only major language in which this is a routinely used technique, because Lisp is the only major language to provide the abstractions that make it convenient. I would like to invite readers who are interested in learning more about macros and other advanced techniques to read the companion volume, On Lisp. Acknowledgements Of all the friends who have helped me during the writing of this book, I owe special thanks to Robert Morris. The whole book reflects his influence, and is very much the better for it. Several of the examples are derived from programs he originally wrote, including Henley (page 138) and the pattern-matcher on page 249. I was fortunate to have a first-rate team of technical reviewers: Skona Brittain, John Foderaro, Nick Levine, Peter Norvig, and Dave Touretzky. There is hardly a page of the book that did not benefit in some way from their suggestions. John Foderaro even rewrote some of the code in Section 5.7. Several other people consented to read all or part of the manuscript, including Ken Anderson, Tom Cheatham, Richard Fateman, Steve Hain, Barry Margolin, Waldo Pacheco, Wheeler Ruml, and Stuart Russell. Ken Anderson and Wheeler Ruml, in particular, made many useful comments. I'm grateful to Professor Cheatham, and Harvard generally, for providing the facilities used to write this book. Thanks also to the staff at Aiken Lab, including Tony Hartman, Dave Mazieres, Janusz Juda, Harry Bochner, and Joanne Klys. I'm glad to have had the chance to work with Alan Apt again. The people at Prentice Hall—Alan, Mona Pompili, Shirley McGuire, and Shirley Michaels—are really a pleasure to work with. The cover is again the work of the incomparable Gino Lee, of the Bow & Arrow Press, Cambridge. This book was typeset using L̂ TgX, a language written by Leslie Lamport atop Donald Knuth's Tj3C, with additional macros by L. A. Carr, Van Jacobson, and Guy Steele. The diagrams were done with Idraw, by John Vlissides and Scott Stanton. The whole was previewed with Ghostview, by Tim Theisen, which is built on Ghostscript, by L. Peter Deutsch. I owe thanks to many others, including Henry Baker, Kim Barrett, Ingrid Bassett, Trevor Blackwell, Paul Becker, Gary Bisbee, Frank Deutschmann, Frances Dickey, Rich and Scott Draves, Bill Dubuque, Dan Friedman, Jenny

X PREFACE Graham, Alice Hartley, David Hendler, Mike Hewett, Glenn Holloway, Brad Karp, Sonya Keene, Ross Knights, Mutsumi Komuro, Steffi Kutzia, David Kuznick, Madi Lord, Julie Mallozzi, Paul McNamee, Dave Moon, Howard Mullings, Mark Nitzberg, Nancy Parmet and her family, Robert Penny, Mike Plusch, Cheryl Sacks, Hazem Sayed, Shannon Spires, Lou Steinberg, Paul Stoddard, John Stone, Guy Steele, Steve Strassmann, Jim Veitch, Dave Watkins, Idelle and Julian Weber, the Weickers, Dave Yost, and Alan Yuille. Most of all, I'd like to thank my parents, and Jackie. Donald Knuth called his classic series The Art of Computer Programming. In his Turing Award Lecture, he explained that this title was a conscious choice—that what drew him to programming was "the possibility of writing beautiful programs." Like architecture, programming has elements of both art and science. A program has to live up to mathematical truth in the same way that a building has to live up to the laws of physics. But the architect's aim is not simply to make a building that doesn't fall down. Almost always the real aim is to make something beautiful. Many programmers feel, like Donald Knuth, that this is also the real aim of programming. Almost all Lisp hackers do. The spirit of Lisp hacking can be expressed in two sentences. Programming should be fun. Programs should be beautiful. That's the spirit I have tried to convey in this book. Paul Graham

Contents 1. Introduction 1 1.1. New Tools 1 1.2. New Techniques 3 1.3. A New Approach 4 2. Welcome to Lisp 7 2.1. Form 7 2.2. Evaluation 9 2.3. Data 10 2.4. List Operations 12 2.5. Truth 13 2.6. Functions 14 2.7. Recursion 16 2.8. Reading Lisp 17 2.9. Input and Output 18 2.10. Variables 19 2.11. Assignment 21 2.12. Functional Programming 22 2.13. Iteration 23 2.14. Functions as Objects 25 2.15. Types 27 2.16. Looking Forward 27 3. Lists 31 3.1. Conses 31 3.2. Equality 34 3.3. Why Lisp Has No Pointers 34 3.4. Building Lists 36 3.5. Example: Compression 36 3.6. Access 39 3.7. Mapping Functions 40 3.8. Trees 40 3.9. Understanding Recursion 42 3.10. Sets 43 3.11. Sequences 45 3.12. Stacks 47 3.13. Dotted Lists 49 3.14. Assoc-lists 51 3.15. Example: Shortest Path 51 3.16. Garbage 54 4. Specialized Data Structures 58 4.1. 4.2. 4.3. 4.4. 4.5. 4.6. 4.7. 4.8. Arrays 58 Example: Binary Search 60 Strings and Characters 61 Sequences 63 Example: Parsing Dates 66 Structures 69 Example: Binary Search Trees 71 Hash Tables 76 5. Control 81 5.1. Blocks 81 5.2. Context 83 5.3. Conditionals 85 5.4. Iteration 87 5.5. Multiple Values 89 5.6. Aborts 91 xi

xii CONTENTS 5.7. Example: Date Arithmetic 92 6. Functions 99 6.1. Global Functions 99 6.2. Local Functions 101 6.3. Parameter Lists 102 6.4. Example: Utilities 104 6.5. Closures 107 6.6. Example: Function Builders 109 6.7. Dynamic Scope 112 6.8. Compilation 113 6.9. Using Recursion 114 7. Input and Output 119 7.1. Streams 119 7.2. Input 121 7.3. Output 123 7.4. Example: String Substitution 125 7.5. Macro Characters 130 8. Symbols 133 8.1. Symbol Names 133 8.2. Property Lists 134 8.3. Symbols Are Big 135 8.4. Creating Symbols 136 8.5. Multiple Packages 136 8.6. Keywords 137 8.7. Symbols and Variables 138 8.8. Example: Random Text 138 9. Numbers 143 9.1. Types 143 9.2. Conversion and Extraction 144 9.3. Comparison 146 9.4. Arithmetic 147 9.5. Exponentiation 148 9.6. Trigonometric Functions 149 9.7. Representation 150 9.8. Example: Ray-Tracing 151 10. Macros 160 10.1. Eval 160 10.2. Macros 162 10.3. Backquote 163 10.4. Example: Quicksort 164 10.5. Macro Design 165 10.6. Generalized Reference 168 10.7. Example: Macro Utilities 169 10.8. On Lisp 173 11. CLOS 176 11.1. Object-Oriented Programming 176 11.2. Classes and Instances 179 11.3. Slot Properties 179 11.4. Superclasses 181 11.5. Precedence 182 11.6. Generic Functions 184 11.7. Auxiliary Methods 187 11.8. Method Combination 189 11.9. Encapsulation 190 11.10. Two Models 192 12. Structure 195 12.1. Shared Structure 195 12.2. Modification 198 12.3. Example: Queues 200 12.4. Destructive Functions 201 12.5. Example: Binary Search Trees 203 12.6. Example: Doubly-Linked Lists 204 12.7. Circular Structure 208 12.8. Constant Structure 210 13. Speed 213 13.1. The Bottleneck Rule 213 13.2. Compilation 214 13.3. Type Declarations 217 13.4. Garbage Avoidance 222 13.5. Example: Pools 226 13.6. Fast Operators 228 13.7. Two-Phase Development 229

CONTENTS 14. Advanced Topics 232 14.1. Type Specifiers 232 14.2. Binary Streams 234 14.3. Read-Macros 235 14.4. Packages 236 14.5. The Loop Facility 239 14.6. Conditions 244 15. Example: Inference 247 15.1. The Aim 247 15.2. Matching 248 15.3. Answering Queries 251 15.4. Analysis 255 16. Example: Generating HTML 257 16.1. HTML 257 16.2. HTML Utilities 259 16.3. An Iteration Utility 262 16.4. Generating Pages 264 17. Example: Objects 269 17.1. Inheritance 269 17.2. Multiple Inheritance 271 17.3. Defining Objects 273 17.4. Functional Syntax 274 17.5. Defining Methods 275 17.6. Instances 277 17.7. New Implementation 277 17.8. Analysis 284 A. Debugging 287 B. Lisp in Lisp 295 C. Changes to Common Lisp 304 D. Language Reference 310 Notes 401 Index 415

ANSI Common Lisp

Introduction John McCarthy and his students began work on the first Lisp implementation in 1958. After FORTRAN, Lisp is the oldest language still in use.0 What's more remarkable is that it is still in the forefront of programming language technology. Programmers who know Lisp will tell you, there is something about this language that sets it apart. Part of what makes Lisp distinctive is that it is designed to evolve. You can use Lisp to define new Lisp operators. As new abstractions become popular (object-oriented programming, for example), it always turns out to be easy to implement them in Lisp. Like DNA, such a language does not go out of style. 1.1 New Tools Why learn Lisp? Because it lets you do things that you can't do in other languages. If you just wanted to write a function to return the sum of the numbers less than n> say, it would look much the same in Lisp and C: ; Lisp /* C */ (defun sum (n) int aum(int n)< (let ((s 0)) int i , s = 0; (dotimes ( i n s) for( i = 0; i < n; i++) (incf s i ) ) ) ) s += i ; re turn(s) ; If you only need to do such simple things, it doesn't really matter which language you use. Suppose instead you want to write a function that takes a 1

2 INTRODUCTION number n, and returns a function that adds n to its argument: ; Lisp (defun addn (n) #'(lambda (x) (+ x n))) What does addn look like in C? You just can't write it. You might be wondering, when does one ever want to do things like this? Programming languages teach you not to want what they cannot provide. You have to think in a language to write programs in it, and it's hard to want something you can't describe. When I first started writing programs—in Basic—I didn't miss recursion, because I didn't know there was such a thing. I thought in Basic. I could only conceive of iterative algorithms, so why should I miss recursion? If you don't miss lexical closures (which is what's being made in the preceding example), take it on faith, for the time being, that Lisp programmers use them all the time. It would be hard to find a Common Lisp program of any length that did not take advantage of closures. By page 112 you will be using them yourself. And closures are only one of the abstractions we don't find in other languages. Another unique feature of Lisp, possibly even more valuable, is that Lisp programs are expressed as Lisp data structures. This means that you can write programs that write programs. Do people actually want to do this? Yes—they're called macros, and again, experienced programmers use them all the time. By page 173 you will be able to write your own. With macros, closures, and run-time typing, Lisp transcends object- oriented programming. If you understood the preceding sentence, you prob­ ably should not be reading this book. You would have to know Lisp pretty well to see why it's true. But it is not just words. It is an important point, and the proof of it is made quite explicit, in code, in Chapter 17. Chapters 2-13 will gradually introduce all the concepts that you'll need in order to understand the code in Chapter 17. The reward for your efforts will be an equivocal one: you will feel as suffocated programming in C++ as an experienced C++ programmer would feel programming in Basic. It's more encouraging, perhaps, if we think about where this feeling comes from. Basic is suffocating to someone used to C++ because an experienced C++ programmer knows techniques that are impossible to express in Basic. Like­ wise, learning Lisp will teach you more than just a new language—it will teach you new and more powerful ways of thinking about programs.

1.2 NEW TECHNIQUES 3 1.2 New Techniques As the preceding section explained, Lisp gives you tools that other languages don't provide. But there is more to the story than this. Taken separately, the new things that come with Lisp—automatic memory management, man­ ifest typing, closures, and so on—each make programming that much easier. Taken together, they form a critical mass that makes possible a new way of programming. Lisp is designed to be extensible: it lets you define new operators yourself. This is possible because the Lisp language is made out of the same functions and macros as your own programs. So it's no more difficult to extend Lisp than to write a program in it. In fact, it's so easy (and so useful) that extending the language is standard practice. As you're writing your program down toward the language, you build the language up toward your program. You work bottom-up, as well as top-down. Almost any program can benefit from having the language tailored to suit its needs, but the more complex the program, the more valuable bottom-up programming becomes. A bottom-up program can be written as a series of layers, each one acting as a sort of programming language for the one above. TgX was one of the earliest programs to be written this way. You can write programs bottom-up in any language, but Lisp is far the most natural vehicle for this style. Bottom-up programming leads naturally to extensible software. If you take the principle of bottom-up programming all the way to the topmost layer of your program, then that layer becomes a programming language for the user. Because the idea of extensibility is so deeply rooted in Lisp, it makes the ideal language for writing extensible software. Three of the most successful programs of the 1980s provide Lisp as an extension language: Gnu Emacs, Autocad, and Interleaf. Working bottom-up is also the best way to get reusable software. The essence of writing reusable software is to separate the general from the specific, and bottom-up programming inherently creates such a separation. Instead of devoting all your effort to writing a single, monolithic application, you devote part of your effort to building a language, and part to writing a (proportionately smaller) application on top of it. What's specific to this application will be concentrated in the topmost layer. The layers beneath will form a language for writing applications like this one—and what could be more reusable than a programming language? Lisp allows you not just to write more sophisticated programs, but to write them faster. Lisp programs tend to be short—the language gives you bigger concepts, so you don't have to use as many. As Frederick Brooks has pointed out, the time it takes to write a program depends mostly on its length.0 So this fact alone means that Lisp programs take less time to write. The effect is