Dahlqvist, F;
Parlant, L;
Silva, A;
(2018)
Layer by Layer – Combining Monads.
In: Fischer, B and Uustalu, T, (eds.)
Theoretical Aspects of Computing – ICTAC 2018. ICTAC 2018. Lecture Notes in Computer Science.
(pp. pp. 153-172).
Springer: Cham.
Preview |
Text
Layer_by_layer_combining_monads.pdf - Accepted Version Download (397kB) | Preview |
Abstract
We develop a modular method to build algebraic structures. Our approach is categorical: we describe the layers of our construct as monads, and combine them using distributive laws. Finding such laws is known to be difficult and our method identifies precise sufficient conditions for two monads to distribute. We either (i) concretely build a distributive law which then provides a monad structure to the composition of layers, or (ii) pinpoint the algebraic obstacles to the existence of a distributive law and suggest a weakening of one layer that ensures distributivity. This method can be applied to a step-by-step construction of a programming language. Our running example will involve three layers: a basic imperative language enriched first by adding non-determinism and then probabilistic choice. The first extension works seamlessly, but the second encounters an obstacle, resulting in an ‘approximate’ language very similar to the probabilistic network specification language ProbNetKAT.
| Type: | Proceedings paper |
|---|---|
| Title: | Layer by Layer – Combining Monads |
| Event: | Theoretical Aspects of Computing – ICTAC 2018. ICTAC 2018. |
| ISBN-13: | 9783030025076 |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1007/978-3-030-02508-3_9 |
| Language: | English |
| Additional information: | This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions. |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10061790 |
Archive Staff Only
 |
View Item |
