A tour of String Diagrams and Monoidal Categories

November 20, 2020

Goals

Show why Monoidal Categories are a good modeling tool for certain class of domains
Show how Monoidal Categories can be represented graphically via String Diagrams

References

Brendan Fong, David I. Spivak. An Invitation to Applied Category Theory: Seven Sketches in Compositionality
John C. Baez, Mike Stay. Physics, Topology, Logic and Computation: A Rosetta Stone
Bob Coecke, Aleks Kissinger. Picturing Quantum Processes: A First Course in Quantum Theory and Diagrammatic Reasoning
Aleks Kissinger. Pictures of Processes: Automated Graph Rewriting for Monoidal Categories and Applications to Quantum Computing

Part I: String Diagrams as Processes

Processes

Processes are everywhere in computing and mathematics:

Functions: sort: List[A] => List[A]
Mathematical functions: $f(x, y) = x^2 + y^2$
Matrices: $M = \begin{pmatrix} a & b & c \\ d & e & f \end{pmatrix}$
Real-world processes: Recipes (ingredients → dish), hardware connections (USB cord connecting a microphone to a computer)

A Process

A process can be visualized as a box with input and output wires:

         ┌───┐
    A ───┤ p ├─── B
         │   ├─── C
         └───┘
   input      output

The process p takes an input of type A and produces outputs of types B and C.

Processes as Diagrams

We can represent different kinds of processes as string diagrams:

Sorting function:

         ┌──────┐
List[A] ─┤ sort ├─ List[A]
         └──────┘

Mathematical function $x^2 + y^2$ :

    ℝ ─┐  ┌────────┐
       ├──┤ x²+y²  ├── ℝ
    ℝ ─┘  └────────┘

Cooking process:

  eggs ───┐  ┌─────────┐
butter ───┼──┤ cooking ├── omelette
cheese ───┘  └─────────┘

Matrix (3 columns → 2 rows):

         ┌─────────────┐
      3 ─┤ (a b c)     ├─ 2
         │ (d e f)     │
         └─────────────┘

Parallel Composition

Two processes can be composed in parallel using the tensor product $\otimes$ :

┌─────────────────┐     ┌─────────────────┐
│  A ─┐  ┌───┐    │     │  A ─┐  ┌───┐    │
│     ├──┤ x ├─ C │     │     ├──┤ x ├─ C │
│  B ─┘  └───┘    │     │  B ─┘  └───┘    │
│       ⊗         │  =  │                 │
│  D ───┬───┬─ E  │     │  D ───┬───┬─ E  │
│       │ y │     │     │       │ y │     │
└───────┴───┴─────┘     └───────┴───┴─────┘

Sequential Composition

Processes can be composed sequentially using >>>:

┌────────────────┐       ┌────────────────┐
│  A ─┬────┬─ B  │       │  B ───┬───┬─ E │
│     │ h1 │     │       │       │ g ├─ F │
│  C ─┼────┼─ D  │  >>>  │  D ───┴───┴    │
│     │ h2 │     │       │       │ f │    │
└─────┴────┴─────┘       └───────┴───┴────┘

                    =

┌──────────────────────────────────────────┐
│  A ─┬────┬────────────────┬───┬─ E       │
│     │ h1 │                │ g ├─ F       │
│  C ─┼────┼────────┬───┬───┴───┴          │
│     │ h2 │        │ f │                  │
└─────┴────┴────────┴───┴──────────────────┘

Complex Diagrams

Complex diagrams can be built by combining parallel and sequential composition:

  A ─┬───┬──────────────────────────────────────────────────────┐
     │ Δ ├──┬───┬───────┬────┬───────┬────┬───────┬─────┬──┬────┼──┬───┬─ B
     └───┘  │ Δ ├───┬───┤ p1 ├───┬───┤ p2 ├───┬───┤ p3  ├──┤fst │  │ t │
            └───┘   │   └────┘   │   └────┘   │   └─────┘  └────┤  └───┘
                    └───┬────┬───┘            │                 │
                        │ p5 ├────────────────┼─────┬────┬──────┘
                        └────┘                └─────┤ p6 │
                                                    └────┘

Process Theories

A "process theory" is an interpretation of a diagram in terms of a concrete class of processes.

In particular it provides an interpretation of wires, boxes, and composition operations of diagrams.

Examples of process theories:

Functions and sets
Linear maps and vector spaces
Matrices and natural numbers

Diagram Equations

Diagrams satisfy certain equations. For example, boxes can slide along wires:

