🔢 mathematics

Monoidal categories graded by partial commutative monoids

This paper introduces monoidal categories graded by partial commutative monoids to axiomatize the graded structure of effectful categories, demonstrating that this framework generalizes both standard monoidal and effectful categories while providing a unified perspective on resource-aware computation and parallelism.

Original authors: Matthew Earnshaw, Chad Nester, Mario Román

Published 2026-03-18

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Matthew Earnshaw, Chad Nester, Mario Román

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 running a busy kitchen. In this kitchen, you have two types of chefs: Pure Chefs and Effectful Chefs.

Pure Chefs are like robots. They chop vegetables or stir a pot. They don't care what anyone else is doing. If Chef A chops an onion and Chef B stirs a soup, they can do it at the exact same time without any problems. They are independent.
Effectful Chefs are like humans. They might need to use a specific oven, or they might need to wait for a pot to cool down. If Chef C tries to use the oven while Chef D is already using it, chaos ensues. They can't just work side-by-side freely; they have to coordinate.

In computer science, we call the "Pure" world a Monoidal Category (everything works in parallel) and the "Effectful" world a Premonoidal Category (things only work in parallel if they don't clash).

This paper introduces a new, super-flexible way to organize these kitchens using a concept called Partial Commutative Monoids (PCMs). Think of a PCM not as a math formula, but as a "Resource Rulebook."

The Big Idea: Grading by Resources

The authors suggest that instead of just saying "Pure" or "Effectful," we should give every task a Grade (a label) that tells us exactly what resources it needs.

Imagine every task in your kitchen has a tag:

Tag "0": Needs nothing. (Pure)
Tag "Oven": Needs the oven.
Tag "Stove": Needs the stove.
Tag "Oven + Stove": Needs both.

The Rulebook (PCM) tells you when you can combine two tasks:

Can you combine "Oven" and "Stove"? Yes! They are different resources. The new task gets the tag "Oven + Stove."
Can you combine "Oven" and "Oven"? No! You can't use the same oven for two things at once. The rulebook says this combination is undefined.

This is the core of the paper: You can only run things in parallel if their resource tags don't clash.

Why is this cool? (The Examples)

The paper shows how this simple idea explains many complex computer science problems:

The "Two-Tag" System (Effectful Categories):
Imagine a rulebook with only two tags: "Clean" and "Dirty."
- You can combine "Clean" + "Clean" = "Clean."
- You can combine "Clean" + "Dirty" = "Dirty."
- But you cannot combine "Dirty" + "Dirty" (because two messy things can't happen at once without a fight).
- Result: This perfectly models the old way of thinking about "Pure vs. Effectful" code. The paper proves that this old way is just a special, simple case of their new, more powerful system.
The "Memory Map" (Separation Logic):
Imagine a computer program that needs to access specific files.
- Task A needs File 1.
- Task B needs File 2.
- Can they run together? Yes!
- Task C needs File 1. Can A and C run together? No! They fight over File 1.
- Result: This helps programmers write code that accesses shared memory safely, ensuring two programs never try to write to the same file at the same time.
The "Bandwidth Budget" (Bounded Resources):
Imagine you have a Wi-Fi connection with a speed limit of 100 Mbps.
- Task A uses 30 Mbps.
- Task B uses 40 Mbps.
- Can they run together? Yes! 30 + 40 = 70, which is under the limit.
- Task C uses 80 Mbps. Can A and C run together? No! 30 + 80 = 110, which breaks the limit.
- Result: This models systems where you have a limited budget (like money, time, or bandwidth) and need to make sure parallel tasks don't overspend.

The "Secret Sauce": The Rulebook as a Map

The authors also show that you can look at this whole system from a different angle. Instead of thinking of the rules as a list, they treat the rules themselves as a map (a mathematical shape called a "promonoidal category").

By turning the Rulebook into a map, they can use advanced math tools to prove that all these different systems (Pure, Effectful, Resource-limited) are actually just different views of the same underlying structure. It's like realizing that a cube, a square, and a line are all just different ways of looking at the same 3D object depending on how you shine the light on it.

Summary in Plain English

The Problem: Computer programs have "pure" parts (easy to run in parallel) and "messy" parts (hard to run in parallel because they fight over resources).
The Old Solution: We had a rigid system that only knew "Pure" or "Messy."
The New Solution: This paper gives us a dynamic Rulebook. We can assign any task a specific "resource tag."
The Magic: The system automatically knows if two tasks can run together. If their tags clash (like two people trying to use the same tool), the system says "No." If they don't clash, it says "Go!" and combines their tags.
The Benefit: This allows computer scientists to build safer, more efficient programs that manage memory, bandwidth, and security levels without crashing or causing errors.

In short, the authors built a universal traffic light system for computer code. It tells every piece of code exactly when it's safe to drive in parallel and when it needs to wait, based on exactly what resources it needs.

1. Problem Statement

The paper addresses the need for a unified categorical framework to model effectful programming languages and resource-sensitive computation.

Context: Effectful categories (or generalized Freyd categories) refine monoidal categories by distinguishing between "pure" morphisms (which form a monoidal category) and "effectful" morphisms (which form a premonoidal category). Pure morphisms can be combined in parallel, while effectful morphisms generally cannot, unless combined with central morphisms.
Limitation of Existing Approaches:
- Standard graded monads and Freyd categories typically use grades that combine under sequential composition.
- Existing models often treat the distinction between pure and effectful computations as a binary state (pure vs. effectful) or rely on specific algebraic structures (like separation algebras) without a general categorical axiomatization for the parallel combination of graded morphisms.
Core Challenge: How to axiomatize a structure where morphisms carry a "grade" (representing resources, effects, or capabilities) such that the monoidal product (parallel composition) is defined only when the grades are compatible (orthogonal), while sequential composition preserves the grade.

2. Methodology

The authors introduce a new algebraic structure called a Partial Commutative Monoid (PCM) and use it to define PCM-graded monoidal categories.

Partial Commutative Monoids (PCMs): A set $E$ equipped with a partial binary operation $\oplus$ and a unit $0$. The operation is commutative and associative where defined. The partiality models the constraint that certain resources cannot be combined (e.g., two programs trying to write to the same memory location).
Axiomatization: The paper defines an $E$ $E$ -graded monoidal category as a family of categories $\{C_a\}_{a \in E}$ ${C_{a}}_{a \in E}$ indexed by the PCM, sharing a common set of objects.
- Grading: Morphisms $f: X \to Y$ have a specific grade $a \in E$ .
- Sequential Composition: Defined within each grade $C_a$ .
- Monoidal Product: Defined only for morphisms with orthogonal grades $a \perp b$ (where $a \oplus b$ is defined). The product maps $C_a \times C_b \to C_{a \oplus b}$ .
- Regrading: Functors exist to map morphisms from a "smaller" grade to a "larger" one in the extension preorder ( $a \leq b$ if $\exists c, a \oplus c = b$ ).
Categorical Reformulation: The authors reformulate these structures as monoids in a monoidal category of lax monoidal functors. They achieve this by viewing a PCM as a thin promonoidal category (specifically a Bool-promonoidal category), which induces a convolution monoidal structure on presheaves. This connects the work to the theory of duoidal categories and enriched category theory (Heunen and Sigal).

3. Key Contributions

A. Definition of PCM-Graded Monoidal Categories

The central contribution is the formal definition of monoidal categories graded by a PCM. This structure generalizes:

Monoidal Categories: Recovered when grading by the singleton PCM ($1$).
Effectful Categories: Recovered when grading by the 2-element PCM ( $2 = \{0, 1\}$ ), where $1 \oplus 1$ is undefined.
Freyd Categories: Recovered when the grading is cartesian and symmetric.

B. Modeling Resource-Sensitive Parallelism

The framework provides a natural way to model non-interfering parallelism and bounded resources:

Powerset PCMs ( $P(X)$ ): Models programs accessing a set of devices $X$ . The monoidal product is defined only if the sets of accessed devices are disjoint ( $S \cap T = \emptyset$ ).
Read-Write PCMs ($RW$): Models memory access where read-read overlap is allowed, but any write overlap is forbidden.
Interval PCMs ( $[0, r]$ ): Models bounded resources (e.g., bandwidth or CPU cycles). The product is defined only if the sum of resource usage does not exceed the bound $r$ .

C. Isomorphism with Effectful Categories

The paper proves that the category of effectful categories is isomorphic to the category of 2-graded monoidal categories. Furthermore, it establishes that 2-graded monoidal categories form a coreflective subcategory of PCM-graded monoidal categories (for PCMs with a top element). This provides a new perspective on effectful categories as a specific instance of a broader graded framework.

D. Construction of Global Categories

The authors show how to assemble the family of local categories $\{C_a\}$ into a single "global" category under certain conditions on the PCM's extension preorder:

If the preorder has binary joins, the global category is formed by taking the disjoint union of hom-sets and defining composition via the join of grades.
If the preorder is directed, a quotient category can be formed by identifying morphisms via regrading functors.
This allows for the modeling of sequential composition of heterogeneously graded morphisms (e.g., composing a program using resource $A$ with one using resource $B$ ).

E. Categorical Reformulation via Promonoidal Categories

By encoding a PCM as a thin promonoidal category, the authors demonstrate that PCM-graded monoidal categories are precisely monoids in the category of lax monoidal functors from the object monoid to the category of presheaves on the PCM. This unifies the concept with existing literature on graded monads and duoidal categories.

4. Results

Theorem 4.2: Establishes the isomorphism between the category of strict effectful categories and 2-graded monoidal categories.
Theorem 4.4: Shows that 2-graded monoidal categories are a coreflective subcategory of PCM-graded monoidal categories (for PCMs with a top element).
Theorem 4.15: Proves that Freyd categories are isomorphic to cartesian 2-graded monoidal categories.
Proposition 5.1 & 5.6: Demonstrates conditions under which an $E$ -graded monoidal category can be collapsed into a single category with heterogeneous sequential composition.
Theorem 6.6: Provides the reformulation of PCM-graded monoidal categories as monoids in a specific monoidal category of functors, linking the work to Heunen and Sigal's enriched Freyd categories.

5. Significance

Unification: The paper provides a single, uniform framework that encompasses monoidal categories, effectful categories, Freyd categories, and various resource-sensitive models (separation logic, bounded resources) under one roof.
Flexibility: By varying the grading PCM, the framework can model diverse scenarios:
- Binary effects: Pure vs. Impure.
- Spatial separation: Disjoint memory regions (Separation Logic).
- Quantitative bounds: Bandwidth or time limits.
Theoretical Depth: The connection to promonoidal categories and duoidal structures opens the door to applying advanced tools from enriched category theory to the semantics of effectful programming.
Future Directions: The work suggests a path toward "partial duoid" graded categories where grades combine differently under sequential vs. monoidal composition, potentially bridging the gap between separation logic and traditional graded type systems.

In summary, this paper successfully generalizes the semantics of effectful programming by introducing a flexible grading mechanism based on partial commutative monoids, offering a robust mathematical foundation for reasoning about parallelism, resource usage, and side effects in programming languages.