Schedule

Aug-31 - Sep-06

• Assignments:
  • Assignment 1: Racket Recursion and Higher-Order List Programming: Assigned on Mon, Aug 31 | Assignment
• Mon, Aug 31 Lecture: Racket, recursion, and higher-order list programming
  • Topics:
    • Course orientation and the interpreter-to-compiler arc
    • Natural recursion over lists
    • Functions as values; map, filter, and procedural abstraction
  • Preparation:
    • 📖 Course syllabus
• Wed, Sep 02 Lecture: letrec, quasiquote, and match
  • Topics:
    • Recursive local bindings
    • Quasiquotation and unquotation for constructing syntax
    • Structural pattern matching over Racket data

Sep-07 - Sep-13

• Assignments:
  • Assignment 2: Free and Bound Variables and Lexical Address: Assigned on Mon, Sep 07 | Assignment
• Mon, Sep 07 Lecture: No class — Labor Day (University closed)
• Wed, Sep 09 Lecture: Free and bound variables; lexical address
  • Topics:
    • Quiz: Assignment 1 verification — recursion and higher-order list programming
    • Binding structure and variable occurrence
    • Free and bound variables
    • Lexical addressing as a structurally recursive syntax transformation

Sep-14 - Sep-20

• Assignments:
  • Assignment 3: Interpreters and Representation Independence: Assigned on Mon, Sep 14 | Assignment
• Mon, Sep 14 Lecture: Introduction to interpreters
  • Topics:
    • Quiz: Assignment 2 verification — free variables and lexical address
    • A higher-order definitional interpreter for a small functional language
    • Environments, closures, and compositional evaluation
• Wed, Sep 16 Lecture: Shortened class — Finishing representation-independent environments and closures
  • Topics:
    • Class meets 1:00-1:45 p.m. after the Mass of the Holy Spirit
    • Functional and data-structural representations of environments
    • Functional and data-structural representations of closures
    • Programming against interfaces rather than representations

Sep-21 - Sep-27

• Assignments:
• Mon, Sep 21 Lecture: Lambda-calculus substitution and normalization
  • Topics:
    • Quiz: Assignment 3 verification — interpreters and representation independence
    • Capture-avoiding substitution and alpha-equivalence
    • Alpha-, beta-, and eta-normalization
    • Normalization by evaluation (NbE)
• Wed, Sep 23 Lecture: Lexical and dynamic scope
  • Topics:
    • Where an interpreter chooses the environment for a procedure body
    • Predicting the observable differences between lexical and dynamic binding

Sep-28 - Oct-04

• Assignments:
  • Assignment 4: Representation-Independent Closures and Dynamic Scope: Assigned on Mon, Sep 28 | Assignment
• Mon, Sep 28 Lecture: Parameter-passing conventions
  • Topics:
    • Call by value, reference, name, and need
    • Boxes, mutation, thunks, and memoization
• Wed, Sep 30 Lecture: Parameter-passing interpreter workshop
  • Topics:
    • Implementing four parameter-passing conventions by changing an evaluator
    • Comparing their observable behavior with small discriminating programs

Oct-05 - Oct-11

• Assignments:
  • Assignment 5: Parameter-Passing Conventions: Assigned on Mon, Oct 05 | Assignment
• Mon, Oct 05 Lecture: Exam 1 review
  • Topics:
    • Quiz: Assignment 4 verification — closures and lexical versus dynamic scope
    • Racket, recursion, quasiquote, match, free and bound variables, and lexical address
    • Interpreters, representation independence, closures, and lexical versus dynamic scope
    • Assignment 5 remains in progress during the exam week
• Wed, Oct 07 Lecture: Exam 1
  • Topics:
    • Individual, closed-resource, and closed-device, in class
    • Cumulative through Assignment 4; parameter passing is not included

Oct-12 - Oct-18

• Assignments:
• Mon, Oct 12 Lecture: No class — Fall Break
• Wed, Oct 14 Lecture: Lambda calculus and equational reasoning
  • Topics:
    • Alpha, beta, and eta equivalence
    • Reduction strategies and equational reasoning
    • Universality and the relationship between calculus and interpreter

Oct-19 - Oct-25

• Assignments:
  • Assignment 6: Continuation-Passing Style: Assigned on Mon, Oct 19 | Assignment
• Mon, Oct 19 Lecture: Introduction to continuations and CPS
  • Topics:
    • Quiz: Assignment 5 verification — parameter-passing conventions
    • System continuations, escape, and explicit control
    • Systematic continuation-passing-style transformation
