Final Project

Proposal due: 04/05
Project due: 05/08
Points: 60

You can work alone or in pairs; pairs are expected to take on a project roughly twice the size of an individual project.

Topics

Your projects can involve programming, writing, or giving a talk, or any combination of the three. (For example, you can write a program and take a few minutes in class to demonstrate it.)

Programming

You can write an extension to your interpreter from PP 1-3, or write a completely new program that relates somehow to the course material. The deliverables will be:

Your code (in a .tgz file, or in a private Git repository). It can be in any language you want; a rough length guideline (for individual projects) is 100-200 lines of Python, but it’s difficult to measure substance by lines of code.
A description of what you did (in a PDF or plain text file). It doesn’t need to be long, but it should include a brief English description of what you implemented, plus the formal semantics of what you implemented (or a citation/link to the semantics).

Below are some suggested programming topics.

Add shift and reset to your interpreter via the CPS transform (1-person project)
Extend your interpreter to do type inference (1 or 2-person)
- A little harder: with let-polymorphism (1 or 2-person)
Write a compiler from λ-calculus to C (1 or 2-person)
- A little harder: with tail call elimination (1 or 2-person)
- Somewhat harder: with reference counting (2-person)

Writing

You can write a paper on any topic related to the course material (but not covered in the course itself). Ideally, this would be a tutorial that is accessible to other students in the class. The deliverable would be just the paper itself (in a PDF file); a rough length guideline (for individual projects) is 3 pages, single-spaced.

Past topics:

Introduction to denotational semantics
Explanation of the proof of confluence of β-reduction (Church-Rosser Theorem)

Talking

Your deliverables will be the talk itself, which should be 25 minutes (per presenter), and any notes or slides you used (in a PDF file). The natural choice for a talk topic would be to take half of a scheduled lecture topic:

04/08: State
04/10: References (TAPL 13)
04/12: Exceptions (TAPL 14)
04/15: Generators (James and Sabry, 2011)
04/17: Nondeterminism

But if there’s another topic you’d like to present, go ahead and propose it. There is time on 04/29 and 05/01 for extra topics. Some more ideas on the theme of computational effects:

Probabilistic programming (related to nondeterminism)
Differentiable programming (Wang et al., 2018)
Asynchronous programming (promises and async/await)

Instructions

By 04/05, please submit (in Sakai) a short description of what you want to do. There’s no minimum length, but it should be clear and specific enough that I can guess how much work it will take. Proposals that meet this requirement will get the full 10 points.

Once I’ve approved your proposal, it’s a promise that if you complete everything you propose, you’ll get at least a 40 out of 50 on the rest of the project.

By 05/08, please submit (in Sakai) all the deliverables for your project (in the formats described above).

Rubric

Criterion	Points
Proposal is clear and specific	10
Project does everything proposed	40
Code/writing/presentation quality	10