Nested wiring diagrams in Semagrams

Owen Lynch

Topos Institute

Spencer Breiner

NIST

July 31, 2023

Prelude: generalized geometric realization

• Let \(\mathsf{Top}\) be a good category of spaces
• Fix a small category \(C\). Call functors \(C \to \mathsf{Set}\) C-sets.
• Let \(\mathrm{Shp} \colon C^\mathrm{op} \to \mathsf{Top}\) be any functor
• Then let \(\mathrm{Shp}^\ast \colon \mathsf{Set}^C \to \mathsf{Top}\) be the left Kan extension of \(\mathrm{Shp}\) along the Yoneda embedding.

\[ \mathrm{Shp}^\ast(F) = \int^{x \in C} F(c) \times \mathrm{Shp}(c) \]

Example: geometric realization of graphs

Let \(C\) be the following small category

\(\mathsf{Set}^C\) is the category of graphs.

Define \(\mathrm{Shp} \colon C^\mathrm{op} \to \mathsf{Top}\) by

\[ E \mapsto [0,1], V \mapsto \ast \] \[ \mathrm{src} \mapsto (\{0\} \subset [0,1]), \mathrm{tgt} \mapsto (\{1\} \subset [0,1]) \]

Figure 1: Peterson graph

Semagrams

• What if all you needed to do to create a graphical editor for C-sets was to specify \(\mathrm{Shp}\)?

• This was the original dream of Semagrams, 2.5 years ago.

• Turns out, not so simple.

What are the hard bits?

• Layout, because geometry ≠ topology
• Mutation
• Interactivity
• Domain-specific UI
• Overlap
• Communication with AlgebraicJulia
• Text
• Getting the little details right
• Style
• Recursive/nested structure

Designing semagrams is hard… but reimplementing these things from scratch for everything we want edit graphically would also be hard

Semagrams History

Semagrams Legacy

• Typescript application; config on the fly via data
• Restricted to three types of graphical entity: boxes, ports, wires
• Virtual dom UI library (mithril, a lightweight React)
• Mutable, non-generic acset data structure for just boxes, ports, wires
• Explicit state machines for interaction

Semagrams (current version)

• Scala.js library; config at compile-time via code
• Generic interface for custom shapes
• FRP library with no virtual dom: Laminar
• Persistent, generic acset data structure (undo/redo for free!)
• Interactivity via an asynchronous monad: cats-effect

Semagrams architecture

Figure 2: Communication architecture of Semagrams

Petri nets

demo

• Petri net editor mostly uses generic functionality
• Rate equation live display is custom

Petri nets keybindings

bindings = Seq(
  keyDown("s").andThen(a.addAtMouse_(S)),
  keyDown("t").andThen(a.addAtMouse_(T)),
  keyDown("d").andThen(a.del),
  keyDown("E")
    .withMods(KeyModifier.Shift)
    .andThen(a.importExport),
  keyDown("z")
    .withMods(KeyModifier.Ctrl)
    .andThen(IO(g.undo())),
  keyDown("Z")
    .withMods(KeyModifier.Ctrl, KeyModifier.Shift)
    .andThen(IO(g.redo())),
  keyDown("x").andThen(a.importExport),
  // ...
)

Petri nets display

//...
lg <- IO(
  g.signal.map(assignBends(Map(I -> (IS, IT), O -> (OT, OS)), 0.5))
)
_ <- es.makeViewport(
  es.MainViewport,
  lg,
  Seq(
    ACSetEntitySource(S, BasicDisc(es)),
    ACSetEntitySource(T, BasicRect(es)),
    ACSetEdgeSource(I, IS, IT, BasicArrow()(es)),
    ACSetEdgeSource(O, OT, OS, BasicArrow()(es))
  )
)
ui <- es.makeUI()
_ <- ui.addHtmlEntity(
  EquationWindow(),
  () =>
    PositionWrapper(Position.botMid(15), massActionTypeset(g.signal))
)
//...

Generalized dragging code

def drag[Memo, Return](
    start: (z: Complex) => IO[Memo],
    during: (Memo, Complex) => Unit,
    after: Memo => IO[Return]
): IO[Return] = for {
  _ <- IO(m.save())
  _ <- IO(m.unrecord())
  m0 = m.now()
  memo <- es.mousePos.flatMap(start)
  ret <- (es.drag.drag(Observer(p => during(memo, p))) >> after(memo))
    .onCancelOrError(IO({
      m.set(m0)
      es.drag.$state.set(None)
    }).flatMap(_ => die))
  _ <- IO(m.record())
} yield ret

Nested wiring diagrams

Figure 3: An example nested wiring diagram

• With operads of wiring diagrams, don’t actually want to collapse
• Keeping around the nested structure helps organize large systems

demo

Nested wiring diagrams via free monads

• Consider the category \(\mathsf{Flng} = \mathsf{Set}^{\mathbb{N}^2}\).
• Interpretation of \(F \in \mathsf{Flng}\) is a functor that sends \((n,m)\) to a set of things that one might put in a box with \(n\) input ports and \(m\) output ports: a collections of “fillings”.
• Directed wiring diagrams are an endofunctor \(\mathrm{DWD}\) on \(\mathsf{Flng}\)

\[ \mathrm{DWD}(F)(n,m) = \sum_{w, b : \mathbb{N}} \sum_{i, o: [b] \to \mathbb{N}} \sum_{\substack{\mathrm{src} \colon [w] \to [n] + \sum_{x : [b]} [o(x)] \\ \mathrm{tgt} \colon [w] \to [m] + \sum_{x : [b]} [i(x)]}} \prod_{x : [b]} F(i(x), o(x))\]

• Note that this is a multivariate polynomial functor, i.e. a endobicomodule on the discrete comonoid on \(\mathbb{N}^2\)
• Nested wiring diagrams with primitive boxes given by \(F \in \mathsf{Flng}\) are elements of \(\mathrm{Free}(\mathrm{DWD})(F)\), where \(\mathrm{Free}(\mathrm{DWD})\) is the free monad on \(\mathrm{DWD}\) (which exists because \(\mathrm{DWD}\) is finitary).
• Open question: how do we generalize this? What is the right notion of “schema” for something like this?

Future work

• Embedding Semagrams in a larger program
• Formalizing better what nested acsets are
• Stabilizing APIs
• Making things more type-safe
• Test suite! (because of functional architecture, we can decouple logic from having to run in browser)
• Interop with backend, version control