CMSC 430
Introduction to Compilers, Fall 2016

Staff

Name Office E-mail Office Hours
(also available by appointment)
Jeff Foster 3423 AVW jfoster at cs T 10-11:30am, W 1-2pm
Willem Wyndham 4101/4103 AVW willem at cs T 1-3pm, Th 2-4pm
Sam Barham 4101/4103 AVW sbarham at terpmail M 10am-12pm, Th 10am-12pm

Information

Location 1122 CSIC (subject to change until the start of the semester)
TimeMW 2:00-3:15pm
Midterm 1Mon, Oct 10, in class
Midterm 2Mon, Nov 21, in class
FinalSat, Dec 17, 2:30-4:30pm (change announced Dec 16!), 1122 CSIC
TextbooksThere are no required or recommended texts. See the resources page for useful online links.

Final Exam Office Hours

Mon, Dec 12 10am-12pm - Sam; 12-2pm - Willem
Tue, Dec 13 10am-11:30am - Sam; 12:20-3pm - Willem
Wed, Dec 14 10am-11:30am - Sam; 2-4pm - Willem
Thu, Dec 15 10am-1pm - Sam; 1-4pm - Willem
Fri, Dec 16 12-2pm - Sam; 2-4pm - Willem

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 several related languages, and will explore parsing, syntax querying, dataflow analysis, compilation to bytecode, type systems, and language interoperation.

WeekMondayWednesday
Aug 29 Introduction
OCaml
Project 0
OCaml
Project 1
Sep 5 Labor Day - No class Lexing and Parsing
03-examples.tar.gz
Sep 12 Lexing and Parsing Lexing and Parsing
Project 2
Sep 19 Lexing and Parsing Operational Semantics
Sep 26 Operational Semantics Operational Semantics
04-op-sem.ml
Project 3
Oct 3 Intermediate Representations
05-vm.ml
Midterm Review
Intermediate Representations
Oct 10 Midterm 1
Parsing problems (solution)
Op. Sem. problems (solution)
Code Geneation
06-codegen-1.ml
Oct 17 Code Generation
06-codegen-2.ml
Code Generation
Project 4
Oct 24 Optimization Data Flow Analysis
(with animations)
Oct 31 Data Flow Analysis Data Flow Analysis
Type Systems
Project 5
Nov 7 Type Systems Type Systems
Nov 14 Type Systems Symbolic Execution
Nov 21 Midterm 2
Data Flow problems (solution)
Type Sys. problems (solution)
Day before Thanksgiving - No class
Nov 28 Register Allocation
Project 6
Language overview
Dec 5 Language overview Static Single Assignment
Types for Ruby
Dec 12 Final Exam Review
Last class
Project 0Learn about some languages
Project 1OCaml Warmup
Project 2SMT Solver Front-End
Project 3RubeVM Interpreter
Project 4Simpl Compiler
Project 5Rube Compiler
Project 6Rube Type Checker
Syllabus subject to change until the start of the semester
Prerequisites: Minimum grade of C- in CMSC330 and CMSC351; and permission of CMNS-Computer Science department. Or must be in the (Computer Science (Doctoral), Computer Science (Master's)) program.
Credits: 3 credits

List of Topics (Tentative)

The following list of lecture topics will vary according to the pace of lecture.

Computing Resources

Programming projects will be developed on the GRACE cluster.

If you have access to another system you are welcome to do your development there instead, but all project submissions must work correctly on the GRACE cluster, and your projects will be graded solely based on their results on the cluster (by the submit server). Because language and library versions may vary with the installation, in unfortunate circumstances a program might work perfectly on your system but not work at all on the cluster. Thus we strongly recommend that if you develop any project on another system, you should complete it several days early to have time to address any compatibility problems.

Office Hours and Web Forum

Office hours for the instructional staff will be posted on the course web page 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 Piazza. Please make it a habit to check Piazza daily, and/or sign up to receive email when updates are posted to Piazza. 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

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:

6 Programming projects42%
2 Midterms34%
Final23%
Meet your professor1%

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 may be submitted up to 24 hours late for a 10% penalty. For example, a project that would earn 90 points for an on-time submission will earn 81 (which is 90 times 0.90) if submitted late. Note that your project score as it appears on the project submission server will not include any late penalties. Any penalties will be incorporated into the final project grade on the grade server. If you submit both on-time and late, your project will received the maximum of the penalty-adjusted scores.

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. You will receive the maximum of your on-time and late score (with penalty applied) for each project. 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 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 two midterms and a final exam. Tentative dates for the exams will be posted on the class web site. The exact dates will be confirmed later, and may vary due to the progress of lecture and other factors. We will let you know the exact dates well in advance.

General Course Related Policies

Please see the Office of Undergraduate Studies page on Course Related Policies.

Learning Assistance Service

If you are experiencing difficulties in keeping up with the academic demands of this course, contact the Learning Assistance Service, 2202 Shoemaker Building, 301-314-7693. Their academic coaches can help with time management, reading, math learning skills, note-taking and exam preparation skills. All their services are free to UM students.

Excused Absences

Please see the Course Related Policies web page for an explanation of what constitutes an excused absence. Note that 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.

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

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

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.

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. Project solutions may not be posted online. 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.

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

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

General

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.

Parsing

Type Systems

Web Accessibility