A Diagrammatic Basis for Computer Programming

arXiv:2512.07240 · cs.LO · Submitted 2025-12-08 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: We're looking at the paper: "A Diagrammatic Basis for Computer Programming".

Jane: Here's the gist of the paper. My task is to synthesize these into a comprehensive, detailed summary of Paper A, keeping the final output approximately 66% of the target length.

Tom: Here is the detailed synthesis: Comprehensive Research Summary Paper A introduces Kleene-Cartesian rig (kc-rig) categories, which are defined as rig categories equipped with two distinct monoidal products: times forming a Cartesian bicategory structure, and plus forming a Kleene bicategory structure.

Jane: The central innovation is the use of tape diagrams as a graphical notation for arrows within these categories, effectively serving as an "assembly language" for interpreting imperative programs and various program logics.

Tom: The paper establishes that the inference rules for these logics are directly derived from the laws governing kc-rig categories, which themselves arise from canonical categorical structures on sets and relations.

Paper summary: Tom: So, to wrap up on "A Diagrammatic Basis for Computer Programming," the main point is that they’ve created a powerful diagrammatic system using Kleene-Cartesian rig categories to model imperative programming logics.

Jane: It’s about showing that the inference rules for these logics are not arbitrary, but follow directly from the laws of these underlying mathematical structures, which are built on how sets and relations interact.

Lu: The big contribution is connecting this diagrammatic notation—the tape diagrams—to real program constructs like Hoare logic, proving those rules follow from the structural laws of the rig categories <ref:2512.07240#pg3>.

Meng: From a deployment view, it’s a formal way to reason about programs that unifies data flow and control flow graphically Paper A.

Tom: And they also characterized the free Kleene-Cartesian category using these tape diagrams, which is a unified graphical language for both data flow and control flow <ref:2512.07240#pg2>.

Jane: The authors showed that their models for these logics coincide with functors between sesquiestrict rig categories, mirroring Lawvere’s earlier approach Paper A.

Lu: It’s a way to encode things like Peano's axiomatization of natural numbers within this framework, demonstrating its expressive power <ref:2512.07240#pg3>.

Tom: And they also show that Kleene bicategories are precisely typed Kleene algebras Paper A.

Jane: So, in simple terms, this paper provides a diagrammatic basis for interpreting imperative programs and related logics by unifying Cartesian and Kleene bicategory structures under the concept of Kleene-Cartesian rig categories.

Meng: It’s about providing a systematic way to handle the complexity of program logics through well-defined categorical laws.

Lalam: This work is quite sure about its connection to established categorical structures <ref:2512.07240#pg3>.

Conclusion: Tom: So, to wrap up on "A Diagrammatic Basis for Computer Programming," the paper is basically showing how you can use these Kleene-Cartesian structures to create a visual language for imperative programming.

Jane: It connects these math structures—the Kleene bicategories and the Cartesian ones—to tape diagrams, which are like pictures that represent both data flow and control flow in programs.

Lu: The core idea is deriving the actual inference rules of things like Hoare logic directly from the laws governing these underlying categories.

Meng: For someone shipping models to production, it means we have a formal way to reason about how programs actually behave when they run, not just what they might do on paper.

Lalam: This framework provides a unified graphical language that handles both product operations and sequencing in one system.

Tom: The authors did this by defining these Kleene-Cartesian rig categories and then showing how their models align with functors between sesquiestrict categories, which is a known approach from Lawvere's work.

Jane: So, the big takeaway is that you can model complex programming logic using these diagrams because the rules are baked into the category structure itself.

Lu: It’s a systematic way to handle program constructs that unifies data flow and control flow under this single concept of Kleene-Cartesian rig categories.

Meng: If this works, it could mean we have a much more rigorous way to prove properties about software before we even start writing the code.

Tom: It’s certainly a lot of formal machinery, but the goal is making imperative programming logic interpretable through these concrete graphical notations called tape diagrams.

Jane: And that leads us right into what this means for how we think about building and verifying complex systems.

FILIPPO BONCHI, ALESSANDRO DI GIORGIO, ELENA DI LAVORE

University of Pisa · Tallinn University of Technology, Estonia · University of Oxford, United Kingdom

cs.LO

Submitted: 2025-12-08

Updated: 2026-10-30

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 98/100

The gist: My task is to synthesize these into a comprehensive, detailed summary of Paper A, keeping the final output approximately 66% of the target length.

Key concepts

