Yarrow is a library for representing large
operations with multiple inputs and outputs.
Here’s a simple string diagram with two operations,
Notice that the
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
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.
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.
Another example is neural network architectures. Below is a 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:
Information has been lost:
Multiple edges between operations
Which inputs connect to which outputs (only “dependency” structure remains)
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.
Filippo Bonchi, Fabio Gadducci, Aleks Kissinger, Pawel Sobocinski, and Fabio Zanasi. String diagram rewrite theory i: rewriting with frobenius structure. 2022. arXiv:2012.01847.
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.
Robin Cockett, Geoffrey Cruttwell, Jonathan Gallagher, Jean-Simon Pacaud Lemay, Benjamin MacAdam, Gordon Plotkin, and Dorette Pronk. Reverse derivative categories. 2019. arXiv:1910.07065.
Dan R. Ghica, George Kaye, and David Sprunger. A compositional theory of digital circuits. 2023. arXiv:2201.10456.
Paul Wilson and Fabio Zanasi. Categories of differentiable polynomial circuits for machine learning. 2022. arXiv:2203.06430.
Paul Wilson and Fabio Zanasi. Data-parallel algorithms for string diagrams. 2023. arXiv:2305.01041.