Computing Degree Show 2015

Implementing a Lambda Calculus Compiler


Thomas Butterwith

The aim of this project was to create a compiler capable of implementing arithmetic as well as Lambda (λ) calculus. The compiler allows a user to input a text file containing any λ expression and outputs a simplified version. Written in Ocaml, a functional programming language, the compiler takes advantage of a number of functional programming techniques.

What is lambda calculus?

λ calculus is a way of expressing functions as formulas. It consists of  a single conversion rule, variable substitution, allowing it to be easily learnt and understood but still powerful enough to create complex sequences of functions.

The final project is a compiler accessed through the command line to simplify λ calculus expressions. Taking in a text file containing any number of λ calculus expressions, separated by a semicolon, the compiler utilises alpha-equivalence and beta simplification to output the λ expression in the simplest form possible. Any errors in syntax or unrecognised tokens within the λ expression file will be displayed to the user via an error message.