CMSC430: Introduction to Compilers

Fall, 2017

Compilers is the study of programming language design and implementation.

Today’s programming languages give programmers unprecedented power and flexibility, and yet sometimes they are still not enough. There are many occasions when it is possible to encode the solution to a programming problem in an existing language, but at the cost of significant effort, loss of elegance and clarity, and reduced maintainability. In these cases, often the best way to solve a problem is to develop a new language that makes the solution easy to express correctly, succinctly, and maintainably. Examples of such languages range from “little” ones like Make, XML, JSON, YAML, Wiki, bash, Windows .ini files, autoconf, etc., to “big” ones like Perl, Python, Ruby, PHP, JavaScript, R, MATLAB, etc. All of these languages were invented because existing languages just weren’t good enough, and in the course of your career, you also may find yourself needing to invent a new programming language!

The goal of CMSC 430 is to arm students with the ability to design, implement, and extend a programming language. Throughout the course, students will design and implement a substantial functional-language compiler of their own, over the course of several projects, and will explore various compiler-related topics such as intermediate representations, desugaring, continuation-passing style, closure conversion, formal semantics, garbage collection, type checking, and flow analysis.

Schedule

Weekly Topics

Below is a (tentative) list of topics we will be covering each week. As the term progresses, some of these topics will likely change or be moved around to adapt to our progress. Such changes will be reflected here as they occur.

Slides and any other materials on these topics may be posted below. I will use Keynote to export pdf and pptx versions of the slides, but sometimes these will not look quite right due to animations or fonts.

• Intro slides (pdf) (pptx)

• Church slides (pdf) (pptx)

• Redex Semantics slides (pdf) (pptx)

• Abstract Machines slides (pdf) (pptx)

• Store-passing Style slides (pdf) (pptx)

• Desugaring Letrec slides (pdf) (pptx)

• CEK slides (pdf) (pptx)

• SSA slides (pdf) (pptx)

• CPS slides (pdf) (pptx)

• Flow Analysis slides (pdf) (pptx)

• Closure conversion slides (pdf) (pptx)

• LLVM IR slides (pdf) (pptx)

• Register Allocation slides (pdf) (pptx)

• HAMT slides (pdf) (pptx)

• Garbage collection slides (pdf) (pptx)

Programming Assignments & Projects

• Assignment 0: Warm-up with Racket (Due: Tuesday, Sept 5)

• Assignment 1: Church encoder (Due: Thursday, Sept 21)

• Assignment 2 (project): Desugaring, promises, exceptions (Due: Friday, Oct 13)

• Assignment 3 (project): Assignment, ANF, CPS-conversion (Due: Monday, Nov 6th)

• Assignment 4 (project): Closure conversion, LLVM emission (Due: Thursday, Nov 30th)

• Assignment 5 (project): Top-level, defines, quasiquote, and (optional) pattern matching (Due: Tuesday, Dec 12th)

Announcements

All announcements will be made on this page or on Piazza. Please sign-up at the start of the semester.

Emergency announcement such as last-minute class cancelations (which should not happen often), will also be announced via the university email system.

• Live-coding an interpreter is posted.

• Assignment 1, reference solution is posted.

• The finished store-passing interpreter is posted.

• Live-coding a back-tracking search using call/cc is posted.

• Assignment 2 (i.e., the first pass of the class compiler) is posted.

• Take a look at the r7rs-small spec. They describe and formalize many of the forms we’re supporting.

• Live-coding a stack-passing interpreter is posted.

• See the end of the CEK slides (download pdf) or the new note on Piazza for the implementation of dynamic-wind and call/cc. An outline for guard is also in the CEK slides.

• Midterm review with self-study questions is posted.

• The latest stack-passing interpreter and our st-ack function is posted.

• Reference solutions for assignment 2 are posted.

• Assignment 3 is posted.

• ANF conversion and CPS conversion live-coding are posted.

• Recommended reading: 1.1-1.5,2.1 from Principles of Program Analysis by Nielson, Nielson, and Hankin (pdf).

• Livecoding a 0-CFA closure analyis is posted.

