Instructor: Will Crichton
Lecture: Tuesday / Thursday 1:00pm-2:20pm @ CIT 101
Office Hours: Thursday 3pm-4pm @ CIT 333, or by appointment
This course explores advanced techniques and recent research in the theory and practice of programming language design. This year’s focus is program analysis: algorithms which deduce facts about programs to improve their correctness and performance. We will cover both static and dynamic analysis techniques used in ahead-of-time compilers, just-in-time compilers, bug-finders, and domain-specific languages. This course will provide hands-on experience designing analyses for a simple language targeting WebAssembly in a JIT compiler implemented in Rust. This course will consist of a mixture of lectures and seminars about research papers.
| Date | Topic | Resources | Assignment |
|---|---|---|---|
| 09/04 | Introduction (slides) | MS Ch1 | |
| 09/09 | Compiler Architecture & Rust | TRPL Ch1-4 | A1: Warmup (handout) |
| 09/11 | Program Semantics (notes) | ALGP Ch2 | |
| 09/16 | Program Semantics contd. (notes) | ALGP Ch3 | |
| 09/18 | Type Inference (notes) | MS Ch3 | A2: Types (TeX, handout) |
| 09/23 | Intraprocedural Dataflow (notes) | ALGP Ch4, MS Ch5 | |
| 09/25 | Intraprocedural Dataflow contd. (notes) | ALGP Ch5, MS Ch5 | |
| 09/30 | Dataflow Theory (notes) | ALGP Ch6 | |
| 10/02 | Pointer Analysis (notes) | ALGP Ch10, MS Ch11 | A3: Optimization (handout, test cases) |
| 10/07 | Interprocedural Dataflow (notes) | ALGP Ch8-9, MS Ch8+10 | |
| 10/09 | Information Flow Analysis (notes) | ||
| 10/14 | Information Flow Analysis contd. (notes) | ||
| 10/16 | Fuzzing (notes) | ALGP Ch16 | A4: Flows (handout, TeX, test cases, updated starter, ref compilers) |
| 10/21 | Constraint Solving | ALGP Ch12 | |
| 10/23 | Symbolic Execution (notes) | ALGP Ch13 | |
| 10/28 | JIT Compilers (notes) | Paper Presentations (handout) | |
| 10/30 | JIT Compilers contd. (links) | A5: Dynamism (handout, test cases), Project Proposal (handout) | |
| 11/04 | Discussion: "Getting into the Flow: Towards Better Type Error Messages for Constraint-Based Type Inference" | ||
| 11/06 | Discussion: "Data Flow Analysis is Model Checking of Abstract Interpretations" | ||
| 11/11 | Discussion: "Modular Information Flow through Ownership" | Project proposal due | |
| 11/13 | Discussion: "RacerD: Compositional Static Race Detection" | ||
| 11/18 | Discussion: "KLEE: Unassisted and Automatic Generation of High-Coverage Tests for Complex Systems Programs" | ||
| 11/20 | Discussion: "One VM to Rule Them All" | ||
| 11/25 | Office Hours | Project checkpoint due | |
| 11/27 | Thanksgiving | ||
| 12/02 | Guest lecture: Shriram Krishnamurthi on flow typing | ||
| 12/04 | Guest lecture: Yuka Ikarashi on exocompliation | ||
| 12/09 | Reading period | ||
| 12/04 | Reading period | Project writeup due |
Resources:
Grades will be determined by a weighted average of assessments (60%), participation (15%), and a final
project (25%). The participation grade will be determined based on student engagement during in-class research
paper discussions. Assessments will be a mixture of hand-graded written problems and auto-graded programming
problems. The final project will include an ungraded checkpoint for students to get early feedback on their
progress. There are no costs to take this course. All lecture notes will be made freely available online. Over 13 weeks, students will spend 2.5 hours per week in class (32.5 hours total). Required reading for the
discussions is expected to take approximately 3 hours per week (39 hours). Assignments are expected to take
approximately 8 hours per week for the first 10 weeks (80 hours). The final project is expected to take
approximately 10 hours per week for the last 3 weeks (30 hours). Total: 32.5 + 39 + 80 + 30 = 181.5 hrs.
Students are expected to attend lectures and especially discussion seminars in-person. The listed deadline
for all assignments is a recommended soft deadline. The hard deadline is no later than 2 days after the soft
deadline. Further extensions are not guaranteed and will be provided on a case-by-case basis — contact Will as
soon as you know that you need an extension.
Brown University is committed to full inclusion of all students. Please inform me early in the term if you
may require accommodations or modification of any of course procedures. You may speak with me after class,
during office hours, or by appointment. If you need accommodations around online learning or in classroom
accommodations, please be sure to reach out to Student Accessibility Services (SAS) for their assistance
(sas@brown.edu, 401-863-9588). Undergraduates in need of short-term academic advice or support can contact an
academic dean in the College by emailing college@brown.edu. Graduate students may contact one of the deans in
the Graduate School by emailing graduate_school@brown.edu.
In general, it is acceptable to get help to a problem, and it is not acceptable to get a solution to a
problem. This rule applies no matter whether you are consulting Google, an LLM, a TA, a fellow student, or any
other resource. But remember: only your instructors and TAs are trained to help you without giving you the
solution. We will not prevent you from using other resources, but you must be careful when using them.
Specifically:
Syllabus
Learning Goals
Assessment
Course Materials
180 Hours of Work
Attendance Policies
Accessibility and Accommodations
Academic Integrity Policy
Bounties