Final Project

• Proposal due: 11/18
• Project due: 12/15
• Points: 60

You can work alone or in pairs. Each undergraduate student is expected to take on roughly one “unit” of work (to be defined below); each graduate student, two “units.”

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 is that a “unit” is 100-200 lines of Python, although 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 an extension to your interpreter from PP 1-3:
  • Call-by-need evaluation (1 unit)
  • Algebraic datatypes (1 unit)
  • Type inference (2 units)
  • State (1 unit)
  • Exceptions (1 unit)
  • A more exotic effect like resumable exceptions, generators, nondeterminism, automatic differentiation, etc.
• Write a compiler from λ-calculus to C (2 units)
  • or from ELVM assembler to λ-calculus (2 units)
• Design your own programming language and write an interpreter

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 is that a “unit” 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 and any notes or slides you used (in a PDF file). A rough guideline is that a “unit” is about 15 minutes. There is time on 12/05 and 12/07 for extra topics.

Instructions

By 11/18, please submit (in Canvas) 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 12/15, please submit (in Canvas) 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