Wiring diagrams for Mealy machines

wiring diagrams
Author

Keri D’Angelo

Published

2024-08-19

Abstract

Operad algebras are a known tool for the composition of dynamical systems, but what happens when we have a machine where the output of the machine also depends on the input into it? In this post, we give background on how we want to extend the operad of directed wiring diagrams to the operad of dependent directed wiring diagrams, and then use this to be able to compose these kinds of machines.

Moore machines are a simple type of finite state machine. They consist of

(Shultz, Spivak, and Vasilakopoulou 2016) gives a framework for composing Moore machines using directed wiring diagrams. In a Moore machine, the input can only affect the output through the state. Some systems don’t function like this, though. For example, consider an elevator. In an elevator

If we tried to model an elevator as a Moore machine, then the output signal to move up or down depends only on the floor that the elevator is on. But that’s not how elevators work! The signal to move up or down depends both on the floor (i.e. its state) and on the button pressed (i.e. its input). For example, assume the current state of the elevator is open on floor 4 and you enter the elevator. When you enter, if you push 3, the elevator outputs a signal for it to move down; however, if you would have pushed floor 7 instead, the elevator would have outputted a signal for the elevator to move up.

This sort of machine — one in which the input can directly and instantaneously affect the output — is called a Mealy machine.

This summer, I’ve been working with Sophie to understand how to compose Mealy machines with wiring diagrams. In this post, we’ll explain how to upgrade directed wiring diagrams (DWDs) to dependent directed wiring diagrams (dDWDs) which will be the syntax for composing Mealy machines.

1 DWDs are a syntax for composing Moore machines

Operad algebras are blueprints for composition. An operad algebra consist of:

  • The operad, which we will denote \mathcal{O}, is the syntax for composition. For example when we’re composing dynamical systems, it describes the interface of the dynamical system and ways that the systems can interact.
  • The algebra is an operad functor F:\mathcal{O}\to \mathbf{Set} and gives the semantics of composition. For example, when we’re composing dynamical systems, it describes how the dynamics function and the action of composition.

Let’s start with an overview of the symmetric monoidal category of directed wiring diagrams (called \mathbf{DWD}) whose underlying operad is a syntax for composing Moore machines as described in (Libkind et al. 2021). Then in , we’ll extend \mathbf{DWD} to account for dependency between the inputs and outputs.

The objects of \mathbf{DWD} are interfaces to directed dynamical systems \binom{\mathsf{X}_{\mathsf{in}}}{\mathsf{X}_{\mathsf{out}}} as pictured below:

which has set of input ports \mathsf{X}_{\mathsf{in}} and set of output ports \mathsf{X}_{\mathsf{out}}. Morphisms f:\binom{\mathsf{X}_{\mathsf{in}}}{\mathsf{X}_{\mathsf{out}}}\to \binom{\mathsf{Y}_{\mathsf{in}}}{\mathsf{Y}_{\mathsf{out}}} in \mathbf{DWD} are diagrams of finite sets:

The maps s and t denote the source and target maps, and we call such a morphism a DWD. The figure below shows how to visualize a DWD. The wires in \mathsf{W}_{\mathsf{in}} go from \mathsf{Y}_{\mathsf{in}} to \mathsf{X}_{\mathsf{in}}, the wires in \mathsf{W} go from \mathsf{X}_{\mathsf{out}} to \mathsf{X}_{\mathsf{in}}, and the wires in \mathsf{W}_{\mathsf{out}} go from \mathsf{X}_{\mathsf{out}} to \mathsf{Y}_{\mathsf{out}}.

Then an operad algebra F: \mathbf{DWD}\to \mathbf{Set} on \mathbf{DWD} can then be defined on objects as: \begin{aligned} \binom{\mathsf{X}_{\mathsf{in}}}{\mathsf{X}_{\mathsf{out}}}\mapsto \Bigl\{\left(S, \binom{u}{r}: \binom{\mathbb{R}^S}{\mathbb{R}^S} \leftrightarrows \binom{\mathbb{R}^{\mathsf{X}_{\mathsf{in}}}}{\mathbb{R}^{\mathsf{X}_{\mathsf{out}}}}\right)\Bigr\} \end{aligned} where S is the set of state variables, the update function has type u: \mathbb{R}^S\times \mathbb{R}^{\mathsf{X}_{\mathsf{in}}} \to \mathbb{R}^S, and the readout function has type r: \mathbb{R}^S \to \mathbb{R}^{\mathsf{X}_{\mathsf{out}}}.

