Structure And Interpretation Of Computer Programs

A classic. Recommended book found in TYCS.

For updates see: SICP_logs

1 Building Abstractions With Procedures

1.1 Elements of Programming

Some fundamental keywords, as they relate to scheme.

Procedures, combinations, special forms, etc.

Case study: Square Roots by Newton's method. The point here is to start with a mathematical definition, then turn it into a structure of procedures.

1.2 Procedures and Processes

Linear recursion and iteration.

Tree recursion: process evolution looks like a tree.

Orders of growth (space vs time).

Case studies such as: exponentiation and GCD. Explore linear recursive vs iterative processes, and analyze growth.

1.3 Formulating abstractions with higher-order procedures

Introducing things like let, lambda, etc.

They make a parallel between higher-order functions and the sigma notation in Mathematics. Some sequences are explored.

Various sequences are explored: sum of cubes, pi/8 sum, sum of integers (using identity function).

Case study: finding roots of equations using half-interval method.

2 Building Abstractions With Data

2.1 Introduction to Data Abstraction

Introduces the idea of compound data objects. Uses rational number type as an initial example. Abstraction barriers. cons, car, and cdr get re-implemented in scheme (wow!).

2.2 Hierarchical Data and the Closure Property

The sequence, and how they are represented in Scheme as cons's (aka a linked list). Introduction to list operations. Mapping over lists. Hierarchical structures (aka Trees). Mapping over trees. Sequence operations (like how a DSP engineer would think). "Picture language" used as a visual way to synthesize complex operations from a core set of primitives using high-order operations.

2.3 Symbolic Data

The quote operator. Symbolic algebra. Abstract data. Implementations of Binary trees. Huffman encoding and huffman trees.

2.4 Multiple Representations for Abstract Data

Example used: complex numbers, and how they can be represented differently (this may be in 2.5?) (this may be in 2.5?). Builds up abstractions for how to manage complex number operations. Dispatching on Type. Generic interfaces. Data-directed programming.

2.5 Systems with Generic Operations

More on generic systems using compelx numbers as example. Hierarchies of types. Inadequacies of hierarchies.

I "super-skimmed" 2.5.3 section on symbolic algebra, as it was very math-oriented and not really interesting to me.

3 Modularity, Objects, and State

3.1 Assignment and Local State

Introducing set! using a bank acount withdraw as an example. Using local state to make different instances of withdraw. Building a stateful RNG and using it in monte-carlo simulations (showcasing how it simplifies code). Downfalls of assignment/state: can not use substitution like previous chapters. Programming without assignment: functional programming. Samness.

3.2 The Environment Model of Evaluation

Variables as "places" instead of values. Analysis of Environments used in simple procedures like square and sum-of-squares. Analysis of make-withdraw. Internal defitions in environments. Sharing and identity. Mutation=assignment.

3.3 Modeling with Mutable Data

Queues. Tables: one and two dimensions. Local tables with separate lookup and insert for each table. Digital circuit simulator implementation: logic, wires, agenda, constraints.

3.4 Concurrency: Time is of the Essence

TBD.

3.5 Streams

TBD.

4 Metalinguistic Abstraction

4.1 The metacircular environment

TBD.

4.2 Variations on a Scheme -- Lazy Evaluation

TBD.

4.3 Variations on a Scheme -- Nondeterministic Computing

TBD.

4.4 Logic Programming

TBD.

5 Computing with Register Machines

5.1 Designing Register Machines

TBD.

5.2 A Register-Machine Simulator

TBD.

5.3 Storage Allocation and Garbage Collection

TBD.

5.4 The Explict-Control Evaluator

TBD.

5.5 Compilation

TBD.