Course at a glance

Instructor:	Norman Ramsey. Office hours TBA and by appointment (Zoom).
Labs:	Thursdays 1:30–2:45 in Cummings 642
Code reviews:	Tuesdays 1:30–2:45 in Cummings 240
Discussion:	Slack `cs106spring2023.slack.com`.

Modules

Course overview

Materials:

Video: Overview of the course (8 minutes)
Handout: Introduction to vScheme
Three videos about the system:
- The UFT demo (12½ minutes) shows the translation of a simple function from higher-order Scheme code all the way to virtual object code. Each intermediate form is shown. This video shows what the system does but not how it is built.
- The big picture, lower level (11½ minutes) shows how the first half of the system is built in modules 1 to 4: the VM, virtual object code, and virtual assembly code.
- The big picture, higher level (9 minutes) shows how the second half of the system is built in modules 5 to 10: K-normal form, first-order vScheme, unambiguous vScheme, and vScheme itself.

The end-of-term workshop and final reflection

Materials:

Video: Preparing for the end-of-term workshop (8 minutes)
Handout: “Effective Oral Presentations” (4 pages) by Jean-Luc Doumont
Handout: Expectations for the workshop and your final reflection

Module 1 (SVM):

Intraprocedural Code and Virtual-Machine State

Materials:

Video: Introduction to module 1 (5 minutes)
Video: Embedding and projection of values 1 (12½ awkward minutes—not my best video)
Handout: Module 1: Virtual-Machine State
Handout: VM Semantics, Part I
Handout: Instruction Formats
Handout: Principles of Bytecode Interpretation
Handout: Overview of the starter code

January 16 to January 22: What you need to do

Wednesday	Watch the 8-minute overview of the course and instructor
	Watch the 5-minute overview of module 1
	Read the introduction to Module 1: Virtual-Machine State
	Read the handout VM Semantics, Part I
	Look at the pre-lab exercises for module 1
	Watch the 12½-minute video on embedding and projection
Thursday	Before 1:30, complete the pre-lab exercises for module 1
Thursday	Lab at 1:30pm in Cummings 642
Friday	Read “Principles of Efficient Bytecode Interpretation”
	Continue working on your VM using the post-lab directions
	Read the syllabus

Module 2 (SVM):

The VM Loader

Materials:

Video: Intro to module 2, with brief comment on module 1 (5 minutes)
Handout: Rationale, steps, and learning outcomes
Video: The “what” and “why” of parsing
Handout: Syntax of virtual object code
Video: Demonstration of parsing virtual object code
Handout: Semantics of virtual object code and loading
Handout: Overview of this week’s code
Handout: A quick guide to debugging

January 23 to January 29: What you need to do

Monday	Submit your VM by 11:59pm
Monday	Prepare for Tuesday’s code review
Tuesday	Code Review at 1:30pm in Cummings 240
Tuesday	Submit your reflection on module 1 by 11:59pm
Wednesday (or Thursday before lab)	Watch the video introduction to module 2 (and review of module 1) (5 minutes)
	Read the introduction to module 2
	Read the handout on virtual object code
	Watch videos on the “what” and “why” of parsing and on parsing virtual object code
	If you prefer to read, skip the parsing videos and explore the recommended reading on parsing
	Update your git repository
Thursday	Before 1:30, take a quick look at the lab exercises
Thursday	Lab at 1:30pm in Cummings 642
Friday	Look at the after-lab directions
	Plan to finish your loader by Monday night
	Optional: Check out the overview videos

Module 3 (UFT):

Parsing

Main handout: Module 3 (parsing and unparsing, assembly language and object code)
Video: introduction to module 3 (3½ minutes)
Handout: The baby error monad
Optional video: Making types work for you in the error monad (11½ minutes)
Handout: Design considerations for assembly-language syntax
Video: What parsing combinators can do for us (10 minutes)
Alternative video: Lightning introduction to parsing combinators, made for a professional audience (3½ minutes)
Handout: Introduction to combinator parsing
Handout: Software development in Standard ML
Handout: Overview of the code
Video: Embedding and projection part 2: embedding and projecting programs (4 minutes)

