🔢 mathematics

Monoidal categories graded by partial commutative monoids

Dit artikel introduceert monoidale categorieën die zijn gegradueerd door partiële commutatieve monoiden als een axiomatische raamwerk om effectvolle categorieën en gerelateerde structuren, zoals Freyd-categorieën, te modelleren en te generaliseren.

Oorspronkelijke auteurs: Matthew Earnshaw, Chad Nester, Mario Román

Gepubliceerd 2026-03-18

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Matthew Earnshaw, Chad Nester, Mario Román

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een grote, chaotische keuken hebt waar verschillende chefs werken. Sommige chefs doen alleen maar "pure" taken, zoals het snijden van groenten of het wegen van bloem. Deze taken zijn veilig: je kunt ze tegelijkertijd uitvoeren zonder dat ze elkaar in de weg zitten.

Andere chefs doen "effectvolle" taken, zoals het gebruiken van de oven of het mixen van een zure saus. Deze taken zijn riskant. Als twee chefs tegelijkertijd proberen dezelfde oven te gebruiken, ontstaat er een conflict. Ze kunnen niet gewoon "naast elkaar" werken; ze moeten wachten of een van hen moet stoppen.

Dit papier introduceert een nieuwe manier om naar deze keuken (en naar computerprogramma's) te kijken. De auteurs noemen dit monoidale categorieën die zijn "gegradeerd" door partiële commutatieve monoiden. Dat klinkt als een enorme mond vol wiskunde, maar laten we het vertalen naar alledaags taalgebruik.

1. Het idee van "Graden" (Labels)

In de oude manier van kijken hadden we twee soorten chefs: veilige en onveilige. Maar in de echte wereld is het niet zo zwart-wit.

Soms heb je een taak die alleen 1 liter water nodig heeft.
Soms heb je een taak die 5 liter water nodig heeft.
Soms heb je een taak die geen water nodig heeft.

De auteurs zeggen: "Laten we elke taak een label geven dat aangeeft hoeveel 'ruimte' of 'bronnen' hij nodig heeft." Dit label noemen ze een graad.

2. De "Partiële" Regel (Wanneer mag je samenwerken?)

Hier komt het slimme deel. In de oude theorie mochten je taken altijd worden gecombineerd. Maar in deze nieuwe theorie geldt een nieuwe regel: Je mag twee taken alleen tegelijkertijd uitvoeren als hun labels het toelaten.

Stel je voor dat je labels hebt als "Gebruikt de OVEN" en "Gebruikt de KOFFIEKOP".

Taak A: Gebruikt de OVEN.
Taak B: Gebruikt de KOFFIEKOP.
Mag je ze samen doen? Ja! Ze gebruiken verschillende apparaten. Hun labels zijn "orthogonaal" (ze botsen niet).
Taak C: Gebruikt de OVEN.
Taak D: Gebruikt de OVEN.
Mag je ze samen doen? Nee! De combinatie is niet gedefinieerd. Je kunt niet twee keer dezelfde oven tegelijk gebruiken.

Dit noemen ze een partiële operatie: het werkt soms, en soms niet. Het hangt af van de labels.

3. De Drie Manieren om te Kijken (Voorbeelden uit het papier)

De auteurs laten zien dat deze ene nieuwe theorie eigenlijk drie bekende dingen in één pakketje verpakt:

De "Veilige" Keuken (Monoidale Categorieën):
Stel dat alle chefs alleen maar groenten snijden. Niemand gebruikt de oven. Dan is er nooit een conflict. Je kunt alles tegelijk doen. Dit is de oude, veilige wiskunde die we al kenden.
De "Effectvolle" Keuken (Effectful Categories):
Dit is het geval dat we al kenden: er zijn twee soorten chefs (veilig en onveilig). Als je een onveilige taak doet, moet je oppassen met wie je samenwerkt. Dit is precies wat dit papier generaliseert.
De "Slimme" Keuken (Nieuwe Voorbeelden):
Hier wordt het echt interessant. De auteurs laten zien dat je veel meer kunt modelleren dan alleen "veilig vs. onveilig":
- De Bandbreedte-keuken: Stel je voor dat je een internetverbinding hebt van maximaal 100 Mbps. Een taak gebruikt 30 Mbps, een andere 40 Mbps. Samen doen ze 70 Mbps. Dat mag! Maar als je een taak van 60 Mbps en een van 50 Mbps wilt combineren, is dat verboden (110 > 100). De taak kan niet bestaan. Dit modelleert hoe computers omgaan met beperkte bandbreedte of geheugen.
- De "Lezen en Schrijven"-keuken: Een taak mag alleen samenwerken met een andere als ze niet tegelijkertijd proberen iets op te schrijven in hetzelfde bestand. Als ze alleen lezen, is dat oké.

4. Waarom is dit nuttig?

Vroeger moesten programmeurs en wiskundigen aparte regels bedenken voor elke situatie:

"Hoe doen we het met geheugen?"
"Hoe doen we het met beveiliging?"
"Hoe doen we het met parallelle verwerking?"

Met deze nieuwe theorie hebben ze één universele taal bedacht. Ze zeggen: "Geef elk probleem een set labels (de graad) en een set regels over welke labels samen mogen."

Als je geheugen wilt modelleren, geef je labels als "Gebruikt blok A".
Als je beveiliging wilt modelleren, geef je labels als "Niveau 1" of "Niveau 2".
Als je tijd wilt modelleren, geef je labels als "Duurt 5 seconden".

De wiskunde achter de schermen zorgt er dan automatisch voor dat je nooit een programma schrijft dat twee keer dezelfde geheugenplek tegelijk gebruikt, of dat te veel bandbreedte vraagt.

Samenvattend in een Metafoor

Stel je voor dat je een legoblokken-set hebt.

De oude theorie zei: "Je mag blokken alleen stapelen als ze beide 'veilig' zijn, of als je heel voorzichtig bent."
Deze nieuwe theorie zegt: "Elk blok heeft een stempel (een graad). Je mag twee blokken alleen aan elkaar klikken als hun stempels niet botsen."

Soms is het stempel "Geen risico" (dan mag je alles doen). Soms is het stempel "Gebruikt de rode klem" (dan mag je niet samenwerken met iemand die ook de rode klem gebruikt).

De auteurs hebben bewezen dat deze ene regel ("klikken mag alleen als de stempels niet botsen") precies genoeg is om alle complexe situaties in computerprogramma's te beschrijven, van simpele rekenmachines tot complexe systemen die tegelijkertijd met bestanden, geheugen en beveiliging werken.

Het is alsof ze een universele bouwvoorschriften hebben geschreven die werkt voor elke soort bouwproject, zolang je maar de juiste labels op je materialen plakt.

Titel: Monoidale categorieën gegradueerd door partiële commutatieve monoiden

Auteurs: Matthew Earnshaw, Chad Nester, Mario Román
Doelwit: MFPS 2026 (Proceedings)

1. Het Probleem

De semantiek van effectvolle programmeertalen vereist vaak een onderscheid tussen "pure" berekeningen (die onafhankelijk van elkaar zijn en parallel uitgevoerd kunnen worden) en "effectvolle" berekeningen (die afhankelijkheden hebben en niet zomaar parallel gecombineerd kunnen worden).

Bestaande modellen: Effectvolle categorieën (of gegeneraliseerde Freyd-categorieën) modelleren dit door twee klassen van morfismen te hebben: een monoidale categorie voor pure berekeningen en een premonoidale categorie voor effectvolle berekeningen.
Beperkingen: Bestaande theorieën over gegradueerde systemen (zoals gegradueerde monaden) combineren grades meestal onder sequentiële compositie. In effectvolle contexten moeten grades echter combineren onder het monoidale product (parallelle uitvoering), en deze combinatie is vaak partiëel gedefinieerd. Bijvoorbeeld: het parallelle uitvoeren van twee programma's die dezelfde hulpbronnen gebruiken, is niet toegestaan.
De kernvraag: Hoe kan men een uniforme structuur definiëren die monoidale categorieën, effectvolle categorieën en andere resource-gevoelige scenario's (zoals geheugenbeperkingen of beveiligingsniveaus) verenigt, waarbij de gedefinieerdheid van het monoidale product wordt bepaald door een algebraïsche graad?

2. Methodologie

De auteurs introduceren een nieuw axiomatisch raamwerk: monoidale categorieën gegradueerd door partiële commutatieve monoiden (PCM).

Partiële Commutatieve Monoiden (PCM): Een verzameling $E$ met een partiële operatie $\oplus$ en een eenheid $0$. De operatie is commutatief en associatief waar gedefinieerd. De "orthogonaliteit" ( $a \perp b$ ) betekent dat $a \oplus b$ gedefinieerd is.
Definitie van een $E$ -gegradueerde monoidale categorie:
- Een familie van categorieën $\{C_a\}_{a \in E}$ , geïndexeerd door de grades.
- Een monoid van objecten $(C_{obj}, \otimes, I)$ dat voor alle categorieën gemeenschappelijk is.
- Regrading functors: Voor $a \leq b$ (in de extensie-preorde) bestaat er een functor $(-)^b_a: C_a \to C_b$ .
- Partiële monoidale producten: Voor elke paar grades $a, b$ met $a \perp b$ , bestaat er een operatie:
  $(\otimes)_{a,b}: C_a(X; Y) \times C_b(X'; Y') \to C_{a \oplus b}(X \otimes X'; Y \otimes Y')$
- De axioma's garanderen consistentie met regrading en associativiteit/commutativiteit waar gedefinieerd.

Technische vertaling:
De auteurs tonen aan dat deze structuur geïsoleerd kan worden als monoiden in een monoidale categorie van lax monoidale functors. Ze modelleren de PCM als een "dun promonoidale categorie" (een Bool-verrijkte promonoidale categorie). Hierdoor kunnen ze PCM-gegradueerde categorieën karakteriseren als monoiden in een categorie van presheaves, wat een diepere categorische connectie legt met bestaande literatuur over duoidale categorieën.

3. Belangrijkste Bijdragen

Unificatie van Categorieën:
- Monoidale categorieën: Ontstaan als het geval waarin de PCM de singleton $\{0\}$ is.
- Effectvolle categorieën: Zijn isomorf met $2$-gegradueerde monoidale categorieën (waarbij $2 = \{0, 1\}$ en $1 \oplus 1$ niet gedefinieerd is).
- Freyd-categorieën: Worden herwonnen als cartesiaanse $2$-gegradueerde monoidale categorieën.
Nieuwe Modelleringsmogelijkheden:
De auteurs presenteren concrete voorbeelden van PCMs die specifieke resource-beperkingen modelleren:
- Powerset PCM ( $P(X)$ ): Modelleren van niet-interfererende parallelle uitvoering. Twee programma's kunnen parallel draaien alleen als ze disjuncte sets van hulpbronnen (bijv. bestandshandles, geheugenlocaties) gebruiken.
- Interval PCM ( $[0, r]$ ): Modelleren van gebonden hulpbronnen (bijv. bandbreedte). Het monoidale product is gedefinieerd alleen als de som van de gebruikte hulpbronnen de limiet $r$ niet overschrijdt.
- RW-PCM (Read/Write): Modelleren van race-free parallelisme waarbij lees-lees overlap toegestaan is, maar schrijf-acties strikt gescheiden moeten zijn.
Categorische Relaties:
- Coreflectiviteit: De categorie van effectvolle categorieën is een coreflectieve deelcategorie van de categorie van PCM-gegradueerde monoidale categorieën (voor PCMs met een top-element).
- Globale Categorieën: Als de extensie-preorde van de PCM goed gedragen is (bijv. heeft joins), kunnen de lokale categorieën $C_a$ worden samengevoegd tot één enkele "globale" categorie met heterogene compositie.
Formele Karakterisering:
In Sectie 6 wordt bewezen dat PCM-gegradueerde monoidale categorieën exact overeenkomen met monoiden in een specifieke categorie van lax monoidale functors, waarbij de PCM wordt gezien als een dun promonoidale categorie. Dit koppelt het werk aan de theorie van duoidale categorieën en verrijkte categorieën.

4. Resultaten

Isomorfisme: Er is een strikt isomorfisme tussen de categorie van strikte effectvolle categorieën en de categorie van $2$-gegradueerde monoidale categorieën.
Uitbreiding: De theorie generaliseert Freyd-categorieën naar een breed scala aan resource-gevoelige contexten, niet beperkt tot slechts twee niveaus (puur/effectvol).
Constructie: De auteurs tonen aan hoe men een globale categorie kan construeren uit een gegradueerde structuur door gebruik te maken van joins in de grade-structuur of door regrading-functors te identificeren.
Symmetrie en Cartesiaanse Structuur: De theorie wordt uitgebreid met symmetrische en cartesiaanse structuren, wat leidt tot een isomorfisme met Freyd-categorieën in de cartesiaanse setting.

5. Betekenis en Toekomstperspectief

Semantiek van Programmeertalen: Dit werk biedt een krachtig, uniform raamwerk voor de semantiek van talen met effecten, waarbij het mogelijk maakt om kwantitatieve beperkingen (zoals geheugen, tijd, beveiligingsniveaus) direct in de categorische structuur te integreren.
Verbinding met Separatie Logica: De gebruikte PCMs (zoals separation algebras) zijn fundamenteel in separation logic voor het verifiëren van programma's. Dit werk legt een brug tussen categorische semantiek en formele verificatiemethoden voor hulpbronbeheer.
Generalisatie: De auteurs suggereren dat dit raamwerk kan worden uitgebreid naar "partiële duoidale" gradaties, waarbij zowel sequentiële als monoidale compositie hun eigen gradatie-structuren hebben. Dit zou een gemeenschappelijke basis kunnen vormen voor verschillende bestaande theorieën over gegradueerde systemen.
Praktische Toepassing: Het model is direct toepasbaar op het modelleren van parallelle programma's die gedeelde resources gebruiken, waarbij de "undefinedness" van het monoidale product de onmogelijkheid van race conditions of resource-conflicten formaliseert.

Kortom, dit artikel introduceert een fundamentele uitbreiding van de categorische theorie die de beperkingen van traditionele monoidale en premonoidale categorieën overbrugt, en een wiskundig robuuste basis biedt voor het modelleren van complexe, resource-gevoelige softwaresystemen.