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.

Course format

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):

Homeworks

Quizzes

Final project

Participation

45%

30%

15%

10%

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

Sections

Two sections are offered:

  • AA 8:30am, EEB 045
  • AC 1:30pm, MEB 245

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.

  • HW1, assigned 10/2, due 10/11
  • HW2, assigned 10/12, due 10/25
  • HW3, assigned 10/26, due 11/8
  • HW4 assigned 11/9, due 11/22
  • HW5:

Week

Mon

Tue

Wed

Thu

Fri

1

Sep 28
First lec.

29

30

2

 

 

3

Oct 11
HW1 due

Oct 12

HW2 out

4

Oct 19

Quiz 1

5

Oct 25
HW2 due

HW3 out

6

Nov 2

Quiz 2

7

Nov 8
HW3 due

HW5.1 due

HW4 out

Veterans
Day

8

Nov 16

Quiz 3

Nov 18

HW5.2 due

9

Nov 22
HW4 due

Thanks-
giving

Thanks-
giving

10

HW5.3 due

Nov 30

Quiz 4

11

Dec 9
Quiz 5

12

Finals week

Dec 14, 8am
HW5.4 due

Dec 15
Demos

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).

Recommended Books

These five books are on reserve in the Engineering Library:

JavaScript, the good parts

JavaScript, the Definitive Guide

  • JS is our implementation language

Mastering Regular Expressions

  • more than you need to know about this topic

The Definitive ANTLR 4 Reference

  • ANTLR is our parser

Programming in Lua

  • how to implement objects; how to use coroutines

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

email: bodik@cs.washington.edu 

phone: (206) 616-7172

Bindita Chaudhuri, 10:30-11:30am Wednesdays in CSE 218 and 10-11am Fridays in CSE 220

email: bindita@cs.washington.edu

Sam Elliott, 11am-12pm Tuesdays in CSE 218

email: ashe2@cs.washington.edu

Julie Newcomb, 2:30-3:30pm Mondays in CSE 220

email: newcombj@cs.washington.edu