Instructor: John Reppy Ry 256 TAs: Kavon Farvardin Truong Son Hy Lecture: TR 13:30-14:50 Ry 251 Recitations: W 15:00-15:50 Ry 276 W 16:00-16:50 Ry 276 Piazza: piazza.com/uchicago/fall2016/cmsc22600/home
Day Time Location Monday 10:00-11:00 Eck 131 Tuesday 15:00-16:00 Ry 256 Wednesday 10:00-11:00 Eck 131 Wednesday 17:00-18:00 Ry 176 Thursday 15:00-16:00 Ry 256 Friday 14:15-15:45 Eck 131
A vast majority of computer programs must deal with textual input of some form or another. This input can range from simple configuration languages to data description languages (e.g., XML) to scripting languages to full-blown programming languages. In this course, we cover the tools and techniques used to process the full range of computer languages (i.e., languages that specify programs and data on computers). Topics include scanning and parsing, tree representations of structured input, simple typechecking, translation between intermediate forms, code generation and optimization, and some run-time system issues. This course is a project oriented course in which students will construct a fully working compiler for a small programming language. There will be homework assignments and programming projects. We will use Standard ML (SML) for the majority of the programming projects.
Students should have taken CMSC 15400 (Introduction to Computer Systems).
The main text for the course is
Title: Modern Compiler Implementation in ML Author: Andrew Appel Publisher: Cambridge University Press, 1998 Errata: www.cs.princeton.edu/~appel/modern/ml/errata.html
The programming assignments will be written using the SML programming language. The following book is one of the better introductions to SML programming.
Title: ML for the Working Programmer (2nd Edition) Authors: L.C. Paulson Publisher: Cambridge University Press, 1996
The following reference may also be useful:
Title: The Standard ML Library Editors: Emden Gansner and John Reppy Publisher: Cambridge University Press, 2004
Grading for the course will be based on the following scheme:
Percentage Component 30% Homework assignments 70% Projects
Class participation will also be a factor in the assignment of grades.
There will be one written exam, which will be given on Thursday November 17 in class.
Date Assignment Due date Sep. 27 Homework 1 Oct. 7 (11pm) Oct. 24 Homework 2 Nov. 1 Nov. 15 Homework 3 Nov. 22
The following handouts cover material that is not in the text.
Examples of Shift-Reduce Parser Construction
This document decribes the various forms of shift-reduce parsing that we covered
in lecture using a common example grammar.
(Coming soon)
Basic polymorphic typechecking
This document describes the techniques for typechecking Hindly-Milner polymorphism.
Assigned Project description Due date Oct 6: Project 1 — Parser and Scanner Oct. 21 Oct. 20: Project 2 — Type checker Nov. 5 Nov. 6: Project 3 — Normalizer Nov. 21 Nov. 22: Project 4 — Code generator Dec. 6
All project assignments will be due at 11pm
Project overview [Revised 2016-10-23] Project 1 — Parser and Scanner [Revised 2016-10-16] The SooL Type System [Revised 2016-11-06] Project 2 — Type Checker [Revised 2016-11-03] Project 3 — Normalizer [Revised 2016-11-17] Project 4 — Code Generation [Revised 2016-12-03] Optimization (extra credit)
Script for downloading and building LLVM tools (build-llvm.sh)
You will find the following resources useful for programming the projects:
The Standard ML of New Jersey (SML/NJ) system. The latest version is 110.80 and is available for most Mac OS X, Windows, and most Unix systems.
The documentation for the The Standard ML Basis Library is available online (there is also a book version of this material that includes additional tutorial material).
SML/NJ Language Processing Tools User Guide [pdf]
User guide to the ml-ulex scanner generator and ml-antlr parser generator tools.
Programming in SML'97: An on-line tutorial
A tutorial introduction to programming in SML.
Single-pass generation of static
single-assignment form for structured languages
This paper by Marc Brandis and Hanspeter Mössenböck describes a simple, single-pass,
algorithm for converting block-structured programs into SSA representation.
[The following is owed to Stuart Kurtz]
The University of Chicago is a scholarly academic community. You need to both understand and internalize the ethics of our community. A good place to start is with the Cadet's Honor Code of the US Military Academy: "A Cadet will not lie, cheat, or steal, or tolerate those who do." It is important to understand that the notion of property that matters most to academics is ideas, and that to pass someone else's ideas off as your own is to lie, cheat, and steal.
The University has a formal policy on Academic Honesty, which is somewhat more verbose than West Point's. Even so, you should read and understand it.
We believe that student interactions are an important and useful means to mastery of the material. We recommend that you discuss the material in this class with other students, and that includes the homework assignments. So what is the boundary between acceptable collaboration and academic misconduct? First, while it is acceptable to discuss homework, it is not acceptable to turn in someone else's work as your own. When the time comes to write down your answer, you should write it down yourself from your own memory. Moreover, you should cite any material discussions, or written sources, e.g.,
Note: I discussed this exercise with Jane Smith.
The University's policy, for its relative length, says less than it should regarding the culpability of those who know of misconduct by others, but do not report it. An all too common case has been where one student has decided to "help" another student by giving them a copy of their assignment, only to have that other student copy it and turn it in. In such cases, we view both students as culpable and pursue disciplinary sanctions against both.
For the student collaborations, it can be a slippery slope that leads from sanctioned collaboration to outright misconduct. But for all the slipperyness, there is a clear line: present only your ideas as yours and attribute all others.
If you have any questions about what is or is not proper academic conduct, please ask your instructors.
Last revised: December 3, 2016