DisCoPy

DisCoPy is a Python toolkit for computing with string diagrams.

• Organisation: https://discopy.org
• Documentation: https://docs.discopy.org
• Source code: https://github.com/discopy/discopy
• Paper (for applied category theorists): https://doi.org/10.4204/EPTCS.333.13
• Paper (for quantum computer scientists): https://arxiv.org/abs/2205.05190

Features

• abstract base classes for Category, MonoidalCategory and their subclasses as classified in Selinger's Survey of graphical languages for monoidal categories (2009)
• a Diagram data structure for string diagrams in any (pre)monoidal category with methods for diagram composition, drawing, rewriting and Functor evaluation into:
  • Function, i.e. wires as types and boxes as functions with either disjoint union (python.additive) or tuples (python.multiplicative)
  • Tensor, i.e. wires as dimensions and boxes as arrays from NumPy, PyTorch, TensorFlow, TensorNetwork, JAX and Quimb
• an implementation of formal grammars (context-free, categorial, pregroup or dependency) with interfaces to lambeq, spaCy and NLTK
• an implementation of categorical quantum mechanics interfacing with:
  • tket for circuit compilation
  • PyZX for optimisation with the ZX calculus
• a Drawing data structure for labeled graphs embedded in the plane
• a Term data structure for lambda terms in the internal language of (bi)closed monoidal categories and their translation back and forth to diagrams
• a Hypergraph data structure for string diagrams in hypergraph categories and its restrictions to symmetric, traced, compact and Markov categories
• a combinantorial map data structure for string diagrams in compact categories and its restrictions to symmetric, (bi)closed and traced categories. The orientation on boxes can also help to enforce planarity.
• a Stream data structure, an implementation of monoidal streams as a category with delayed feedback
• the Int-construction, also called the geometry of interaction, i.e. the free tortile/compact closed category on a balanced/symmetric traced category

Quickstart

pip install discopy

If you want to see DisCoPy in action, you can check out the following notebooks:

• What is a diagram?
• QNLP Tutorial
• Geometry of Chatbot Interaction

Or you can keep scrolling down, skip the theory and go straight to the examples on cooking, natural language and a geometry of chatbot interaction.

Theory: categories, diagrams and gotchas

• discopy.abc describes the hierarchy of monoidal categories with extra structures
• each abstract base class is implemented by a concrete module e.g. discopy.monoidal implements the class Diagram of morphisms in the free MonoidalCategory generated by:
  1. Ob as generating objects and Ty as the free monoid over Ob with @ as product and Ty() as unit
  2. Box as generating morphisms each with a list of objects dom: Ty and cod: Ty as input and output.
• a monoidal Layer(*inside) is a tensor product of boxes and plumbing, represented by non-empty Ty, with at least one box and no adjacent plumbing; a symmetric layer also allows Permutation as plumbing and may consist of a single non-identity permutation; whiskering X @ f and f @ X adds more plumbing on either side
• a Diagram(inside, dom, cod) is a sequence of composable layers inside with a designated input dom and output cod: the identity diagram is the empty sequence with dom == cod, composition f >> g is sequence concatenation
• the tensor of diagrams is decomposed in terms of composition and whiskering i.e. f @ g = f @ g.dom >> f.cod @ g, this is biased in the sense that f happens before g so that diagrams really live in a premonoidal category
• the first gotcha of DisCoPy: Box is a subclass of Diagram with a cyclic reference list(box.inside) == [Layer(box)]
• every categorical structure is implemented with the factory method pattern so that e.g. the method Diagram.swap computes the symmetry of arbitrary types with Diagram.swap_factory = Swap as subroutine for generating subclasses of Box for the symmetry of atomic types
• the second gotcha of DisCoPy: each C: Category comes with a class attribute such that ; this happens with the decorator and it allows for e.g. the subclass to know that it lives inside a bigger category

Example: Cooking

This example is inspired from Pawel Sobocinski's blog post Crema di Mascarpone and Diagrammatic Reasoning.

from discopy.utils import factory
from discopy.symmetric import Ty, Box, Diagram, Permutation, Swap

@factory
class Ingredient(Ty):
  "The objects of the category of recipe diagrams."

@factory
class Recipe(Diagram):
  ob = Ingredient

class CookingStep(Box, Recipe):
  "A cooking step is a box in a recipe diagram."

class CookingPermutation(Permutation, CookingStep):
  "A permutation of ingredients."

class CookingSwap(CookingPermutation, Swap, CookingStep):
  "A cooking swap takes two ingredients `X @ Y` and gives `Y @ X`."

Recipe.swap_factory = CookingSwap  # Recipes need to know how to swap.
Recipe.permutation_factory = CookingPermutation

