Categorical Semantics of Reversible Pattern-Matching

Kostia Chardonnet
(LMF, Université Paris Saclay. IRIF, Université de Paris.)
Louis Lemonnier
(LMF, Université Paris Saclay.)
Benoît Valiron
(LMF, CentraleSupélec, Université Paris Saclay)

This paper is concerned with categorical structures for reversible computation. In particular, we focus on a typed, functional reversible language based on Theseus. We discuss how join inverse rig categories do not in general capture pattern-matching, the core construct Theseus uses to enforce reversibility. We then derive a categorical structure to add to join inverse rig categories in order to capture pattern-matching. We show how such a structure makes an adequate model for reversible pattern-matching.

In Ana Sokolova: Proceedings 37th Conference on Mathematical Foundations of Programming Semantics (MFPS 2021), Hybrid: Salzburg, Austria and Online, 30th August - 2nd September, 2021, Electronic Proceedings in Theoretical Computer Science 351, pp. 18–33.
Published: 29th December 2021.

ArXived at: http://dx.doi.org/10.4204/EPTCS.351.2 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org