Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: learning: questions

Topic: Choosing wires

keorn (May 03 2020 at 21:39):

Wiring diagrams are great at representing a sequence of actions (boxes from left to right) and actions being performed in parallel (boxes above each other). What would be the most natural way to represent performing one of multiple actions? One could think of a box which takes input wires and directs them to one of possible boxes, the output would be a coproduct of possible outputs. One way to represent this without a new box type is to choose output after performing all parallel actions, but this has wrong semantics.

This seems useful to represent recursion-free program execution.

Sam Tenka (May 03 2020 at 22:40):

Hi!

I think the "parallel dimensions" topic addresses this obliquely:
https://categorytheory.zulipchat.com/#narrow/stream/229199-learning.3A-basic.20questions/topic/parallel.20dimensions

There's also a way of thinking about flow charts in terms of coproducts --- see Remark 6.7 of Selinger's Survey of Graphical Languages for Monoidal Categories for an example with a while loop that has a branch similar to what you mention. Chapter 9 of the same deals with multiple monoidal operations at once, e.g. product and coproduct.

I think part of what you're saying when you say that performing a choice after all the parallel actions is that $+$ and $\times$ should only distribute one way in the category we're trying to construct: $A + (B \times C) \neq (A + B) \times (A + C)$. Depending on the situation, there is a whole range of possible ways we might want our two monoidal operations to interact. Perhaps it would be illuminating to specify exactly what sorts of distributivity axioms your intuition demands for the case at hand :slight_smile:

Fabrizio Genovese (May 03 2020 at 23:10):

keorn said:

Wiring diagrams are great at representing a sequence of actions (boxes from left to right) and actions being performed in parallel (boxes above each other). What would be the most natural way to represent performing one of multiple actions? One could think of a box which takes input wires and directs them to one of possible boxes, the output would be a coproduct of possible outputs. One way to represent this without a new box type is to choose output after performing all parallel actions, but this has wrong semantics.

This seems useful to represent recursion-free program execution.

As you said, choice can be represented with coproducts. Coproducts define a monoidal structure, so if your monoidal structure is a coproduct parallel wires will already represent choices. Moreover you get a monoid for free, meaning that you can always merge two wires with the same type into one: $A + A \to A$

Fabrizio Genovese (May 03 2020 at 23:11):

I guess what you want is representing choice _while_ already having another monoidal structure around. That is, you are already using parallel wires to represent something. In this case the underlying categorical structure you want is probably the one of a bimonoidal category, that is, a category with two monoidal structures that interact with each other.

Fabrizio Genovese (May 03 2020 at 23:13):

@Sam Tenka (naive student) already referenced some relevant discussion that have happened here before about this. In general, the idea is that a graphical calculus for cats with two monoidal structures should be thought of as 3-d diagrams, where lines can be parallel in a surface, and surfaces can be parallel with each other.

Fabrizio Genovese (May 03 2020 at 23:14):

The precise details of how to formalise this graphical calculus are a work in progres, and various people are working on some flavors of it,such as @Jules Hedges and @Antonin Delpeuch .

Antonin Delpeuch (May 04 2020 at 06:59):

yes we are on it! hopefully it should be written up soon :)

keorn (May 04 2020 at 07:40):

Thanks a lot for the pointers, looking forward to the writeup @Antonin Delpeuch . 3-d diagrams sound like a bit of a hassle though. Since each box can contain another wiring diagram in it, would it not be possible to simply have another box type where vertical axis is assumed to point into that 3rd dimension? (I know that would require a proper examination, but wondering if this sounds like the right intuition)

Antonin Delpeuch (May 04 2020 at 08:04):

Yes that sort of idea has been used before, although I cannot find the paper which does that anymore, perhaps @Jules Hedges or @Cole Comfort remember what it was? (the one which flattened 3D structure as thickened wires)

Jules Hedges (May 04 2020 at 09:54):

Backtracking to 2-dimensional case because my brain hasn't finished booting up yet: If you want to "promote" flowcharts into string diagrams, the usual start would be the category of finite sets and partial functions with $\otimes = +$. That admits a trace, where a particle goes around the loop repeatedly until it comes out, if ever. If you apply the Int construction then it no longer has to be strictly oriented, and then you pretty much have flowcharts. This is mostly in Abramsky's "retracing some paths in process algebra"

Jules Hedges (May 04 2020 at 09:55):

This is "particle style geometry of interaction", where "particle style" means you imagine a token moving around your string diagram, it can only be in one wire at a time, generally when $\otimes$ is a coproduct or kinda looks like one

Jalex Stark (May 04 2020 at 12:50):

In quantum computing, we tensor on an extra hilbert space and draw the choice as a unitary operation "controlled" by the extra factor

Cole Comfort (May 04 2020 at 13:57):

keorn said:

Thanks a lot for the pointers, looking forward to the writeup Antonin Delpeuch . 3-d diagrams sound like a bit of a hassle though. Since each box can contain another wiring diagram in it, would it not be possible to simply have another box type where vertical axis is assumed to point into that 3rd dimension? (I know that would require a proper examination, but wondering if this sounds like the right intuition)

Ross does this sort of flattening of the 2.5th dimension in his paper Generalised Proof-Nets for Compact Categories with Biproducts treating the coproduct as a bifunctorial box in the graphical calculus. This is what people are implicitly doing when they are summing over diagrams.

keorn (May 04 2020 at 19:42):

Cole Comfort said:

Ross does this sort of flattening of the 2.5th dimension in his paper Generalised Proof-Nets for Compact Categories with Biproducts treating the coproduct as a bifunctorial box in the graphical calculus. This is what people are implicitly doing when they are summing over diagrams.

Cheers, that paper looks spot on, let me digest it.

Jules Hedges (May 04 2020 at 21:35):

Antonin Delpeuch said:

yes we are on it! hopefully it should be written up soon :)

aaaaaaaa no time no time no time