Fundamentals of Programming Languages

CSCI 5535 and ECEN 5533

View project on GitHub

Homework Projects

All homework must be completed in pairs only. You may discuss the problems with other groups. If you discuss the problems with another group, you must cite them (following the collaboration policy).

Homework solutions should be submitted by 6:00 p.m. on the due date (with an automatic twenty-four hour extension). Please take note of the distinction between the assignment deadline and the automatic extension. Questions about the assignment may not answered as promptly after the deadline, particularly when the extension extends into the weekend. Early submissions are welcome.

Homework Assignment 4

Project Proposal Due Friday, March 23, 2018
Full Assignment Due Friday, April 6, 2018

Homework Assignment 3

Due Friday, March 9, 2018

Homework Assignment 2

Due Friday, February 23, 2018

Homework Assignment 1

Due Friday, February 9, 2018

Homework Assignment 0

Due Friday, January 26, 2018

Class Participation and Online Discussion

It is important to attend class and read the readings. Lively class discussion is also important, which includes in-class participation, as well as participation in the online forums.

Students are expected to be active participants in the online forums (e.g., around at least 1 substantive post per class meeting). You may and are encouraged to post comments or questions about the reading before the class where we will cover it. Posting early will help focus our discussion.

Here are some examples of good comments:

  • Questions about the reading or the class discussion.
  • Thoughtful answers to other people’s questions.
  • Clarification of some point discussed in class.
  • What you think is the main point or key idea in the reading set.
  • An idea of how some work could be improved from the reading or class discussion.

If everything from a class meeting seems clear to you, try to come up with a question that tests your classmates’ understanding. Put yourself in the position of an instructor!

Overall, the intent is for you to to take a moment to reflect upon the day’s reading or class discussion. I will read all posts, but I may not respond to all of them (e.g., if I believe your classmates’ answers are sufficient).

Final Project

Project Guidelines

Students are expected to select and complete a substantial course project during the semester on a topic related to the class.

Projects should be done in groups of two (other group compositions must be discussed on a case-by-case basis). The expectations will naturally depend on the number of group members.

The first step is to submit a project proposal. The proposal should explain what you expect to learn from the project (i.e., why is it interesting to you?) and should include a work schedule. Make sure to budget time for writing a short project paper (~5 pages) describing the project and for preparing a short (~15-20 minutes, depends on number of projects) project presentation during the last week of classes. The main purpose of the proposal is for me to give you feedback on its feasibility.

The main goal of the project is to allow you to customize the content of the course to your own interests. The goal is not to force you all to produce novel results in one semester. Course projects like this often lead to collaborations that eventually yield exciting research. In the hopefully-likely event that you end up enjoying your project, come see me about taking it further (say, to publication).

Project Dates

  • A pre-proposal is due on February 23, 2018.
  • The project proposal is due on March 23, 2018.
  • A project status update is due on April 13, 2018.
  • Project presentations will be held during the last week of classes.
  • The project paper is due on Sunday, May 6, 2018.
  • Peer reviews on project papers are due on Monday, May 7, 2018.

Project Scale

I do not expect each project to lead to novel results, though I hope some projects could eventually lead to publication!

  • I do expect a consistent effort on the project. Once we stop having weekly homework assignments, that amount of time should be entirely directed towards your project.
  • Notably, “one long weekend” will not suffice. I can tell. Trust me.
  • You are welcome to tackle a more ambitious project. Such a project should have “stages” so that you have something to show at the end of the semester. I (or your advisor) can provide extra guidance on such projects.
  • The number of group members should depend on the size of the project. Note that the grading for a two-person project will actually require “twice as much work” than a one-person project rather than the standard “1.5-times as much work”. You should be able to split up the project paper (e.g., “I did section 1, Grace Hopper did section 2, and we shared section 3”).

Project Kinds

Projects on any subject related to the class are acceptable. The goal is to allow you to customize the project to your interests. There are two main types of projects: implementation projects, theory projects, and research projects.

In general, I recommend that you try to do a research project. They are typically a bit harder because they typically involve both theory and implementation.

Undergraduate students may undertake implementation or theory projects but are free to pursue research projects. Graduate students must aim for a research project.

Implementation Projects

Pick a fragment of a language or a relevant algorithm, and implement it! There is no firm limit on the amount of code.

