CSE 401: Introduction to Compiler Construction
Autumn 2016, MWF 12:30pm-1:20pm, MGH 241
What you will learn
Programming languages bridge two levels of abstraction: (i) the world of the programmer who uses concepts of his domain, such as graphs or matrices, and (ii) the world of the computer, which prefers abstractions that can be efficiently executed, such as arrays, threads, and remote procedure calls.
This course will teach you how languages translate the programmer abstraction into the executable abstractions. We will talk about compilers, interpreters, parsers, and optimizations. The lectures will cover both general-purpose languages and the recent modern languages designed for a specific domain task. The programming assignments will focus on the domain-specific languages. Students interested in a project that implements a general-purpose compiler should consider registering for CSE401 in Spring 2017.
The programming homeworks will follow the recently developed CSEP590c course, minus the d3 assignment.
This is a project oriented course that also comes with a substantial foundational material. A lot of material will be learnt in programing homeworks, while some will only be touched on in lectures and sections.
Grade breakdown (tentative; will be adjusted in response to relative sizes of homeworks and projects):
Syllabus and lecture materials
Each part of the course describes some fundamental technology (e.g., parsing) in the context of some real-world applications (e.g., templating, which is translating data into formatted documents).
Part I: Implementation Strategies / Regular Expressions
Lecture 1: Abstractions and language revolutions.
Lecture 2: Implementation strategies.
Lecture 3: Compiling regular expressions.
Lecture 4: Fluent to AST. Regexes vs. REs.
Lecture 5: Review and Discussion
Part II: Optimizations / Query Languages
Lecture 6: Big Data and Spark
Lecture 7: A Query Language (HW2)
Lecture 8: Global dataflow analysis
Lecture 9: Code generation (data)
Lecture 10: Quiz 1 + The Future of Software (talk)
Lecture 11: Code generation (control)
Part III: Parsing / Templating
Lecture 12: Grammars, Parse Trees, Ambiguity (problem set)
Lecture 13: Templating (problem set, reading: 1, 2, live)
Lecture 14: Recursive Descent Parsers (problem set)
Lecture 15: Syntax-directed translation (problem set)
Lecture 16: Quiz 2 + Introduction to Final Project (HW5)
Part IV: Reactive Languages, Laziness / Working with Internet Data
Lecture 17: no lecture (work on HW5 problem selection)
Lecture 18: Rx, a reactive language (reading: start on p. 7, ex)
Lecture 19: Iterators (reading: Chapter 7, exercise + answer)
Lecture 20: Coroutines (reading: 9.1, 9.3, 3.3.2, 5.3, problem set)
Lecture 21: Quiz 3 + Push-pull pipes (read 9.2, handout, ex)
Lecture 22: Implementation of a coroutine interpreter (questions)
Part V: Types and Objects, Garbage Collection, Staging (problem sets)
Lecture 23: Objects in a dynamically typed language (read 16-16.2)
Lecture 24: Objects in a statically typed language (reading 16.4)
Lecture 25: finish the bitflip exploit
Lecture 26: Quiz 4 + V8 JIT compiler (read: hidden classes)
Lecture 27: Garbage Collection (read: V8 GC classic, modern 1,2)
Lecture 28: finish GC and V8 (read: value representation, broader)
Lecture 29: Bootstrapping + Trusting Trust (reading)
Lecture 30: Quiz 5 + What to keep learning
Two sections are offered:
Here you will find links to section materials. You need to log in with your UW google id (not your UW CSE id).
Homeworks and the final project
There will be four programming homeworks. The first one will be individual, while the rest will be done in pairs.
The final project will be the “fifth homework”. You will design and implement a small language of your choice. Typically, this design will extend the four homeworks.
Our handouts will be “live” google docs on which students can ask clarifications questions by adding comments to the text. The discussion about the homework will thus take place in the doc, not on Piazza. Use your <username>@uw.edu google login to get to these documents.
Exams and key dates
Instead of midterms, we will have about five quizzes. They will be 20-minutes long and will be held during lectures. They will take place roughly a week after the HW is due; this week will be used to work on problem sets and reviewing the feedback for your HW.
The poster and demo session will replace the final exam and will be held during the assigned final exam slot (Thursday, December 15, 2016, 830-1020). Location: somewhere in CSE (stay tuned).
These five books are on reserve in the Engineering Library:
Mastering Regular Expressions
The Definitive ANTLR 4 Reference
Programming in Lua
Where to ask questions?
Questions about lectures? Ask them on the Piazza 401 page.
Questions about homeworks: add comments to handout docs.
Questions on anything else: Ask them on the Piazza 401 page.
A private message to the instructors: Send it via Piazza.
Any of the above: Come to our office hours.
Where are 401 announcements?
You can find all announcements on Piazza, in the tab Resources. Check that page often or subscribe to email notifications.
Staff and office hours
Ras Bodik, 3-4pm Tuesdays in CSE 644
phone: (206) 616-7172
Bindita Chaudhuri, 10:30-11:30am Wednesdays in CSE 218 and 10-11am Fridays in CSE 220
Sam Elliott, 11am-12pm Tuesdays in CSE 218
Julie Newcomb, 2:30-3:30pm Mondays in CSE 220