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

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

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.
Original languageEnglish
Title of host publication37th European Conference on Object-Oriented Programming (ECOOP 2023)
EditorsKarim Ali, Guido Salvaneschi
Number of pages27
PublisherDagstuhl Publishing
Publication dateJul 2023
Article number18
ISBN (Print)978-3-95977-281-5
DOIs
Publication statusPublished - Jul 2023
Event37th European Conference on Object-Oriented Programming, ECOOP 2023 - Seattle, United States
Duration: 17 Jul 202321 Jul 2023

Conference

Conference37th European Conference on Object-Oriented Programming, ECOOP 2023
Country/TerritoryUnited States
CitySeattle
Period17/07/202321/07/2023
SeriesLeibniz International Proceedings in Informatics
Volume263
ISSN1868-8969

Keywords

  • type and effect systems
  • purity reflection
  • lazy evaluation
  • parallel evaluation

Fingerprint

Dive into the research topics of 'Programming with Purity Reflection: Peaceful Coexistence of Effects, Laziness, and Parallelism'. Together they form a unique fingerprint.

Cite this