Compositional Structures for Systems Engineering and Design @ NIST

11/4/22

\[ \newcommand{\cat}[1]{\mathsf{#1}} \newcommand{\Set}{\mathsf{Set}} \newcommand{\Petri}{\mathsf{Petri}} \]

- Overview and aims
- Design themes
- Applications to scientific modeling

James Fairbanks

University of Florida

Angeline Aguinaldo

University of Maryland & Topos Institute

Andrew Baas

George Tech Research Institute

Kris Brown

Topos Institute

Evan Patterson

Topos Institute

Xiaoyan Li

University of Saskatchewan

Sophie Libkind

Stanford University & Topos Institute

Owen Lynch

Topos Institute

- a collaborative project to
*operationalize*applied category theory (ACT) - as a family of open source software packages written in Julia
- focused on technical computing for science and engineering

Present wave of ACT ongoing for 10+ years:

- SMCs and wiring diagrams
- Open systems via cospans
- Functorial semantics in science
- Categorical DBs and data migration

*Our aim is to operationalize this novel math as useful technology*:

- Implement CT abstractions as highly general software
- Instantiate these abstractions in specific scientific and engineering domains
- Interoperate between domains and applications, functorially

Image: Libkind, Baas, Patterson, Fairbanks 2021 (arxiv:2105.12282)

- Generic framework for ACT in Catlab.jl
- Web-based interactive tools in Semagrams.jl
- Builing on these, modeling frameworks for specific domains, such as
- epidemiology (Petri nets, stock flow diagrams)
- dynamical systems
- computational physics (simplicial sets, discrete exterior calculus)

Category theory gains computational content in three ways:

**Designing**programs and programming languages**Proving**theorems about categories and/or programs**Modeling**the world, computationally

Not mutually exclusive, but Catlab is mostly about #3.

CT in **progamming language theory**:

- Categorical concepts model the
*program*or*language* - Types/functions viewed as objects/morphisms in a category (think
`Hask`

)

CT as a **modeling language**:

- Categorical concepts model the
*subject-matter domain* - Implies nothing about the host programming language

Having a model-program “isomorphism” is nice when it works, but

- host type system imposes heavy constraints
- cost of extensibility is very high: have to write a new language!

We take a pragmatic approach to designing categorical software.

CT and categorical logic enrich the traditional **syntax-semantics** distinction, making both more flexible:

- Syntax is not relegated to meta-math but becomes part of math itself
- Semantics is then just a functor (“functorial semantics”)

In conventional progamming:

- syntax is defined by
- the host language
- sometimes by DSLs

- in either case, syntax is
**symbolic**, based on expression trees

In AlgebraicJulia:

- DSLs give a “frontend” for syntax, via
- Julia macros
- Semagrams graphical editor

- but underlying data is
**combinatorial**

Undirected wiring diagrams (UWDs) form an operad, a categorical gadget for hierarchical syntax.

Undirected wiring diagrams are a syntax for composing…

- Spans
- Data tables in a conjunctive query

- Structured cospans
- Open graphs
- Open Petri nets (
`AlgebraicPetri`

) - Open free diagrams in a category (
`Decapodes`

)

- Open dynamical systems via “resource sharing” (
`AlgebraicDynamics`

)

All of these algebras are implemented in AlgebraicJulia, with benefits arising from the shared abstraction.

Spivak 2013 (arXiv:1305.0297); Libkind, Baas, Patterson, Fairbanks 2021 (arxiv:2105.12282)

A very useful generic data structure is provided by:

- \(\cat{C}\)-sets, or copresheaves on a category \(\cat{C}\)
- more generally, attributed \(\cat{C}\)-sets or “acsets”

**Example**: UWDs are acsets on the following schema.

Spivak 2012 (arXiv:1009.1166); Patterson, Lynch, Fairbanks 2022 (arXiv:2106.04703)

Box | name |
---|---|

1 | R |

2 | S |

3 | T |

Port | box | junction |
---|---|---|

1 | 1 | 1 |

2 | 1 | 4 |

3 | 2 | 2 |

4 | 2 | 4 |

5 | 3 | 3 |

6 | 3 | 4 |

OuterPort | outer_junction |
---|---|

1 | 1 |

2 | 2 |

3 | 3 |

Junction | variable |
---|---|

1 | x |

2 | y |

3 | z |

4 | w |

The utility of \(\cat{C}\)-sets as an abstraction are the **operations** you can do on them:

- Limits
- Colimits
- Data migration
- using diagram categories, not Kan extensions

- Rule-based rewriting (AlgebraicRewriting.jl)
- using double pushout (DPO) rewriting and related methods

- Propositional logic of a topos

All of these are implemented in AlgebraicJulia.

Current areas of focus:

- epidemiology
- computational physics

Modern scientific models can be very complex, yet

- such complexity is not accidental
- but is the result of the combining and extending simpler models

This is by necessity, since scientific models are (still) created by humans!

So, on one hand:

Even very complicated models tend to have compositional structure, at least implicitly.

But, on the other hand:

Existing modeling tools tend to miss this structure entirely.

Model created in AnyLogic, courtesy of Nathaniel Osgood and Xiaoyan Li

A major aim of AlgebraicJulia is to enable building scientific models in an explicitly structured way.

In the **epidemiology** domain, using compartmental models based on

- Petri nets (AlgebraicPetri.jl)
- stock and flow diagrams (StockFlow.jl)

we have two main notions of composition:

- composition of open systems
- “just” colimits, in CT terms

- stratification, e.g., by demographic characteristics
- “just” limits, in CT terms

Libkind, Baas, Halter, Patterson, Fairbanks 2022 (arXiv:2203.16345)

**Code**: open Petri nets and composing Petri nets

- Stratification partitions a population into relevant subpopulations (demographics, location, etc)
- Products of Petri nets are not enough
- But products of typed Petri nets are:
- Products in slice category \(\Petri/P_{\textsf{type}}\)
- Equivalently, pullbacks in \(\Petri\)

Libkind, Baas, Halter, Patterson, Fairbanks 2022 (arXiv:2203.16345)

**Code**: Stratifying Petri nets

**Computational physics** has some challenges analogous to epidemiology:

- Complex models are needed, e.g., for engineering design
- “Multiphysics” models compose physics of distinct phenomena, e.g., reaction-diffusion-advection

But also its own unique challenges:

- Can involve complex geometric domains
- Unlike for ODEs, state-of-the-art for PDEs is to write bespoke solvers!

We’ve taken some first steps in applying ACT in this domain (work ongoing).

Maxwell’s equation become more “strongly typed” in exterior calculus:

Patterson, Baas, Hosgood, Fairbanks 2022 (arXiv:2204.01843)

- Formulate physics diagrammatically
- using exterior calculus
- composing different physical principles

- Define geometry (CombinatorialSpaces.jl)
- 2D semi-simplicial sets (\(\cat{C}\)-sets!)
- discrete exterior calculus (DEC) operators

- Generate simulator (Decapodes.jl)
- computation graph (directed wiring diagram)
- Julia code generation

Work in progress

**Resources**

- Blog: algebraicjulia.org/blog
- Code: github.com/AlgebraicJulia
- Papers & talks: algebraicjulia.org
- Chat:
`#catlab.jl`

stream on Julia Zulip

**Contributing**

We welcome new contributors at all levels of experience.

Please reach out if interested!