Generating Well-Typed Terms That Are Not "Useless"
Justin Frank, Benjamin Quiring, Leonidas Lampropoulos
Abstract
Random generation of well-typed terms lies at the core of effective random testing of compilers for functional languages. Existing techniques have had success following a top-down type-oriented approach to generation that makes choices locally, which suffers from an inherent limitation: the type of an expression is often generated independently from the expression itself. Such generation frequently yields functions with argument types that cannot be used to produce a result in a meaningful way, leaving those arguments unused. Such "use-less" functions can hinder both performance, as the argument generation code is dead but still needs to be compiled, and effectiveness, as a lot of interesting optimizations are tested less frequently.
In this paper, we introduce a novel algorithm that is significantly more effective at generating functions that use their arguments. We formalize both the "local" and the "nonlocal" algorithms as step-relations in an extension of the simply-typed lambda calculus with type and arguments holes, showing how delaying the generation of types for subexpressions by allowing nonlocal generation steps leads to "useful" functions. We implement our algorithm demonstrating that it's much closer to real programs in terms of argument usage rate, and we replicate a case study from the literature that finds bugs in the strictness analyzer of GHC, with our approach finding bugs four times faster than the current state-of-the-art local approach.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
4 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
Cited by top-tier papers4
- Webs and Flow-Directed Well-Typedness Preserving Program TransformationsBenjamin Quiring, David Van Horn, John H. Reppy, Olin ShiversPLDI 2025 · 2 citations
- Divergence-Aware Testing of Graphics Shader Compiler Back-EndsDongwei Xiao, Shuai Wang, Zhibo Liu, Yiteng Peng et al.PLDI 2025 · 1 citation
- Trace-Guided Synthesis of Effectful Test GeneratorsZhe Zhou, Ankush Desai, Benjamin Delaware, Suresh JagannathanPLDI 2026 · 1 citation
- Testing Theorems, Fully AutomaticallySegev Elazar Mittelman, Harrison Goldstein, Leonidas LampropoulosOOPSLA 2026
Related papers
- Random testing for C and C++ compilers with YARPGenVsevolod Livinskii, Dmitry Babokin, John RegehrOOPSLA 2020 · 140 citations
- Fail Faster: Staging and Fast Randomness for High-Performance PBTCynthia Richey, Joseph W. Cutler, Harrison Goldstein, Benjamin C. PierceOOPSLA 2026 · 1 citation
- Boosting Compiler Testing by Injecting Real-World CodeShaohua Li, Theodoros Theodoridis, Zhendong SuPLDI 2024 · 24 citations
- Fuzzing Loop Optimizations in Compilers for C++ and Data-Parallel LanguagesVsevolod Livinskii, Dmitry Babokin, John RegehrPLDI 2023 · 42 citations
- Total Type Error Localization and Recovery with HolesEric Zhao, Raef Maroof, Anand Dukkipati, Andrew Blinn et al.POPL 2024 · 15 citations
