Nested wiring diagrams via bicomodules

Research
1

I’ve been thinking for a while about how to do nested wiring diagrams in a way that is satisfying to me, and I think I finally have a mathematical story, which is not yet totally “nice”, but at least captures the essence of what I’m trying to do.

The basic idea is that recursive structures should be presented via an endo-bicomodule of a discrete category, and then the actual recursive structures are given by either the free monad or cofree comonad (depending on whether you want list-like or stream-like structures).

What is an endo-bicomodule of a discrete category? Suppose that the set of objects in the discrete category is A. Then an endo-bicomodule consists of a function from A to polynomials in the variables \{y_a | a \in A\}.

For wiring diagrams, the set we use is A = \mathbb{N}^2. Then the map is

(n,m) \mapsto \sum_{\substack{B \colon \mathsf{FinSet} \\ W \colon \mathsf{FinSet}}} \sum_{\substack{i \colon B \to \mathbb{N} \\ o \colon B \to \mathbb{N}}} \sum_{\substack{\mathrm{src} \colon W \to [n] + \sum_{b \in B} [o(b)] \\ \mathrm{tgt} \colon W \to [m] + \sum_{b \in B} [i(b)]}} \prod_{b \in B} y_{i(b),o(b)}

We use [n] to refer to \{1,\ldots,n\}, if n \in \mathbb{N}.

This might look like a horific polynomial, and it kind of is. But it’s not actually that bad, once you get over the fact that there’s so much going on in the sum.

A position of the polynomial consists of a set of boxes, a set of wires, a choice of number of inputs and number of outputs for each box, and then an assignment of source and target to each wire. The source of a wire is either a global input (element of [n]), or an output of a box (element of \sum_{b \in B} [o(b)]). Likewise, the target of a wire is either a global output (element of [m]), or an input of a box (element of \sum_{b \in B} [i(b)].

Then at each position, there is a “typed direction” for each box in the position, typed by the inputs and outputs of that box. This represents the hole to put another wiring diagram into, or alternatively some “machine” that you are composing with wiring diagrams.

The free monad on this endo-bicomodule then represents arbitrarily-nested wiring diagrams.

We can also apply this endo-bicomodule directly to a bicomodule from \mathbb{N}^2 y to \emptyset (which is just a \mathbb{N}^2-indexed collection of sets), and then we get the set of wiring diagrams where each box is filled with an appropriate element. An algebra of the operad of wiring diagrams is just an algebra for the parametric right adjoint functor \mathsf{Set}^{\mathbb{N}^2} \to \mathsf{Set}^{\mathbb{N}^2} corresponding to this bicomodule.

Exercises to the reader:

  • Use prolynomials to come up with a notion of morphism between this presentation of wiring diagrams, and then derive what the right morphisms between nested wiring diagrams are
  • Make a better way of writing down this bicomodule
  • Implement nested wiring diagrams based on this formalism in Julia and Scala, and send PRs to Catlab and Semagrams, respectively.