cs202-compiler-construction

UVM CS202: Compiler Construction (Spring 2021)

Announcements

Administrative

Course Description

This course covers the design and construction of compilers. You’ll learn how to translate a high-level, garbage-collected programming language all the way into Intel x86 assembly language.

Instead of learning about each phase of the compilation process sequentially, we’ll start by compiling a tiny subset of the target language directly into assembly code. Each week, we’ll add a new feature to our language, and learn about all the phases needed to compile that feature into assembly. At each step, you’ll have a functioning compiler that can run real code; by the end of the course, your compiler will work on a realistic programming language including first-class functions.

Topics covered include:

This course will be structured around lectures and a weekly programming assignment. Each lecture will cover a new language feature and the techniques needed to compile it; in the corresponding programming assignment, you will implement support for the new feature in your own compiler. Students should expect to spend 6-8 hours per week outside of class on the weekly programming assignments. The required materials for this course are all freely available online.

Students will also complete a final project, in which they extend their compiler with an additional significant language feature of their choice.

Graduate students are expected to complete additional challenge exercises included in each assignment, and to select more ambitious final projects compared to undergraduate students.

This course is primarily intended for computer science students, but may also be appropriate for some graduate students in other areas with an interest in programming languages and strong programming experience.

Prerequisites: CS124 and CS125

Text and Resources

Please do not buy any books for this course. All required reference material is available online for free.

The primary textbook we will use for this course is:

For questions about Haskell, course material, or assignments, post to Piazza. Feel free to answer others’ questions, but please do not share code or solutions. You can access Piazza here:

Code and resources for assignments:

Other resources:

Policies

Grading

Your grade for the course will be determined as follows:

Your final grade will be determined by summing the total number of points awarded and calculating the percentage of the total possible points. This percentage is translated into a letter grade as follows:

Undergraduate Students

Percent Letter Grade
98-100 A+
93-97 A
90-92 A-
87-89 B+
83-86 B
80-82 B-
77-79 C+
73-76 C
70-72 C-
67-69 D+
63-66 D
60-62 D-
<60 F

Graduate Students

Percent Letter Grade
98-100 A+
93-97 A
90-92 A-
87-89 B+
83-86 B
80-82 B-
77-79 C+
73-76 C
70-72 C-
<70 F

Assignments

Assignments will generally be due weekly on Mondays at 11:59pm, with breaks for the midterm exam and final project. Your assignment will be graded using a test suite which will be made available one day before the assignment due date.

Late assignments will not be accepted. Each assignment builds extensively on the last one, and mastering the assignment material is crucial to success in this course. If you fall behind on completing the assignments, it will be extremely difficult to catch up.

Therefore, on Tuesday after each assignment due date, we will discuss that assignment’s solution in lecture, and the complete solution will be made available on Blackboard. I encourage students to take advantage of the official solutions to avoid falling behind.

Partial credit will be (extensively) given on assignments. I encourage you to submit something for every assignment, even if your solution is far from complete.

Most assignments include a challenge exercise, which generally involves extending your compiler with extra features or optimization capabilities. Graduate students are required to complete all of the challenge exercises, and the challenge exercise will account for 20% of the total grade for the assignment. Undergraduates who successfully complete the challenge exercise for an assignment will receive 5% extra credit for that assignment.

Assignments will be graded according to the following rubric:

Grade Assignment Status
100 Passes all test cases
95 Passes 75% of test cases
90 Passes 50% of test cases
85 Passes at least 1 test case
80 Project compiles; all passes appear to be nearly complete
75 All or nearly all passes appear nearly complete
70 Significant work on all passes
65 Significant work on at least 75% of the passes
60 Significant work on at least half of the passes
<60 Missing passes

Exams

There will be two exams:

The exams will not be cumulative: the midterm will cover the material from the first four assignments, and the final will cover the material from the last three assignments and subsequent lectures.

Final Projects

Each student will select and complete a new language feature for their compiler. Final project deliverables will consist of a short project proposal, a compiler implementing the selected language feature, and test cases demonstrating its use. Final projects may be completed in teams of up to 3 students; larger teams will be expected to complete more ambitious projects.

Graduate Students

Graduate students will be expected to complete additional requirements in order to receive graduate credit for this course:

Collaboration & Allowed References

Collaboration on the high-level ideas and approach on assignments is encouraged. Copying someone else’s work (outside of your team members) is not allowed.

The official references for the course are listed in the schedule below. Copying from references other than these is not allowed. In particular, code should not be copied from other sources, including Stack Overflow and other public sources.

Students caught copying work are eligible for immediate failure of the course and disciplinary action by the University. All academic integrity misconduct will be treated according to UVM’s Code of Academic Integrity.

Guest Lectures & Extra Credit

During the semester there will be ~3 guest lectures from visiting faculty. I will give 0.5% extra credit towards your final grade for each of these lectures that you attend. To receive extra credit, you must bring a notepad to the lecture, take notes in person during the lecture, and then turn your notes in to the instructor personally at the end of the talk.

