15-417 HOT Compilation
Fall 2015

Karl Crary
TR Noon – 1:30
Gates-Hillman 4211

Course Information

The course covers the implementation of compilers for higher-order typed languages such as ML. Topics include type checking, type directed compilation, elaboration, phase splitting, CPS conversion, closure conversion, allocation, and garbage collection. The course is disjoint from the standard compilers course (15-411); thus, topics such as parsing and code generation are not covered. Students will implement an ML compiler and runtime system as a term project.

Prerequisite: 15-312 Principles of Programming Languages (or equivalent)

There is no textbook for the course. Attendance in lectures is essential.

Announcements

Dec 21 The final due date for projects 5 and 7 is extended to December 22.
Dec 10 The final due date for all projects and project revisions is December 21.
Dec 10 The final project has been issued. It is due December 21.
Nov 26 Corrected project 5 binaries have been posted.
Nov 21 A minor revision of the sixth project's support code has been posted.
Nov 20 The sixth project has been issued. It is due December 8.
Nov 13 The fifth project has been issued. It is due December 1.
Nov 3 Corrected project 4 binaries have been posted.
Oct 22 The fourth project has been issued. It is due November 5.
Oct 21 To typeset an atom in Latex, use the macros: 
\newcommand{\satom}[1]{\llparenthesis{\,#1\,}\rrparenthesis}
\newcommand{\datom}[1]{\langle\hspace{-0.2em}|%
{\,#1\,}|\hspace{-0.2em}\rangle}
This will require the stmaryrd package.
Oct 21 A corrected version of the third project's support code has been posted.
Oct 9 The third project has been issued. It is due October 23.
Sep 29 The second project has been issued. It is due October 6.
Sep 11 The first project has been issued. It is due September 18.

Topics

Sep 1 F-omega
Sep 3 Typechecking for F-omega
Sep 8 Binding
Sep 15 Singleton kinds
Sep 22 Typechecking for singleton kinds
Sep 24 Type-directed translation
Sep 29 CPS conversion
Oct 8 Closure conversion
Oct 15 Allocation
Oct 20 Module type theory
Nov 3 Phase splitting
Nov 12 Garbage collection
Nov 19 Elaboration

Projects

Students will complete several projects through which they will implement an ML compiler and runtime system.

Form of projects

For each project, students will be given a Standard ML signature to implement. The intended meaning of that signature will be made clear in class. Attendance in lectures is essential.

This signature to implement will be included in a collection of resource code that we will supply. Students should not modify any resource code. (Since projects will be graded using the original resource code, any modifications will likely result in project failure.)

On some occasions, we may supply some resource code in executable form, without supplying source code. We will do so by supplying an SML of New Jersey image extended with the relevant code.

Project submission

Students should hand in their projects by concatenating their source code into a single file and submitting it to Autolab.

This file should not include the resource code that we supply. Also, this file should not contain diagnostic code; submissions should not print anything to console.

Commenced projects

Project 1
Equivalence checking for F-omega.
Implement Equiv : EQUIV.
[support code]
Due September 18. Submit here.

Project 2
Equivalence checking for singleton kinds.
Implement Equiv : EQUIV.
[support code]
Due October 6. Submit here.

Project 3
CPS conversion.
Implement CpsConvert : CPS_CONVERT.
[support code, Windows heap image (9MB), Linux heap image (9MB), Mac heap image (9MB)]
Due October 23. Submit here.

Project 4
Closure conversion.
Implement ClosureConvert : CLOSURE_CONVERT.
Implement Hoist : HOIST.
[support code, Windows heap image (9MB), Linux heap image (9MB), Mac heap image (9MB)]
Due November 5. Submit here.

Project 5
Phase splitting.
Implement PhaseSplit : PHASE_SPLIT.
[support code, Windows heap image (9MB), Linux heap image (9MB), Mac heap image (8MB)]
Due December 1. Submit here.

Project 6
Garbage collection.
Implement the function gc(), as described in README.
[support code, Windows heap image (9MB), Linux heap image (9MB), Mac heap image (8MB)]
Due December 8. Submit here.

Project 7
Elaboration.
Implement Elaborate : ELABORATE.
[support code, Windows heap image (9MB), Linux heap image (9MB), Mac heap image (8MB)]
Due December 21. Submit here.

SML/NJ runtime binaries
Windows runtime
Linux runtime

Stress test sources
test1.sml
test2.sml
test3.sml
gctest.sml, gctest.c

Grading

Grading is based on the number of successfully completed projects. For each project, students will submit their solution by the project's due date. On the due date, the projects will be graded automatically using a variety of test cases. If a student's solution passes all tests, the project will be marked as completed. If not, no score will be recorded and the student will have the opportunity to correct his/her solution. Students will be given a second-pass due date, by which they must submit their revised solution, which will be tested in a similar fashion to his/her original submission. This process continues until the project has been completed, or the course has ended.

The final due date for all projects and project revisions is December 21.

Students are urged not to try to exploit the system by turning in "token" submissions to procrastinate a project. This places students in the unfortunate position of having to complete several earlier projects during the busiest part of their semester. Therefore, token submission will not be accepted. If, in the judgement of the instructor, any submission does not represent a credible effort, the project will be marked as failed, and no further submissions for that project will be accepted.

It is expected that most students will successfully complete all the projects and earn an A for the course.