egg, white, yolk = Ingredient("egg"), Ingredient("white"), Ingredient("yolk")
crack = CookingStep("crack", egg, white @ yolk)
merge = lambda X: CookingStep("merge", X @ X, X)

# DisCoPy allows string diagrams to be defined as Python functions

@Recipe.from_callable(egg @ egg, white @ yolk)
def crack_two_eggs(x, y):
    (a, b), (c, d) = crack(x), crack(y)
    return (merge(white)(a, c), merge(yolk)(b, d))

# ... or in point-free style using parallel (@) and sequential (>>) composition

assert crack_two_eggs == (crack @ crack
  >> white @ CookingSwap(yolk, white) @ yolk
  >> merge(white) @ merge(yolk)).foliation()

crack_two_eggs.draw(doctest="docs/_static/readme/crack-eggs.svg")

By default, DisCoPy diagrams are made of layers with exactly one box in between some (possibly empty) list of wires on its left- and right-hand side. We can get more general diagrams by specifying the list of layers inside manually:

from discopy.monoidal import Equation
from discopy.symmetric import Layer

A, B, C, D = Ty(*"ABCD")
f, g = Box("f", A, B), Box("g", C, D)

left, right = f @ g.dom >> f.cod @ g, f.dom @ g >> f @ g.cod
middle = Diagram(inside=(Layer(f, g), ), dom=A @ C, cod=B @ D)

Equation(Equation(
  left, middle, symbol="$\\rightarrow$"), right, symbol="$\\leftarrow$").draw()

or by calling the method Diagram.foliation which will minimize the length of the diagram:

crack_two_eggs_at_once = crack_two_eggs.foliation()

empty = Ingredient()

assert crack_two_eggs_at_once == Recipe(
  dom=egg @ egg, cod=white @ yolk, inside=(
    Layer(crack, crack),
    Layer(white, CookingSwap(yolk, white), yolk),
    Layer(merge(white), merge(yolk))))

crack_two_eggs_at_once.draw(
  doctest="docs/_static/readme/crack-two-eggs-at-once.svg")

Theory: functors, terms, maps and hypergraphs

Functor is the main algorithm of DisCoPy, there is one for each module X in the hierarchy for the class of functors with domain given by the free X-category defined there. Functors can have arbitrary categories as codomain, by default they are endofunctors on the free X-category i.e. they send diagrams to diagrams by opening up boxes. When the codomain is a concrete category, functors can perform arbitrary computation e.g. discopy.matrix, discopy.python and discopy.drawing define instances of the MonoidalCategory abstract base class, i.e. even the diagram layout algorithm itself is a functor.

However in most applications outside of diagram layout, computing a for loop over a list of layers with every swap explicit is not the most elegant way to evaluate a diagram. DisCoPy has a number of alternative data structures that can encode different layers of the hierarchy in a faithful way:

• Term is a simply-typed lambda term in the internal language of monoidal closed categories, it can represent any diagram with a single output wire
• CMap is a combinatorial map encodes diagrams in any compact closed category as a permutation on the ports of each of its boxes
• Hypergraph encodes any diagram in a hypergraph category, i.e. with spiders (a.k.a. special commutative Frobenius algebras)

These come with methods for converting back and forth to diagrams which allow to e.g. simplify diagrams by removing redundant swaps and to check equality of diagrams up to the axioms of (symmetric, traced, compact, etc.) monoidal categories. They can also come with methods for evaluating them directly in a concrete category, e.g. a CMap with a Tensor on each node can be compiled directly to an Einstein notation without translating it to a list of layers.

Note that while Functor implements only functors with free categories as domain, DisCoPy also implements instances of 2-functors i.e. with categories of categories as domain. For instance, the Int-construction takes traced categories to compact categories and Stream takes monoidal categories to feedback categories, see

Example: Alice loves Bob

Snakes & Sentences

Wires can be bent using two special kinds of boxes: cups and caps, which satisfy the snake equations.

from discopy.rigid import Ty, Id, Cup, Cap, Equation

x = Ty('x')
left_snake = x @ Cap(x.r, x) >> Cup(x, x.r) @ x
right_snake =  Cap(x, x.l) @ x >> x @ Cup(x.l, x)
assert left_snake.normal_form() == Id(x) == right_snake.normal_form()

Equation(left_snake, Id(x), right_snake).draw(
  doctest="docs/_static/readme/typed-snake-equation.svg")

In particular, DisCoPy can draw the grammatical structure of natural language sentences encoded as reductions in a pregroup grammar. See Lambek, From Word To Sentence (2008) for an introduction.

from discopy.grammar.pregroup import Ty, Word, Cup

s, n = Ty('s'), Ty('n')  # sentence and noun
Alice, Bob = Word('Alice', n), Word('Bob', n)
loves = Word('loves', n.r @ s @ n.l)

