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.


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.)


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)


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)


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)


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).


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