Composing open dynamical systems I: Directed composition

Composition of machines

Machines are dynamical systems which compose via directed communication. Informally, a machine consists of five component parts: - inputs - states - outputs - dynamics for evolution - a readout function

We will assume throughout this blog post that the evolution rule is an ODE with exogenous variables (also called a driven or forced ODE). Exogenous variables drive the dynamics but their values are determined elsewhere. For example, in the differential equation \dot r(t) = \alpha r(t) - \beta r(t)h(t), h is an exogenous variable which drives the system, while \alpha and \beta are (fixed) parameters. Following the informal defintion, we implement a machine as a struct below.

struct Machine{T}
    ninputs::Int
    nstates::Int
    noutputs::Int
    dynamics::Function
    readout::Function
end

nstates(m::Machine)  = m.nstates
ninputs(m::Machine)  = m.ninputs
noutputs(m::Machine) = m.noutputs

Following the general approach, we will first define a composition syntax. Here is our first set of rules for composing machines: for each machine (locally called the receiver), each input of that machine is wired to the output of a machine (locally called the sender). The sender transmits its output to the receiver which uses the information as input to its evolution function. In the special case where the sender and receiver are the same machine, the composition induces a feedback loop.

This composition syntax is captured by the category of single-input port graphs, which is defined by the schema \mathsf{Sch}(\mathsf{SIPortGraph}) below. \

A single-input port graph is a \mathsf{C}-set over \mathsf{Sch}(\mathsf{SIPortGraph}), i.e. a functor d: \mathsf{Sch}(\mathsf{SIPortGraph}) \to \mathsf{Set}. This composition pattern consists of 1. a set of boxes d(\textrm{Box}). 2. Every box b has a set of in-ports d(\operatorname{box_{in}})^{-1}(b) \subseteq d(P_{\textrm{in}}) and a set of out-ports d(\operatorname{box_{out}})^{-1}(b) \subseteq d(P_{\textrm{out}}). 3. Every in-port p \in d(P_{\textrm{in}}) is fed information by a unique out-port d(\operatorname{wire})(p) \in d(P_{\textrm{out}}).

Implemented in Catlab, we have:

using Catlab, Catlab.CategoricalAlgebra

@present SchSIPortGraph(FreeSchema) begin        
    Box::Ob
    InPort::Ob
    OutPort::Ob
    
    in_port_box::Hom(InPort, Box)
    out_port_box::Hom(OutPort, Box)
    wire::Hom(InPort, OutPort)
end

@abstract_acset_type AbstractSIPortGraph
@acset_type SIPortGraph(SchSIPortGraph,
  index=[:in_port_box, :out_port_box, :wire]) <: AbstractSIPortGraph

A machine may fill a box² of the composition pattern if 1. the number of in-ports of the box equals the number of inputs to the machine, and 2. the number of out-ports of the box equals the number of outputs of the machine.

The following method checks if a machine fills a chosen box of a composition pattern.

function fills(m::Machine, d::AbstractSIPortGraph, b::Int)
    b ≤ nparts(d, :Box) || error("Trying to fill box $b, when $d has fewer than $b boxes")
    
    return (ninputs(m) == length(incident(d, b, :in_port_box))) && (noutputs(m) == length(incident(d, b, :out_port_box)))
end

Now, given (1) a composition pattern and (2) a primitive machine filling each box, we can produce a new machine — the composite of the primitive machines — using the oapply method defined below. This composite machine has no inputs and no outputs. Its dynamics are induced by the driven dynamics of the primitive machines where the wires define how to set the inputs of each primitive machine.³ We think of information of type T flowing along the wires.

using  Catlab.CategoricalAlgebra.FinSets

function oapply(d::SIPortGraph, xs::Vector{Machine{T}}) where T  
    
    for box in parts(d, :Box)
        fills(xs[box], d, box) || error("$(xs[box]) does not fill box $box")
    end
    
    States = coproduct((FinSet∘nstates).(xs))
    Outputs = coproduct((FinSet∘noutputs).(xs))
    
    function internal_readout(u)
        readouts = zeros(length(apex(Outputs)))
        for box in parts(d, :Box)
            view(readouts, legs(Outputs)[box](:)) .= xs[box].readout(view(u, legs(States)[box](:)))
        end
        return readouts
    end
    
    function v(u,p,t)
        dotu = zero(u)
        readouts = internal_readout(u)
        for box in parts(d, :Box)
            inputs = view(readouts, subpart(d, incident(d, box, :in_port_box), :wire))
            vars = legs(States)[box](:)
            view(dotu, vars) .= xs[box].dynamics(view(u, vars), inputs, t)
        end
        return dotu
    end
    
    return Machine{T}(0, length(apex(States)), 0, v, x -> 0)
end

We check that the machines have the correct signature for the box it fills when we construct the total system, not when we run it. This validation allows modeling software to reject malformed models and gives dynamical systems modelers the advantages associated with static type checking.

α, β, γ, δ = 0.3, 0.015, 0.015, 0.7

dotr(x, p, t) = [α*x[1] - β*x[1]*p[1]]
dotf(x, p, t) = [γ*x[1]*p[1] - δ*x[1]]

# Define the primitive systems
rabbit = Machine{Float64}(1,1,1, dotr, x -> x)
fox    = Machine{Float64}(1,1,1, dotf, x -> x)