┌───────────────┐       ┌───────────────┐
│    ┌─┐        │       │               │
│ ───┤f├──┐ ┌─┐ │       │ ┌─┐  ┌─┐      │
│    └─┘  └─┤g├─│   =   │ ┤g├──┤f├────  │
│         ┌─┤ ├─│       │ └─┘  └─┘      │
│ ────────┘ └─┘ │       │               │
└───────────────┘       └───────────────┘

And crossing wires can be "pulled apart":

┌─────────────────┐       ┌─────────────┐
│   ┌─┐           │       │     ┌─┐     │
│ ──┤f├──╲   ╱─── │       │  ───┤g├───  │
│   └─┘   ╲ ╱     │   =   │     └─┘     │
│         ╱ ╲     │       │     ┌─┐     │
│ ──┬─┬──╱   ╲─── │       │  ───┤f├───  │
│   │g│           │       │     └─┘     │
└───┴─┴───────────┘       └─────────────┘

Process Equations

Processes can satisfy domain-specific equations:

Idempotence of sort:

┌─────────────────────────────┐       ┌───────────────────┐
│ List[A] ──┬────┬──┬────┬─── │   =   │ List[A] ──┬────┬─ │
│           │sort│  │sort│    │       │           │sort│  │
└───────────┴────┴──┴────┴────┘       └───────────┴────┴──┘

Identity element for addition:

┌───────────────────┐       ┌─────────────┐
│        0          │       │             │
│   ───┬───┬─── m   │   =   │ ─── m ───   │
│      │ + │        │       │             │
│   ───┴───┴───     │       │             │
└───────────────────┘       └─────────────┘

Part II: String Diagrams as Monoidal Categories

Formalization

This diagrammatic language can be formalized by using category theory, specifically monoidal categories.

Plan

┌────────────┐     ┌────────────┐     ┌────────────┐     ┌────────────┐
│ Categories ├─────┤  Monoidal  ├─────┤ Cartesian  ├─────┤ Symmetric  │
│            │     │ Categories │     │  Monoidal  │     │  Monoidal  │
└────────────┘     └────────────┘     │ Categories │     │ Categories │
                                      └────────────┘     └────────────┘
     >>>               ⊗               (_, _)               ╲╱
                                                            ╱╲

1. Categories

A category consists of:

Objects: A, B, C, D, ...
Arrows (morphisms) between objects: $f: A \to B$
Composition: if $f: A \to B$ and $g: B \to C$ , then $g \circ f: A \to C$
Identity: for each object A, an identity morphism $1_A: A \to A$

As string diagrams:

A morphism $f: A \to B$ :

      ┌───┐
  A ──┤ f ├── B
      └───┘

The identity $1_A$ :

  A ───────── A   :=   A ──┬────┬── A
                          │ 1_A │
                          └────┘

Composition $g \circ f$ :

      ┌───┐   ┌───┐              ┌───┐       ┌───┐
  A ──┤ f ├───┤ g ├── C   :=   A─┤ f ├─B >>>─┤ g ├─C
      └───┘   └───┘              └───┘       └───┘

Category Equations

Left identity: $1_B \circ f = f$

  A ─────── >>> ─┬───┬─ B       ┌───┐
                │ f │       =   A──┤ f ├──B
                └───┘           └───┘

Right identity: $f \circ 1_A = f$

  ┌───┐               ┌───┐
A─┤ f ├─B >>> B───B = A──┤ f ├──B
  └───┘               └───┘

Associativity: $(h \circ g) \circ f = h \circ (g \circ f)$

  ┌───┐     ┌───┐          ┌───┐         ┌───┐     ┌───┐
(A┤ f ├B>>>B┤ g ├C)>>>C──┬─┤ h ├─D = A──┤ f ├──B>>>(B──┤ g ├C>>>C──┬─┤ h ├D)
  └───┘     └───┘        └─┴───┴         └───┘      └───┘        └─┴───┘

                            =

                      ┌───┐ ┌───┐ ┌───┐
                    A─┤ f ├─┤ g ├─┤ h ├─D
                      └───┘ └───┘ └───┘

Example: Matrices

Matrices form a category where:

Objects: natural numbers (representing dimensions)
Arrows $n \to m$ : matrices of size $m \times n$
Composition: matrix multiplication
Identity $1_n$ : identity matrix $I_n$

For a matrix $A$ with $n$ columns and $m$ rows:

$A = \begin{pmatrix} a_{11} & \cdots & a_{1n} \\ \vdots & \ddots & \vdots \\ a_{m1} & \cdots & a_{mn} \end{pmatrix}$

      ┌───┐
  n ──┤ A ├── m
      └───┘