sentence = Alice @ loves @ Bob >> Cup(n, n.r) @ s @ Cup(n.l, n)
sentence.foliation().draw(doctest="docs/_static/readme/alice-loves-bob.svg")

Many other grammatical frameworks can be encoded as diagrams, e.g. cfg (context-free), categorial and dependency grammars.

Functors & Rewrites

Monoidal functors compute the meaning of a diagram, given an interpretation for each wire and for each box. In particular, tensor-valued functors evaluate a diagram as a tensor network using numpy, PyTorch, TensorFlow, TensorNetwork or JAX.

Applied to pregroup diagrams, DisCoPy implements the categorical compositional distributional (DisCoCat) models of Clark, Coecke, Sadrzadeh (2008).

from discopy.grammar import pregroup
from discopy.tensor import Dim, Tensor

F = pregroup.Functor(
    ob_map={s: 1, n: 2},
    ar_map={Alice: [1, 0], loves: [[0, 1], [1, 0]], Bob: [0, 1]},
    cod=Tensor)

assert F(sentence)

Diagram-valued functors can fill each box with a complex diagram. The result can then be simplified using diagram.normalize() to remove the snakes, this is called autonomisation.

from discopy.grammar.pregroup import Cap, Box

def wiring(word):
    if word.cod == n:  # word is a noun
        return word
    if word.cod == n.r @ s @ n.l:  # word is a transitive verb
        box = Box(word.name, n @ n, s)
        return Cap(n.r, n) @ Cap(n, n.l) >> n.r @ box @ n.l

W = pregroup.Functor(ob_map={s: s, n: n}, ar_map=wiring)

rewrite_steps = W(sentence).normalize()
sentence.to_gif(
  *rewrite_steps, doctest="docs/_static/readme/autonomisation.gif",
  timestep=1000, figsize=(4, 4))

A geometry of chatbot interaction

The Int-construction of Joyal, Street & Verity (1996) is

a glorification of the construction of the integers from the natural numbers

i.e. the same we can pretend that a commutative monoid is a group so long as it is cancellative (i.e. a + x == b + x implies a == b) we can pretend that a monoidal category has cups and caps so long as it is traced, i.e. it has feedback loops:

Concretely, we get a compact category where the objects are given by pairs of objects in the traced category, morphisms are bidirectional processes with a positive and a negative direction. Composition given by symmetric feedback, i.e. tracing out the common boundary of the two processes so they can communicate along an infinity-shaped pair of wires between them:

We can use this geometry of interaction to interpret words as processes rather than states:

from discopy.interaction import Ty, Int
from discopy.compact import Ty as T, Diagram as D, Box, Equation

N, S = T('N'), T('S')
A, B = Box('A', N, N), Box('B', N, N)
L = Box('L', N @ S @ N, N @ S @ N)
swaps = D.permutation((2, 1, 0), N @ S @ N)
G = pregroup.Functor(
    ob_map={s: Ty[T](S, S), n: Ty[T](N, N)},
    ar_map={Alice: A, loves: swaps >> L, Bob: B},
    cod=Int(D))

ALB_trace = (A @ S @ B >> L).trace(left=True).trace(left=False).foliation()

assert Equation(G(sentence).inside, ALB_trace)

Equation(sentence.foliation(), ALB_trace, symbol="$\\mapsto$").draw()

Streams and delayed feedback

A key axiom of traced monoidal categories which allows to simplify diagrams is the yanking equation:

If we relax this assumption we get the concept of a feedback category where the objects come with a delay operation and the feedback loops have a more restricted shape:

Given a symmetric category, we can construct a feedback category of monoidal streams where the feedback operation is given by adding an internal state. We can use this to unroll our diagram of the previous section:

from discopy.stream import Ty, Stream

N, S = Ty("N"), Ty("S")
A, B = [Stream.sequence(f, N, N) for f in "AB"]
L = Stream.sequence('L', S.head @ N.delay() @ N.delay(), N @ N)
ALB = (L >> A @ B).feedback(dom=S.head, cod=Ty(), mem=N @ N)
ALB.unroll(2).now.foliation().draw()

References

If you use DisCoPy in the context of an academic publication, we suggest you cite:

• G. de Felice, A. Toumi & B. Coecke, DisCoPy: Monoidal Categories in Python, EPTCS 333, 2021, pp. 183-197, DOI: 10.4204/EPTCS.333.13

If furthermore your work is related to quantum computing, you can also cite:

• A. Toumi, G. de Felice & R. Yeung, DisCoPy for the quantum computer scientist, arXiv:2205.05190

If you use any of the recent features (e.g. Hypergraph) you could also mention:

• A. Toumi, R. Yeung, B. Poór & G. de Felice, DisCoPy: the Hierarchy of Graphical Languages in Python arXiv:2311.10608

Contribute

We're keen to welcome new contributors!

First, read the contributing guidelines then open an issue.