CMSC 22610
Implementation of Computer Languages - I
Winter 2005

General Information

Course: CMSC 22610
Implementation of Computer Languages - I
Instructor: John Reppy Hinds 033
Tue. 4-5pm.
TA: Haitao Gao Hinds 030
Wed. 9-10am; Fri. 3-4pm
Lecture: TR 1:30-2:50
Ry 251
Mailing list:


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 will 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, interpretation, simple code generation, and some run-time system issues. 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) and be familiar with C programming.

This course is the first in a sequence of two courses that cover the implementation of computer languages. The second course (CMSC 22620) covers more advanced issues related specifically to the translation of general purpose programming languages.

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
The following reference may also be useful:
Title: The Standard ML Library
Editors: Emden Gansner and John Reppy
Publisher: Cambridge University Press, 2004

Homework assignments

Homework is due at the beginning of class and late homework will not be accepted for credit.
Date Assignment Due date
Jan. 4 Homework 1 Jan. 11
Jan. 11 Homework 2 Jan. 20
Feb. 3 Homework 3 Feb. 10
Feb. 10 Homework 4 Feb. 17
Feb. 24 Homework 5 Mar. 3
Mar. 3 Homework 6 Mar. 10

Course project

The course project is to implement a subset of ML with simple subtyping, called MLR. The project will be divided into four milestones with the following tentative due dates:
Jan. 21:Project 1 --- Lexer
Jan. 31:Project 2 --- Parser
Feb. 25:Project 3 --- Typechecker
Mar. 17:Project 4 --- Code generation and runtime

Project handouts

Project handouts are available online from the following links:
Project overview
Project 1 --- MLR Lexer
Project 1 Sample code [.tgz]
Project 2 --- MLR Parser (Revised 2005-01-24)
Project 3 --- MLR Typechecker
Project 4 --- MLR Interpretation (Revised March 11, 2005)
Handout 5 --- MLR code generation (Revised March 12, 2005)
Handout 6 --- Runtime functions
MLR virtual machine source (Revised March 21, 2005)
Sample MLR programs (Revised March 14, 2005)


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

Handouts and assignments

The following is a list of the handouts that have been distributed in class with links to PDF files. As necessary, we will post revisions here.

Handout 1 --- Course information
Handout 2 --- Project overview
Handout 3 --- Introduction to CVS
Handout 4 --- Basic polymorphic typechecking
Handout 5 --- MLR code generation (Revised March 12, 2005)
Handout 6 --- Runtime functions
Homework 1
Homework 2
Homework 3
Homework 4
Homework 5
Homework 6

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 21 2005.