1
Structure and Interpretation
of Computer Programs
second edition
Harold Abelson and Gerald Jay Sussman
with Julie Sussman
foreword by Alan J. Perlis
The MIT Press
Cambridge, Massachusetts London, England
McGraw-Hill Book Company
New York St. Louis San Francisco Montreal Toronto
2
This book is one of a series of texts written by faculty of the Electrical Engineering and Computer
Science Department at the Massachusetts Institute of Technology. It was edited and produced by
The MIT Press under a joint production-distribution arrangement with the McGraw-Hill Book
Company.
Ordering Information:
North America
Text orders should be addressed to the McGraw-Hill Book Company.
All other orders should be addressed to The MIT Press.
Outside North America
All orders should be addressed to The MIT Press or its local distributor.
© 1996 by The Massachusetts Institute of Technology
Second edition
All rights reserved. No part of this book may be reproduced in any form or by any electronic or
mechanical means (including photocopying, recording, or information storage and retrieval)
without permission in writing from the publisher.
This book was set by the authors using the LATEX typesetting system and was printed and bound
in the United States of America.
Library of Congress Cataloging-in-Publication Data
Abelson, Harold
Structure and interpretation of computer programs / Harold Abelson
and Gerald Jay Sussman, with Julie Sussman. -- 2nd ed.
p. cm. -- (Electrical engineering and computer science
series)
Includes bibliographical references and index.
ISBN 0-262-01153-0 (MIT Press hardcover)
ISBN 0-262-51087-1 (MIT Press paperback)
ISBN 0-07-000484-6 (McGraw-Hill hardcover)
1. Electronic digital computers -- Programming. 2. LISP (Computer
program language) I. Sussman, Gerald Jay. II. Sussman, Julie.
III. Title. IV. Series: MIT electrical engineering and computer
science series.
QA76.6.A255 1996
005.13'3 -- dc20 96-17756
Fourth printing, 1999
3
This book is dedicated, in respect and admiration, to the spirit that lives in the computer.
``I think that it's extraordinarily important that we in computer science keep fun in computing.
When it started out, it was an awful lot of fun. Of course, the paying customers got shafted every
now and then, and after a while we began to take their complaints seriously. We began to feel as if
we really were responsible for the successful, error-free perfect use of these machines. I don't think
we are. I think we're responsible for stretching them, setting them off in new directions, and keeping
fun in the house. I hope the field of computer science never loses its sense of fun. Above all, I hope
we don't become missionaries. Don't feel as if you're Bible salesmen. The world has too many of
those already. What you know about computing other people will learn. Don't feel as if the key to
successful computing is only in your hands. What's in your hands, I think and hope, is intelligence:
the ability to see the machine as more than when you were first led up to it, that you can make it
more.''
Alan J. Perlis (April 1, 1922-February 7, 1990)
4
Contents
Foreword
Preface to the Second Edition
Preface to the First Edition
Acknowledgments
1 Building Abstractions with Procedures
1.1 The Elements of Programming
1.1.1 Expressions
1.1.2 Naming and the Environment
1.1.3 Evaluating Combinations
1.1.4 Compound Procedures
1.1.5 The Substitution Model for Procedure Application
1.1.6 Conditional Expressions and Predicates
1.1.7 Example: Square Roots by Newton's Method
1.1.8 Procedures as Black-Box Abstractions
1.2 Procedures and the Processes They Generate
1.2.1 Linear Recursion and Iteration
1.2.2 Tree Recursion
1.2.3 Orders of Growth
1.2.4 Exponentiation
1.2.5 Greatest Common Divisors
1.2.6 Example: Testing for Primality
1.3 Formulating Abstractions with Higher-Order Procedures
1.3.1 Procedures as Arguments
1.3.2 Constructing Procedures Using Lambda
1.3.3 Procedures as General Methods
1.3.4 Procedures as Returned Values
2 Building Abstractions with Data
2.1 Introduction to Data Abstraction
2.1.1 Example: Arithmetic Operations for Rational Numbers
2.1.2 Abstraction Barriers
2.1.3 What Is Meant by Data?
2.1.4 Extended Exercise: Interval Arithmetic
2.2 Hierarchical Data and the Closure Property
2.2.1 Representing Sequences
2.2.2 Hierarchical Structures
2.2.3 Sequences as Conventional Interfaces
2.2.4 Example: A Picture Language
2.3 Symbolic Data
2.3.1 Quotation
2.3.2 Example: Symbolic Differentiation
2.3.3 Example: Representing Sets
5