January 30 to February 5: What you need to do

Monday	Submit your VM (with loader) by 11:59pm
Monday	Prepare for Tuesday’s code review
Tuesday	Code Review at 1:30pm in Cummings 240
Tuesday	Submit your reflection on module 2 by 11:59pm
Wednesday	Watch the video introduction to module 3 (3½ minutes)
	Take a quick look at the introduction to module 3 and preparation for lab
	Review Standard ML
	Watch either the custom video (10 minutes) or the professional video (3½ minutes) on parsing combinators
Wednesday (or Thursday before lab)	Learn about error monads
	If you want to polish your ML skills, watch the video “Making types work for you in the error monad”. This video is similar to my 105 lecture on the same topic, but it uses the error monad.
	Read my introduction to combinator parsing
	Start designing concrete syntax for your assembly code
Thursday	Before 1:30, complete the algebraic laws for the baby error monad
Thursday	Lab at 1:30pm in Cummings 642
Friday	Pull new code from the student git repo
Friday	Continue working; follow the post-lab directions

Module 4 (UFT):

Assembly

Module 4 handout: Introduction, step by step, learning outcomes
Video: Introduction to module 4 (1½ minutes)
Video: Low-level languages and the UFT (part of the course overview, 11½ minutes)
Handout: Hints for writing and debugging combinator parsers
Handout: Overview of the code
After-module video: Brief commentary on module 4 (1½ minutes)

February 6 to February 12: What you need to do

Monday	Submit your unparser by 11:59pm
Monday	Prepare for Tuesday’s code review
Tuesday	Code Review at 1:30pm in Cummings 240
	Unless you’ve watched it already, watch the second video on embedding and projection (4 minutes)
	Submit your reflections on module 3 by 11:59pm
Wednesday	Consider watching the brief commentary on module 3 (1 minute)
Wednesday	Watch the introduction to module 4 (1½ minutes)
Wednesday (or Thursday before lab)	Post your opinion about Spring break (to Slack)
	Update your git repository and confirm that you can build a UFT with `make`.
	If you haven’t already watched the overview video on the big picture (lower level), do it before deciding on a lab
	Decide on a lab and review for it
Thursday	By 11:00am, let me know if you want to spend your lab writing the key assembler pass (label elimination) or if you prefer help with your parser.
Thursday	Lab at 1:30pm in Cummings 642
Friday	Continue working on your assembler: parser, unparser, and label elimination

Module 5 (UFT):

Disambiguation and K-normal form

Master handout: Module 5 introduction, step by step, learning outcomes
Video: Introduction to module 5 (1 minute)
Video: High-level languages and the UFT (big picture) (from the course overview, 9 minutes)
Video: Demonstration of embedding, projection, disambiguation, and K-normal form (11 minutes)
Handout: K-normal form
Handout: Unambiguous vScheme
Handout: Secrets of the UFT driver
Note: Function composition with error types (helpful when writing passes for the UFT driver)
Handout: Overview of the code

February 13 to February 19: What you need to do

Monday	Submit your UFT by 11:59pm
Monday	Prepare for Tuesday’s code review
Tuesday	Code Review at 1:30pm in Cummings 240
Tuesday	Submit your reflections on module 4 by 11:59pm
Wednesday (or Thursday before lab)	Consider watching the brief commentary on module 4 (1½ minutes)
	Watch the introduction to module 5 (1 minute)
	Watch the overview video on high-level languages and the UFT (the plan for modules 5 to 10, 9 minutes)
	Study vScheme and Unambiguous vScheme
	Understand eta-expansion
Thursday	Before 1:30, know the answers to four pre-lab questions
	(The video demonstration of embedding, projection, disambiguation, and K-normal form could be useful before lab, but it’s not necessary.)
	Lab at 1:30pm in Cummings 642: Disambiguating Scheme
