Structure and Interpretation of Computer Programs

I used this book for my introductory CompSci class. It was a pretty good book, but I had a hard time understanding some of it. Definitely will require a re-read after I understand a few more things. Here's the table of contents for you viewing pleasure.

Table of Contents:

Contents
Foreword
Preface to the Second Edition 
Preface to the First Edition 
Acknowledgments 
1 Building Abstractions with Procedures 
  1 The Elements of Programming 
    1 Expressions 
    2 Naming and the Environment 
    3 Evaluating Combinations 
    4 Compound Procedures 
    5 The Substitution Model for Procedure Application 
    6 Conditional Expressions and Predicates 
    7 Example: Square Roots by Newton's Method 
    8 Procedures as Black-Box Abstractions 
  2 Procedures and the Processes They Generate 
    1 Linear Recursion and Iteration 
    2 Tree Recursion 
    3 Orders of Growth 
    4 Exponentiation 
    5 Greatest Common Divisors 
    6 Example: Testing for Primality 
  3 Formulating Abstractions with Higher-Order Procedures 
    1 Procedures as Arguments 
    2 Constructing Procedures Using Lambda 
    3 Procedures as General Methods 
    4 Procedures as Returned Values 
2 Building Abstractions with Data 
  1 Introduction to Data Abstraction 
    1 Example: Arithmetic Operations for Rational Numbers 
    2 Abstraction Barriers 
    3 What Is Meant by Data? 
    4 Extended Exercise: Interval Arithmetic 
  2 Hierarchical Data and the Closure Property
 
    1 Representing Sequences 
    2 Hierarchical Structures 
    3 Sequences as Conventional Interfaces 
    4 Example: A Picture Language 
  3 Symbolic Data 
    1 Quotation 
    2 Example: Symbolic Differentiation 
    3 Example: Representing Sets 
    4 Example: Huffman Encoding Trees 
  4 Multiple Representations for Abstract Data 
    1 Representations for Complex Numbers 
    2 Tagged data 
    3 Data-Directed Programming and Additivity 
  5 Systems with Generic Operations 
    1 Generic Arithmetic Operations 
    2 Combining Data of Different Types 
    3 Example: Symbolic Algebra 
3 Modularity, Objects, and State 
  1 Assignment and Local State 
    1 Local State Variables 
    2 The Benefits of Introducing Assignment 
    3 The Costs of Introducing Assignment 
  2 The Environment Model of Evaluation 
    1 The Rules for Evaluation 
    2 Applying Simple Procedures 
    3 Frames as the Repository of Local State 
    4 Internal Definitions 
  3 Modeling with Mutable Data 
    1 Mutable List Structure 
    2 Representing Queues 
    3 Representing Tables 
    4 A Simulator for Digital Circuits 
    5 Propagation of Constraints 
  4 Concurrency: Time Is of the Essence 
    1 The Nature of Time in Concurrent Systems 
    2 Mechanisms for Controlling Concurrency 
  5 Streams 
    1 Streams Are Delayed Lists 
    2 Infinite Streams 
    3 Exploiting the Stream Paradigm 
    4 Streams and Delayed Evaluation 
    5 Modularity of Functional Programs and Modularity
      of Objects 
4 Metalinguistic Abstraction 
  1 The Metacircular Evaluator 
    1 The Core of the Evaluator 
    2 Representing Expressions 
    3 Evaluator Data Structures 
    4 Running the Evaluator as a Program 
    5 Data as Programs 
    6 Internal Definitions 
    7 Separating Syntactic Analysis from Execution 
  2 Variations on a Scheme--Lazy Evaluation 
    1 Normal Order and Applicative Order 
    2 An Interpreter with Lazy Evaluation 
    3 Streams as Lazy Lists 
  3 Variations on a Scheme--Nondeterministic Computing 
    1 Amb and Search 
    2 Examples of Nondeterministic Programs 
    3 Implementing the Amb Evaluator 
  4 Logic Programming 
    1 Deductive Information Retrieval 
    2 How the Query System Works 
    3 Is Logic Programming Mathematical Logic? 
    4 Implementing the Query System 
5 Computing with Register Machines 
  1 Designing Register Machines 
    1 A Language for Describing Register Machines 
    2 Abstraction in Machine Design 
    3 Subroutines 
    4 Using a Stack to Implement Recursion 
    5 Instruction Summary 
  2 A Register-Machine Simulator 
    1 The Machine Model 
    2 The Assembler 
    3 Generating Execution Procedures for Instructions 
    4 Monitoring Machine Performance 
  3 Storage Allocation and Garbage Collection 
    1 Memory as Vectors 
    2 Maintaining the Illusion of Infinite Memory 
  4 The Explicit-Control Evaluator 
    1 The Core of the Explicit-Control Evaluator 
    2 Sequence Evaluation and Tail Recursion 
    3 Conditionals, Assignments, and Definitions 
    4 Running the Evaluator 
  5 Compilation 
    1 Structure of the Compiler 
    2 Compiling Expressions 
    3 Compiling Combinations 
    4 Combining Instruction Sequences 
    5 An Example of Compiled Code 
    6 Lexical Addressing 
    7 Interfacing Compiled Code to the Evaluator 
References 
List of Exercises 
Index

Structure and Interpretation of Computer Programs is probably the best book to read for somebody who already knows a decent amount of programming on a practical level, but would like to grok the idea and theory of programming on a deeper level. That deeper understanding if left to stew will turn into a more subtle and efficient approach to program design and problem solving.

The first section starts out with familair contstructs like simple mathmatical formulas and expressions that are in a way simple programs on their own. It guides the reader through the theory behind evaluating expressions. From there the book takes the reader through more complex constructs, including the ideas of abstraction and recursion. As the book progresses, the reader is coached through the design and implementation of a simple interpreter to evaluate expressions, building up to the idea of creating your own programming language.

The middle portion of the book tackles some problems that illustrate how much flexibility and power can be harnessed by carefully identifying the problem and creating a language that expresses both the problem and the solution. You can see everyday examples of very powerful software created in such a manner if you look at things like Alias Wavefront (a good portion of that is written in Scheme and the user can customize it to no end), emacs (which also uses a variant of Lisp), and sendmail which uses it's own special configuration language to provide the robust and flexible email infrastructure we rely on daily.

The final portion of the book takes all the things we've learned so far and puts them together and in so doing prepares us to go full circle and end up back and the very beginning of computing itself, but this time with a much deeper understanding. In this section the book takes us through the design of a simple logic simulator that contains the building blocks of a modern register machine (a CPU). The simulator is programmed through an input file that contains a list of functional blocks and their interconnections. The book shows us that a complex enough input file for that simulator will generate a simple processor. Once we have our CPU, we next write an assembler to create programs for the simulated proccessor. The final task is to write a compiler for the virtual machine that we have just constructed, which will take a high level language and turn it into our assembly language, which once assembled can be run using our simulated processor.

The beauty of this approach to teaching the basics of programming is that it is very well rounded. The neat thing about this book is that it starts out with concrete stuff that pretty much anybody can grasp, and works its way towards the theoretical problems while still providing concrete examples. I would say that any programmer with the time should give this book a read (or several) because it will save you the time it took to read many times over in the course of your work, and that aside, it's fun and well written.

As sketerpot points out, the entire book is online for public use at the following URL: http://mitpress.mit.edu/sicp/