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.
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 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 |
Lab at 1:30pm in Cummings 642 |
|
Friday |
|
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 |
Prepare for Tuesday’s code review |
|
Tuesday |
Code Review at 1:30pm in Cummings 240 |
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 |
|
Thursday |
Before 1:30, take a quick look at the lab exercises |
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 |
Prepare for Tuesday’s code review |
|
Tuesday |
Code Review at 1:30pm in Cummings 240 |
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. |
|
Start designing concrete syntax for your assembly code |
|
Thursday |
Before 1:30, complete the algebraic laws for the baby error monad |
Lab at 1:30pm in Cummings 642 |
|
Friday |
Pull new code from the student git repo |
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 |
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) |
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 |
|
If you haven’t already watched the overview video on the big picture (lower level), do it before deciding on a lab |
|
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. |
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 |
Prepare for Tuesday’s code review |
|
Tuesday |
Code Review at 1:30pm in Cummings 240 |
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 |
|
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 |
Submit your reflections on module 5 by 11:59pm |
|
Wednesday |
Watch the introduction to module 6 (2½ minutes) |
Complete the essential pre-lab steps:
|
|
Thursday |
Before lab, if you can, prepare the recommended pre-lab steps |
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) |
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 |
Prepare for Tuesday’s code review |
|
Tuesday |
Code Review at 1:30pm in Cummings 240 |
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 |
|
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. |
|
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 |
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 |
|
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 |
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
- 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) |
Review continuation-passing style |
|
Wednesday (or Thursday before lab) |
Essential: Extend your UFT driver with support for First-Order Scheme |
Read about K-normalization and register allocation |
|
Review the abstract syntax in |
|
Thursday |
Lab at 1:30pm in Cummings 642 |
Friday |
Complete your K-normalizer |
Module 10 (UFT):
Closure conversion
- Handout: How Closures Work
April 3 to April 9: What you need to do
All week |
Think about your wishes for module 12 |
Monday |
Finish integration testing |
Submit homework for module 9 by 11:59pm |
|
Tuesday |
Code Review at 1:30pm in Cummings 240 |
Submit your reflections on module 9 by 11:59pm |
|
Thursday |
Before 1:30, complete the pre-lab exercises for module 10 |
Lab at 1:30pm in Cummings 642 |
Module 11 (SVM):
Garbage collection
- Book chapter: Automatic memory management
- Video: Introduction to module 11
- Video: GC basics
- External videos: Recommended from Redgate and Matthew Flatt (see details in handout)
- Handout: Guide to reading the GC chapter
- Handout: Guide to file
vmheap.c
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 |
Submit your reflections on module 10 by 11:59pm |
|
Wednesday |
Commit to a plan for module 12 |
Thursday |
Before 1:30, complete the pre-lab exercises for module 11 |
Lab at 1:30pm in Cummings 642 |
Module 12 (system):
Dealer’s choice
Choose from one of these options (detailed explanations in main handout):
- Benchmark your system and improve its run-time performance
- Improve performance by enabling any binary primitive to take a literal operand
- Implement μML pattern matching (no type system required)
- Add CS 105 Nano-ML type inference, remove tag checks from VM projections
- Adapt your UFT/SVM system to run your language from CS 107
- Implement a more user-friendly concrete syntax
- Improve usability: add a read-eval-print loop (including
use
) plus support for#!
scripts Implement error handling: support for a stack trace and for
check-error
- Implement a peephole optimizer
- Compile vScheme to C code, eliminating instruction-dispatch overhead
[Or propose your own]
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 |
Submit your reflections on module 11 by 11:59pm |
|
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 |
Submit your reflections on module 12 by 11:59pm |
|
Thursday |
Class at 1:30pm: Workshop preparation |
May 1 to May 7: What you need to do
All week |
Prepare 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 |