UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

Layer by Layer – Combining Monads

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. Green open access

[img]
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 > 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
Downloads since deposit
66Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item