Matrix multiplication $A \cdot B$ :

      ┌───┐   ┌───┐
  p ──┤ B ├───┤ A ├── m
      └───┘   └───┘

Identity matrix:

$I_n = \begin{pmatrix} 1 & \cdots & 0 \\ \vdots & \ddots & \vdots \\ 0 & \cdots & 1 \end{pmatrix}$

      ┌───┐
  n ──┤ I ├── n
      └───┘

2a. Strict Monoidal Categories

A strict monoidal category is a category with a monoid structure on the objects and arrows.

This means we have a parallel composition operation: an associative binary operation called the tensor product:

$\otimes : \mathcal{C} \times \mathcal{C} \to \mathcal{C}$

On objects:

┌───┐
│ A │     ┌───────┐     ┌───┐
├───┤  =  │ A ⊗ B │  =  │ A │
│ B │     └───────┘     │ B │
└───┘                   └───┘

On arrows:

┌─────────┐
│  A──f─B │     ┌─────────────┐     ┌─────────┐
│    ⊗    │  =  │A⊗C──f⊗g─B⊗D│  =  │  A──f─B │
│  C──g─D │     └─────────────┘     │  C──g─D │
└─────────┘                         └─────────┘

Unit object:

There is a neutral or unit object $I$ , with identity $1_I: I \to I$ .

A morphism $f: I \to B$ (from the unit):

      ┌───┐
      │ f ├── B
      └───┘

           ┌─────┐       ┌───┐
      ⊗    │     │   =   │ f │   =   ⊗   ┌───┐
           │  f  │       └───┘           │ f │
           │     │       ┌───┐           └───┘
           └─────┘       │ f │
                         └───┘

One More Law

The tensor product and composition satisfy an interchange law:

$(f_1 \mathbin{>\!\!>\!\!>} g_1) \otimes (f_2 \mathbin{>\!\!>\!\!>} g_2) = (f_1 \otimes f_2) \mathbin{>\!\!>\!\!>} (g_1 \otimes g_2)$

This says that it doesn't matter whether we first compose sequentially then in parallel, or first in parallel then sequentially:

┌─────────────────────┐
│  ───┬────┬───┬────┬─│
│     │ f₁ │   │ g₁ │ │
│  ───┼────┼───┼────┼─│
│     │ f₂ │   │ g₂ │ │
│  ───┴────┴───┴────┴─│
└─────────────────────┘

Matrices Again

Matrices form a monoidal category using the Kronecker product as parallel composition:

$A \otimes B = \begin{pmatrix} a_{11}B & \cdots & a_{1n}B \\ \vdots & \ddots & \vdots \\ a_{m1}B & \cdots & a_{mn}B \end{pmatrix}$

On objects it operates as multiplication of natural numbers
The number 0 is the unit $I$

      ┌─────┐
  qn ─┤A ⊗ B├─ pm
      └─────┘

2b. Monoidal Categories

In many cases it's not literally true that:

$(X \otimes Y) \otimes Z = X \otimes (Y \otimes Z)$

$I \otimes X = X = X \otimes I$

For example in Scala:

((x, y), z) ≠ (x, (y, z))

Instead we're forced to require isomorphisms:

Associator: $\alpha_{X,Y,Z} : (X \otimes Y) \otimes Z \xrightarrow{\sim} X \otimes (Y \otimes Z)$
Left unitor: $\lambda_X : I \otimes X \xrightarrow{\sim} X$
Right unitor: $\rho_X : X \otimes I \xrightarrow{\sim} X$

These must satisfy certain coherence laws (pentagon and triangle equations).

3. Cartesian Monoidal Categories

A Cartesian monoidal category has additional structure:

Projections - we can extract the first and second components:

  A ─┬─────┬─ A          A ─┬─────┬─ B
  B ─┤ fst │             B ─┤ snd │
     └─────┘                └─────┘

Diagonal - we can duplicate information:

      ┌───┐─ A
  A ──┤ Δ │
      └───┘─ A

Terminal morphism - we can discard information:

      ┌───┐
  A ──┤ ! │
      └───┘

4. Symmetric Monoidal Categories

A symmetric monoidal category has a swap operation:

  X ───╲   ╱─── Y          X ───┬──────┬─── Y
       ╲ ╱            :=        │ swap │
       ╱ ╲                      └──────┘
  Y ───╱   ╲─── X          Y ──────────── X

