CS21b: Structure and Interpretation of Computer Programs

CS21b (Spring 2017): 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, email). Office hours: T and F 11am-12pm, 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.

TAs:

Karishma Reddy Khan, email (Office hours 11-12 MW)
Prakhar Sahay, email (Office hours 12-1 MTW)
Kelley Lynch, email (Office hours 2-3 MTWTh)
The TAs run office hours in the Vertica lounge.


Class Information


PROBLEM SETS

  • Problem Set 1: Lunar Lander (due February 7). pdf required Scheme code
  • Problem Set 2: Computer Psychiatrist (due March 3). pdf required Scheme code
  • Problem Set 3: Stable Marriage (due March 14). pdf required Scheme code
  • Problem Set 4: Streams (due March 28). pdf required Scheme code
  • Problem Set 5: Metacircular evaluator (due April 21). pdf required Scheme code normal order evaluator
  • Problem Set 6: Metacircular Compiler (due May 2). pdf required Scheme code

    Lecture notes

  • Introduction ppt key
  • Cursing, and recursing ppt key
  • Higher order procedures ppt key
  • Picture language ppt key
  • Data ppt key
  • Binomial queues ppt key
  • Symbolic differentiation and pattern matching: steps towards the interpreter pdf Scheme code
  • State ppt key
  • Dining philosophers (an exercise in state and message passing) ppt key
  • Streams ppt key
  • Metacircular evaluator ppt key
  • Variations on the basic metacircular evaluator ppt key
  • Syntactic sugar
  • Separating syntactic analysis from execution
  • An explicit-control metacircular evaluator
  • Relating the "ordinary" and explicit-control metacircular evaluator
  • Lexical addressing
  • Register machine compiler