1 CPSC 411 Syllabus
1.1 Land Acknowledgement
UBC’s Point Grey Campus is located on the traditional, ancestral, and unceded territory of the xwməθkwəy̓əm (Musqueam) people. The land it is situated on has always been a place of learning for the Musqueam people, who for millennia have passed on their culture, history, and traditions from one generation to the next on this site.
1.2 Course Description
The goal of this course is to give students experience designing, implementing, and extending programming languages. Students will start from a machine language, the x86-64 CPU instruction set with Linux system calls (x64), and incrementally build a compiler for a subset of Racket to this machine language. In the process, students will practice building, extending, and maintaining a complex piece of software, and practice creating, enforcing, and exploiting abstractions formalized in programming languages.
The course assumes familiarity with basic functional programming in Racket, and some simple imperative programming in assembly.
1.3 Course Information
Course Title | Introduction to Compiler Construction |
Course Number | CPSC 411 |
1.4 Prerequisites
A passing grade in CPSC 311.
1.5 Course Materials
No textbook is required. Weekly lecture notes will be posted, and additional reading from a freely available electronic textbook may be suggested.
1.6 Contacts
Instructor | Contact Details | Office | Office Hours |
Prof. Ronald Garcia | ICCS 387 | Tue. 3:30pm--5:00pm | |
Prof. William J. Bowman | ICCS 389 | None |
TA | Contact Details | Office | Office Hours |
Nico Ritschel | DLC Table 6 | Wed. 1:30pm--2:30pm | |
Lily Bryant | DLC Table 1 | Thur. 12:00pm--1:00pm |
1.6.1 Communication about the Course
There are three primary means for communicating between those involved in this course, in addition to the regular lecture sections. In no particular order, these are:
Office hours
The Piazza course discussion board. The instructor, TAs, and all students are expected to read the discussion board on a very regular basis. Late breaking information about assignments, corrections to mistakes made in class, and generally useful information will often be communicated through Piazza. You are responsible for keeping up with posts on Piazza – pleas of ignorance will not be received.
Piazza is also a very effective means of communication if used correctly. Questions about the assignments should be posted to the Piazza rather than being emailed to the instructor or a TA, as everyone will see both the question and its answer. All students are encouraged to post answers to questions posed on Piazza as well.
Email
Email to the instructor or TAs is effective in limited circumstances. It is the most effective means of scheduling a consulting time when the regular hours are impossible or insufficient. It is an appropriate means of asking questions concerning the grading of assignments and examinations. It is not an appropriate means of asking questions about the assignments - see Piazza.
1.7 Course Structure
The course is structured around semester-long project in which students design implement a programming language by building a compiler to x64. The project will be divided into weekly assignments designing an extension to the previous week’s source language to implement that week. During lecture, we will walk through the limitations in the prior week’s language, design a new source language, and introduce necessary background knowledge of algorithms, translations, optimizations, and machine implementation details.
The assignments a0–a2 will be done individually, and the rest of the project will be in teams of three.
There will be a midterm and final that focus on the concepts covered in lecture and in assignments. The structure of the exams will be different than the assignments. While the assignments focus on implementing a compiler, the exams will test you on the concepts and design elements that are discussed in lecture and are implicit in the assignments.
1.7.1 Working in Groups
How you organize work between yourself is ultimately up to you. We recommend you use pair programming (recommended because it is more fun and helps each of you learn from one another). If, however, you decide to divide the workload between team members, this is not strictly forbidden. However, we expect that each team member completely understands the code developed by other team members. Each team member should be prepared to answer questions about all specific code details or implementation decisions. See also the section on Project Evaluation below. If you cannot answer questions about the solution you submitted you should not expect any credit for submitting it.
1.8 Learning Objectives
Implement the basic translations necessary to compile modern high-level languages to modern register machine architectures.
Identify and describe limitations in existing languages.
Design and implement languages to lift limitations.
Describe language features at different levels of abstractions, corresponding to different stages of compilation.
Differentiate between invariants that must be enforced, and invariants that can be relied upon.
1.9 Schedule of Topics
- Intro. to language design: understanding a language, statement-based language
x64
interpreters
type checking
- Creating abstractions: variables and value-based language
the stack
run-time systems
instruction selection
- The pros and cons of abstraction
register allocation
program analysis
graph coloring
optimization
- Exposing low-level control flow
jumps
conditional statements
basic blocks
control flow and program analysis
- Abstracting control flow
tail calls (non-returning functions)
continuation-passing style
calling conventions
control flow and program analysis
- Function call and return
non-tail calls
- Exposing memory access
heap
memory safety
- Adding data structures and primitives
tagging
immediate data: booleans, symbols, integers
structured data: strings, lists, arrays
dynamic typing
memory management
garbage collection
- First-class computations
closure conversion
lexical scope
closure optimizations
- Surface language niceities
implicit casts
syntactic sugar
1.10 Evaluation
The following is a tentative grading scheme for the course, although it is subject to change at the instructor’s discretion.
Project – 50%
Midterm – 20%
Final – 30%
1.10.1 Late Policy
The most recent commit that is pushed to the GitHub Students instance by the deadline is the one that gets graded. If you have a local commit that was before the deadline, but you forgot to push it, then it will not be graded.
To prevent TAs from grading the same assignment twice, you must post on Piazza before the deadline to request a late day. If you need to request a second or third late day, you must post again before your extended deadline.
1 day – 10%
2 day – 30%
3 day – 50%
More than 3 days late – don’t bother
1.10.2 Project Evaluation
The project, the compiler you write through this course, will be divided into approximately 13 assignments. An assignment will be marked each week to provide on-going feedback on your project.
We will evaluate more than merely whether or not your code "works". We may review your code and/or ask you as a group to demonstrate your compiler as part of determining your final grade.
Demonstrate that your solution works in a live demo.
Answer questions about all the code you submitted as a team.
Defend various implementation choices you have made during the course of the project.
Show that you can "think outside the box" about alternative implementation strategies or extensions to the project which may not have been part of the original project specification.
If you used a division of labor rather than collectively developing the compiler, you should be fully aware of the other member’s work, and should be able to answer questions about the whole project as if it was entirely your own work.
It is very important that you think about different possible implementation/design choices throughout the project and make informed decisions. It is often the case that no single choice is "the best". Each strategy typically has some benefits and some drawbacks in terms of efficiency, code maintainability, ease of implementation etc.
To demonstrate that you can think about these choices and their repercussions, you should be able to explain alternatives and their relative benefits, as well as justify the often subjective value judgements that are inherent in choosing one solution over another.
1.10.3 Important: We will grade you on design
In each exercise, we use the word design to remind you that you should not merely write code, but design it. You should design your code, ala the design recipe, for every assignment in this class. It should go without saying, but we have to say it. So here, we are saying it very explicitly:
You must follow the design recipe; start designing first, then implement the exercises. When you start by designing your code, you will force yourself to think through your code carefully before writing it. We will grade your design. We will grade your design even if we forgot to say "design". Early starter code will demonstrate good design. However, even if the starter code does not demonstrate good design, or explicitly say how to design the code, or list the parts of the design recipe, you must design your compiler passes and not merely implement them.
You must write a signature and purpose statement. If the starter code does not have a signature or purpose statement, you must write them. The signature should say what kinds of data the inputs and outputs are. The purpose statement should be a terse, plain English description of what code is meant to accomplish. You should write these first, as they help you think through the code you’re about to write. You will lose marks if you do not write them.
You should follow the template for your input language. The template will help ensure you cover all the cases, get you started writing your code, and avoid unnecessarily complicated code. You’re not writing simple functions in 110 now, so this is not a hard and fast rule. Sometimes, not very often, it will make sense to compose functions or write higher-order functions, or use mutable variables. But when in doubt, you should follow the design template.
Write your tests before you write your code. Use RackUnit: Unit Testing for testing. You must write tests.
You must write unit tests for each pass.
You must write integration tests for the entire compiler for each assignment.
Your tests must test each kind of expression in the source language.
Your tests must test edge cases—
We do not want you to lose marks. We want you all to get an A and learn to be BAMF compiler hackers. Designing your compiler will teach you much more than merely implementing it. So design your code, then write it.
See The Compiler Design Recipe for more on the design recipe in the context of compilers.
1.10.4 Sharing Tests
To encourage discussion of the design of your compilers, you may discuss and share tests on Piazza. However, you may not copy more than half of the tests required for any individual exercise from other students. You or your group must write at least half of your test suite.
You may also discuss ideas for property-based testing, without sharing the implementations for type checkers or interpreters.
No other code should be shared between individuals or teams.
1.11 Copying and Plagiarism Policy
Please read the departmental policy on Plagiarism and Collaboration here.
You might find it interesting to read Dr. Tamara Munzner’s Cheating: The List Of Things I Never Want To Hear Again.
Plagiarism means passing of someone else’s work as your own. Plagiarism is a serious offense and dealt with quite harshly by the university. Cases are forwarded to the Dean’s office and can result in suspension from the university as well as an entry on your academic transcript.
The key to using other people’s code without committing plagiarism is to make it absolutely clear how much of your project is your own work and how much it is based on someone else’s work. When copying something, or adapting it as part of your solution, you are fully responsible to provide clear references to your sources, and explain to what extent your solution is based on these sources. Code comments are a good way to do that for programming assignments.
For the individual assignments, you are expected to work alone. If you do rely on other people’s work, for whatever reason, and properly explain the nature and extent of the collaboration, this is not plagiarism (i.e., with proper explanation, you are not implying that the work is your own). You can submit such a properly commented solution for partial credit.
For the rest of the project you will work in teams. It is expected that the work submitted as a team is collaborative work. As such we will treat the code as being developed by all team members together. We do not require you to provide comments about the details of exactly who wrote every single line of code. However, during the demo, if we sense that there is an imbalance in the contributions made by each team member, we may ask for clarification and we may reflect this imbalance in your final marks.
You are not supposed to copy code or otherwise collaborate with people other than those on your own project team. If you do, then you can still submit your work for partial credit, provided that you provide adequate documentation of your sources and the extent to which your solution is derived from them.
When you are provided starter code, as is the case in most of our assignments, it is automatically assumed that you did not write the starter code yourself. It is therefore not necessary to provide explicit documentation to explain this obvious fact. On the other hand, it is automatically assumed that you are claiming any code that differs from the original starter code as entirely your own work. If this is not the case, you are fully responsible to provide a clear and complete explanation of this fact. Any failure to do so will be considered academic misconduct. Forgetfulness is not an excuse.