General Information

Instructor:

John Reppy

jhr@cs.uchicago.edu.

TAs:

Pouya Mahdi Gholami

Sydney Zink

This term, the course will be taught online with asynchronous lectures and synchronous recitation sections.

We use Piazza to provide interactive help and for posting class announcements.

Course Description

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. We use Standard ML (SML) as the primary implementation language for the programming projects.

It is expected that you have had some experience with functional programming (from either CMSC 15100 or 16100) and that you have taken CMSC 15400 (Introduction to Computer Systems).

Lectures

Lectures are pre-recorded videos hosted by Panopto and posted on the course’s Canvas page. The lectures are organized into eight modules, as follows:

Module Post Date Completion Date Description

1

9/28

10/2

Course Information

2

9/30

10/15

Scanning

3

10/12

10/27

Parsing

4

10/26

11/7

Type Checking

5

11/15

12/6

Intermediate Representations

6

11/18

12/6

Program Analysis

7

12/2

12/7

Code Generation

Most lectures include a short quiz at the end of the lecture that should be completed before the end of the module’s period.

Recitations

You are expected to participate in a recitation section via Zoom each week (except for 9th week, which is Thanksgiving break).

Week Date Topic

1

9/30

Crash course in Standard ML

2

10/7

Project 1 Overview and using ML-ULex

3

10/14

Using ML-Antlr

4

10/21

Project 2 Overview

5

10/28

Q&A

6

11/4

Q&A

7

11/11

Project 3 Review

8

11/18

Project 4 Overview and LLVM

9

Thanksgiving break

10

12/2

Garbage Collection Hooks

Office Hours

Office hours will be conducted via Zoom. We will post a Zoom link on Piazza shortly before office hours begin. If you want to talk to the host, add a response to the Piazza thread; we will use the order of these responses as a queuing mechanism. When you join the meeting, you will be put into the waiting room; and the host let you into the meeting when it is your turn. It is important that we can identify you in the waiting room, so please include your "Zoom" identity in the Piazza post.

The schedule of office hours is as follows:

Weekday Time Host

Monday

17:00-18:00

Pouya Mahdi Gholami

Tuesday

11:00-12:00

John Reppy

Thursday

14:00-15:00

John Reppy

Sunday

13:00-14:00

Sydney Zink

You may also schedule a meeting with the instructor by sending email to jhr@cs.uchicago.edu.

Course Project

The project for the course is to implement a small functional programming language, called LangF, which is an enrichment of System F.

The project grade will comprise the bulk of your course grade, and will involve a significant effort to complete, so it is important that you give it sufficient time and effort. Because the seed code for each part includes a solution for the previous parts, we do not accept late submissions or give extensions.

The project consists of four parts:

Post Date Description Due Date

10/07

Project 1 — Parser

10/20

10/21

Project 2 — Type Checker

11/05

11/06

Project 3 — Optimizer

11/20

11/21

Project 4 — Code Generator

12/10

Projects will be due at 23:59 (Chicago time) on their due date.

Project Documents

The project description and other documents are posted here and on Canvas.

Post Date Description Revised

09/30

Project Overview

10/18

10/07

Project 1 — Parser

10/18

10/21

Project 2 — Type Checker

10/30

10/21

The LangF Type System

11/03

11/07

Project 3 — LangF Simplification and Optimization

11/19

11/11

SimpleAST Optimizations

11/19

11/21

Project 4 — Closure Conversion and Code Generator

12/09

11/25

LLVM Code Generation

Standard ML

As mentioned above, we use the Standard ML language for the programming projects in this course. Standard ML (usually refered to as SML) is a strict functional programming language with a long history an a number of implementations. For this course, we use Version 110.98.1 of the Standard ML of New Jersey (SML/NJ) system. This software is open source and supports Intel/AMD processors running Linux (32 and 64-bit), macOS (32 and 64-bit), and Windows (32-bit).

Note

While it will be possible to develop the first three parts of the course project on Windows, the last part requires either Linux or macOS.

Textbooks

We do not require a textbook for this class, but we recommend the following if you are looking for a source of additional information.

  • Modern Compiler Implementation in ML, by Andrew Apply. Cambridge University Press, 1998.
    This book is a good overview of compilers that uses SML as its implementation language (there is also a version for Java).

  • ML for the Working Programmer (2nd Ed.), by L.C. Paulson, Cambridge University Press, 1996.
    This book is one of the better introductions to programming with SML.

Online Resources

SML Tutorials

There are a number of online SML tutorials. We recommend the following:

SML Documentation

LLVM Documentation

The last part of the project will use the LLVM toolchain to produce machine code that can be executed.

Academic Honesty

Note

The following discussion 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.

Recording and Deletion Policies for Academic Year 2020-1

The Recording and Deletion Policies for the current academic year can be found in the Student Manual under Petitions, Audio & Video Recording on Campus.

  • Do not record, share, or disseminate any course sessions, videos, transcripts, audio, or chats.

  • Do not share links for the course to those not currently enrolled.

  • Any Zoom cloud recordings will be automatically deleted 90 days after the completion of the recording.

Zoom guidelines

We will be using Zoom for some parts of this class. We expect your interactions via Zoom to be consistent with an in-person class experience. Respect the people you are working with. Enter the Zoom meetings muted if possible (unfortunately, it will not be possible if you’re calling in), and unmute to speak. Raise your hand if you would like to speak. [There’s a “Raise Hand” button on the participant page.] If your background is unusually noisy, use the chat channel instead of unmuting. We strongly encourage you to have your camera on during our Zoom sessions, but we will understand if some of you prefer to keep your video off.

Note that you can set your name in your Zoom profile, so you do not have to go with whatever was assigned. Feel free to include your pronouns in your name (if you do, please include them after your last name).

Some of our Zoom recitation meetings may be recorded and saved to the cloud to allow students in this class to review the discussion, and especially to allow students who cannot participate the opportunity to benefit from them. We will not make these recordings available to anyone but class participants, we will not make them available after the quarter, and students will not be allowed to save copies. We have no way to guarantee that students will follow this policy, however. If you have FERPA concerns, please mask yourself accordingly, e.g., by turning off video and using an alias.

COVID-19 Policies

Since this class is remote this year, most of these policies do not directly apply, but we include them for your information.

UChicago Health Pact

All students on campus are required to adhere to the guidelines in the UChicago Health Pact in order to promote a safe environment in the classroom.

Secure face coverings must be worn appropriately at all times while in University buildings. Maintain a distance of 6 feet from others. Do not attend an in-person class if you feel unwell or are experiencing COVID-19 related symptoms The complete text of the UChicago Health Pact along with additional information about COVID-19 protocols can be found here.

Any concerns over inappropriate PPE usage, physical distancing, cleaning/disinfection, or other COVID-19 related public health concerns should be directed to UCAIR.

If there is an emergency, call 773-702-8181 or dial 123 on any campus phone.

Reporting COVID-19 Exposure or a Confirmed Case

If you were potentially exposed to COVID-19 or your COVID-19 test results come back positive, reach out immediately to C19HealthReport@uchicago.edu.