Sum and tensor of quantitative effects

Tools

Bacci, Giorgio and Mardare, Radu and Panangaden, Prakash and Plotkin, Gordon D. (2024) Sum and tensor of quantitative effects. Logical Methods in Computer Science, 20 (4). 9:1-9:62. 9. ISSN 1860-5974 (https://doi.org/10.46298/lmcs-20(4:9)2024)

[thumbnail of Bacci-etal-Sum-and-Tensor-of-Quantitative-Effects]
Preview
 Text. Filename: Bacci-etal-Sum-and-Tensor-of-Quantitative-Effects.pdf
Final Published Version
License: Creative Commons Attribution 4.0 logo
Download (779kB)| Preview

Abstract

Inspired by the seminal work of Hyland, Plotkin, and Power on the combination of algebraic computational effects via sum and tensor, we develop an analogous theory for the combination of quantitative algebraic effects. Quantitative algebraic effects are monadic computational effects on categories of metric spaces, which, moreover, have an algebraic presentation in the form of quantitative equational theories, a logical framework introduced by Mardare, Panangaden, and Plotkin that generalises equational logic to account for a concept of approximate equality. As our main result, we show that the sum and tensor of two quantitative equational theories correspond to the categorical sum (i.e., coproduct) and tensor, respectively, of their effects qua monads. We further give a theory of quantitative effect transformers based on these two operations, essentially providing quantitative analogues to the following monad transformers due to Moggi: exception, resumption, reader, and writer transformers. Finally, as an application, we provide the first quantitative algebraic axiomatizations to the following coalgebraic structures: Markov processes, labelled Markov processes, Mealy machines, and Markov decision processes, each endowed with their respective bisimilarity metrics. Apart from the intrinsic interest in these axiomatizations, it is pleasing they have been obtained as the composition, via sum and tensor, of simpler quantitative equational theories.

CORE (COnnecting REpositories)