We present purity reflection, a programming language feature that enables higher-order functions to inspect the purity of their function arguments and to vary their behavior based on this information. The upshot is that operations on data structures can selectively use lazy and/or parallel evaluation while ensuring that side effects are never lost or re-ordered. The technique builds on a recent Hindley-Milner style type and effect system based on Boolean unification which supports both effect polymorphism and complete type inference. We illustrate that avoiding the so-called ‘poisoning problem’ is crucial to support purity reflection.

We propose several new data structures that use purity reflection to switch between eager and lazy, sequential and parallel evaluation. We propose a DelayList which is maximally lazy but switches to eager evaluation for impure operations. We also propose a DelayMap which is maximally lazy in its keys, but also exploits eager and parallel evaluation.

We implement purity reflection as an extension of the Flix programming language. We present a new effect-aware form of monomorphization that eliminates purity reflection at compile-time. We evaluate the cost of this new monomorphization on compilation time and on code size, and determine that it is minimal.