💻 computer science

A Diagrammatic Basis for Computer Programming

This paper introduces Kleene-Cartesian rig categories and their associated tape diagrams as a graphical notation capable of conveniently representing imperative programs and various program logics.

Original authors: Filippo Bonchi, Alessandro Di Giorgio, Elena Di Lavore

Published 2026-04-22

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Filippo Bonchi, Alessandro Di Giorgio, Elena Di Lavore

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 describe how a computer program works. Usually, we do this with code (text) or flowcharts (diagrams). But what if we could describe programs using a single, unified visual language that handles both what the data is (like numbers or names) and how the program moves (like loops and decisions)?

This paper introduces exactly that: a new way to draw programs called Tape Diagrams, built on a mathematical foundation called Kleene-Cartesian Rig Categories.

Here is the breakdown in simple terms, using analogies.

1. The Two Big Problems: Data vs. Control

Think of a computer program as a factory.

Data Flow (The Products): This is the stuff moving through the factory. Raw materials go in, get processed, and come out as finished goods. In math, this is like a "Cartesian" system where things can be copied and thrown away easily (like making a photocopy of a document or shredding it).
Control Flow (The Machines): This is the machinery deciding what happens next. "If the part is red, paint it; if it's blue, discard it." Or, "Keep painting until the box is full." This involves loops and choices. In math, this is like a "Kleene" system, which is great at handling repetition (like a loop) and branching (like an "if/else" statement).

The Problem: Historically, mathematicians and computer scientists had two different languages to describe these two things. One language was great for data but bad for loops. The other was great for loops but messy for data. It was like trying to build a house using a hammer for the nails and a screwdriver for the wood, but having to switch tools constantly and losing track of the blueprint.

2. The Solution: The "Rig" Category (The Double-Tool)

The authors introduce a concept called a Rig Category.

The Analogy: Imagine a "Rig" (short for Ring, but without the subtraction) as a Swiss Army Knife for math. It has two main tools built into one handle:
1. Tool A (The Copy/Share Tool): Handles data. It lets you split a wire into two (copying data) or merge two wires (combining data).
2. Tool B (The Loop/Choice Tool): Handles control. It lets you create a loop (a feedback wire that goes back to the start) or a choice (a wire that splits into "yes" or "no" paths).

The magic of this paper is showing how these two tools can work together perfectly without breaking the rules of logic. They call this a Kleene-Cartesian Rig Category.

3. The Visual Language: Tape Diagrams

How do you draw this? The authors use Tape Diagrams.

The Analogy: Imagine a reel of film or a tape measure.
- The Inner Layer (The Circuit): Inside the tape, you draw standard string diagrams. These represent the data flow (the products moving through the factory).
- The Outer Layer (The Tape): The tape itself represents the control flow (the machines deciding the path).
- Nesting: You can put a whole "inner circuit" inside a "tape loop." This means you can visually see a loop (the tape) containing a complex data process (the circuit).

It's like looking at a subway map (control flow) where every station has a detailed blueprint of the train station inside it (data flow).

4. Why Does This Matter? (The "Assembly Language" for Logic)

The paper claims these diagrams act as an "Assembly Language" for program logic.

What is Assembly Language? It's a low-level code that talks directly to the hardware. It's precise and powerful.
The Paper's Claim: By using these Tape Diagrams, you can prove that famous rules of computer science (like Hoare Logic, used to prove programs are bug-free) aren't just arbitrary rules made up by humans. Instead, they naturally fall out of the geometry of the diagrams.

Example:
If you draw a "While Loop" in this system, the diagram automatically forces the rules of the loop to be correct. You don't have to memorize a rulebook; the shape of the tape is the rule.

5. Real-World Examples in the Paper

The authors show this works for:

Natural Numbers: They can draw the Peano axioms (the rules for counting 0, 1, 2...) using these tapes.
Imperative Programs: They can translate standard code (like x = x + 1 or if x > 0 then...) into these diagrams.
Relational Logic: They can prove that two different programs do the exact same thing just by looking at whether their diagrams can be transformed into each other.

Summary

This paper is like inventing a new universal grammar for computer programs.

Before: We had separate languages for "how data moves" and "how decisions are made."
Now: We have Tape Diagrams, a single visual language where data and control flow are woven together.
The Benefit: It makes it easier to reason about complex software, prove that programs are correct, and understand the deep mathematical structure behind the code we write every day.

It turns the abstract, scary math of "categories" into a set of intuitive, drawable rules that look like a mix of a circuit board and a flowchart, finally unifying the two halves of programming into one beautiful picture.

1. Problem Statement

