Programming with Purity Reflection: Peaceful Coexistence of Effects, Laziness, and Parallelism

TY - GEN

T1 - Programming with Purity Reflection

T2 - 37th European Conference on Object-Oriented Programming, ECOOP 2023

AU - Madsen, Magnus

AU - Pol, Jaco van de

PY - 2023/7

Y1 - 2023/7

N2 - 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 values, 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. And finally, we evaluate the cost of this new monomorphization on compilation time and on code size, and determine that it is minimal.

AB - 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 values, 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. And finally, we evaluate the cost of this new monomorphization on compilation time and on code size, and determine that it is minimal.

KW - type and effect systems

KW - purity reflection

KW - lazy evaluation

KW - parallel evaluation

UR - http://www.scopus.com/inward/record.url?scp=85168856359&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ECOOP.2023.18

DO - 10.4230/LIPIcs.ECOOP.2023.18

M3 - Article in proceedings

SN - 978-3-95977-281-5

T3 - Leibniz International Proceedings in Informatics

BT - 37th European Conference on Object-Oriented Programming (ECOOP 2023)

A2 - Ali, Karim

A2 - Salvaneschi, Guido

PB - Dagstuhl Publishing

Y2 - 17 July 2023 through 21 July 2023

ER -