An implementation project should feature “numbers”: controlled, experimental results that help to sway your audience in favor of a point you are making. You should actually have a point: “I implemented a register allocator” is not quite good enough. You will want something more like: “Graph-coloring register allocation yields fewer spills and thus smaller and faster code than greedy register allocation. On the X benchmarks for the Y architecture, replacing a greedy register allocator in the Z compiler with a graph-coloring one resulting in a A% decrease in code size and a B% decrease in average executing time.”

Your implementation must be relevant to language design or analysis. It could also be relevant to language implementation, provided that it has sufficient conceptual content and is close enough to the course. Graph-coloring register allocation wouldn’t actually cut it.

Theory Projects

Theoretical projects are similar in spirit to implementation projects, except that they deliver a system of formal definitions and proofs rather than a collection of source code. Rather than evaluate the system empirically, using “numbers”, theory projects are evaluated based on what they prove.

Research Projects

There are many kinds of research projects, including the following:

  • Design and implement a program analysis
  • Invent a language or a language feature for some particular purpose or with some particular characteristic (e.g., to make program analysis and understanding more tractable)
  • Try to formalize some interesting aspect of some existing language
  • Explore novel techniques for implementing a given language fragment

These projects are harder because they always involve some survey work and often involve some implementation. If you want to do a research project, and you are not yet sufficiently familiar with the area of the project, you should start with a brief survey and then turn it into a research project. While research is necessarily open-ended, be sure that you have a well-defined goal for the end of the semester so that you have something to write up and present.

The Proposal

Your proposal should address at least the following questions:

  1. Who are the members of your team?
  2. What basic problem will your project try to solve?
  3. Define the problem that you will solve as concretely as possible. Provide a scope of expected and potential results. Give a few example programs that exhibit the problem that you are trying to solve.
  4. What is the general approach that you intend to use to solve the problem?
  5. Why do you think that approach will solve the problem? What resources (papers, book chapters, etc.) do you plan to base your solution on? Is there one in particular that you plan to follow? What about your solution will be similar? What will be different?
  6. How do you plan to demonstrate your idea?
  7. How will you evaluate your idea? What will be the measurement for success?

Your proposal should be concise and specific. Do not be long-winded or vague. You will not be graded on the length of the proposal, but you will be graded on how many interesting things you say.

Your pre-proposal should consist of answers to at least the first two questions. The purpose of the pre-proposal is to help you get started thinking about your project and discussing with me as needed.

The Status Update

The status update is a short write-up. It should explain what you have done so far and how you plan to meet your goals in the final weeks of the project. Like your proposal, you will not be graded on the length of your status update but rather on how concrete you are on where you are.

The Presentation

The presentation should be short and should describe what the problem was, what the difficulties were, and what was accomplished or learned. You will find it much easier to prepare the talk using slides (perhaps 8 to 12 slides, depending on your speed).

While preparing the talk keep in mind who your audience is. You will be presenting to colleagues who are eager to find out (1) about new exciting facets of compilation and (2) how much fun you had. Plan to motivate the project (i.e., why is this important?) and to describe what you learned from it. Keep in mind that your colleagues have not read all the papers that you have read to do the project.

Project presentations will be held on the final week of classes. Students presenting on Tuesday will receive a small amount of extra credit to make up for presenting earlier.

The Paper

Your write up at the end of the semester should be in the form of a short research paper. The project paper should have an abstract and an introduction describing the tackled problem, its motivation, and a very brief summary of the accomplishment. Then you should write a description of your notations (especially if they are different from what we used in class). Then you continue with the body of the material. The paper should end with a conclusion putting in perspective the accomplishment of the project and mentioning the open problems and with a bibliography of cited papers. Research papers should also have a related work section in which they compare the work with previous research results.

You might want to browse the papers from PLDI 2017 or POPL 2017. Aside from giving you a number of data points for how the paper should look graphically, reading the electronic editions might help you to find a topic. Extending previously-published work is often not a bad start.

Your project paper should be ~5 pages, as necessary, while being as concise and concrete as possible. Like your proposal, you will not be graded on length but on how many interesting things you say. You will turn in a PDF as well as your implementation code. You will want to use the LaTeX class file produced by ACM/SIGPLAN. Please use the two-column format.

Peer Review

You will have the opportunity to write reviews of your peers’ project papers for extra credit. Take a look at the Paper Review Form for further details.