• Livecoding a bottom-up closure converter is posted.

• Reference solution for assignment 3 is posted.

• Assignment 4 is posted.

• An example HAMT implementation, written in C++ with Boehm GC, is posted.

• Assignment 5 is posted.

• Reference solution for assignment 4 is posted.

• Take-home final is posted.

• Reference solution for assignment 5 is posted.

Grades

All grades will be made on grades.cs.umd.edu.

Submit

All submissions will be made on submit.cs.umd.edu.

Syllabus

Prerequisites

Computing Resources

Programming projects may be developed on the GRACE cluster. You should download and install Racket 6.10 for development on your own machine. Assignments must run correctly on this version of Racket.

All project submissions will be graded solely based on the results obtained by the submit server. As your own machine may be setup somewhat differently, it is strongly recommend that you should complete the assignment well in advance of the deadline and ensure it is working by checking it against the public tests via submit.cs.umd.edu.

Office Hours and Web Forum

Office hours for the instructional staff will be posted on the course web page within a few days into the semester.

While we will provide assistance with assignments during office hours, you are responsible for developing and debugging your own programs. Do not rely on the instructional staff to make your project work.

Important announcements will be made in class or on the class web page. Please make it a habit to check the class web page daily. You may also use the class web forum to ask general questions of interest to the class as a whole, e.g., administrative issues or project clarification questions. Please do not post any information that would violate the university academic integrity policy.

Grading

Assignments, projects, and exams will not be graded on a curve, however final letter grades may be. The grades server will provide you with up-to-date grades and statistics so you can gauge your own progress.

You are responsible for all material discussed in lecture and posted on the class web page, including announcements, deadlines, policies, etc. During the semester we may provide ungraded practice homework exercises and solutions. While we will not collect these exercises, completing them is essential preparation for exams. You may work together on these ungraded homeworks, and you may of course come to office hours for additional help.

Your final course grade will be determined according to the following percentages:

Any request for reconsideration of any grading on coursework must be submitted within one week of when it is returned. Exam regrading requests must be made in writing. Any coursework submitted for reconsideration may be regraded in its entirety, which could result in a lower score if warranted.

Final course grades will be curved as necessary, based on each student’s total numeric score for all coursework at the end of the semester. Important: Completing the programming assignments is an essential part of the course. Therefore, we may fail any student who does not make a good-faith attempt on all course projects, regardless of the student’s performance or scores on the other coursework.

Programming Projects

Projects must be submitted electronically following the instructions given in class. Projects may not be submitted by any other means (e.g., please do not email your projects to us). It is your responsibility to test your program and verify that it works properly before submitting. All projects are due at 11:59:59pm on the day indicated on the project assignment, according to the submission server’s internal clock. Projects will not be accepted late unless by special permission given in advance.

Project extensions will not be granted due to system problems, network problems, power outages, etc., so do not wait to submit a project until the night it is due. You may submit multiple times up to the deadline, and only your last on-time submission is graded. Similarly, if you submit late, only your last submission before the deadline will be graded. No consideration in grading will be made for errors made in transferring files or submitting the wrong version of your project. Having a working, unsubmitted version will not count; only submitted code will be be counted.

Unlike lower-level programming classes, we will not always provide you with test cases before projects are due. Instead, you will be responsible for developing your own techniques for testing your projects. To reiterate: your projects will be graded based on test cases not provided in advance. Because grading is done automatically, you must follow the project specification exactly. Also, while projects will generally not be graded on style or documentation, we reserve the right to manually grade program source code for some projects.

Finally, any "hard coding" in a project assignment will result in a score of zero for that project, and is considered a bad-faith effort. Hard coding refers to attempting to make a program appear as if it works correctly, when in fact it does not. One example of hard coding would be printing the desired output instead of computing it. This is only one example, and if you have any questions as to what constitutes hard coding, be sure to ask ahead of time.

Exam Scheduling

The class includes a midterm and a final exam. Dates for the exams are posted on the Schedule. The date of these exams is tentative and may change based on the University Registrar. Confirmation of an exam date will be posted on the schedule at least two weeks in advance of any exam.

