Lune

POPL2022Top-tier venue

Symmetries in reversible programming: from symmetric rig groupoids to reversible programming languages

Vikraman Choudhury, Jacek Karwowski, Amr Sabry

Abstract

The Pi family of reversible programming languages for boolean circuits is presented as a syntax of combinators witnessing type isomorphisms of algebraic data types. In this paper, we give a denotational semantics for this language, using weak groupoids à la Homotopy Type Theory, and show how to derive an equational theory for it, presented by 2-combinators witnessing equivalences of type isomorphisms. We establish a correspondence between the syntactic groupoid of the language and a formally presented univalent subuniverse of finite types. The correspondence relates 1-combinators to 1-paths, and 2-combinators to 2-paths in the universe, which is shown to be sound and complete for both levels, forming an equivalence of groupoids. We use this to establish a Curry-Howard-Lambek correspondence between Reversible Logic, Reversible Programming Languages, and Symmetric Rig Groupoids, by showing that the syntax of Pi is presented by the free symmetric rig groupoid, given by finite sets and bijections. Using the formalisation of our results, we perform normalisation-by-evaluation, verification and synthesis of reversible logic gates, motivated by examples from quantum computing. We also show how to reason about and transfer theorems between different representations of reversible circuits.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

4 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • The Relational Machine Calculus cites A computational interpretation of compact closed categories: reversible programming with negative and fractional types
  • Compositional Quantum Control Flow with Efficient Compilation in Qunity cites Qunity: A Unified Language for Quantum and Classical Computing
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers4

  1. Qunity: A Unified Language for Quantum and Classical ComputingFinn Voichick, Liyi Li, Robert Rand, Michael HicksPOPL 2023 · 35 citations
  2. With a Few Square Roots, Quantum Computing Is as Easy as PiJacques Carette, Chris Heunen, Robin Kaarsgaard, Amr SabryPOPL 2024 · 7 citations
  3. The Relational Machine CalculusChris Barrett, Daniel Castle, Willem HeijltjesLICS 2024 · 1 citation
  4. Compositional Quantum Control Flow with Efficient Compilation in QunityMikhail Mints, Finn Voichick, Leonidas Lampropoulos, Robert RandOOPSLA 2025

Builds on5

  1. Internalizing representation independence with univalenceCarlo Angiuli, Evan Cavallo, Anders Mörtberg, Max ZeunerPOPL 2021 · 18 citations
  2. Categories of NetsJohn C. Baez, Fabrizio Genovese, Jade Master, Michael ShulmanLICS 2021 · 14 citations
  3. A computational interpretation of compact closed categories: reversible programming with negative and fractional typesChao-Hong Chen, Amr SabryPOPL 2021 · 9 citations
  4. Decidable Synthesis of Programs with Uninterpreted FunctionsPaul Krogmeier, Umang Mathur, Adithya Murali, P. Madhusudan et al.CAV 2020 · 8 citations
  5. Coherence via Well-Foundedness: Taming Set-Quotients in Homotopy Type TheoryNicolai Kraus, Jakob von RaumerLICS 2020 · 8 citations

Related papers

  1. One Rig to Control Them AllChris Heunen, Robin Kaarsgaard, Louis LemonnierLICS 2026 · 2 citations
  2. Complete ω-Regular Supermartingale CertificatesAlessandro Abate, Mirco Giacobbe, Sergey Ichtchenko, Diptarko RoyLICS 2026
  3. Hadamard-Pi: Equational Quantum ProgrammingWang Fang, Chris Heunen, Robin KaarsgaardPOPL 2026
  4. Constructing Higher Inductive Types as Groupoid QuotientsNiels van der WeideLICS 2020 · 1 citation
  5. A Constructive Model of Directed Univalence in Bicubical SetsMatthew Z. Weaver, Daniel R. LicataLICS 2020 · 15 citations
Dusk over the sea between two cliffs drawn in fine vertical lines