Structure and Interpretation of Computer Programs by Harold Abelson and Gerald Jay Sussman with Julie Sussman -- Read -- Imperial Library of Trantor

Index

Structure and Interpretation of Computer Programs Chapter 1

Programming in Lisp 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

Applicative order versus normal order

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

Local names Internal definitions and block structure

1.2 Procedures and the Processes They Generate

1.2.1 Linear Recursion and Iteration 1.2.2 Tree Recursion

Example: Counting change

1.2.3 Orders of Growth 1.2.4 Exponentiation 1.2.5 Greatest Common Divisors 1.2.6 Example: Testing for Primality

Searching for divisors The Fermat test Probabilistic methods

1.3 Formulating Abstractions with Higher-Order Procedures

1.3.1 Procedures as Arguments 1.3.2 Constructing Procedures Using Lambda

Using let to create local variables

1.3.3 Procedures as General Methods

Finding roots of equations by the half-interval method Finding fixed points of functions

1.3.4 Procedures as Returned Values

Newton's method Abstractions and first-class procedures

Chapter 2

2.1 Introduction to Data Abstraction

2.1.1 Example: Arithmetic Operations for Rational Numbers

Pairs Representing 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

List operations Mapping over lists

2.2.2 Hierarchical Structures

Mapping over trees

2.2.3 Sequences as Conventional Interfaces

Sequence Operations Nested Mappings

2.2.4 Example: A Picture Language

The picture language Higher-order operations Frames Painters Transforming and combining painters Levels of language for robust design

2.3 Symbolic Data

2.3.1 Quotation 2.3.2 Example: Symbolic Differentiation

The differentiation program with abstract data Representing algebraic expressions

2.3.3 Example: Representing Sets

Sets as unordered lists Sets as ordered lists Sets as binary trees Sets and information retrieval

2.3.4 Example: Huffman Encoding Trees

Generating Huffman trees Representing Huffman trees The decoding procedure Sets of weighted elements

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

Message passing

2.5 Systems with Generic Operations

2.5.1 Generic Arithmetic Operations 2.5.2 Combining Data of Different Types

Coercion Hierarchies of types Inadequacies of hierarchies

2.5.3 Example: Symbolic Algebra

Arithmetic on polynomials Representing term lists Hierarchies of types in symbolic algebra Extended exercise: Rational functions

Chapter 3

3.1 Assignment and Local State

3.1.1 Local State Variables 3.1.2 The Benefits of Introducing Assignment 3.1.3 The Costs of Introducing Assignment

Sameness and change Pitfalls of imperative programming

3.2 The Environment Model of Evaluation

3.2.1 The Rules for Evaluation 3.2.2 Applying Simple Procedures 3.2.3 Frames as the Repository of Local State 3.2.4 Internal Definitions

3.3 Modeling with Mutable Data

3.3.1 Mutable List Structure

Sharing and identity Mutation is just assignment

3.3.2 Representing Queues 3.3.3 Representing Tables

Two-dimensional tables Creating local tables

3.3.4 A Simulator for Digital Circuits

Primitive function boxes Representing wires The agenda A sample simulation Implementing the agenda

3.3.5 Propagation of Constraints

Using the constraint system Implementing the constraint system Representing connectors

3.4 Concurrency: Time Is of the Essence

3.4.1 The Nature of Time in Concurrent Systems

Correct behavior of concurrent programs

3.4.2 Mechanisms for Controlling Concurrency

Serializing access to shared state Serializers in Scheme Complexity of using multiple shared resources Implementing serializers Deadlock Concurrency, time, and communication

3.5 Streams

3.5.1 Streams Are Delayed Lists

The stream implementation in action Implementing delay and force

3.5.2 Infinite Streams

Defining streams implicitly

3.5.3 Exploiting the Stream Paradigm

Formulating iterations as stream processes Infinite streams of pairs Streams as signals

3.5.4 Streams and Delayed Evaluation

Normal-order evaluation

3.5.5 Modularity of Functional Programs and Modularity of Objects

