Objectives

[top]

The primary objective of the unit project is to have the students explore a programming language concept or problem in greater depth than is possible with the standard lecture and machine problems.

Overview

[top]

Those of you who are signed up for 1 unit of credit for CS 421 will need to complete a unit project. The deadlines are listed to the right of this page. You may work alone or in groups of two to three people. You should expect about two MP's worth of work for each person involved in the project. You may do any of the following:

• Pick a project topic from the list below

• Find a research paper published in ACM or IEEE that details a programming language concept, and implement it.

• Pick two published research papers on programming language topics (some may be found here), write a two to four page summary of each, and prepare a twenty minute presentation of each.

• Develop a project idea of your own, based on previous experience or research interests.

Project Proposal

[top]

Write a proposal at least half page long that details the scope of your project and an implementation schedule. If you are basing your project on a paper, cite the paper and provide a URL to a PDF or postscript version. Be sure to include a description of the target language you want to work on, the concept you want to implement, and an outline of how you would like to to demonstrate your project at the end of the semester. Also, give a clear outline of each individual's responsibility in the project.

Your proposals are due by Tuesday 15 November 2011. You should submit your proposal electronically, in plain text form contained in the body of an e-mail message (no attachments please). It should be not more than 2 pages long. Feel free to ask for an appointment to discuss the project proposal with me before the proposals are due. Alternately, you may present me personally with a paper version.

Final submission By default, propject demonstrations and paper presentations will be on Tuesday 13 Decemeber 2011. To avoid an incomplete in this course, you should present you final submission by Friday 16 December 2011.

Project Ideas

[top]

Here are some potential project ideas. Most of these suggestions are intended to interface with the development of MicroML done in the course MPs.

Prolog implementation in OCAML

Implement a simple version of Prolog in OCaml. This work can build upon the unification algorithim in MP5. The full project would include a grammar, lexer, parser, semantics, evaluator (including back-tracking). If only one student wants to work on this, pieces could be cut out.

Add polymorphism to MicroML

Add full let polymorphism via a complete implementation of algorithm W (or equivalent) to the type system of MicroML.

Checking Tail Recursion

Write programs to determine whether a given MicroML program is tail recursive

Algebraic Data Types for MicroML

Expand MicroML to include mutually recursive algebraic type declarations, and type inference to go with.

Record Types for MicroML

Expand MicroML to include record types. This could be done as in OCaml and would require support for type declarations, or it could be done as in SML where record types do not require abbreviations.

Match Statements for MicroML

Expand MicroML with patterns and a generic match statement - syntax, typing, semantics. You should be able to match patterns that use arbitray nesting of lists, pairs and constants such as integers and strings

Project Reports

[top]

The due dates for this project are listed on the side of this page.

Before you begin your project, you should submit a proposal and have it approved. The proposal should be submitted by email, or in writing to me personally.

At the end of the project, you need to turn in two things:

a tar file containing your source code, tests, and Makefile; and

a project report, as a PDF file, containing the information below. Later, we will arrange a demo session where each group will give a brief presentation and demo of their code.

Your final report should have 4 sections:

Overview

Describe the motivation, goals, and broad accomplishments of your project in general terms.

Implementation

A brief description of the important aspects of your implementation, in terms of (a) the major tasks or capabilities of your code; (b) components of the code; (d) status of the project -- what works well, what works partially, and and what is not implemented at all. You MUST compare these with your original proposed goals in the project proposal.

Tests

Coming up with appropriate tests is one of the most important part of good software development. Your tests should include unit tests, feature tests, and larger test codes. Give a short description of the tests used, performance results if appropriate (e.g., memory consumption for garbage collection) etc. Be sure to explain how these tests exercise the concept(s) you've implemented.

Listing

A listing of your code. The code should be documented thoroughly and clearly. You don't need to comment every single line or even every single function. Instead, focus on the central functions and data structures in your implementation, and document them well.

Project Demo

[top]

By default, we will have demos and paper presentations on Tuesday, Dec. 13 (contact me if you have an exam scheduled at that time). During this time, your group will make a brief presentation of your work and then give a demo of your project.