A Random Generation of Haskell Programs Applied to Optimization Testing in Compilers

Guilherme Graeff; Braulio Mello; Denio Duarte; Andrei Braga; Sampaio Braga; Samuel Feitosa

doi:10.22456/2175-2745.134925

Authors

Guilherme Graeff Universidade Federal da Fronteira Sul
Braulio Mello Universidade Federal da Fronteira Sul
Denio Duarte Universidade Federal da Fronteira Sul
Andrei Braga Universidade Federal da Fronteira Sul
Sampaio Braga Universidade Federal da Fronteira Sul
Samuel Feitosa Universidade Federal da Fronteira Sull

DOI:

https://doi.org/10.22456/2175-2745.134925

Keywords:

Programming Languages, Program Generation, Compiler Testing, Property-based Testing

Abstract

Compilers and interpreters are essential for developing any system or application, so validating their functionality and properties is crucial. These tools are susceptible to failures, like any software artifact, which can introduce errors into programs developed using them. For example, a compiler or interpreter error that alters a program’s behavior can compromise a critical system, and the system impact can be costly. The literature reports several problems found in compilers and interpreters of different languages. When bugs are detected in early releases, they can be reported to the development team, who can fix them before the end user notices the problem. This work describes the procedure used to generate random Haskell programs, which serve as input for property-based tests. More specifically, this work aims to test the compilation and behavior properties of a program, comparing the compilation and execution results of programs generated with different levels of optimization of the Glasgow Haskell Compiler (GHC). From developing a tool that automates the tests, 10,000 random programs were generated, compiled, and executed, of which 57 presented compilation errors with different optimization levels. This result demonstrates that the used approach is promising for error detection and can be improved in further studies.

Downloads

Download data is not yet available.

References

YANG, X. et al. Finding and understanding bugs in C compilers. SIGPLAN Not., Association for Computing Machinery, New York, NY, USA, v. 46, n. 6, p. 283–294, jun 2011. Disponível em: ⟨https://doi.org/10.1145/1993316.1993532⟩.

BRITTO, G. A.; TEIXEIRA, L.; GHEYI, R. TSDolly: A program generator for TypeScript. In: Proceedings of the 25th Brazilian Symposium on Programming Languages. New York, NY, USA: Association for Computing Machinery, 2021. (SBLP ’21), p. 66–74. Disponível em: ⟨https://doi.org/10.1145/3475061.3475079⟩.

CHEN, J. et al. A survey of compiler testing. ACM Comput. Surv., Association for Computing Machinery, New York, NY, USA, v. 53, n. 1, p. 1–36, feb 2020. Disponível em: ⟨https://doi.org/10.1145/3363562⟩.

PAŁKA, M. H. et al. Testing an optimising compiler by generating random lambda terms. In: Proceedings of the 6th International Workshop on Automation of Software Test. New York, NY, USA: Association for Computing Machinery, 2011. (AST ’11), p. 91–97. Disponível em: ⟨https://doi.org/10.1145/1982595.1982615⟩.

FEITOSA, S. da S. Strategies for testing and formalizing properties of modern programming languages. Tese (PhD thesis) — Universidade Federal de Pelotas, Pelotas, RS, Brazil, 2019. Disponível em: ⟨https://guaiaca.ufpel.edu.br/handle/prefix/6280⟩.

KRAUS, L. F. et al. Synthesis of random realworld java programs from preexisting libraries. New York, NY, USA, p. 108–115, 2021. Disponível em: ⟨https://doi.org/10.1145/3475061.3475087⟩.

BARENDREGT, H. The Lambda Calculus. Its syntax and semantics. Amsterdam: North Holland, 1984. Disponível em: ⟨https://www.sciencedirect.com/bookseries/studies-in-logic-and-the-foundations-of-mathematics/vol/103/suppl/C⟩.

PIERCE, B. C. Types and Programming Languages. Cambridge, MA: The MIT Press, 2002. Disponível em: ⟨https://mitpress.mit.edu/9780262303828/types-and-programming-languages/⟩.

O’SULLIVAN, B.; GOERZEN, J.; STEWART, D. B. Real World Haskell. [S.l.]: O’Reilly Media, 2008.

HUDAK, P. et al. A history of Haskell: Being lazy with class. In: Proceedings of the Third ACM SIGPLAN Conference on History of Programming Languages. New York, NY, USA: ACM, 2007. (HOPL III, 12), p. 12–1–12–55. Disponível em: ⟨https://doi.org/10.1145/1238844.1238856⟩.

GITHUB. github.com, 2019. Disponível em: ⟨https://github.com/github/semantic/blob/main/docs/why-haskell.md⟩.

GHC Optimizations. haskell.org, 2020. Disponível em: ⟨https://downloads.haskell.org/ghc/latest/docs/users guide/using-optimisation.html⟩.

CLAESSEN, K.; HUGHES, J. Quickcheck: A lightweight tool for random testing of Haskell programs. SIGPLAN Not., Association for Computing Machinery, New York, NY, USA, v. 35, n. 9, p. 268–279, sep 2000. Disponível em: ⟨https://doi.org/10.1145/357766.351266⟩.

FEITOSA, S. da S.; RIBEIRO, R. G.; BOIS, A. R. D. Generating random well-typed Featherweight Java programs using QuickCheck. Electronic Notes in Theoretical Computer Science, v. 342, p. 3–20, 2019. The proceedings of CLEI 2018, the XLIV Latin American Computing Conference. Disponível em: ⟨https://www.sciencedirect.com/science/article/pii/S1571066119300027⟩.