Assignments

Assignment Topics Covered Text Chapter Due Date
1 Compiling R0 to x86 Chapter 1 & 2 Jan 27, 11:59pm
2 Compiling R1 to x86 Chapter 2 Feb 10, 11:59pm
3 Register Allocation Chapter 3 Feb 24, 11:59pm
4 Booleans and Control Flow (R2) Chapter 4 Mar 9, 11:59pm
- Midterm Exam (assignments 1-4) 1 - 4 Mar 5 (in class)
5 Vectors and Garbage Collection (R3) Chapter 5 Apr 6, 11:59pm
6 Compiling Functions (R4) Chapter 6 Apr 20, 11:59pm
7 Compiling First-Class Functions (R5) Chapter 7 Canceled
  Final Project   See below
- Final Exam (assignments 5-7) 5 - 7 See below

Class Schedule

Date Topic Assignment
Tue, Jan 14 Welcome & Haskell  
Thu, Jan 16 ASTs & Interpreters  
Tue, Jan 21 x86 Assembly  
Thu, Jan 23 Compiling R0  
Tue, Jan 28 A1 review; Compiling R1 I A1 Due (Monday)
Thu, Jan 30 Compiling R1 II  
Tue, Feb 04 Compiling R1 III  
Thu, Feb 06 Register allocation I  
Tue, Feb 11 A2 review; Register allocation II A2 Due (Monday)
Thu, Feb 13 Register allocation III  
Tue, Feb 18 Booleans & Typechecking  
Thu, Feb 20 Compiling R2 I  
Tue, Feb 25 A3 review; Compiling R2 II A3 Due (Monday)
Thu, Feb 27 REVIEW FOR MIDTERM  
Tue, Mar 03 NO CLASS  
Thu, Mar 05 MIDTERM  
Tue, Mar 10 NO CLASS: Spring Break A4 Due (Monday)
Thu, Mar 12 NO CLASS: Spring Break  
Tue, Mar 17 No class  
Thu, Mar 19 A4 review  
Tue, Mar 24 Vectors & Garbage collection I  
Thu, Mar 26 Vectors & Garbage collection II  
Tue, Mar 31 Vectors & Garbage collection III  
Thu, Apr 02 A5 walkthrough  
Tue, Apr 07 A5 review A5 Due (Monday)
Thu, Apr 09 Compiling functions I  
Tue, Apr 14 Compiling functions II  
Thu, Apr 16 Compiling first-class functions Project proposals due (Friday)
Tue, Apr 21 A6 review A6 Due (Monday)
Thu, Apr 23 Dynamic typing; objects  
Tue, Apr 28 Optimization; binary & instruction sets  
Thu, Apr 30 Review for final exam  
Mon, May 04   Final projects due (Monday)
Thu, May 07 FINAL EXAM (take-home) Final exam due (Thursday)

Final Projects

Suggested Project Ideas

For each of these project ideas, a parser and lecture video will be provided.

Records (Simple Object System)

Extend the vectors present in R4 to records with named fields. Record types are sufficient to implement a simple object system, in which an object’s methods are stored as functions in record fields. There is no chapter in the textbook describing this extension, but a parser and compiler template will be provided, as well as a lecture video.

Example:

record Point {
  add: (Point, Point) -> Point,
  x: Integer,
  y: Integer
}

def addPoint(self: Point, other: Point): Point = {
  Point(self.add, self.x + other.x, other.x + other.y)
}

let p1 = Point(addPoint, 1, 2) in
let p2 = Point(addPoint, 3, 4) in
p1.add(p1, p2)

Anonymous (Lexically-scoped) Functions

Extend the R4 language to support anonmyous functions (i.e. “lambda” functions), as described in chapter 7 of the textbook. Your anonymous functions should be lexically scoped. A parser, compiler template, and lecture video will be provided.

Example:

let x = 5 in
let f = lambda y: Integer -> x + y
in f(6)

Dynamic Typing

Extend the R4 language to support dynamic typing as described in chapter 8 of the textbook. A parser, compiler template, and lecture video will be provided.

Example:

42 == (if 5 == 5 then 42 else True)

Other Project Ideas

More complicated:

Very tough:

Requirements

The goal of the final project is for you to design and implement your own compiler extension. Final projects will be completed in groups of 1-3. The deliverables for the project will be as follows:

Schedule & Grading

The final project is worth 14% of your final grade. The schedule for final project deliverables, and the contribution of each one to the grade you receive for the final project, are as follows:

Deliverable Due Date Grade Percent Turn In
Project Proposal & Meeting Signup 4/17/20 at 11:59pm 10% Blackboard
Project Meetings 4/20/20 - 4/24/20 10% MS Teams
Implementation & README 5/4/20 at 11:59pm 50% Blackboard
Project Presentations 5/4/20 - 5/7/20 30% MS Teams