This algebra (fully defined in (Libkind et al. 2021)) turns out to be a lax monoidal functor and tells how to compose multiple dynamical systems.

2 A dependent DWD category

We’ll define our syntax for composing Mealy machines in two steps. First we’ll define a category \int \overline{\mathsf{W}} that consists of directed wiring diagrams that additionally keeps track of dependencies between inputs and outputs. Second, we’ll focus on a wide subcategory that removes cycles.

2.1 Grothendieck construction

Recall that the readout function type r: \mathbb{R}^S \to \mathbb{R}^{\mathsf{X}_{\mathsf{out}}} is not sufficient for our elevator example. For our elevator, we need our readout function to have the type r:\mathbb{R}^S\times \mathbb{R}^{\mathsf{X}_{\mathsf{in}}} \to \mathbb{R}^{\mathsf{X}_{\mathsf{out}}}, so the output is allowed to depend on the input into the machine, as well.

Our first question is: how do we extend the category \mathbf{DWD} to account for the dependency of outputs on inputs? For an object \binom{\mathsf{X}_{\mathsf{in}}}{\mathsf{X}_{\mathsf{out}}}, let’s think of a dependency as a span

where the map (s,t) \colon \mathsf{d_X} \to \mathsf{X}_{\mathsf{in}}\times \mathsf{X}_{\mathsf{out}} is injective. The elements of \mathsf{d_X} represent dependency wires from \mathsf{X}_{\mathsf{in}} to \mathsf{X}_{\mathsf{out}}. So the interface of a Mealy machine is of the form \left(\binom{\mathsf{X}_{\mathsf{in}}}{\mathsf{X}_{\mathsf{out}}}, \mathsf{d_X}\right). We picture this interface as the pair

The first element of the pair is the object \binom{\mathsf{X}_{\mathsf{in}}}{\mathsf{X}_{\mathsf{out}}}=\binom{1}{2}, and the second element of the pair is a dependency on \binom{1}{2}, where the left output port depends on the one input port and the right output port doesn’t depend on any input ports. These interfaces look like the objects in a Grothendieck construction of a functor out of \mathbf{DWD}.

Let’s define a functor \overline{\mathsf{W}}: \mathbf{DWD}\to \mathbf{Poset}. On objects it maps \binom{\mathsf{X}_{\mathsf{in}}}{\mathsf{X}_{\mathsf{out}}} to the set of all possible dependencies on \binom{\mathsf{X}_{\mathsf{in}}}{\mathsf{X}_{\mathsf{out}}}. This set \overline{\mathsf{W}}\binom{\mathsf{X}_{\mathsf{in}}}{\mathsf{X}_{\mathsf{out}}} has a poset structure given by inclusion.

For example, \overline{\mathsf{W}}\binom{1}{2} is the poset:

We can now already see how the interface in the figure above is an object of \int \overline{\mathsf{W}}.

On morphisms f: \binom{\mathsf{X}_{\mathsf{in}}}{\mathsf{X}_{\mathsf{out}}}\to \binom{\mathsf{Y}_{\mathsf{in}}}{\mathsf{Y}_{\mathsf{out}}} in \mathbf{DWD}, we will define a functor of posets \overline{\mathsf{W}}(f) : \overline{\mathsf{W}}\binom{\mathsf{X}_{\mathsf{in}}}{\mathsf{X}_{\mathsf{out}}}\to \overline{\mathsf{W}}\binom{\mathsf{Y}_{\mathsf{in}}}{\mathsf{Y}_{\mathsf{out}}}. This functor can be defined using pullbacks. Let \mathsf{d_X}\in \overline{\mathsf{W}}(X). First, consider the set \begin{aligned} & \mathsf{W}_{\mathsf{in}}\times_{\mathsf{X}_{\mathsf{in}}}\mathsf{d_X}\times_{\mathsf{X}_{\mathsf{out}}}\times \mathsf{W}_{\mathsf{out}} \\&+ (\mathsf{W}_{\mathsf{in}}\times_{\mathsf{X}_{\mathsf{in}}}\mathsf{d_X}\times_{\mathsf{X}_{\mathsf{out}}}W\times_{\mathsf{X}_{\mathsf{in}}}\mathsf{d_X}\times_{\mathsf{X}_{\mathsf{out}}}\mathsf{W}_{\mathsf{out}}) + \cdot\cdot\cdot \\&+(\mathsf{W}_{\mathsf{in}}\times_{\mathsf{X}_{\mathsf{in}}}(\mathsf{d_X}\times_{\mathsf{X}_{\mathsf{out}}}\mathsf{W})^n\times_{\mathsf{X}_{\mathsf{in}}}\mathsf{d_X} \times_{\mathsf{X}_{\mathsf{out}}}\mathsf{W}_{\mathsf{out}}) \end{aligned}

