# 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`

.

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.

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.

# Bibliography

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.