🔢 mathematics

Non-Cartesian Guarded Recursion with Daggers

This paper extends the framework of guarded recursion to reversible programming by constructing a suitable categorical model within dagger rig categories, thereby enabling the formalization of higher-order reversible languages with features like symmetric pattern matching.

Original authors: Louis Lemonnier

Published 2026-07-01

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Louis Lemonnier

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to build a machine that never loses information. In the world of classical computers, if you delete a file, that information is gone forever. But in reversible programming, every step must be undoable. If you turn a knob to the right, you must be able to turn it back to the left to get exactly where you started. This is crucial for things like quantum computing, where losing information breaks the laws of physics.

However, there's a tricky problem: Recursion. This is when a function calls itself to solve a problem (like counting down from 100 to 0). In reversible systems, it's very hard to make a function call itself without getting stuck in an infinite loop or losing the ability to "rewind" the process.

This paper, by Louis Lemonnier, proposes a new way to build these reversible machines so they can handle recursion safely. Here is the breakdown using simple analogies:

1. The Problem: The "Time Travel" Dilemma

In normal programming, we use a mathematical "map" (called a category) to understand how code works. For standard computers, this map is very flexible (Cartesian). But for reversible and quantum computers, the map is different and stricter (Dagger categories).

The problem is that the standard tools for handling recursion (letting a function call itself) don't work on this stricter map. It's like trying to use a GPS designed for a car to navigate a boat; the rules of the road are different.

2. The Solution: The "Time-Traveling Conveyor Belt"

The author introduces a concept called Guarded Recursion. Think of this as a safety guardrail.

The "Later" Modality (▶): Imagine a conveyor belt in a factory. You can't put a finished product on the belt until the previous step is done. In this paper, the "Later" modality is like a "Next Stop" sign. It forces the computer to say, "I can't finish this recursive step right now; I have to wait one tick of the clock."
The Guard: This "waiting" acts as a guard. It ensures that the recursion doesn't happen instantly and infinitely. It forces the process to move forward in time step-by-step, which keeps the system stable and reversible.

3. The Construction: Building a New Factory

The paper shows how to build a new "factory" (a mathematical structure) out of any existing one, specifically designed to handle this "time-traveling" logic.

The Topos of Trees: The author uses a known, safe model called the "Topos of Trees" (which is like a family tree of time steps) as a blueprint.
The Enrichment: Instead of just looking at the machines (objects), the author looks at the instructions (morphisms) between them. They wrap these instructions in a special "time-layer" that ensures every step respects the "Later" guard.
The Result: They create a new mathematical world where you can have reversible machines that also have the ability to call themselves, as long as they respect the time delay.

4. The "Dagger" (The Undo Button)

A key feature of reversible programming is the Dagger. Think of the Dagger as a universal "Undo" button.

In this new factory, the author proves that you can still press "Undo" on every step, even with the time delays.
They show that if you build a reversible machine using their new method, you can still reverse the flow of data perfectly. It's like recording a movie and then playing it backward frame-by-frame without any glitches.

5. The Application: Symmetric Pattern Matching

The paper demonstrates this by applying it to a specific language called Symmetric Pattern Matching.

The Analogy: Imagine a set of matching socks. In this language, you can say, "If I have a red sock, swap it for a blue one. If I have a blue one, swap it for red." The author shows that their new "time-guarded" system can handle these swaps even when the socks are part of an infinite list (like an endless stream of socks).
Quantum Control: They show how this can be used to build "Quantum If" statements. In a normal computer, an "If" statement checks a condition and chooses a path. In a quantum computer, you can't just "look" at the condition without breaking the quantum state. Their system allows the computer to choose a path based on a quantum bit (qubit) without measuring it, keeping the process reversible.

Summary

The paper doesn't invent a new physical computer. Instead, it invents a new mathematical blueprint (a model).

It takes the strict rules of reversible/quantum computing.
It adds a time-delay mechanism (Guarded Recursion) to allow functions to call themselves safely.
It proves that you can still reverse (undo) every step in this new system.

This allows programmers to write complex, self-referencing code for quantum computers without breaking the fundamental laws of reversibility. It's like giving a time-traveling robot a rulebook that ensures it never gets stuck in a time loop.

Technical Summary: Non-cartesian guarded recursion with daggers