Excused Absences

Besides the policies in this syllabus, the University’s policies apply during the semester. Various policies that may be relevant appear in the Undergraduate Catalog.

If you experience difficulty during the semester keeping up with the academic demands of your courses, you may consider contacting the Learning Assistance Service in 2201 Shoemaker Building at (301) 314-7693. Their educational counselors can help with time management issues, reading, note-taking, and exam preparation skills.

Any student who needs to be excused for an absence from a single lecture, recitation, or lab due to a medically necessitated absence shall: a) Make a reasonable attempt to inform the instructor of his/her illness prior to the class. b) Upon returning to the class, present their instructor with a self-signed note attesting to the date of their illness. Each note must contain an acknowledgment by the student that the information provided is true and correct. Providing false information to University officials is prohibited under Part 9(i) of the Code of Student Conduct (V-1.00(B) University of Maryland Code of Student Conduct) and may result in disciplinary action.

The self-documentation may not be used for the Major Scheduled Grading Events as defined below and it may only be used for only 1 class meeting during the semester. Any student who needs to be excused for a prolonged absence (2 or more consecutive class meetings), or for a Major Scheduled Grading Event, must provide written documentation of the illness from the Health Center or from an outside health care provider. This documentation must verify dates of treatment and indicate the timeframe that the student was unable to meet academic responsibilities. In addition, it must contain the name and phone number of the medical service provider to be used if verification is needed. No diagnostic information will ever be requested. The Major Scheduled Grading Events for this course include project deadlines and any midterm or final exam.

It is the University’s policy to provide accommodations for students with religious observances conflicting with exams, but it is your responsibility to inform the instructor in advance of intended religious observances. Written notice must be provided immediately upon an exam date being announced or confirmed in order for an absence to be excused. If you have a conflict with one of the planned exams, you must inform us prior to the end of the first two weeks of the class.

For missed exams due to excused absences, the instructor will arrange a makeup exam. However, unless immediate notice is given as early as possible of the reason for any missed coursework, an excused absence may not be granted. If you might miss an exam for any other reason other than those above, you must contact the instructor in advance to discuss the circumstances. We are not obligated to offer a substitute assignment or to provide a makeup exam unless the failure to perform was due to an excused absence.

The policies for excused absences do not apply to project assignments. Projects will be assigned with sufficient time to be completed by students who have a reasonable understanding of the necessary material and begin promptly. In cases of extremely serious documented illness of lengthy duration or other protracted, severe emergency situations, the instructor may consider extensions on project assignments, depending upon the specific circumstances.

Students with Disabilities

Students with disabilities who have been certified by Disability Support Services as needing any type of special accommodations should see the instructor as soon as possible within the first two weeks of class. All arrangements for exam accommodations as a result of disability must be made and arranged with the instructor at least three business days prior to the exam date, or accommodations will not be made.

Academic Integrity

Don’t cheat. Just don’t do it.

You may not share code, view one another’s code, share or discuss solutions. We have tools to check for duplicate code modulo variable renaming, comments, clause ordering, etc. It’s not worth it.

The Campus Senate has adopted a policy asking students to include the following statement on each examination or assignment in every course: "I pledge on my honor that I have not given or received any unauthorized assistance on this examination (or assignment)." Consequently, you will be requested to include this pledge on each exam and project. Please also carefully read the Office of Information Technology’s policy regarding acceptable use of computer accounts.

Programming projects are to be written individually, therefore cooperation or use of unauthorized materials on projects is a violation of the University’s Code of Academic Integrity. Any evidence of this, or of unacceptable use of computer accounts, use of unauthorized materials or cooperation on exams or quizzes, or other possible violations of the Honor Code, will be submitted to the Student Honor Council, which could result in an XF for the course, suspension, or expulsion.

• For learning the course concepts (including the programming languages), students are welcome to study together or to receive help from anyone else. You may discuss with others the project requirements, the features of the programming languages used, what was discussed in class and in the class web forum, and general syntax errors. Examples of questions that would be allowed are "Does a Java class definition end in a semicolon?" or "What does a ’class not found’ error indicate?", because they convey no information about the contents of a project.

