CS21b: Structure and Interpretation of Computer Programs

CS21b (Spring 2012): 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: Tuesday and Friday 10-11am, 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:

Hui Qi, email.

Class Information

PROBLEM SETS

Submission Guidelines

  • Problem Set 1: Lunar Lander (due February 7). pdf required Scheme code
  • Problem Set 2: Computer Psychiatrist (due March 2). pdf required Scheme code
  • Problem Set 3: Stable Marriage (due March 16). pdf required Scheme code
  • Problem Set 4: Stream Processing (due March 23). pdf required Scheme code
  • Problem Set 5: Metacircular Evaluator (due April 17). pdf required Scheme code normal order Scheme evaluator
  • Problem Set 6: Metacircular Compiler (due May 1). pdf required Scheme code

    Handouts

  • Symbolic differentiation and pattern matching
  • Syntactic sugar: making the language you want
  • Separating syntactic analysis from execution
  • An explicit-control metacircular evaluator
  • Explicit-control metacircular evaluator: example calculations
  • Lexical addressing and the compile-time environment
  • A register machine compiler

    Lecture notes

  • Introduction
  • Cursing, and recursing
  • Higher Order Procedures
  • Picture language
  • Data with Destiny
  • Binomial priority queues
  • I am the state
  • Dining philosophers
  • Stream processing
  • Scheme, in Scheme: Metacircular Evaluator
  • Dynamic Binding and Normal-order Evaluation