With inverse:

  Y ───╲   ╱─── X
       ╲ ╱
       ╱ ╲
  X ───╱   ╲─── Y

This representation is chosen so that:

  X ──╲   ╱──╲   ╱── X       X ───────────── X
      ╲ ╱    ╲ ╱
      ╱ ╲    ╱ ╲         =
  Y ──╱   ╲──╱   ╲── Y       Y ───────────── Y

Furthermore, the swap satisfies symmetry:

  X ──╲   ╱── X       X ───────────── X
      ╲ ╱
      ╱ ╲         =
  Y ──╱   ╲── Y       Y ───────────── Y

Circuit Diagrams

The diagrams we have discussed so far contain no loops. To be more precise, they are called circuit diagrams.

Feedback loops can be introduced via compact closed categories (which won't be discussed here).

Part III: String Diagrams in Scala

Airflow-like Process Manager

We can express complex process pipelines using a DSL:

val initial =
  Δ >>> (id ++ Δ) >>> assocL

val top = (id ++ p1) >>> p2 >>> p3 >>> fst >>> p4

val bottom = p5 >>> p6

val program = initial >>> (top ++ bottom) >>> t

This corresponds to the complex diagram:

  A ─┬───┬──────────────────────────────────────────────────────┐
     │ Δ ├──┬───┬───────┬────┬───────┬────┬───────┬─────┬──┬────┼──┬───┬─ B
     └───┘  │ Δ ├───┬───┤ p1 ├───┬───┤ p2 ├───┬───┤ p3  ├──┤fst │  │ t │
            └───┘   │   └────┘   │   └────┘   │   └─────┘  └────┤  └───┘
                    └───┬────┬───┘            │                 │
                        │ p5 ├────────────────┼─────┬────┬──────┘
                        └────┘                └─────┤ p6 │
                                                    └────┘

Tagless Process DSL

We can define a tagless final DSL for processes:

Category Structure

trait ProcessOpsDSL[Process[_, _]] {
  type >[A, B] = Process[A, B]
  type ~[B, A] = Process[A, B]

  def id[A]: A > A

  extension [A, B, C] (f: A > B)
    @alpha("andThen")
    def >>> (g: B > C): A > C

  extension [A, B, C] (g: B > C)
    @alpha("compose")
    def ◦ (f: A > B): A > C = f >>> g

Cartesian Structure

  def fst[A, B]: (A, B) > A
  def snd[A, B]: (A, B) > B

  extension [A, B, C] (f: A > B)
    @alpha("mergeInput")
    def &&& (g: A > C): A > (B, C)

  @alpha("duplicate")
  def Δ[A]: A > (A, A) = id[A] &&& id[A]

  // terminal object and monoidal unit
  type I = EmptyTuple

  def discard[A]: A > I

Monoidal Structure

  def assocR[X, Y, Z] : ((X, Y), Z) > (X, (Y, Z))
  def assocL[X, Y, Z] : ((X, Y), Z) ~ (X, (Y, Z))

  def injR[X]: X > (I, X)
  def injL[X]: X > (X, I)

  // tensor on objects: A ⊗ B = (A, B)
  // tensor on arrows: f ⊗ g = f ++ g
  extension [A1, A2, B1, B2] (f: A1 > B1)
    @alpha("combine")
    def ++ (g: A2 > B2): (A1, A2) > (B1, B2)

  def swap[X, Y]: (X, Y) > (Y, X)
  def swapInverse[X, Y]: (X, Y) ~ (Y, X)
}

Laws

The DSL must satisfy categorical laws:

Category Laws

@Law
def associativity[A, B, C, D](
  f: A > B,
  g: B > C,
  h: C > D
) =
  h ◦ (g ◦ f) ⟷ (h ◦ g) ◦ f

@Law
def identityL[A, B](f: A > B) =
  (id[B] ◦ f) ⟷ f

@Law
def identityR[A, B](f: A > B) =
  f ◦ id[A] ⟷ f

Tensor Laws

@Law
def tensorCompositionLaw[A1, A2, B1, B2, C1, C2](
  f1: A1 > B1, f2: A2 > B2,
  g1: B1 > C1, g2: B2 > C2,
) =
  (g1 ◦ f1) ++ (g2 ◦ f2) ⟷ (g1 ++ g2) ◦ (f1 ++ f2)

@Law
def tensorIdentityLaw[A, B] =
  id[A] ++ id[B] ⟷ id[(A, B)]

Monoidal Laws

@Law
def triangleEquation[X, Y] =
  assocR[X, I, Y] >>> (id[X] ++ snd[I, Y]) ⟷
  (fst[I, Y] ++ id[Y])

@Law
def pentagonEquation[W, X, Y, Z] =
  (assocR[W, X, Y] ++ id[Z]) >>>
  assocR[W, (X, Y), Z] >>>
  (id[W] ++ assocR[X, Y, Z]) ⟷
  (assocR[(W, X), Y, Z] >>> assocR[W, X, (Y, Z)])

Symmetric Monoidal Laws

@Law
def hexagonEquation1[X, Y, Z] =
  (assocL[X, Y, Z] >>> (swap[X, Y] ++ id[Z]) >>>
  assocR[Y, X, Z] >>> (id[Y] ++ swap[X, Z]) >>>
  assocL[Y, Z, X]) ⟷
  swap[X, (Y, Z)]

@Law
def symmetry[X, Y] =
  swap[X, Y] ⟷ swapInverse[Y, X]

ZIO Interpreter

We can interpret processes as ZIO effects:

given RIOProcessOps as ProcessDSLOps[RIO]:
  def id[A] = RIO.identity[A]

  @alpha("andThen")
  def [A, B, C] (f: RIO[A, B]) >>> (g: RIO[B, C]) = f andThen g

  def fst[A, B]: RIO[(A, B), A] = RIO.first
  def snd[A, B]: RIO[(A, B), B] = RIO.second

  @alpha("mergeInput")
  def [A, B, C] (f: RIO[A, B]) &&& (g: RIO[A, C]): RIO[A, (B, C)] = f &&& g

  def discard[A]: RIO[A, I] = RIO.succeed(EmptyTuple)

  def assocR[X, Y, Z]: ((X, Y), Z) > (X, (Y, Z)) =
    RIO.fromFunction { case ((x, y), z) => (x, (y, z)) }

  def assocL[X, Y, Z]: ((X, Y), Z) ~ (X, (Y, Z)) =
    RIO.fromFunction { case (x, (y, z)) => ((x, y), z) }

  def injR[X]: X > (I, X) = RIO.fromFunction { a => (EmptyTuple, a) }
  def injL[X]: X > (X, I) = RIO.fromFunction { a => (a, EmptyTuple) }

  @alpha("combine")
  def [A1, A2, B1, B2] (f: A1 > B1) ++ (g: A2 > B2): (A1, A2) > (B1, B2) =
    val left = fst >>> f
    val right = snd >>> g
    (left zipWithPar right) ((x, y) => (x, y))

  def swap[X, Y]: (X, Y) > (Y, X) = RIO.swap
  def swapInverse[X, Y]: (X, Y) ~ (Y, X) = RIO.swap

Where RIO[A,B] ≈ A => Either[Throwable, B].

Process DSL Architecture

The DSL is designed with multiple interpreters:

           ProcessDSLOps[⇝[_, _]]
                   │
         ┌─────────┴─────────┐
         │                   │
         ▼                   ▼
ProcessDSLOps[RIO]   ProcessDSLOps[PortGraph]
                             │
                     ┌───────┴───────┐
                     │               │
                     ▼               ▼
                 Graphviz           D3

Category of Port Graphs

Port graphs provide a concrete representation for string diagrams:

val graph1 =
  PortGraph(
    boxes = SeqMap(
      a -> (List("A"), List("B","C","D")),
      b -> (List("D","C","G"), List("Y","E","F")),
      c -> (List("B","Y"), List("Z")),
    ),
    incoming = List((a, 0), (b, 2)),
    inner = List(
      (a, 0) -> (c, 0),
      (a, 1) -> (b, 1),
      (a, 2) -> (b, 0),
      (b, 0) -> (c, 1),
    ),
    outgoing = List((c, 0), (b, 1), (b, 2))
  )

val graph2 = singleBox("x", List("Z", "E", "F"), List("W"))

val combined = graph1 andThen graph2

def render[B, P](pg: PortGraph[B, P]): graphviz.model.Graph = ???

This allows us to:

Compose graphs sequentially and in parallel
Render them visually using Graphviz or D3
Execute them as actual processes using the ZIO interpreter

Bibliography

Brendan Fong, David I. Spivak. Seven Sketches in Compositionality
John C. Baez, Mike Stay. Physics, Topology, Logic and Computation: A Rosetta Stone
Bob Coecke, Aleks Kissinger. Picturing Quantum Processes: A First Course in Quantum Theory and Diagrammatic Reasoning
Aleks Kissinger. Pictures of Processes