Structure and Interpretation of Computer Programs

Programming is not only about writing code that works. It is also about understanding how computational processes are structured, how abstractions are built, and how complex systems evolve from simple rules. Learning these principles is essential for anyone studying computer science or aiming to develop robust software systems.

Structure and Interpretation of Computer Programs is widely recognized as a foundational text in computer science education. It explores the intellectual structure of programming through a dialect of Lisp, focusing on abstraction, modeling, and the relationship between programs and machines.

About the book

Structure and Interpretation of Computer Programs (Second Edition) is written by Harold Abelson and Gerald Jay Sussman, with Julie Sussman, and includes a foreword by Alan J. Perlis. This edition is presented in an Unofficial Texinfo Format.

The book uses a dialect of Lisp as its primary language. Rather than focusing on syntax or specific tools, it emphasizes fundamental concepts: abstraction, modularity, evaluation models, state, concurrency, interpreters, compilers, and machine models.

It is intended for students of computer science, self-learners with a serious interest in programming, and developers who want a deeper conceptual understanding of how programs are structured and executed. While prior exposure to programming is helpful, the text develops its ideas progressively and systematically.

What you will learn

The book develops programming as a disciplined method for modeling processes. It introduces abstraction through procedures and data, and then extends these ideas to modular systems with state and objects.

Readers learn how to reason about recursion and iteration, analyze orders of growth, and design higher-order procedures. The text also explores data abstraction, symbolic processing, generic operations, and systems that support multiple representations.

Later chapters examine assignment and state, the environment model of evaluation, concurrency control, streams, and lazy evaluation. The book then moves into metalinguistic abstraction, including the construction of interpreters and evaluators. It concludes with register machines, storage allocation, garbage collection, and compilation.

By working through these topics, readers gain a deeper understanding of:

• How programming languages can be modeled and implemented
• How abstraction manages complexity
• How interpreters and compilers are structured
• How machine-level models relate to high-level programs
• How to design modular and extensible systems

The content is applicable to language design, systems programming, compiler construction, and advanced software engineering.

Table of contents

• Unofficial Texinfo Format
• Dedication
• 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
    • 2.3.4 Example: Huffman Encoding Trees
  • 2.4 Multiple Representations for Abstract Data
    • 2.4.1 Representations for Complex Numbers
    • 2.4.2 Tagged Data
    • 2.4.3 Data-Directed Programming and Additivity
  • 2.5 Systems with Generic Operations
    • 2.5.1 Generic Arithmetic Operations
    • 2.5.2 Combining Data of Different Types
    • 2.5.3 Example: Symbolic Algebra
• 3 Modularity, Objects, and State
  • 3.1 Assignment and Local State
  • 3.2 The Environment Model of Evaluation
  • 3.3 Modeling with Mutable Data
  • 3.4 Concurrency: Time Is of the Essence
  • 3.5 Streams
• 4 Metalinguistic Abstraction
  • 4.1 The Metacircular Evaluator
  • 4.2 Variations on a Scheme — Lazy Evaluation
  • 4.3 Variations on a Scheme — Nondeterministic Computing
  • 4.4 Logic Programming
• 5 Computing with Register Machines
  • 5.1 Designing Register Machines
  • 5.2 A Register-Machine Simulator
  • 5.3 Storage Allocation and Garbage Collection
  • 5.4 The Explicit-Control Evaluator
  • 5.5 Compilation
• References
• List of Exercises
• List of Figures
• Index
• Colophon

Book details

• Title: Structure and Interpretation of Computer Programs (Second Edition)
• Author(s): Harold Abelson and Gerald Jay Sussman, with Julie Sussman; foreword by Alan J. Perlis
• Language: English
• License: Creative Commons Attribution-ShareAlike 3.0 Unported (CC BY-SA 3.0)

More books by language: Programming

---

Legal notice: This book is shared for educational purposes only. The content is distributed under Creative Commons licenses or with explicit permission from the author. FreeProgrammingBooks does not host copyrighted material.