Structure and Interpretation of Computer Programs

---

 

  

[Go to first, previous, next page;   contents;   index]

---

[Go to first, previous, next page;   contents;   index]

                 

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 

[Go to first, previous, next page;   contents;   index]

---

[Go to first, previous, next page;   contents;   index]

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 L

A

T

E

X 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 

[Go to first, previous, next page;   contents;   index]

---

[Go to first, previous, next page;   contents;   index]

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)

[Go to first, previous, next page;   contents;   index]

---

[Go to first, previous, next page;   contents;   index]

 

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

---