Friday	Read about K-normal form
	Define a representation for K-normal form
	Watch the video demonstration of embedding, projection, disambiguation, and K-normal form (11 minutes)
	Embed K-normal form into Scheme
	Project Unambiguous vScheme into K-normal form
	Add K-normal-form support to the UFT

Module 6 (UFT):

Code generation

Module handout: Module step by step, learning outcomes
Video: Introduction to module 6 (2½ minutes)
Handout: Code generation from K-normal form
Handout: Overview of the code
Handout: Secrets of the UFT driver (from module 5)

February 20 to February 26: What you need to do

Monday	Submit homework for module 5 by 11:59pm
Tuesday	Code Review at 1:30pm in Cummings 240
Tuesday	Submit your reflections on module 5 by 11:59pm
Wednesday	Watch the introduction to module 6 (2½ minutes)
Wednesday	Complete the essential pre-lab steps: Study code generation Review secrets of the UFT driver
Thursday	Before lab, if you can, prepare the recommended pre-lab steps
Thursday	Stealth Lab from 1:30 to 2:45, Cummings 642
Friday	Stealth Lab from 4:00 to 5:00 (one hour only), Cummings 542 (fifth floor)
Friday	Work towards completing and testing your code generator

Module 7 (SVM):

Functions in the virtual machine

Main handout for module 7: Introduction, step by step, learning outcomes
Video: Introduction to module 7
Video (optional): review of call stacks (8 minutes, from CS 50).
Handout: Understanding procedure calls
Handout: Operational semantics of procedure calls
Handout: Test codes for call, tail-call, and return instructions
Handout: Overview of the code
Zip file: Test codes from the testing handout

February 27 to March 5: What you need to do

Monday	Submit your complete, tested code generator for module 6 by 11:59pm
Monday	Prepare for Tuesday’s code review
Tuesday	Code Review at 1:30pm in Cummings 240
Tuesday	Submit your reflections on module 6 by 11:59pm
Wednesday	Watch the video introduction to module 7 (4 minutes)
	To get a key bug fix in `disasm.c`, `git pull`
	Consider adding a debug mode to your SVM
Wednesday (or Thursday before lab)	Recommended: review hardware procedure calls
	Essential: Read the handout on understanding procedure calls and the operational semantics of calls. Take notes.
	Essential: set up your loader and your `vmrun` for lab.
Thursday	Lab at 1:30pm in Cummings 642

Module 8 (UFT):

Functions in the translator

Main handout for module 8: Introduction, step by step, learning outcomes
Video: Introduction to module 8 (1½ minutes)
Handout: Overview of the code

March 6 to March 12: What you need to do

Monday	Submit homework for module 7 by 11:59pm
Tuesday	Code Review at 1:30pm in Cummings 240
Tuesday	Submit your reflections on module 7 by 11:59pm
Wednesday (or Thursday before lab)	Watch the video introduction to module 8 (1½ minutes)
	Update your working tree using `git pull`
	Study tail position and write equations of translation for it
Thursday	Lab at 1:30pm in Cummings 642

March 13 to March 19: What you need to do

Monday	Submit homework for module 8 by 11:59pm
Tuesday	Code Review at 1:30pm in Cummings 240
Tuesday	Submit your reflections on module 8 by 11:59pm
Thursday	No class (payback for stealth lab)

March 20 to March 26: Spring Break

All week

Spring Break

Module 9 (UFT):

K-Normalization

Main handout: Introduction, module step by step, learning outcomes
Video: Introduction to module 9 (5 minutes)
Handout: K-Normalization and Register Allocation

March 27 to April 2: What you need to do

Monday	Review possibilities for module 12. Come to class sufficiently well informed that for each possibility you can vote Yes or No on the question, “I might like doing this.”
Tuesday	Class at 1:30pm: Alternatives for module 12 (Cummings 342)
Tuesday	Review continuation-passing style
Wednesday (or Thursday before lab)	Watch the video introduction to module 9 (5 minutes)
	Essential: Extend your UFT driver with support for First-Order Scheme
	Read about K-normalization and register allocation
	Review the abstract syntax in `foscheme.sml` and `knf.sml`
