Sefism is free for learners. We are here to help you grow, one step at a time.Join for free
Sefism.
Other

Interpreter and Type Checker for a Small Language

A compilers final year project: design a small functional teaching language and implement it end to end, with a lexer, parser, Hindley-Milner type inference, clear error messages and a tree-walking interpreter or bytecode VM. Built as a teaching tool for an introductory programming languages course, with a browser playground so students can try it without installing anything.

Topics
Difficulty

Advanced

Needs a team, real planning, and a supervisor who knows the area.
Effort

1 semester · 2 students

Deliverables

8 to ship

3 optional extras

Suggested stack

Rust, OCaml or TypeScriptHand-written recursive descent parserUnion-find for type unificationWebAssembly for the browser buildA snapshot testing libraryGitHub Actions
A suggestion, not a requirement. Swap anything for what you already know.

What you should ship

  • A language specification with a formal grammar and typing rules, written before implementation
  • A lexer and parser producing an abstract syntax tree, with error recovery and messages that include line and column
  • A static type checker with Hindley-Milner inference, let-polymorphism, algebraic data types and pattern matching
  • Exhaustiveness checking for pattern matches, with the missing cases listed in the error
  • An evaluator: a tree-walking interpreter, or a bytecode compiler and virtual machine
  • Type error messages that show both conflicting types and the positions that produced them
  • A test suite of at least 100 programs that must run correctly and 50 that must be rejected with a specific error
  • A browser playground built to WebAssembly where users type a program and see types, errors and output

If you have time left

  • Bytecode compilation with a measured speed comparison against tree walking
  • A language server providing hover types, completion and inline errors in an editor
  • A mark and sweep garbage collector instead of relying on the host language

The problem: type systems taught without a working checker

Programming languages and compilers courses teach grammars, type rules and inference on paper. Students memorise the rules for the exam without ever seeing a checker reject a program, and most never build one. Meanwhile the languages they use at work, TypeScript, Rust, Kotlin and Swift, lean heavily on type inference and good error messages, and the engineers who understand how those work are rare.

This project demonstrates understanding of the whole path from text to execution. It has an unambiguous correctness criterion and it is impossible to fake: an examiner can ask about any part and the answers reveal immediately whether you built it.

What already exists and the gap

  • Crafting Interpreters by Robert Nystrom builds Lox twice: jlox, a tree-walking interpreter in Java, and clox, a bytecode VM in C. Lox is dynamically typed.
  • CodeCrafters' Build your own Interpreter challenge follows a similar tree-walking path step by step.
  • OCaml, Elm and Gleam are real languages with Hindley-Milner style inference; Elm is well known for friendly compiler errors.

The popular learning paths skip static typing, and the real typed languages are too big to study end to end. The gap is a small, statically typed teaching language with inference and error messages designed for learners, plus a playground a lecturer could put in front of a class.

What you build

The language: integers, booleans, strings, functions, let bindings, algebraic data types, pattern matching and recursion. That is plenty.

The implementation:

  1. Specification with grammar and typing rules.
  2. Lexer and parser with positions and error recovery.
  3. Type checker with inference and exhaustiveness checks.
  4. Evaluator, tree-walking or bytecode.
  5. Playground in the browser via WebAssembly.

Users: a lecturer teaching an introductory programming languages or functional programming course, and the students in it. Examples in the playground should come from that syllabus.

The technically interesting part

Type inference with good errors. Hindley-Milner inference is substantially harder than checking explicit annotations, and substantially more impressive. Get unification working on a tiny core (functions and integers) before adding data types. Then the real work: when unification fails, you must report where each conflicting type came from, not just "type error". Track the source position of every constraint so the message can say "this branch is Int, this branch is String", pointing at both.

Show your supervisor a table of 20 deliberately wrong programs, your error message for each, and how a student in a small test understood them.

How to evaluate it

  • Positive and negative tests: at least 100 programs that must run with expected output, 50 that must be rejected with a specific error; type checkers are usually wrong by accepting things they should not.
  • Error message study: 8 students each fix 10 broken programs using your messages; record time and success, and compare with the same programs in a language they know.
  • Performance: for the evaluator, time on a few standard benchmarks (recursive Fibonacci, list sorting); with bytecode, compare against tree walking.
  • Property tests: generate random well-typed programs and check that they never crash the evaluator, which tests type soundness in practice.

Suggested plan

  1. Weeks 1 to 2: language specification and example programs.
  2. Weeks 3 to 4: lexer, parser, error recovery, AST printer.
  3. Weeks 5 to 8: type inference, data types, pattern matching, exhaustiveness.
  4. Weeks 9 to 10: evaluator.
  5. Weeks 11 to 12: error message work, playground.
  6. Weeks 13 to 14: evaluation study and report.

Path to a product

This is not a commercial product and should not be framed as one. The realistic outcomes are a teaching tool your department's languages course can use, an open source project other learners study, and a portfolio piece that leads to interviews for compiler, developer tools and language server work.

Scope warning

Small language, deep implementation. No modules, no concurrency, no standard library beyond a few built-ins, no type classes or traits. Do not use a parser generator unless your supervisor requires one. Decide early whether you do full inference or annotated checking, and be honest in the report about which you built.

Learn what you need on Sefism

Get help with this idea

Most language projects fail by growing the language instead of deepening the implementation. A mentor can help you freeze the feature list, plan the inference milestones and design the error message study. If you are new here, create a free account first.

Ideas and guidance, not finished projects

These are project ideas and scoping guidance, published free for students to use as a starting point. I do not build, write, or sell final-year projects, and I do not complete coursework for anyone. Take an idea, make it yours, and build it.

Not sure this one fits you?

I help students pick an idea that matches their skills and their deadline, then scope it down until it is finishable. Guidance only, never done for you.

Discuss this idea
Work with me

Stuck on something specific?

Writing only gets you so far. If you want an answer to your situation rather than the general case, book a session and we will work through it together. Sessions are free for approved Sefism members, and a few slots open each week.

Book a free sessionSee all services

Follow along

New writing, resources and project ideas land here first.