Validating Type Checkers Using Property-Based Testing

Bachelor thesis (2021)

Authors

S. Juhošová Electrical Engineering, Mathematics and Computer Science

Contributors

C.B. Poulsen Programming Languages - EEMCS (supervisor 1)
C.R. van der Rest Programming Languages - EEMCS (supervisor 2)
K.G. Langendoen Embedded Systems - EEMCS (coach)
Faculty
Electrical Engineering, Mathematics and Computer Science
Copyright: © 2021 Sára Juhošová
More Info
expand_more

Published Date

02-07-2021

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Abstract

Manually testing definitional interpreters and their type checkers is a tedious and error-prone process which can largely benefit from automation. This study evaluates the effectiveness of property-based testing on errors in type checkers. Metrics used include the ability to catch different types of errors as well as the ability to provide a good margin of confidence in the results. We define two languages in Haskell and identify properties which should hold for their type checkers. Using a bottom-up approach to expression generation, we evaluate the effectiveness of property-based testing on test suites of type checkers with various types of errors. The method proves to be effective for both the simple and the complex language and manages to catch all defined error types with at least one property to a sufficient degree of confidence. We conclude that property-based testing is an effective tool to help with manual grading of type checkers for definitional interpreters.