Testing an Optimising Compiler by Generating Random Lambda Terms

This paper considers random testing of a compiler, usingrandomly generated programs as inputs, and comparing theirbehaviour with and without optimisation. Since the generated programs must compile, then we need to take intoaccount syntax, scope rules, and type checking during ourrandom generation. Doing so, while attaining a good distribution of test data, proves surprisingly subtle; the maincontribution of this paper is a workable solution to this problem. We used it to generate typed functions on lists, whichwe compiled using the Glasgow Haskell compiler, a matureproduction quality Haskell compiler. After around 20,000tests we triggered an optimiser failure, and automaticallysimplified it to a program with just a few constructs