COPLAS Talk: Purity Polymorphism: Peaceful Cohabitation of Side-Effects, Laziness, and Parallelism

Speaker

Magnus Madsen is an assistant professor at Aarhus University and the lead developer of the Flix programming language.

Title

Purity Polymorphism: Peaceful Cohabitation of Side-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 behaviour 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.

Our 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. Specifically, we illustrate that this type and effect offers a much more fine-grained typing compared to more traditional effect systems based on row polymorphism. It is this insight that enables our new programming construct.

We implement purity reflection as an extension of the Flix programming language and use it to retrofit two existing data structures and to implement two new data structures, including a map that uses both selective lazy and parallel evaluation. We show how to use an effect-aware form of monomorphization to implement purity reflection as a construct that can be eliminated entirely at compile-time. We evaluate the cost of this new monomorphization on compilation time and on code size and determine that it is negligible.

Host: Troels Henriksen

All are welcome. No registration is required.  Feel free to forward this invitation. 

The Copenhagen Programming Languages Seminar (COPLAS) is a collaboration between DTU, ITU, Roskilde University and UCPH. To be informed about COPLAS activities and related talks, visit https://list.ku.dk/postorius/lists/sci-diku-prog-lang.list.ku.dk.