License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ECOOP.2023.18
URN: urn:nbn:de:0030-drops-182112
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18211/
Madsen, Magnus ;
van de Pol, Jaco
Programming with Purity Reflection: Peaceful Coexistence of Effects, Laziness, and Parallelism
Abstract
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.
BibTeX - Entry
@InProceedings{madsen_et_al:LIPIcs.ECOOP.2023.18,
author = {Madsen, Magnus and van de Pol, Jaco},
title = {{Programming with Purity Reflection: Peaceful Coexistence of Effects, Laziness, and Parallelism}},
booktitle = {37th European Conference on Object-Oriented Programming (ECOOP 2023)},
pages = {18:1--18:27},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-281-5},
ISSN = {1868-8969},
year = {2023},
volume = {263},
editor = {Ali, Karim and Salvaneschi, Guido},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18211},
URN = {urn:nbn:de:0030-drops-182112},
doi = {10.4230/LIPIcs.ECOOP.2023.18},
annote = {Keywords: type and effect systems, purity reflection, lazy evaluation, parallel evaluation}
}
|
Keywords: |
|
type and effect systems, purity reflection, lazy evaluation, parallel evaluation |
|
Collection: |
|
37th European Conference on Object-Oriented Programming (ECOOP 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
11.07.2023 |
