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.