Problem Statement
Guarded recursion is a well-established framework for formalizing streams and recursive data types in classical programming languages, typically modeled within cartesian closed categories (CCCs). However, many significant computing paradigms—specifically reversible, concurrent, and quantum programming—do not admit semantics in CCCs. Instead, they rely on categories equipped with a dagger (an involutive operator on morphisms), such as inverse categories or categories of Hilbert spaces. While inductive types can be modeled in some dagger categories (e.g., inverse categories via enrichment in directed complete partial orders), the interpretation of recursion remains an open or problematic issue in others, particularly Hilbert spaces. The paper addresses the gap in providing a denotational semantics for guarded recursion within the context of dagger categories, aiming to support reversible programming languages that require both reversibility and recursive data structures.

Methodology
The author proposes a categorical construction that adapts the "topos of trees" approach (synthetic guarded domain theory) to non-cartesian settings. The methodology proceeds in three main stages:

The Guarded Construction ( $C^\infty$ ): Starting from an arbitrary category $C$ with a terminal object, the paper constructs a new category $C^\infty$ (isomorphic to $C^{\mathbb{N}^{op}}$ ). Objects in $C^\infty$ are sequences of objects in $C$ connected by morphisms, resembling presheaves. This construction introduces a "later" functor ( $L$ ) and a "next" natural transformation ( $\nu$ ), which shift the sequence components and insert a terminal object, effectively modeling the delay modality required for guarded recursion.
Enrichment and Fixed Points: The category $C^\infty$ is shown to be enriched over the topos of trees ( $S$ ). This enrichment allows the application of fixed point theorems from synthetic guarded domain theory. Specifically, the paper demonstrates that locally contractive functors on $C^\infty$ admit unique fixed points, enabling the interpretation of guarded inductive types (e.g., streams and lists) even when the base category $C$ is not cartesian closed.
Integration with Dagger Rig Structure: To model reversible computation, the paper focuses on dagger rig categories (categories with a dagger, tensor product $\otimes$ , and sum type $\oplus$ ). The author observes that while the rig structure (tensor and sum) is preserved by the guarded construction, the dagger structure is not automatically preserved in $C^\infty$ because the component-wise dagger of a natural transformation may not yield a valid morphism in the constructed category. To resolve this, the paper defines a refined subcategory $C^\infty_e$ (using dagger epimorphisms) and a further subcategory $C^\infty_\dagger$ containing only "daggerable" morphisms (those whose pointwise dagger forms a valid morphism in the category).

Key Contributions and Results

Non-Cartesian Guarded Model: The paper constructs a categorical model for guarded recursion starting from any category with a terminal object, generalizing the topos of trees approach to non-cartesian settings.
Preservation of Rig Structure: It is proven that if the base category $C$ is a dagger rig category, the guarded construction $C^\infty$ preserves the rig structure (tensor and sum types), making it suitable for modeling data types like pairs and lists.
Daggerable Subcategory: The paper identifies that the full construction does not inherently support a dagger. It introduces the category $C^\infty_\dagger$ , a subcategory of the guarded construction where morphisms admit a dagger. It is shown that $C^\infty_\dagger$ is itself a dagger rig category.
Fixed Point Existence: Theorem 3.12 establishes that locally contractive functors on $C^\infty$ admit parameterized fixed points. This result is applied to the subcategory $C^\infty_\dagger$ to interpret guarded inductive types within a reversible setting.
Semantics of Guarded Symmetric Pattern Matching: The paper applies the constructed model to interpret "guarded symmetric pattern matching," a higher-order reversible programming language. The semantics covers:
- Ground types (including guarded inductive types like lists).
- First-order functions (isos) defined via joins of reversible partial functions.
- Higher-order functions via a simply-typed guarded $\lambda$ -calculus enriched in $S$ .
- Specific examples include a quantum control operation and a higher-order definition of the Quantum Fourier Transform (QFT) for lists of qubits.

Significance and Claims
The paper claims to extend the utility of guarded recursion beyond classical stream processing to reversible and quantum programming paradigms. By bridging the semantics of reversible programming (dagger categories) with guarded recursion (topos of trees), the author provides a denotational model for higher-order reversible languages that support infinite data types.

The author explicitly notes that while the construction solves the problem of modeling guarded inductive types in dagger rig categories, it does not resolve the broader open question of whether Hilbert spaces can interpret general recursion. Instead, the paper offers a specific path through guarded recursion. The significance lies in providing a sound categorical foundation for reversible languages with features like symmetric pattern matching and guarded recursion, allowing for the definition of complex quantum algorithms (like QFT) in a high-order, reversible formalism without relying on low-level circuit descriptions. The paper modestly acknowledges that the semantics of streams in dagger categories requires a new theory, as the standard limit construction fails due to the zero-object nature of terminal objects in dagger categories.