A functional-programming view of time

Chapter 4

4.1 The Metacircular Evaluator

4.1.1 The Core of the Evaluator

Eval

Primitive expressions Special forms Combinations

Apply Procedure arguments Conditionals Sequences Assignments and definitions

4.1.2 Representing Expressions

Derived expressions

4.1.3 Evaluator Data Structures

Testing of predicates Representing procedures Operations on Environments

4.1.4 Running the Evaluator as a Program 4.1.5 Data as Programs 4.1.6 Internal Definitions 4.1.7 Separating Syntactic Analysis from Execution

4.2 Variations on a Scheme – Lazy Evaluation

4.2.1 Normal Order and Applicative Order 4.2.2 An Interpreter with Lazy Evaluation

Modifying the evaluator Representing thunks

4.2.3 Streams as Lazy Lists

4.3 Variations on a Scheme – Nondeterministic Computing

4.3.1 Amb and Search

Driver loop

4.3.2 Examples of Nondeterministic Programs

Logic Puzzles Parsing natural language

4.3.3 Implementing the Amb Evaluator

Execution procedures and continuations Structure of the evaluator Simple expressions Conditionals and sequences Definitions and assignments Procedure applications Evaluating amb expressions Driver loop

4.4 Logic Programming

4.4.1 Deductive Information Retrieval

A sample data base Simple queries Compound queries Rules Logic as programs

4.4.2 How the Query System Works

Pattern matching Streams of frames Compound queries Unification Applying rules Simple queries The query evaluator and the driver loop

4.4.3 Is Logic Programming Mathematical Logic?

Infinite loops Problems with not

4.4.4 Implementing the Query System

4.4.4.1 The Driver Loop and Instantiation 4.4.4.2 The Evaluator Simple queries Compound queries Filters 4.4.4.3 Finding Assertions by Pattern Matching Patterns with dotted tails 4.4.4.4 Rules and Unification 4.4.4.5 Maintaining the Data Base 4.4.4.6 Stream Operations 4.4.4.7 Query Syntax Procedures 4.4.4.8 Frames and Bindings

Chapter 5

5.1 Designing Register Machines

5.1.1 A Language for Describing Register Machines

Actions

5.1.2 Abstraction in Machine Design 5.1.3 Subroutines 5.1.4 Using a Stack to Implement Recursion

A double recursion

5.1.5 Instruction Summary

5.2 A Register-Machine Simulator

5.2.1 The Machine Model

Registers The stack The basic machine

5.2.2 The Assembler 5.2.3 Generating Execution Procedures for Instructions

Assign instructions Test, branch, and goto instructions Other instructions Execution procedures for subexpressions

5.2.4 Monitoring Machine Performance

5.3 Storage Allocation and Garbage Collection

5.3.1 Memory as Vectors

Representing Lisp data Implementing the primitive list operations Implementing stacks

5.3.2 Maintaining the Illusion of Infinite Memory

Implementation of a stop-and-copy garbage collector

5.4 The Explicit-Control Evaluator

Registers and operations 5.4.1 The Core of the Explicit-Control Evaluator

Evaluating simple expressions Evaluating procedure applications Procedure application

5.4.2 Sequence Evaluation and Tail Recursion

Tail recursion

5.4.3 Conditionals, Assignments, and Definitions

Assignments and definitions

5.4.4 Running the Evaluator

Monitoring the performance of the evaluator

5.5 Compilation

An overview of the compiler 5.5.1 Structure of the Compiler

Targets and linkages Instruction sequences and stack usage

5.5.2 Compiling Expressions

Compiling linkage code Compiling simple expressions Compiling conditional expressions Compiling sequences Compiling lambda expressions

5.5.3 Compiling Combinations

Applying procedures Applying compiled procedures

5.5.4 Combining Instruction Sequences 5.5.5 An Example of Compiled Code 5.5.6 Lexical Addressing 5.5.7 Interfacing Compiled Code to the Evaluator

Interpretation and compilation

← Prev
Back
Next →

← Prev
Back
Next →