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

[ ] Read Section 1.1: The Elements of Programming

[ ] Watch Computer Science 61A - Lecture 1: functional programming 1

[ ] Watch Computer Science 61A - Lecture 2: functional programming 2

Higher-order procedures

[ ] Read Section 1.3: Formulating Abstractions with Higher-Order Procedures

[ ] Watch Computer Science 61A - Lecture 3: higher-order procedures 1

[ ] Watch Computer Science 61A - Lecture 4: higher-order procedures 2

Recursion and iteration

[ ] Read Section 1.2-1.2.4: Procedures and the Processes They Generate

[ ] Watch Computer Science 61A - Lecture 7: orders of growth

[ ] Watch Computer Science 61A - Lecture 8: recursion and iteration

Data abstraction, sequences

[ ] Read Section 2.2.1: Representing Sequences

[ ] Watch Computer Science 61A - Lecture 9: data abstraction

[ ] Read Sections 2.1: Introduction to Data Abstraction

[ ] Watch Computer Science 61A - Lecture 10: sequences

[ ] Watch Computer Science 61A - Lecture 11: Example: calculato

Hierarchical data/Scheme interpreter

[ ] Read Section 2.2.2: Hierarchical Structures

[ ] Read Section 2.2.3: Sequences as Conventional Interfaces

[ ] Read Section 2.3.1: Quotation

[ ] Read Section 2.3.3 Example: Representing Sets

[ ] Watch Computer Science 61A - Lecture 12: hierarchical data

[ ] Watch Computer Science 61A - Lecture 13: hierarchical data

[ ] Watch Computer Science 61A - Lecture 14: Example: Scheme-1 interpreter

Generic operators

[ ] Read Section 2.4: Multiple Representations for Abstract Data

[ ] Read Section 2.5 (through 2.5.2): Systems with Generic Operations

[ ] Watch Computer Science 61A - Lecture 16: generic operators

[ ] Watch Computer Science 61A - Lecture 17: generic operators

Object-oriented programming

[ ] Read Object-Oriented Programming | Above the line view

[ ] Watch Computer Science 61A - Lecture 18: object-oriented programming

[ ] Watch Computer Science 61A - Lecture 19: object-oriented programming

[ ] Watch Computer Science 61A - Lecture 20: object-oriented programming

Local state variables, environments

[ ] Read Section 3.1: Assignment and Local State

[ ] Read Section 3.2: The Environment Model of Evaluation

[ ] Read Object-Oriented Programming | Below the line view

[ ] Watch Computer Science 61A - Lecture 21: assignment and state

[ ] Watch Computer Science 61A - Lecture 22: environments

[ ] Watch Computer Science 61A - Lecture 23: environments

Mutable data, queues, tables

[ ] Read Sections 3.3.1-3.3.3

[ ] Watch Computer Science 61A - Lecture 24: mutable data

[ ] Watch Computer Science 61A - Lecture 25: mutable data

[ ] Watch Computer Science 61A - Lecture 26: vectors

Client/server paradigm, Concurrency

[ ] Read Section 3.4: Concurrency: Time Is of the Essence

[ ] Watch Computer Science 61A - Lecture 30: client-server programming

[ ] Watch Computer Science 61A - Lecture 31: concurrency

[ ] Watch Computer Science 61A - Lecture 32: concurrency

Streams

[ ] Read Section 3.5.1-3.5.3

[ ] Read Section 3.5.5: Modularity of Functional Programs and Modularity of Objects

[ ] Watch Computer Science 61A - Lecture 33: streams

[ ] Watch Computer Science 61A - Lecture 34: streams

[ ] Watch Computer Science 61A - Lecture 35: Therac-25

Metacircular evaluator

[ ] Read Section 4.1: The Metacircular Evaluator

[ ] Watch Computer Science 61A - Lecture 36: metacircular evaluator

[ ] Watch Computer Science 61A - Lecture 37: metacircular evaluator

[ ] Watch Computer Science 61A - Lecture 38: mapreduce

[ ] Watch Computer Science 61A - Lecture 39: mapreduce

Analyzing evaluator

[ ] Watch Computer Science 61A - Lecture 40: analyzing evaluator

Lazy evaluator, Nondeterministic evaluator

[ ] Read Section 4.2: Variations on a Scheme -- Lazy Evaluation

[ ] Read Section 4.3: Variations on a Scheme -- Nondeterministic Computing

[ ] Watch Computer Science 61A - Lecture 41: lazy evaluator

Logic programming

[ ] Read Section 4.4.1-4.43

[ ] Watch Computer Science 61A - Lecture 42: logic programming

[ ] Watch Computer Science 61A - Lecture 43: logic programming

Review

[ ] Watch Computer Science 61A - Lecture 44: Review