where n=|\mathsf{X}_{\mathsf{in}}+ \mathsf{X}_{\mathsf{out}}|. For example, an element of this set consists of an input wire followed by a dependency followed by looping wire followed by another dependency followed by an output wire. These represent ways that information can flow from \mathsf{Y}_{\mathsf{in}} to \mathsf{Y}_{\mathsf{out}} via the wires of f and the dependencies \mathsf{d_X}. Once n > |\mathsf{X}_{\mathsf{out}}+ \mathsf{X}_{\mathsf{in}}|, we must have a cycle, and therefore, will just give duplicates of existing relations between \mathsf{Y}_{\mathsf{in}} and \mathsf{Y}_{\mathsf{out}}. Second, if there are multiple dependent wires between the same input port in \mathsf{Y}_{\mathsf{in}} and output port in \mathsf{Y}_{\mathsf{out}} we’ll squash them to a single dependency. Therefore, we end up with a relation between \mathsf{Y}_{\mathsf{in}} and \mathsf{Y}_{\mathsf{out}} which we’ll call \overline{\mathsf{W}}(f)(\mathsf{d_X}).

Let’s consider an example in the picture below:

Dependencies in \binom{\mathsf{Y}_{\mathsf{in}}}{\mathsf{Y}_{\mathsf{out}}} from the first input port to the first output port, and the second input port to the third output port, are by paths in \mathsf{W}_{\mathsf{in}}\times_{\mathsf{X}_{\mathsf{in}}} \mathsf{d_X} \times_{\mathsf{X}_{\mathsf{out}}} \mathsf{W}_{\mathsf{out}}.The dependency from the first input port to the third output port by taking a path in \mathsf{W}_{\mathsf{in}}\times_{\mathsf{X}_{\mathsf{in}}} \mathsf{d_X} \times_{\mathsf{X}_{\mathsf{out}}} \mathsf{W}\times_{\mathsf{X}_{\mathsf{in}}} \mathsf{d_X} \times_{\mathsf{X}_{\mathsf{out}}} \mathsf{W}_{\mathsf{out}}.

Dependencies in \binom{\mathsf{Y}_{\mathsf{in}}}{\mathsf{Y}_{\mathsf{out}}} from the first input port to the first output port, and the second input port to the third output port, are by paths in \mathsf{W}_{\mathsf{in}}\times_{\mathsf{X}_{\mathsf{in}}} \mathsf{d_X} \times_{\mathsf{X}_{\mathsf{out}}} \mathsf{W}_{\mathsf{out}}.The dependency from the first input port to the third output port by taking a path in \mathsf{W}_{\mathsf{in}}\times_{\mathsf{X}_{\mathsf{in}}} \mathsf{d_X} \times_{\mathsf{X}_{\mathsf{out}}} \mathsf{W}\times_{\mathsf{X}_{\mathsf{in}}} \mathsf{d_X} \times_{\mathsf{X}_{\mathsf{out}}} \mathsf{W}_{\mathsf{out}}.

Now that we have our functor, we can take the Grothendieck construction of \overline{\mathsf{W}}, which we will denote by the usual notation \int \overline{\mathsf{W}}. Objects of \int \overline{\mathsf{W}} look like \left( \binom{\mathsf{X}_{\mathsf{in}}}{\mathsf{X}_{\mathsf{out}}}, \mathsf{d_X}\right), and morphisms are pairs (f,\leq): \left(\binom{\mathsf{X}_{\mathsf{in}}}{\mathsf{X}_{\mathsf{out}}}, \mathsf{d_X}\right) \to \left(\binom{\mathsf{Y}_{\mathsf{in}}}{\mathsf{Y}_{\mathsf{out}}}, \mathsf{d_Y}\right) where f: \binom{\mathsf{X}_{\mathsf{in}}}{\mathsf{X}_{\mathsf{out}}}\to \binom{\mathsf{Y}_{\mathsf{in}}}{\mathsf{Y}_{\mathsf{out}}} is a morphism in \mathbf{DWD}, and \overline{\mathsf{W}}(f)(\mathsf{d_X}) \leq \mathsf{d_Y} in the poset \overline{\mathsf{W}}\binom{\mathsf{Y}_{\mathsf{in}}}{\mathsf{Y}_{\mathsf{out}}}.