# Define the composition pattern
rabbitfox_pattern = SIPortGraph()
add_parts!(rabbitfox_pattern, :Box,     2)
add_parts!(rabbitfox_pattern, :OutPort, 2, out_port_box=[1,2])
add_parts!(rabbitfox_pattern, :InPort,  2, in_port_box=[1,2], wire=[2,1])

# Compose
rabbitfox_sys = oapply(rabbitfox_pattern, [rabbit, fox])

Composition patterns from graphs

The innovation of composing dynamical systems as machines alleviates some of the bookkeeping endemic to implementing a complicated ODE. However, the mappings of ports can still be quite intricate in a composition of machines with many variables, boxes, and wires. In this section, we use directed graphs to present composition patterns more succinctly.⁴

Recall the schema for graphs introduced in an earlier blog post:

We can transform an instance of Graph into an instance of SIPortGraph via pullback functorial data migration (see Appendix) induced by the functor \mathsf{Th(SIPortGraph)} \to \mathsf{Th(Graph)} defined on objects by - P_{\textrm{in}}\mapsto E, P_{\textrm{out}}\mapsto E - \textrm{Box}\mapsto V

and on morphisms by - \operatorname{wire}\mapsto \operatorname{id}(E) - \operatorname{box_{in}}\mapsto \operatorname{tgt} - \operatorname{box_{out}}\mapsto \operatorname{src}

Single-input port graphs induced by ordinary graphs are a restricted class of single-input port graphs. Generically, a single-input port graph allows out-port splitting, i.e. two distinct in-ports may be wired to a single out-port. This syntactic feature implements the copying of output data and is not available in the more restrictive composition syntax defined by the theory of graphs.

using Catlab.Graphs: SchGraph, Graph

ocean_graph = Graph(3)
add_parts!(ocean_graph, :E, 4, src=[1,2,2,3], tgt=[2,1,3,2])

using Catlab.Theories: id
E = SchGraph[:E]

# Define the composition pattern via data migration
ocean_pattern = SIPortGraph()
migrate!(ocean_pattern, ocean_graph, 
    Dict(:InPort => :E, :OutPort => :E, :Box => :V),
    Dict(:wire => id(E), :in_port_box => :tgt, :out_port_box => :src))

α, β, γ, δ, β′, γ′, δ′ = 0.3, 0.015, 0.015, 0.7, 0.017, 0.017, 0.35

dotfish(f, p, t) = [α*f[1] - β*p[1]*f[1]]
dotFISH(F, p, t) = [γ*p[1]*F[1] - δ*F[1] - β′*p[2]*F[1]]
dotsharks(s, p, t) = [-δ′*s[1] + γ′*s[1]*p[1]]

# Define the primitive systems
fish   = Machine{Float64}(1,1,1, dotfish,   f->f)
FISH   = Machine{Float64}(2,1,2, dotFISH,   F->[F[1], F[1]])
sharks = Machine{Float64}(1,1,1, dotsharks, s->s)

# Compose
ocean_sys = oapply(ocean_pattern, [fish, FISH, sharks])

The bigger picture

In this post, we discussed two theories of directed composition — \mathsf{Th(SIPortGraph)} and \mathsf{Th(Graph)} — which fit into the larger zoo of directed composition syntaxes.

The functors between these theories define contravariant transformations between composition patterns in different syntaxes. The previous section exemplified this process applied to the functor from \mathsf{Th(SIPortGraph)} to \mathsf{Th(Graph)}.

In the following subsections, we briefly describe the remaining theories of directed composition.

Port graphs and circular port graphs

Port graphs extend single-input port graphs by allowing in-ports to accept any number of incoming wires. In application, this means we can merge information (+) and generate trivial information (0). The schema for \mathsf{Sch}(\mathsf{PortGraph}) is below.

Concretely, every port graph consists of a set of boxes. Each box has set of in-ports and a set of out-ports. A port graph also has a set of wires which connect out-ports to in-ports.

Circular port graphs⁵ similarly consist of a set of boxes and a set of wires which connect ports, but they do not distinguish between in-ports and out-ports — a machine may both receive and emit information through any port. The functor from \mathsf{Th(PortGraph)} to \mathsf{Th(CPG)} turns circular port graphs into port graphs by duplicating every port with one copy interpretted as an in-port and the other as an out-port. Circular port graphs are particularly useful for modeling systems where the composition pattern is given by a network, such as a mesh of points in a reaction-diffusion model or a network of cities in a transportation grid. Such networks often arise in physics modeling.

Up next

In the next blog post of this series, we will investigate undirected theories for composition of dynamical systems as well as the strength of open composition syntaxes.

Appendix: Pullback Functorial Data Migration

f Let F: \mathsf{C} \to \mathsf{D} be a functor between categories \mathsf{C} and \mathsf{D}. Then F contravariantly induces a map from \mathsf{D}-sets to \mathsf{C}-sets by precomposition, which maps a \mathsf{D}-set X: \mathsf{D} \to \mathsf{Set}, to the \mathsf{C}-set F \operatorname{⨟}X : \mathsf{C} \to \mathsf{Set}. We call this transformation pulling back X along F. We saw an example of migrating the data of a half-edge graph to the data of a symmetric graph and vice versa⁶ in a previous post.