Interpreter and Type Checker for a Small Language
Design a small programming language and implement it end to end: lexer, parser, type checker, and either a tree walking interpreter or a bytecode virtual machine. A classic project that demonstrates depth of understanding better than almost anything else.
Advanced
Needs a team, real planning, and a supervisor who knows the area.1 semester, 2 students
5 to ship
3 optional extrasSuggested stack
What you should ship
- Language specification with formal grammar and typing rules
- Lexer and parser producing an abstract syntax tree, with useful error messages including position
- Static type checker supporting functions, algebraic data types and pattern matching, with inference
- Evaluator, either a tree walking interpreter or a bytecode virtual machine
- Test suite covering the specification, including programs that must be rejected with the right error
If you have time left
- Bytecode compilation with a measured speed comparison against tree walking
- A language server providing completion and inline errors in an editor
- Garbage collection rather than relying on the host language
Why this project still earns its place
It demonstrates understanding of the entire stack 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 or assembled it.
What you build
A grammar, a lexer and parser, a type checker with inference, and an evaluator. The type checker is where the intellectual content is; parsing is largely mechanical.
The design decision that determines difficulty
Type inference. Implementing full inference in the Hindley-Milner style is substantially harder than checking explicit annotations and substantially more impressive. Decide early, be honest about which you did, and if you attempt inference, get unification working before adding features.
The deliverable that proves it works
The test suite, specifically the negative tests. A hundred programs that should compile and run correctly, plus fifty that must be rejected with a specific error, is more convincing than any demonstration. Type checkers are usually wrong by accepting things they should not.
The part to spend unexpected time on
Error messages. A type checker that says type error is a fail. One that says the branches of this expression have different types, one is a number and the other is text, with the positions of both, is a genuine engineering contribution and is what real language implementations spend enormous effort on.
Scope warning
Small language, deep implementation. Functions, algebraic data types, pattern matching and let bindings are plenty. No modules, no concurrency, no standard library.
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.
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. Every session is free; a few slots open each week.
Follow along
New writing, resources and project ideas land here first.