Structure and Interpretation of Computer Programs

This is a self-paced course in programming.

It is based on Berkley's course delivered in Spring 2011 of the same name.

The target audience are serious programmers looking to advance their knowledge beyond some specific language or technology.

The course itself is based on the highly acclaimed SICP book, considered by many to be one of the most important Computer Science books ever written.

Usage

Fork the repo.

Study each item in sequence, checking off each item as you finish it.

You can use Dr. Racket in SICP compatibility mode to execute the code in the book.

Course overview

Computer science isn’t about computers (that’s electrical engineering) and it isn’t primarily a science (we invent things more than we discover them).

CS is partly a form of engineering (concerned with building reliable, efficient mechanisms, but in software instead of metal) and partly an art form (using programming as a medium for creative expression).

Programming is really easy, as long as you’re solving small problems. Any kid in junior high school can write programs in BASIC, and not just exercises, either; kids do quite interesting and useful things with computers. But BASIC doesn’t scale up; once the problem is so complicated that you can’t keep it all in your head at once, you need help, in the form of more powerful ways of thinking about programming. (But in this course we mostly use small examples, because we’d never get finished otherwise, so you have to imagine how you think each technique would work out in a larger case.)

We deal with three big programming styles/approaches/paradigms:

  • Functional programming (2 months)
  • Object-oriented programming (1 month)
  • Client-server programming (1 week)
  • Logic programming (1 week)

The big idea of the course is abstraction: inventing languages that let us talk more nearly in a problem’s own terms and less in terms of the computer’s mechanisms or capabilities. There is a hierarchy of abstraction:

Application programs
High-level language (Scheme)
Low-level language (C)
Machine language
Architecture (registers, memory, arithmetic unit, etc)
circuit elements (gates)
transistors
solid-state physics
quantum mechanics

We look at lower levels; all are important but we want to start at the highest level to get you thinking right.

Functional Programming

Higher-order procedures

Recursion and iteration

Data abstraction, sequences

Hierarchical data/Scheme interpreter

Generic operators

Object-oriented programming

Local state variables, environments

Mutable data, queues, tables

Client/server paradigm, Concurrency

Streams

Metacircular evaluator

Analyzing evaluator

Lazy evaluator, Nondeterministic evaluator

Logic programming

Review