2.2 But what about loops?

If we try to use the morphisms of \int \overline{\mathsf{W}} to compose Mealy machines, we run into the following problem. Consider the composite of Mealy machines below.

The Mealy machine in the first box takes both an input a and a state x_t, and outputs ax_t^2 and updates the state to a + x_t. The Mealy machine in the second box takes both an input b and a state y_t, and outputs b+y_t and updates the state to by_t.

In this example, we end up with a loop leaving our system unsolvable. To get the output of the top box in the picture, namely, ax_t^2, we need the input a. How do we get the input a? Well, we need the output of the bottom box y_t+b, which depends on the input b. How do we get the input b? Well, we need the output of the top box, ax_t^2. And we end up in a loop we cannot escape. Therefore, \int \overline{\mathsf{W}} is not quite the right category we want, but we are close!

2.3 The wide subcategory dDWD

To make sure we never get a loop, we want to remove any morphisms in \int \overline{\mathsf{W}} that will cause this problem. Therefore, we want to restrict our focus to a subcategory of \int \overline{\mathsf{W}} that keeps all objects \left(\binom{\mathsf{X}_{\mathsf{in}}}{\mathsf{X}_{\mathsf{out}}}, \mathsf{d_X}\right) from \int \overline{\mathsf{W}} and removes some of the morphisms.

To see how such a dependent loop can form, consider the following picture.

In the dependency \mathsf{d_X}, the left output port depends on the left input port (pictured by a blue line). Moreover, f:\binom{\mathsf{X}_{\mathsf{in}}}{\mathsf{X}_{\mathsf{out}}}\to \binom{\mathsf{Y}_{\mathsf{in}}}{\mathsf{Y}_{\mathsf{out}}} gives a looping wire from the left output port to the left input port. Therefore, this becomes a dependency loop, where the output depends on the input which depends on the output, and so on.

So in our subcategory of \int \overline{\mathsf{W}}, we will remove the morphisms (f, \leq): \left(\binom{\mathsf{X}_{\mathsf{in}}}{\mathsf{X}_{\mathsf{out}}}, \mathsf{d_X}\right) \to \left(\binom{\mathsf{Y}_{\mathsf{in}}}{\mathsf{Y}_{\mathsf{out}}}, \mathsf{d_Y}\right) where the looping wires of f and the dependencies \mathsf{d_X} form cycles. By some fun algebraic manipulations, we can show if (f,\leq): \left(\binom{\mathsf{X}_{\mathsf{in}}}{\mathsf{X}_{\mathsf{out}}}, \mathsf{d_X}\right) \to \left(\binom{\mathsf{Y}_{\mathsf{in}}}{\mathsf{Y}_{\mathsf{out}}}, \mathsf{d_Y}\right) is acyclic, and (g, \leq) : \left(\binom{\mathsf{Y}_{\mathsf{in}}}{\mathsf{Y}_{\mathsf{out}}}, \mathsf{d_Y}\right) \to \left(\binom{\mathsf{Z}_{\mathsf{in}}}{\mathsf{Z}_{\mathsf{out}}}, \mathsf{d_Z}\right) is acyclic, then (g,\leq)\circ (f, \leq) is acyclic, and therefore, these morphisms form a category. We call this category \mathbf{dDWD} for dependent directed wiring diagrams.

We now have everything we need to set up our operad algebra of Mealy machines F: \mathbf{dDWD}\to \mathbf{Set}!

References

Libkind, Sophie, Andrew Baas, Evan Patterson, and James Fairbanks. 2021. “Operadic Modeling of Dynamical Systems: Mathematics and Computation.” https://arxiv.org/abs/2105.12282.
Shultz, Patrick, David I. Spivak, and Christina Vasilakopoulou. 2016. “Dynamical Systems and Sheaves.” Applied Categorical Structures 28.
Leaving a comment will set a cookie in your browser. For more information, see our cookies policy.