cs-4400-sp26

Miniproject: Implementing a Custom Language

Due dates: (All deadlines 11:59pm unless specified otherwise)

• 4/7 Tuesday: Post your proposed project to piazza
• 4/10 Friday: First repo commit snapshot
• 4/14 Tuesday: Second repo commit snapshot
• 4/17 Friday: Third repo commit snapshot
• 4/22 Wednesday: Final commits due
• 4/24 Friday 3:30-5:30: Present your work

This project will serve as a capstone for everything you’ve learned in the class. You will:

• Design a language: choose a set of features, a syntax, typing rules, and operational semantics, according to a set of criteria that you define.
  • You must combine a set of features that we have not previously combined in this class or the other section, and justify why you think the combination is appropriate.
  • We are not expecting a full-featured, general-purpose language: ideally, you should start with a language you implemented or extended on one of the homework assignments (or discussed as a class in lecture), and propose a small extension, such as adopting a feature from a different homework assignment or lecture.
• Implement your language.
• Document your language.
• Give a presentation about your language to the class.

More detailed instructions given below.

Deliverables

What to submit:

• You will make a repository under the course organization for your code and push commits at least four times during development, by the appointed deadlines (see the top of this page). The repository will be the final deliverable for the project, including the source code, documentation, and presentation slides.
• There will be a Gradescope assignment with one question, “did you complete the project?” that you should submit the answer “yes” to. Your grade for the project will be marked on this assignment.

Implementation

Your implementation should be done either in Plait or Lean, the two supported languages in this class. If you have a burning desire to use a different language for your implementation, we may allow this in some special cases (if you have a specific reason); please consult with course staff.

We expect your code to consist of a way to:

• Write programs, either in concrete or abstract syntax.
  • Include a directory of examples.
• Run programs:
  • An interpreter: Can be stack-based, continuation-based, or direct recursive style.
  • Optionally, a compiler: use an existing interpreter from class and compile your language to that language.
• Type-check, scope-check, or otherwise statically analyze programs, as appropriate for your language.
• Test your code: provide unit- and end-to-end tests that cover all features of the language.

If you are at a loss for a set of features that would be interesting to investigate, here are some ideas:

• STLC with declarations, recursive types, and labelled, n-ary sums and products.
  • Example: allows writing the nat-list type as mu t. (nil : Unit) + (cons : nat * t)
• Extend STLC with parametric polymorphism (e.g. System F). Implement a bidirectional typing algorithm. Explore Church encodings.
• An imperative language with let (immutable references) in addition to ref (mutable references), higher-order functions (lambdas), arrays, and syntactic sugar for while and for loops. Show how to implement recursion with higher-order store (Landin’s knot).
  • Bonus: implement break and continue with stacks or continuations.
• A language with typed exceptions, first-class continuations, and asynchronous control flow (such as async/await) or generators (a la JS or Python’s yield).
• STLC with named effect handlers, implemented as a continuation-passing interpreter. Implement effects such as printing or mutable store via effect handlers.
• A nondeterministic language for grammar expansion, such as Tracery.

Documentation

Documentation will be provided in the following forms:

• A README.md file in your repository giving an overview and example program
• Comments throughout your codebase

• A formal specification of the language

• Give your language a name. Make it yours!
  • For extra credit, give it a logo.
• Explain the design goals of your language and, at a high level, what design decisions you made to meet these goals.
  • explain tradeoffs, e.g. simplicity over efficiency, or expressiveness over minimalism
  • explain any formal properties you expect to hold
• Give a formal specification of the language’s type system and semantics.
  • restate formal properties in terms of this language’s semantics
• Comment your code thoroughly:
  • Give a high-level overview of how the code is organized.
  • For each datatype defined with define-type, describe what it maps to in your formal description, and give examples below alongside their concrete syntax (where appropriate)
  • For each function, provide a natural language comment describing its intended semantics and purpose.
• Give several example programs, including those that do and do not type-check, and describe how they evaluate.

Presentation

• Plan to speak for 5 minutes and answer questions for 5 minutes
• To be delivered during the final exam slot for this course (4/24 Friday 3:30-5:30)
• Add your slides to your repository

Expected content:

• Overview - design goals, features, small examples
• Demonstration of example programs and how they run, programs that will be rejected by the type checker, etc.
• Code walk: briefly show us your code repo and overview how the code is organized, how much is dedicated to which features, etc.
• Describe what decisions you made, bugs you fixed, etc.
• General lessons learned.

Grading Rubric

• Did you submit on-time interim commits (8%)
  • 2% for each commit
• Implementation (32%)
  • Code should run efficiently on all examples
  • Instructor/TA should be able to write their own example programs and run them
  • Code should be legible; instructors should be able to follow the structure and understand the implementation choices you made
  • Code should match what is in the formal spec
  • The scope of the implementation delivers on your proposed topic and demonstrates the learning objectives of the course.
• Documentation (45%)
  • Inference rule definitions should make sense and align with what is in the code.
  • Prose should clearly explain the scope of your project, design decisions, and functionality of your codebase.
• Presentation (15%)
  • All expected components in slides
  • Slides easy to read, speech easy to understand
  • Staying within time limit
  • Answering questions well

GenAI policy and considerations

The purpose of this project is for you to make your own design and implementation choices based on what you have learned in this class, demonstrating an understanding of the implications of various decisions for language design. We will be asking you to explain your decisions during the presentation, and you should be prepared to defend them. We will not police your use of GenAI tools to help you with the ideation process, but please consider alternatives (such as discussion your design with the instructor or TA) before you do this, and make sure you can justify all design and implementation choices as your own.

All writing and code in your deliverables should be authored by you, reflecting your thought process. Using GenAI to produce written text or code that you submit for grading will be considered an academic integrity violation, equivalent to hiring another person to write it for you.