yarrow

Yarrow is a library for representing large string diagrams: networks of operations with multiple inputs and outputs. Here’s a simple string diagram with two operations, summary and divide.

A diagram of an ETL process

Fig. 1 A diagram representing a simple program for computing the mean of a list of numbers.

Notice that the Count and Sum wires are crossed: the diagram represents Sum / Count and not Count / Sum. Think of operations as having an ordered list of input and output ports, in the same way a Python function has an ordered list of arguments.

Yarrow represents string diagrams using the Diagram datastructure (see yarrow.diagram). This datastructure can also be thought of as a kind of hypergraph - see Theory for more information.

Warning

Yarrow is still in early development. The API is not stable, and several features are not yet implemented. See the Roadmap for more information.

What yarrow is not

Yarrow is not a library for graph layout. A yarrow.diagram is not a picture; it is analogous to a graph or tree.

What yarrow is for

You can think of a yarrow.diagram as generalising syntax trees to syntax graphs. This is most useful when the primitive operations in an expression can have multiple outputs. Here are two examples.

Below is an electronic circuit implementing a 2-bit adder. It’s built from two 1-bit full-adders which both have two outputs: a sum and carry bit.

A 2-bit adder pictured as a string diagram

Fig. 2 A 2-bit adder pictured as a string diagram

Another example is neural network architectures. Below is a bilinear layer pictured as a string diagram.

A neural network bilinear layer pictured as a string diagram

Fig. 3 A neural network bilinear layer pictured as a string diagram

In both of these cases, the diagrams are completely formal mathematical objects. Specifically, a diagram is an arrows in a category (see Theory). Examples of categories for circuits and neural networks are described in [GKS23] and [WZ22], but you can use Yarrow without worrying about category theory at all.

Why yarrow instead of a directed graph?

A yarrow.diagram does extra bookkeeping that directed graphs do not. Try to represent the program in Fig. 1 as a DAG whose nodes represent operations:

A DAG

Information has been lost:

  1. Multiple edges between operations

  2. Which inputs connect to which outputs (only “dependency” structure remains)

  3. The “dangling wires” representing inputs/outputs to the whole diagram

yarrow.diagram keeps track of all of this information.

The Mathematics of Yarrow

The yarrow.diagram datastructure has a formal mathematical interpretation. Each Diagram is an arrow of the free symmetric monoidal category presented by a given signature. For a complete explanation, see the paper [WZ23] and the Theory section.

Contents:

Bibliography

[BGK+22]

Filippo Bonchi, Fabio Gadducci, Aleks Kissinger, Pawel Sobocinski, and Fabio Zanasi. String diagram rewrite theory i: rewriting with frobenius structure. 2022. arXiv:2012.01847.

[BGK+16]

Filippo Bonchi, Fabio Gadducci, Aleks Kissinger, Paweł Sobociński, and Fabio Zanasi. Rewriting modulo symmetric monoidal structure. In Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science. ACM, jul 2016. URL: https://doi.org/10.1145\%2F2933575.2935316, doi:10.1145/2933575.2935316.

[CCG+19]

Robin Cockett, Geoffrey Cruttwell, Jonathan Gallagher, Jean-Simon Pacaud Lemay, Benjamin MacAdam, Gordon Plotkin, and Dorette Pronk. Reverse derivative categories. 2019. arXiv:1910.07065.

[GKS23]

Dan R. Ghica, George Kaye, and David Sprunger. A compositional theory of digital circuits. 2023. arXiv:2201.10456.

[WZ22]

Paul Wilson and Fabio Zanasi. Categories of differentiable polynomial circuits for machine learning. 2022. arXiv:2203.06430.

[WZ23]

Paul Wilson and Fabio Zanasi. Data-parallel algorithms for string diagrams. 2023. arXiv:2305.01041.