• Wed, Oct 21 Lecture: Remote class — CPS interpreters
  • Topics:
    • Class meets remotely, 12:30–1:45 p.m. Eastern; access details in Canvas.
    • Transforming an evaluator into continuation-passing style
    • Simple and serious expressions, administrative bindings, and tail calls

Oct-26 - Nov-01

• Assignments:
  • Assignment 7: CPS Interpreters and Representation-Independent Continuations: Assigned on Mon, Oct 26 | Assignment
• Mon, Oct 26 Lecture: Remote class — Representation-independent continuations
  • Topics:
    • Class meets remotely, 12:30–1:45 p.m. Eastern; access details in Canvas.
    • Defunctionalizing continuations and introducing apply-k
    • Programming against a continuation interface rather than its representation
• Wed, Oct 28 Lecture: Remote class — Registerization
  • Topics:
    • Class meets remotely, 12:30–1:45 p.m. Eastern; access details in Canvas.
    • Replacing parameters with registers
    • Program-counter style and the path toward an abstract machine
  • Extra Resources:
    • Historical notes: Representation Independence Procedure

Nov-02 - Nov-08

• Assignments:
  • Assignment 8: Registerization and Trampolining: Assigned on Mon, Nov 02 | Assignment
• Mon, Nov 02 Lecture: Trampolining
  • Topics:
    • Quiz: Assignment 6 verification — continuation-passing style
    • Trampolines and bounded host-stack use
    • Iterative control over registerized procedures
    • Assignment 8 emphasizes registerization and finishes with trampolining
• Wed, Nov 04 Lecture: Exam 2 review
  • Topics:
    • Quiz: Assignment 7 verification — CPS interpreters and continuation representations
    • Cumulative review with emphasis on parameter passing, CPS, continuation representation, registerization, and trampolining
    • Assignment 9 itself is not on Exam 2

Nov-09 - Nov-15

• Assignments:
  • Assignment 9: ParentheC Interpreter and Code Review: Assigned on Mon, Nov 09 | Assignment
• Mon, Nov 09 Lecture: ParentheC demonstration
  • Topics:
    • Quiz: Assignment 8 verification — registerization and trampolining
    • Unionizing data, dismounting the trampoline, and translating to C
    • Assignment 9 resumes the corrected Assignment 7 interpreter
    • The code review may draw from any preserved intermediate version
    • Assignment 9 deadline: Sunday, November 29, at 10 p.m. Eastern
• Wed, Nov 11 Lecture: Exam 2
  • Topics:
    • Individual, closed-resource, and closed-device, in class
    • Cumulative, with emphasis on parameter passing through trampolining; Assignment 9 is not included

Nov-16 - Nov-22

• Assignments:
• Mon, Nov 16 Lecture: Store-passing style
  • Topics:
    • Threading an explicit store alongside a computation's value
    • Environments as mappings from variables to locations and stores as mappings from locations to values
    • Interpreting assignment and sequencing without relying on host-language mutation
• Wed, Nov 18 Lecture: Macros and language extension
  • Topics:
    • Syntactic abstraction with syntax-rules
    • When a library is not enough: extending a language's grammar

Nov-23 - Nov-29

• Assignments:
• Mon, Nov 23 Lecture: Objects through interpreters
  • Topics:
    • Objects, classes, and method dispatch as language features
• Wed, Nov 25 Lecture: No class — Thanksgiving recess

Nov-30 - Dec-06

• Assignments:
• Mon, Nov 30 Lecture: Types
  • Topics:
    • Static semantics and type judgments
    • Typing rules for expressions and functions
• Wed, Dec 02 Lecture: Type inference
  • Topics:
    • Single cumulative paper-quiz makeup window for documented additional absences
    • Constraint generation, unification, and inference

Dec-07 - Dec-13

• Assignments:
• Mon, Dec 07 Lecture: Staging, compiler structure, and domain-specific languages
  • Topics:
    • Moving computation across stages
    • Lexing, parsing, elaboration, evaluation, and compilation
    • Designing languages for particular problem domains
• Wed, Dec 09 Lecture: Exam 3 review
  • Topics:
    • Cumulative review, including regression from Exams 1 and 2
    • ParentheC transformations, store-passing style, objects, types, staging, compilers, and language extension

Dec-14 - Dec-20

• Assignments:
• Mon, Dec 14 Lecture: Exam 3
  • Topics:
    • Individual, closed-resource, and closed-device, in class on the last day of class
    • Cumulative, with emphasis on the post-Exam 2 material