Overview / Paper & Project Abstract

This paper presents an evaluation of different generation methods of input expressions to definitional interpreters. We compare three different ways of generating expressions of a specified algebraic data type. The approaches that we describe are QuickCheck, SmallCheck and a uniform generation technique, as laid out in their original papers. Subsequently, we illustrate some of the advantages and pitfalls that ought to be considered when using each of the aforementioned approaches. Experimental evaluation shows that the uniform generation method can provide promising results at the expense of time. Compared with this, the QuickCheck and SmallCheck off-the-shelf generation methods are time-efficient, yet lack precision when it comes to generating well-typed terms.

Outcome

The code corresponding to this research paper is open-sourced and available on GitHub, as linked above. It includes implementations of the different input expression generation methods, along with the experimental setup used for evaluation. The repository serves as a resource for researchers and practitioners interested in exploring input expression generation techniques for definitional interpreters.

This paper represented my Bachelor's thesis in Computer Science & Engineering at TU Delft, and was awarded a grade of 8 (out of 10). I started this project after discovering and playing around with Haskell and property-based testing, and wanted to explore these topics further in an academic context.

To this day, Haskell, while considered slightly esoteric by some, remains a programming language that I genuinely like. This is probably a reason why I always try to include functional programming concepts in work, e.g. type safety, immutability, and pure functions.