Kleene-Cartesian rig (kc-rig) categories
These are special categories that possess two types of monoidal products: one forming a Cartesian bicategory structure ($\otimes$) and another forming a Kleene bicategory structure ($\oplus$). They serve as the central mathematical setting for modeling complex programming logics.
Tape Diagrams
These are graphical notations used to represent arrows within kc-rig categories. They function like an assembly language, allowing researchers to visually encode imperative program constructs and control flow in a structured way.
Kleene bicategories
These structures arise from the Kleene fragment of relations, characterized by a disjoint union monoidal product ($\oplus$). They are essential for representing certain types of non-deterministic or sequential program behaviors within the categorical framework.
Kleene-Cartesian theories
These are models derived from sesquistrict kc-rig categories. They provide a way to formally define and verify programs, showing that these models correspond to functors between different categories, similar to how Lawvere's approach works.

Terminology

Summary

My task is to synthesize these into a comprehensive, detailed summary of Paper A, keeping the final output approximately 66% of the target length.

Here is the detailed synthesis:

Comprehensive Research Summary

Paper A introduces Kleene-Cartesian rig (kc-rig) categories, which are defined as rig categories equipped with two distinct monoidal products: times forming a Cartesian bicategory structure, and plus forming a Kleene bicategory structure. The central innovation is the use of tape diagrams as a graphical notation for arrows within these categories, effectively serving as an assembly language for interpreting imperative programs and various program logics.

The paper establishes that the inference rules for these logics are directly derived from the laws governing kc-rig categories, which themselves arise from canonical categorical structures on sets and relations. p. 1

Where the paper says it

While the inference rules for each of these logics are usually defined by the ingenuity of the researchers, in our approach such rules follow from the laws of Kleene-Cartesian rig categories. These laws arise from the interaction of canonical categorical structures on the category of sets and relations.

Specifically, it distinguishes between two fundamental monoidal structures on relations: (Rel, times, 1), related to regular theories (Cartesian product), and (Rel, plus, 0), related to the Kleene fragment (disjoint union), the latter yielding Kleene bicategories. p. 3
Where the paper says it