• When it comes to actually writing a project assignment, other than help from the instructional staff a project must solely and entirely be your own work. Working with another student or individual, or using anyone else’s work in any way except as noted in this paragraph, is a violation of the code of academic integrity and will be reported to the Honor Council. You may not discuss design of any part of a project with anyone except the instructor or teaching assistants. Examples of questions you may not ask others might be "How did you implement this part of the project?" or "Please look at my code and help me find my stupid syntax error!". You may not use any disallowed source of information in creating either their project design or code. When writing projects you are free to use ideas or short fragments of code from published textbooks or publicly available information, but the specific source must be cited in a comment in the relevant section of the program.

Violations of the Code of Academic Integrity may include, but are not limited to:

1. Failing to do all or any of the work on a project by yourself, other than assistance from the instructional staff.

2. Using any ideas or any part of another person’s project, or copying any other individual’s work in any way.

3. Giving any parts or ideas from your project, including test data, to another student.

4. Allowing any other students access to your program on any computer system.

5. Transferring any part of a project to or from another student or individual by any means, electronic or otherwise.

If you have any question about a particular situation or source then consult with the instructors in advance. Should you have difficulty with a programming assignment you should see the instructional staff in office hours, and not solicit help from anyone else in violation of these rules.

It is the responsibility, under the honor policy, of anyone who suspects an incident of academic dishonesty has occurred to report it to their instructor, or directly to the Honor Council.

Every semester the department has discovered a number of students attempting to cheat on project assignments, in violation of academic integrity requirements. Students’ academic careers have been significantly affected by a decision to cheat. Think about whether you want to join them before contemplating cheating, or before helping a friend to cheat.

You are welcome and encouraged to study and compare or discuss their implementations of the programming projects with any others after they are graded, provided that all of the students in question have received nonzero scores for that project assignment, and if that project will not be extended upon in a later project assignment.

Course Evaluations

If you have a suggestion for improving this class, don’t hesitate to tell the instructor or TA(s) dring the semester. At the end of the semester, please don’t forget to provide your feedback using the campus-wide CourseEvalUM system. Your comments will help make this class better.

Right to Change Information

Although every effort has been made to be complete and accurate, unforeseen circumstances arising during the semester could require the adjustment of any material given here. Consequently, given due notice to students, the instructors reserve the right to change any information on this syllabus or in other course materials.

Course Materials

Some lecture slides include materials developed by Jeffrey S. Foster, Chau-Wen Tseng, Keith Cooper, and Lori Pollock.

Resources

General

• PLUM: Programming Languages at University of Maryland

• Programming language theory texts online

• Great works in programming languages

• PL Enthusiast

PL Textbooks

Here are books you may be interested in if you want to go into much more depth on some of the class material, and in many cases beyond it. None of these is required for the class. The books with boldfaced titles are particularly good.

• Aho, Lam, Sethi, Ullman, Compilers: Principles, Techniques, and Tools (ALSU)

• Appel, Compiling with Continuations

• Barendregt, Lambda Calculi with Types (web download)

• Clarke, Grumberg, and Peled, Model Checking

• Felleisen, Findler, and Flatt, Semantics Engineering with PLT Redex

• Gries, The Science of Programming

• Hankin, Lambda Calculi: A Guide for Computer Scientists.

• Huth and Ryan, Logic in Computer Science: Modelling and Reasoning about Systems

• Mitchell, Foundations for Programming Languages

• Muchnick, Advanced Compiler Design and Implementation

• Nielson and Nielson, Semantics with Applications: A Formal Introduction (web download)

• Nielson, Nielson, and Hankin, Principles of Program Analysis

• Pierce, Types and Programming Languages (TAPL)

• Winskel, The Formal Semantics of Programming Languages

Parsing

• LR parsing on wikipedia

• Bison - GNU parser generator

• ocamllex and ocamlyacc documentation

Type Systems

• TAPL

• Luca Cardelli, Type Systems

• David MacQueen, Quick Introduction to Type Systems

• Neal Parikh, Notes on Types and Programming Languages