CS21b: Structure and Interpretation of Computer Programs

CS21b (Autumn 2008): Structure and Interpretation of Computer Programs

"There are only 5 ideas in Computer Science, and by the time you finish this course, you will know 3 of them."

Course instructor: Harry Mairson (Volen 257, x2724, mairson@cs). Office hours: Monday and Wednesday 12-1pm, and by arrangement. If you can't make these hours, drop by another time--I'm flexible, and usually in. I promise to talk to you during office hours, and I probably will anyways if it's another time.

TA:

Matthew Goldfield, email, x6-2728, Volen 136. Office hours: Tuesday and Thursday, 12-1.30pm, and by appointment.

Class Information

Fact sheet for course, including day-by-day course syllabus, assignment and due dates for problem sets, etc. pdf
Home page at the MIT Press containing the full text for the course textbook, as well as supplementary material: Structure and Interpretation of Computer Programs, by Hal Abelson and Gerry Sussman, including code for all examples and exercises.
New to MITScheme? You might find the MIT Scheme User's Manual helpful!
Curious for the nitty, gritty details of a specific procedure? Look it up in the MIT Scheme Reference (index).
Online documentation on the Scheme programming language used in the course.
The Scheme Underground. Question: where does "I am not a Church numeral---I am a free variable!" come from?
John's MITScheme Quickstart
Example on using the Scheme debugger (HTML)
Documentation on the Scheme debugger: quick introduction and manual
Comparison of recursion and iteration: elegance vs. speed: Scheme code

PROBLEM SETS

Submission Guidlines

Problem Set 1: Lunar Lander (due September 17). pdf required Scheme code

Problem Set 2: Computer Psychiatrist (due October 13). pdf required Scheme code

Problem Set 3: Stable Marriage (due October 30). pdf required Scheme code

Problem Set 4: Streams (due November 5). pdf required Scheme code

Problem Set 5: Metacircular Evaluator (due November 19). pdf required Scheme code normal order Scheme evaluator

Problem Set 6: Metacircular Compiler (due December 8). pdf required Scheme code

Handouts

Symbolic differentiation: procedural and data representations of knowledge

Syntactic sugar: making the language you want

An explicit-control metacircular evaluator

Explicit-control metacircular evaluator: example calculations

Separating syntactic analysis from execution

Lexical addressing and the compile-time environment

A register machine compiler

Lecture notes

Introduction

Cursing, and Recursing

Higher Order Procedures: what is that lambda thing?

Data with Destiny

L'Etat, c'est moi: State and the Environment Model

Dining philsophers: object oriented programming as state and message passing.

Don't cross the streams! Stream processing

Scheme, in Scheme: Metacircular Evaluator

Dynamic Binding and Normal-order Evaluation