CMSC 22620 / CMSC 32620
Implementation of Computer Languages - II

General Information

Course: CMSC 22620/CMSC 32620
Implementation of Computer Languages - II
Instructor: Matthias Blume TTI-C 257 (UofC Press Building)
TAs: Chunyan Song Hinds 030
Lecture: MWF 1:30-2:20
Ry 251
Mailing list:


CMSC 22620 is the second in a sequence of two courses that cover the implementation of computer languages. The first (CMSC 22610) covered the tools and techniques typically associated with a compiler's front end, i.e, topics such as scanning and parsing, tree representations of structured input, simple typechecking, translation between intermediate forms, interpretation, simple code generation, and some run-time system issues.

In contrast, this course will focus on the back end of a compiler for a general purpose programming languages that translates to machine code for real hardware. It will cover topics such as data representation, representation of control, instruction selection, data-flow analysis, register allocation, and some forms of program optimization. We will also discuss a small selection of problems that arise when compiling modern object-oriented and functional programming languages.

There will be homework assignments and programming projects. We will use Standard ML (SML) for the majority of the programming projects, but some C programming will also be required. Students should have taken CMSC 15400 (Introduction to Computer Systems) as well as CMSC 22610. This means that they should be familiar with C- as well as ML-programming (or at least be prepared to get up to speed with the latter on their own quickly).

Text books

The main text for the course is
Title: Modern Compiler Implementation in ML
Author: Andrew Appel
Publisher: Cambridge University Press, 1998
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

Homework assignments

There will be eight homework assignments over the course of the term. Homework is due at the beginning of class and late homework will not be accepted for credit.
Date Assignment Due date
Apr. 5 Homework 1 Apr. 12
Apr. 14 Homework 2 Apr. 21
Apr. 28 Homework 3 May 5

Course project

The course project is to implement a slightly modified subset of the programming language Java.

The project will be divided into five milestones with the following tentative due dates:

Project 1: Translation to trees
Project 2: Instruction selection
Project 3, milestone 1: liveness analysis or graph coloring
Project 3, milestone 2: graph coloring or liveness analysis
Project 3, milestone 3: register spilling or tree optimization
Project 3, milestone 4: tree optimization or register spilling

Project handouts

Project handouts are available online from the following links:
Project1, code
Project2, code
Project3, code


SML Tutorial slides from lecture (pdf)

The Standard ML Basis Library

The SML/NJ Compilation Manager (CM)

ML-Yacc User's Manual

Programming in SML'97: An on-line tutorial

PowerPC instruction set

Mac OS X Runtime Architecture: PowerPC Calling Conventions (at Apple)

Mac OS X Assembler Guide: Introduction to the Mac OS X Assembler Guide(at Apple)

Handouts and assignments

The following is a list of supporting material, including (but not limited to) handouts that have been distributed in class. As necessary, we will post revisions here.

topics laundry list
Syntax of (Not Quite) MiniJava
Code for Front-End (sample2) The grammer has been corrected, and the tarball now contains file tree.sml with ML type definitions for our tree language.
Code for Front-End (project1) File translate.sml is now a template to be filled in. Look at layout.sml for information on how memory objects (objects and arrays) are to be accessed.
Preliminary list of PowerPC instructions that we will need for the project (to be revised and extended; last update 04/14/2004)
Slides for lecture on instructions selection (adapted from Prof. David MacQueen's original slides)
Tarball with sample C code and corresponding PowerPC/Mach-O assembly code In particular, these examples show how to deal with access to global symbols (both local and external).
Code for Minijava compiler (project2) File cg.sml is now a template to be filled in.
Slides for lecture on liveness analysis (adapted from Prof. David MacQueen's original slides)
Slides for lecture on graph-coloring register allocation (adapted from Prof. David MacQueen's original slides)
Code for Minijava compiler (project3) Templates to be filled in are cg.sml, liveness.sml, color.sml, rewrite.sml, simplify-tree.sml.
Sample code related to CPS A little lambda language with exceptions and call/cc, two versions of the CPS language (one with explicit getters and setters of the exception handler, the other without such operations), and the two corresponding versions of the CPS converter.

Academic Honesty

[The following is due 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: March 17, 2004.