Initial Property-Based Tests (PBTs) for GHC
Motivation
Given the discussion in #24336 (closed), I have examined the head.hackage
repository. There appears to be only PBTs for tests/ghc-tests/tests/MaessenHashtab/HashTest.hs
a HashTable implementation. I have here some example properties (in pseudocode) of things we could test using PBTs. If there is interest from the GHC community, I would be excited to take this opportunity to attempt to write the Generators
required to test such properties. Please, also suggest other properties you think could be tested. I will split each of the [bunches of related] tests in which there is interest into their own issue and work on them from there. Also appreciated would be any guidance or hints on how I could achieve these goals, or where I might find insurmountable blockers.
Properties to Test
For arbitrary (reified) Haskell values f :: a -> b
, x :: a
, and arbitrary GHC ASTs represented by ast :: AST
:
Correctness
-
The optimizer should not change the value returned by a function.
optimize f x === f x
-
The parser and pretty printer agree (modulo, say, whitespace).
(parse . pprint) ast ===~ ast
-
The core lint tests don't fail (for some given classes of core passes).
(core_passes_linting . process_core . to_core) ast === True
Performance
-
The running time of an optimized function should not exceed the unoptimized version's.
run_time (optimize f) x <== run_time f x
This is flakey! Would want to be true with at least probability p > 0.5
of the time though, on average. Measurements of p
give statistics on compiler performance over time, which might be interesting. Seems like a key property to check, but also one of the harder ones to do...
Consistency
-
The composition parse . pprint
is idempotent.
(parse . pprint . parse . pprint) ast === (parse . pprint) ast
Pie in the Sky
-
Some specific hash of the ast is invariant under two runs of the compiler
<no code>
This would be pretty cool, and would enable us to do many of the things that Dhall and Unison do with their hashed ASTs. Probably pretty difficult.