# Structure and Interpretation of Computer Programs

## by Harold Abelson and Gerald Jay Sussman with Julie Sussman

1 Building Abstractions with Procedures

1.1 The Elements of Programming

1.2 Procedures and the Processes They Generate

2 Building Abstractions with Data

2.1 Introduction to Data Abstraction

2.1.4 Extended Exercise: Interval Arithmetic

show exercises

show exercises

- 2.7 Upper and lower bounds of interval
- 2.8 Subtraction of intervals
- 2.9 The width of an interval
- 2.10 Interval that spans zero
- 2.11 The signs of the endpoints of the intervals
- 2.12 Interval produced by center and percentage tolerance
- 2.13 Percentage tolerance of the product of two intervals
- 2.14 Different answers for the two ways of computing formulas for parallel resistors
- 2.15 A form of formula that no variable that represents an uncertain number is repeated
- 2.16 Different answers in equivalent algebraic expressions in general

2.2 Hierarchical Data and the Closure Property

2.3 Symbolic Data

2.3.3 Example: Representing Sets

show exercises

show exercises

- 2.59 Union-set for sets represented as unordered lists
- 2.60 Set with duplicates
- 2.61 Adjoin-set for the ordered representation
- 2.62 Union-set for for sets represented as ordered lists
- 2.63 Converting a binary tree to a list
- 2.64 Partial-tree procedure
- 2.65 Procedures for sets implemented as (balanced) binary trees
- 2.66 Lookup procedure

2.5 Systems with Generic Operations

2.5.3 Example: Symbolic Algebra

show exercises

show exercises

- 2.87 =zero? for polynomials
- 2.88 Subtraction of polynomials
- 2.89 Procedures for dense polynomials
- 2.90 Generic operations on term lists
- 2.91 Division of univariate polynomial
- 2.92 Addition and multiplication of polynomials with different variables
- 2.93 Generic operations in rational-arithmetic package
- 2.94 Generic operation
- 2.95 Pseudodivision
- 2.96 Integerizing factor
- 2.97 Algorithm as a procedure

3 Modularity, Objects, and State

3.1 Assignment and Local State

3.3 Modeling with Mutable Data

3.4 Concurrency: Time Is of the Essence

3.4.2 Mechanisms for Controlling Concurrency

show exercises

show exercises

- 3.39 Remaining possibilities
- 3.40 All possible values of x
- 3.41 Serialized make-account
- 3.42 Make-account changing
- 3.43 Timing diagrams
- 3.44 The problem of transferring an amount from one account to another
- 3.45 Redefine accounts
- 3.46 Draw a timing diagram
- 3.47 Implementations of semaphores
- 3.48 Serialized-exchange with the deadlock-avoidance method
- 3.49 Scenario where the deadlock-avoidance mechanism does not work

3.5 Streams

3.5.2 Infinite Streams

show exercises

show exercises

- 3.53 Description of the elements of the stream
- 3.54 Mul-streams procedure
- 3.55 Partial-sums procedure
- 3.56 Hamming's problem of number generation
- 3.57 Additions in computing Fibonacci numbers.
- 3.58 An interpretation of the stream
- 3.59 Power series represented as infinite streams
- 3.60 Procedure for multiplying series
- 3.61 Invert-unit-series procedure
- 3.62 Div-series procedure

3.5.3 Exploiting the Stream Paradigm

show exercises

show exercises

- 3.63 Efficient of the sqrt-stream procedure
- 3.64 Stream-limit procedure
- 3.65 Three sequences of approximations to the natural logarithm of 2
- 3.66 Order of pairs in the stream
- 3.67 Modification of pairs
- 3.68 Alternative definition of pairs
- 3.69 Triples procedure
- 3.70 Weighting function
- 3.71 Ramanujan numbers
- 3.72 A stream of numbers that can be written as the sum of two squares
- 3.73 An RC circuit
- 3.74 Zero crossings
- 3.75 Signal smoothing
- 3.76 Smooth procedure

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.3.2 Examples of Nondeterministic Programs

show exercises

show exercises

- 4.38 Modify the multiple-dwelling procedure
- 4.39 The order of the restrictions in the multiple-dwelling
- 4.40 Efficiency of generating possibilities
- 4.41 Solve the multiple dwelling puzzle
- 4.42 Solve the "Liars" puzzle
- 4.43 Who is Lorna's father?
- 4.44 A nondeterministic program to solve ''eight-queens puzzle''
- 4.45 Five different ways of sentence parsing
- 4.46 Order of operands evaluation
- 4.47 Alternative variant of parse-verb-phrase
- 4.48 The grammar extension
- 4.49 Sentences generating

4.4 Logic Programming

4.4.4 Implementing the Query System

4.4.4.8 Frames and Bindings

show exercises

show exercises

- 4.71 Explicit delay in the simple-query and disjoin procedures
- 4.72 Streams interleaving
- 4.73 Explicit delay in flatten-stream
- 4.74 A simpler version of stream-flatmap
- 4.75 A new special form - unique
- 4.76 Separate processing the two clauses of the 'and'
- 4.77 The filtering in a ''delayed'' manner
- 4.78 The query language as a nondeterministic program
- 4.79 A rule-application method that uses environments

5 Computing with Register Machines

5.1 Designing Register Machines

show exercises

show exercises

5.2 A Register-Machine Simulator

show exercises

show exercises

5.4 The Explicit-Control Evaluator

5.5 Compilation

5.5.5 An Example of Compiled Code

show exercises

show exercises

- 5.33 Сompare the resulting code of a factorial procedure
- 5.34 The essential difference between the code for iterative and recursive versions of factorial
- 5.35 An example of compiler output
- 5.36 Order of evaluation of compiler
- 5.37 Compiler's preserving mechanism
- 5.38 Support open coding of selected primitives

5.5.6 Lexical Addressing

show exercises

show exercises

- 5.39 lexical-address-lookup and lexical-address-set! procedures
- 5.40 Compile-time environment maintaining
- 5.41 Find-variable procedure
- 5.42 Compile-variable and compile-assignment with lexical-address instructions
- 5.43 The compiler and internal definitions
- 5.44 Modification of the open-coding compiler

5.5.7 Interfacing Compiled Code to the Evaluator

show exercises

show exercises

- 5.45 The quality of the compiler
- 5.46 The effectiveness of compiling the tree-recursive Fibonacci procedure
- 5.47 Modifying evaluator
- 5.48 Compile-and-run primitive
- 5.49 Register machine
- 5.50 Metacircular evaluator
- 5.51 Rudimentary implementation of Scheme in C
- 5.52 Scheme compiler into C instructions