Document Open Access Logo

Localisable Monads

Authors Carmen Constantin , Nuiok Dicaire, Chris Heunen

PDF
Thumbnail PDF

File

LIPIcs.CSL.2022.15.pdf
  • Filesize: 0.76 MB
  • 17 pages

Document Identifiers

Author Details

Carmen Constantin
  • University of Edinburgh, UK
Nuiok Dicaire
  • University of Edinburgh, UK
Chris Heunen
  • University of Edinburgh, UK

Funding

  • Constantin, Carmen: Supported by EPSRC Fellowship EP/R044759/1.
  • Dicaire, Nuiok: Supported by a PGSD Scholarship from the Natural Sciences and Engineering Research Council of Canada (NSERC) and an Enlightenment Scholarship.
  • Heunen, Chris: Supported by EPSRC Fellowship EP/R044759/1.

Acknowledgements

We thank Rui Soares Barbosa, Robert Furber, and Nesta van der Schaaf for useful discussions. We also thank the reviewers for their helpful feedback.

Cite AsGet BibTex

Carmen Constantin, Nuiok Dicaire, and Chris Heunen. Localisable Monads. In 30th EACSL Annual Conference on Computer Science Logic (CSL 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 216, pp. 15:1-15:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.CSL.2022.15

Abstract

Monads govern computational side-effects in programming semantics. A collection of monads can be combined together in a local-to-global way to handle several instances of such effects. Indexed monads and graded monads do this in a modular way. Here, instead, we start with a single monad and equip it with a fine-grained structure by using techniques from tensor topology. This provides an intrinsic theory of local computational effects without needing to know how constituent effects interact beforehand. Specifically, any monoidal category decomposes as a sheaf of local categories over a base space. We identify a notion of localisable monads which characterises when a monad decomposes as a sheaf of monads. Equivalently, localisable monads are formal monads in an appropriate presheaf 2-category, whose algebras we characterise. Three extended examples demonstrate how localisable monads can interpret the base space as locations in a computer memory, as sites in a network of interacting agents acting concurrently, and as time in stochastic processes.

Subject Classification

ACM Subject Classification
  • Theory of computation → Categorical semantics
Keywords
  • Monad
  • Monoidal category
  • Presheaf
  • Central idempotent
  • Graded monad
  • Indexed monad
  • Formal monad
  • Strong monad
  • Commutative monad

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. S. Abramsky. Abstract scalars, loops, and free traced and strongly compact closed categories. In Conference on Algebra and Coalgebra, volume 3629 of Lecture Notes in Computer Science, pages 1-31. Springer, 2005. URL: https://doi.org/10.1007/11548133_1.
  2. R. Soares Barbosa and C. Heunen. Sheaf representation of monoidal categories. arxiv:2106.08896, 2021. Google Scholar
  3. J. Beck. Distributive laws. In Seminar on Triples and Categorical Homology Theory, pages 119-140. Springer, 1969. URL: https://doi.org/10.1007/BFb0083084.
  4. M. A. Bednarczyk, A. M. Borzyszkowski, and W. Pawlowski. Generalized congruences - epimorphisms in Cat. Theory and Applications of Categories, 5(11):266-280, 1999. Google Scholar
  5. C. Constantin, N. Dicaire, and C. Heunen. Localisable monads. arXiv preprint, 2021. URL: http://arxiv.org/abs/2108.01756.
  6. P.-L. Curien and S. Mimram. Coherent presentations of monoidal categories. Logical Methods in Computer Science, 13(3):1-38, 2017. URL: https://doi.org/10.23638/LMCS-13(3:31)2017.
  7. B. Day. On closed category of functors II. In Sydney Category Theory Seminar, number 420 in Lecture Notes in Mathematics, pages 20-54, 1974. Google Scholar
  8. V. Diekert and Y. Métivier. Handbook of formal languages, chapter Partial commutation and traces, pages 457-533. Springer, 1997. URL: https://doi.org/10.1007/978-3-642-59126-6_8.
  9. P. Enrique Moliner, C. Heunen, and S. Tull. Space in monoidal categories. In Electronic Proceedings in Theoretical Computer Science, volume 266, pages 399-410, 2017. URL: https://doi.org/10.4204/EPTCS.266.25.
  10. P. Enrique Moliner, C. Heunen, and S. Tull. Tensor topology. Journal of Pure and Applied Algebra, 224(10):106378, 2020. URL: https://doi.org/10.1016/j.jpaa.2020.106378.
  11. T. Fritz. A synthetic approach to Markov kernels, conditional independence and theorems on sufficient statistics. Advances in Mathematics, 370:107239, 2020. URL: https://doi.org/10.1016/j.aim.2020.107239.
  12. S. Fujii, S. Katsumata, and P.-A. Melliès. Towards a formal theory of graded monads. In Foundations of Software Science and Computation Structures, pages 513-530. Springer, 2015. URL: https://doi.org/10.1007/978-3-662-49630-5_30.
  13. M. Giry. A categorical approach to probability theory. In Categorical Aspects of Topology and Analysis, volume 915 of Lecture Notes in Mathematics, pages 68-85. Springer, 1981. URL: https://doi.org/10.1007/BFb0092872.
  14. C. Heunen and J. P. Lemay. Tensor-restriction categories. Theory and Applications of Categories, 2021. Google Scholar
  15. C. Heunen and M. L. Reyes. Frobenius structures over Hilbert C*-modules. Communications in Mathematical Physics, 361(2):787-824, 2018. URL: https://doi.org/10.1007/s00220-018-3166-0.
  16. C. Heunen and J. Vicary. Categories for quantum theory: an introduction. Oxford University Press, 2019. URL: https://doi.org/10.1093/oso/9780198739623.001.0001.
  17. M. Hyland, G. Plotkin, and J. Power. Combining effects: sum and tensor. Theoretical Computer Science, 357(1-3):70-99, 2006. URL: https://doi.org/10.1016/j.tcs.2006.03.013.
  18. B. Jacobs. Semantics of weakening and contraction. Annals of Pure and Applied Logic, 69:73-106, 1994. URL: https://doi.org/10.1016/0168-0072(94)90020-5.
  19. C. B. Jay. Languages for monoidal categories. Journal of Pure and Applied Algebra, 59:61-85, 1989. URL: https://doi.org/10.1016/0022-4049(89)90163-1.
  20. A. Kock. Bilinearity and cartesian closed monads. Mathematica Scandinavica, 29:161-174, 1971. URL: https://doi.org/10.7146/math.scand.a-11042.
  21. A. Kock. Strong functors and monoidal monads. Archiv der Mathematik, 23:113-120, 1972. URL: https://doi.org/10.1007/BF01304852.
  22. S. Lack. Composing PROPs. Theory and Applications of Categories, 13(13):147-163, 2004. Google Scholar
  23. S. Lack and R. Street. The formal theory of monads II. Journal of Pure and Applied Algebra, 175(1-3):243-265, 2002. URL: https://doi.org/10.1016/S0022-4049(02)00137-8.
  24. F. W. Lawvere. The category of probabilistic mappings. 1962. URL: https://ncatlab.org/nlab/files/lawvereprobability1962.pdf.
  25. T. Leinster. Higher operads, higher categories. Cambridge University Press, 2004. URL: https://doi.org/10.1017/CBO9780511525896.
  26. S. Milius, D. Pattinson, and L. Schröder. Generic trace semantics and graded monads. In Conference on Algebra and Coalgebra in Computer Science, volume 35 of Leibniz International Proceedings in Informatics, pages 253-269, 2015. URL: https://doi.org/10.4230/LIPIcs.CALCO.2015.253.
  27. R. Milner. Communicating and mobile systems: the pi calculus. Cambridge University Press, 1999. Google Scholar
  28. E. Moggi. Computational lambda-calculus and monads. Logic in Computer Science, 1989. URL: https://doi.org/10.1109/LICS.1989.39155.
  29. G. Plotkin and J. Power. Notions of computation determine monads. FoSSaCS, pages 342-356, 2002. URL: https://doi.org/10.1007/3-540-45931-6_24.
  30. G. Plotkin and M. Pretnar. Handlers of algebraic effects. In European Symposium on Programming, volume 5502 of Lecture Notes in Computer Science, pages 80-94, 2009. URL: https://doi.org/10.1007/978-3-642-00590-9_7.
  31. G. D. Plotkin and A. J. Power. Computational effects and operations: an overview. In Domains VI, volume 73 of Electronic Notes in Theoretical Computer Science, pages 149-16, 2004. URL: https://doi.org/10.1016/j.entcs.2004.08.008.
  32. J. Power. Semantics for local computational effects. In Mathematical Foundations of Programming Semantics, volume 158 of Electronic Notes in Theoretical Computer Science, pages 355-371, 2006. URL: https://doi.org/10.1016/j.entcs.2006.04.018.
  33. J. Power. Models, Logics and Higher-Dimensional Categories: A Tribute to the Work of Mihály Makkai, chapter Indexed Lawvere theories for local state, pages 213-229. American Mathematical Society, 2011. Google Scholar
  34. S. Staton. Instances of computational effects: an algebraic perspective. In Logic in Computer Science, pages 519-528, 2013. URL: https://doi.org/10.1109/LICS.2013.58.
  35. R. Street. The formal theory of monads. Journal of Pure and Applied Algebra, 2(2):149-168, 1972. URL: https://doi.org/10.1016/0022-4049(72)90019-9.
  36. A. Westerbaan. Quatum programs as Kleisli maps. In Quantum Physics and Logic, volume 237 of Electronic Proceedings in Theoretical Computer Science, pages 215-228, 2016. URL: https://doi.org/10.4204/EPTCS.236.14.
  37. G. Winskel and M. Nielsen. Handbook of Logic in Computer Science, volume 4, chapter Models for concurrency, pages 1-148. Oxford University Press, 1995. Google Scholar
  38. M. Zwart. On the Non-Compositionality of Monads via Distributive Laws. PhD thesis, University of Oxford, 2020. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact