CS 421: Programming Languages and Compilers
Unit Project

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 4 units 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 Friday Nov 10, 2017. 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, project demonstrations and paper presentations will be on Wednesday Dec 20. To avoid an incomplete in this course, you should present your final submission by Thursday Dec 21.

Project Ideas

[top]

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

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.
Assist with Web Assignment infrastructure
If you are interested in this, you should begin by installing PrairieLearn
Assist with writing / improving existing autograding infrastructure.
Help write infrastructure for testing datatype design
Help write the code for incremental testing of one of the WAs. This could include (but is not necessarily limited to the WAs on natural semantics and transitions semantics, and on Hoare Logic.
Record Types for PicoML
Expand PicoML 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 PicoML
Expand PicoML 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
Algebraic Data Types for PicoML
Expand PicoML to include mutually recursive algebraic type declarations, and type inference to go with. If this is not combined with the pattern matching abone, you need to develop a method of accessing the components of your objects of the newly created data types. A method that was used before the rise of pattern matching was to automatically generate testers, functions that return a boolean saying whether a given object is build from a specific construtor, and destructors, functions that map an object built from a specifc constructor to the immediate subcomponent(s), or raise an exception if the object is not built from the specific constructor. hd, tl, fst, and snd are examples of destructors for lists and pairs already included in PicoML.

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. In addition to the work turned in, 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 Wednesday, Dec 14, 12:00pm - 4:00pm (contact me if you have an exam scheduled at that time). Contact me for a specific time slot for your presentation. During this time, your group will make a brief presentation of your work and then give a demo of your project.

  • Milestone Dates
    Proposal Friday, Nov 11, 2017
    Demos and Paper Presentations Wednesday, Dec 14, 2017
    Final Report Thursday, Dec 16, 2017

    Contents
    Objectives
    Overview
    Project Proposal
    Project Ideas
    Project Reports
    Project Demo