CS21b: Structure and Interpretation of Computer Programs

CS21b (Spring 2019): 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: M W Th 11am-12pm, and by arrangement. If you can't make these hours, send me an email to set up an alternative meeting. I promise to talk to you during office hours, and I probably will anyways if it's another time.


Joel Richter, Head TA email
TAs and office hours:

  • Monday 1:30-3:30 (Brian Gao email )
  • Monday 3:30-5 (Nathaniel Dimick email )
  • Tuesday 11-12 and 1-3: (Luyi Bai email )
  • Wednesday 2-5: (Mark Hutchens email )
  • Thursday 12-3 (Joel Richter)
  • Thursday 3:30-5 (Nathaniel Dimick)
  • Friday 10-11 (Brian Gao)
  • Friday 2-5 (Kevin Zhou email)
    The TAs run office hours in the Vertica lounge.

    Class Information


  • Problem Set 1: Lunar Lander (due February 4). pdf required Scheme code
  • Problem Set 2: Computer Psychiatrist (due February 27). pdf required Scheme code
  • Problem Set 3: Stable Marriage (due March 13). pdf required Scheme code
  • Problem Set 4: Streams (due March 21). pdf required Scheme code
  • Problem Set 5: Metacircular evaluator (due April 8). pdf required Scheme code normal order evaluator
  • Problem Set 6: Metacircular Compiler (due May 1). 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 Priority Queues ppt key
  • Symbolic differentiation and pattern matching: steps towards the interpreter pdf Scheme code
  • State ppt key
  • Streams ppt key
  • Metacircular evaluator ppt key
  • Dynamic binding and normal order evaluation ppt key
  • Syntactic sugar
  • Lexical analysis and parsing for Scheme
  • Separating syntactic analysis from execution
  • An explicit-control metacircular evaluator
  • Some example evaluations with the explicit control evaluator
  • Lexical addressing
  • Register machine compiler