The paper addresses the need for a systematic, algebraic foundation for program logics (such as Hoare logic, incorrectness logic, and relational Hoare logic). While relational calculi and category theory have historically provided foundations for logic (e.g., Lawvere's functorial semantics for equational logic), existing frameworks struggle to unify data flow and control flow within a single, expressive, and diagrammatic framework.

Specifically, the authors identify a gap in modeling imperative programs where:

Data flow is naturally modeled by the Cartesian product of relations (representing state spaces and functions).
Control flow (iteration, loops, non-determinism) requires a different monoidal structure (disjoint union/biproducts) and trace operators to model feedback and iteration.
Current approaches often treat these separately or lack a unified syntax that allows for the derivation of complex program equivalences and proof rules directly from algebraic laws.

2. Methodology

The authors employ Categorical Algebra and Diagrammatic Reasoning to construct a unified framework. Their methodology involves three main steps:

A. Defining Kleene-Cartesian Rig Categories (kc-rig)

They introduce a new categorical structure called a Kleene-Cartesian rig category. A rig category (or semiring category) possesses two monoidal structures:

$(\otimes, 1)$ (Cartesian): Models data flow. This structure is a Cartesian bicategory, where the monoidal product is the Cartesian product of sets. It supports copying and discarding of data (functions).
$(\oplus, 0)$ (Kleene): Models control flow. This structure is a Kleene bicategory, where the monoidal product is the disjoint union (biproduct). It supports non-determinism, choice, and iteration via a uniform trace.

The interaction between these two structures is governed by distributivity laws, ensuring that the "rig" (ring-like) structure holds.

B. Introducing Tape Diagrams

To visualize and compute within these 2D structures (which inherently require 3D for standard string diagrams due to the two monoidal products), the authors utilize Tape Diagrams.

Concept: Tape diagrams are "string diagrams of string diagrams."
Inner Layer (Circuits): Represents the Cartesian structure ( $\otimes$ ), modeling data flow (copying, discarding, function application).
Outer Layer (Tapes): Represents the Kleene structure ( $\oplus$ ), modeling control flow (branching, loops, non-deterministic choice).
Syntax: The diagrams allow for the nesting of circuits within tapes, providing a 2D representation of the interaction between data and control.

C. Functorial Semantics

Following Lawvere's approach, they define Kleene-Cartesian theories as pairs of a signature and a set of axioms (inequalities between tapes). Models of these theories are functors from the freely generated category of tape diagrams to a target category (typically Rel, the category of sets and relations).

3. Key Contributions

1. Kleene Bicategories and Typed Kleene Algebras

The authors formalize Kleene bicategories as poset-enriched traced monoidal categories with biproducts. They prove that these categories are equivalent to Typed Kleene Algebras (Kozen's axioms extended to multiple types). This establishes that the categorical trace on biproducts perfectly captures the algebraic properties of the Kleene star ( $*$ ), which represents iteration.

2. The Tape Diagram Calculus

They present a complete diagrammatic calculus for kc-rig categories.

Theorem 7.1: The category of Tape Diagrams ( $KCT_\Sigma$ ) is the free sesquistrict Kleene-Cartesian rig category generated by a signature.
The calculus includes specific axioms for the interaction of the two monoidal products, including uniformity conditions for the trace, which are crucial for deriving loop invariants and induction principles.

3. Encoding Imperative Programs

The paper demonstrates how to encode standard imperative programming constructs into tape diagrams:

Variables/State: Represented as wires in the Cartesian layer.
Assignments: Modeled using the copy/discard structure of Cartesian bicategories.
Conditionals: Modeled using the biproduct structure ( $\oplus$ ) and coreflexives (predicates).
Loops: Modeled using the Kleene star ( $*$ ) and the trace operator.

4. Derivation of Program Logics

A major result is that standard program logics are not arbitrary rules but consequences of the algebraic laws of kc-rig categories.

Hoare Logic: The authors prove that the inference rules of Hoare logic (partial correctness) follow directly from the axioms of kc-rig categories (Proposition 9.7).
Relational Hoare Logic (RHL): They show that RHL (reasoning about two programs simultaneously) is naturally expressed using the $\otimes$ product of tapes, allowing for the construction of "product programs" and proving properties like non-interference and security.
Other Logics: The framework also captures Incorrectness Logic, Sufficient Incorrectness Logic, and Necessary Logic by simply changing the direction of inequalities in the semantic interpretation.

5. Peano Arithmetic

The authors provide a Kleene-Cartesian theory for Peano's axioms of natural numbers. They show that the principle of mathematical induction is a direct consequence of the posetal uniformity of the trace in the Kleene bicategory structure.

4. Results

Completeness of Encoding: The encoding of imperative programs into tape diagrams is sound. If two programs are equal in the tape calculus, they are extensionally equivalent (have the same relational semantics).
Derivation of Rules: The paper provides explicit diagrammatic derivations showing that:
- Hoare triples $\{P\}C\{Q\}$ correspond to the inequality $E(P)^\dagger ; E(C) \leq E(Q)^\dagger$ .
- The rule for while loops is derived from the uniformity axiom of the trace.
- The frame rule in Relational Hoare Logic is derived from the interaction of the Cartesian product and the trace.
Expressiveness: The framework is shown to be more expressive than standard Kleene Algebra with Tests (KAT) because it explicitly models data flow and variable dependencies, allowing for the proof of equivalences that KAT cannot derive without ad-hoc axioms (e.g., commutativity of assignments on disjoint variables).

5. Significance

Unified Foundation: The paper successfully unifies the algebraic treatment of data flow (Cartesian) and control flow (Kleene) under a single "assembly language" (tape diagrams).
Visual Reasoning: It provides a powerful visual tool for reasoning about complex program properties. The diagrammatic nature makes structural properties (like variable disjointness or loop invariants) immediately visible.
Systematic Logic Generation: Instead of defining proof rules for each new program logic manually, the framework suggests that these rules are inherent to the underlying categorical structure. This offers a systematic way to generate sound proof systems for new logics.
Bridging Theory and Practice: By connecting abstract category theory (rig categories, bicategories) directly to practical imperative programming and verification, the work bridges a significant gap between theoretical computer science and software engineering.
Future Directions: The authors highlight that this framework opens the door to proving complex properties like non-interference and security using purely algebraic manipulations of diagrams, suggesting a path toward automated verification tools based on diagrammatic rewriting.

In summary, this paper establishes Tape Diagrams as a robust, algebraic, and visual foundation for imperative programming, demonstrating that the laws of program logics are natural consequences of the interaction between Cartesian and Kleene structures in category theory.