2), and the Kleene fragment consisting of (2. Our starting observation is that these two fragments arise from two different traced monoidal structures on Rel, the category of sets and relations: (Rel, ⊗, 1) and (Rel, ⊕, 0).

The core contribution is the development of Kleene-Cartesian theories and their models. These models are shown to coincide with functors between sesquistrict kc-rig categories and a category of sesquiestrict rig categories, mirroring Lawvere's approach. Furthermore, the paper demonstrates that Kleene bicategories are precisely typed Kleene algebras. p. 9

Where the paper says it

Kleene Bicategories Having recalled Cartesian bicategories, we now introduce our next ingredient: Kleene bicategories. The name reflects the fact that their axioms capture the complete axiomatisation of Kleene algebras given in [Koz94].

A significant result is the characterization of the free kc-rig category in terms of tape diagrams (Theorem 7. p. 1
Where the paper says it

To construct the freely generated kc-rig category (Theorem 7. 1), we extend tape diagrams [BDGS23], a diagrammatic notation recently introduced for rig categories.

1), establishing these diagrams as a unified graphical language for both data flow and control flow—a representation not easily achieved by other methods, particularly for product programs. p. 1
Where the paper says it

Intuitively, tape diagrams are string diagrams [JS91] in which other string diagrams are nested: the inner diagrams model data flow, and the outer ones model control flow. On one hand, this offers an intuitive unified picture of Bainbridge’s idea; on the other it allows for visualising the laws of kc-rig categories (Figures 8, 9 and 10) in a way that enlights several monoidal algebras occurring

The framework proves that key logical rules, such as those in Hoare logic, follow directly from the structural laws of kc-rig categories (Proposition 9. p. 2

Where the paper says it

In particular, we show that the rules of Hoare logic follow from the laws of kc-rig categories (Proposition 9. Finally, the framework is expressive enough to capture the positive fragment of the calculus of relations with transitive closure, which is the departure of our journey.

7). The encoding of imperative program constructs into these tape diagrams is foundational for reasoning about them within this categorical structure. p. 2
Where the paper says it

We illustrate an example of a KleeneCartesian theory which is not first order: Peano’s axiomatisation of natural numbers. We demonstrate how imperative programs and their logics [Hoa69, Koz00, CCFL13, O’H19, ABGL23] – even more sophisticated ones, like [Ben04], where the interaction of data and control flow play a key role – can be encoded within Kleene-Cartesian tape diagrams.

In essence, Paper A provides a powerful diagrammatic basis for interpreting imperative programs and related logics by unifying Cartesian and Kleene bicategory structures under the concept of kc-rig categories. p. 0
Where the paper says it

In this work, we introduce Kleene-Cartesian rig categories, namely rig categories where ⊗ provides a Cartesian bicategory, while ⊕ a Kleene bicategory. We show that the associated tape diagrams can conveniently deal with imperative programs and various program logics.

Paper B, while distinct in its focus, contributes to the underlying categorical machinery that supports such constructions. p. 1

Where the paper says it

In this second structure, the monoidal product ⊕ is the disjoint union of sets, which acts both as a categorical product and a coproduct, hence, a biproduct. Both monoidal categories are traced [JSV96a]: the trace in (Rel, ⊗, 1) represents feedback, while in (Rel, ⊕, 0) –the focus of our work– it provides iteration [Sel98].

It details advanced techniques for constructing free structures on various categories using adjunctions and quotients by congruences. p. 2
Where the paper says it

Its allegorical fragment can be expressed using Cartesian bicategories, reviewed in Section 3, while its Kleene fragment is captured by Kleene bicategories, introduced in Section 4. To combine these two structures, we recall rig categories in Section 5.

Key results involve establishing adjoint relationships between enriched categories (e. p. 3
Where the paper says it

A poset enriched symmetric monoidal functor is a symmetric monoidal functor that preserves the order ≤. The notion of adjoint arrows, which will play a key role, amounts to the following:

g., relating CMonCat and FBC via the matrix construction), showing how specific functors (like Mat) yield Kleene bicategories, and defining the Kleene congruence (about C) which, when quotiented out, yields a functor that is the left adjoint to an inclusion into KBicat. This work provides the rigorous categorical tools necessary for constructing free Kleene bicategories and rig categories mentioned in Paper A. p. 1
Where the paper says it

Both monoidal categories are traced [JSV96a]: the trace in (Rel, ⊗, 1) represents feedback, while in (Rel, ⊕, 0) –the focus of our work– it provides iteration [Sel98]. Our first step is to extract from (Rel, ⊕, 0) the categorical structures essential for modelling control flow, which we term Kleene bicategories.

**In essence, Paper A applies these advanced categorical constructions (which are detailed in Paper B) to create a novel diagrammatic system (tape diagrams) for modeling imperative programming logics via Kleene-Cartesian rig categories. p. 2

Where the paper says it

In particular, Appendix A contains a dictionary for the structure of Kleene-Cartesian rig categories and its representation as string diagrams and tape diagrams. This paper extends the conference version [BGL25] by including full proofs, additional examples, and several minor results.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Implement program verification systems using Kleene-Cartesian tape diagrams to derive program equivalences that are not directly provable in standard Kleene Algebra with Tests (KAT). This allows for proving sophisticated program equivalences involving nontrivial interactions between data and control flow, as shown in Example 9.3 and 9.4.

  2. Develop relational reasoning capabilities for imperative programs by encoding them into KC tape diagrams to represent Hoare triples as inequalities E(P) †; E(C) ≤I E(Q) †, enabling the verification of program correctness across related executions or programs in lockstep, as illustrated in Section 9.2 and Table 11.

  3. Create a formal proof system for imperative programs that is at least as powerful as Hoare logic by directly deriving its rules from the laws of KC-rig categories (Proposition 9.7), ensuring that the derived equivalences are sound with respect to the extensional semantics JE(Γ ⊢ C)KI.

  4. Enhance data flow analysis by representing complex program properties like non-interference via tape inequalities and the tensor operator, enabling direct representation of product programs as sequential compositions of whiskering operations, as shown in Example 9.9 and Proposition 6.12.

  5. Design a formal verification framework for safety properties (like k-safety) by leveraging the structure of kc-rig categories to derive necessary precondition strengthening rules that are not directly provable in standard Hoare logic, using the derived inequalities from Proposition 4.6 and Lemma D.1.

Abstract

Tape diagrams provide a convenient graphical notation for arrows of rig categories, i.e., categories equipped with two monoidal products, plus and times. In this work, we introduce Kleene-Cartesian rig categories, namely rig categories where times provides a Cartesian bicategory, while plus a Kleene bicategory. We show that the associated tape diagrams can conveniently deal with imperative programs and various program logic.

Sources

Related papers