Thursday	Lab at 1:30pm in Cummings 642
Friday	Complete your K-normalizer

Module 10 (UFT):

Closure conversion

Main handout for module 10: Introduction, step by step, learning outcomes
Handout: How Closures Work
Handout: Overview of the code

April 3 to April 9: What you need to do

Monday	Finish integration testing
Monday	Submit homework for module 9 by 11:59pm
Tuesday	Code Review at 1:30pm in Cummings 240
Tuesday	Submit your reflections on module 9 by 11:59pm
Wednesday	Watch the video introduction to module 10 (2½ minutes)
Wednesday	Read the handout on how closures work
Thursday	Before 1:30, `git pull` and confirm that your UFT builds
Thursday	Lab at 1:30pm in Cummings 642
Friday	Update the UFT driver, implement closure conversion, and follow the ripples downstream through K-normalization, code generation, and SVM instructions.

Module 11 (SVM):

Garbage collection

Main handout: Introduction, module step by step, learning outcomes
Video: Introduction to module 11 (3 minutes)
Video: GC basics (6 minutes)
External videos: Recommended from Redgate, Matthew Flatt, and possibly Christoph Reichenbach (see details in handout)
Handout: Guide to reading the GC chapter
Handout: Garbage-collector interactions with the VM state, the VM heap, and VM registers
Handout: Guide to file vmheap.c
Handout: Overview of module 11 code
Book chapter: Automatic memory management

April 10 to April 16: What you need to do

Monday	Submit homework for module 10 by 11:59pm
Tuesday	Code Review at 1:30pm in Cummings 240
Tuesday	Submit your reflections on module 10 by 11:59pm
Wednesday	Watch video introduction to module 11 (3 minutes)
	Download updates using `git pull`
	Watch video on GC basics (6 minutes)
	Read about garbage-collection basics
Wednesday (or Thursday before lab)	Study tricolor marking and object scanning
	Prepare your VM state for garbage collection, including macros to save and load volatile state
	Familiarize yourself with `vmheap.c`
Thursday	Lab at 1:30pm in Cummings 642

Module 12 (system):

Pattern matching

Pattern-matching option:

Main handout for module 12: Introduction, step by step, learning outcomes
Handout on constructed data
Handout on match compilation
Overview of the code

Benchmarking option:

April 17 to April 23: What you need to do

Monday	Submit homework for module 11 by 11:59pm
Tuesday	Code Review at 1:30pm in Cummings 240
Tuesday	Submit your reflections on module 11 by 11:59pm
Wednesday (or Thursday before lab)	Get a feel for the syntax of case expressions and pattern matching by taking a quick look at chapter 8 in my book
	Read about constructed data in our system
	Get new code via `git pull`, repair your UFT, and add two new forms to your KNF
	Read the handout on match compilation and parts of the paper by Scott and Ramsey
Thursday	Come to lab prepared to implement a key part of figure 8 from the paper
Thursday	Lab at 1:30pm in Cummings 642

April 24 to April 30: What you need to do

Monday	Submit homework for module 12 by 11:59pm
Tuesday	Code Review at 1:30pm in Cummings 240
Tuesday	Submit your reflections on module 12 by 11:59pm
Wednesday	Watch the video on preparing for the final workshop (8 minutes)
Thursday	Class at 1:30pm: Workshop preparation

May 1 to May 7: What you need to do

All week	Read “Effective Oral Presentations” by Jean-Luc Doumont (4 pages)
	Prepare your presentation for the final course workshop

May 8 to May 14: What you need to do

Tuesday

Final course workshop from 2:30 to 6:00 in Cummings 402

2:30	Opening remarks
2:45	Matt Zhou
3:15	Kresten Due
3:45	Alex Bai and Jasper Geer
4:15	Break
4:30	Dennis Yang
5:00	Vivian Li and Stephanie Xu
5:30	Roger Burtonpatel
6:00	Panel meets in closed session

Thursday

Submit your final reflection by 11:59pm