Example schema

This schema (with objects: Wolf, Sheep, Edge, Vertex, and attribute types: Dir and \mathbb{N}) characterizes states of the world where there are wolves and sheep moving around a directed graph.³ These animals have a position, direction, as well as an energy level. Furthermore, the vertices have grass growing which is also represented by an energy level (let grass=0 mean the grass is ready to eat, while grass=n means there are n days left for the grass to grow). The legend on the right shows how we informally represent instances of this schema, although for simplicity we neglect to visually depict the direction of edges or animals. Using Catlab.jl, we can define this schema:

using Catlab, AlgebraicRewriting
@present SchLV <: SchGraph begin
  (Sheep,Wolf)::Ob
  spos::Hom(Sheep, V); wpos::Hom(Wolf, V)

  (Dir,Eng)::AttrType
  grass::Attr(V, Eng)
  seng::Attr(Sheep, Eng); weng::Attr(Wolf, Eng)
  dir::Attr(E, Dir)
  sdir::Attr(Sheep, Dir); wdir::Attr(Wolf, Dir)
end;

@acset_type LV_Generic(SchLV) # Dir and Eng are abstract
const LV = LV_Generic{Symbol, Int} # Dir is a Symbol, Eng is an Int
const yLV = yoneda_cache(LV) # precompute the 'generic' sheep/wolf/grass etc.

Rewrite rules: primitives for data manipulation

Rewrite rules are good candidates for simple S \rightarrow S building blocks, as they can express interesting dynamics while nevertheless being easier objects to work with than general purpose code.⁴ This has the data a partial map L\nrightarrow R which says, for any pattern match of L into one’s world of interest, a possible way for the world to update is to replace L with R. For example, the below rule says that, if a wolf and sheep are in the same location, the wolf can eat the sheep and gain its energy units.

Or, in code:

# pattern we're looking for: wolf + sheep on the same V
L = @acset_colim yLV begin  s::Sheep; w::Wolf; spos(s)==wpos(w) end
# what we're replacing with: just a wolf
R = @acset_colim yLV begin w::Wolf end
# Get the ID's of the relevant energy variables
L_wolf, L_sheep, R_wolf = [only(x).val for x in [L[:weng], L[:seng], R[:weng]]]
# Combine into a rule: L <- R -> R
wolf_eat = Rule(homomorphism(R,L), id(R); 
                expr=(Eng=Dict(R_wolf => engs -> engs[L_wolf]+engs[L_sheep]),))

As another rule, consider two sheep which reproduce if the vertex they share is grassy, unless there is a wolf within striking distance. We can add to the data of a rewrite rule a Negative Application Condition (NAC) which embeds the matched pattern L into a forbidden pattern N with the implied semantics of: the rule cannot be applied to a given pattern L if N also matches.

Or, in code:

# Pattern we're looking for: sheep + sheep on green grass (i.e. grass = 0)
L = @acset_colim yLV begin 
  (s1,s2)::Sheep; 
  spos(s1) == spos(s2); grass(spos(s1)) == 0 
end 
# Replacing with: new sheep facing North @ 5 eng
R = @acset_colim yLV begin 
  (s1,s2,s3)::Sheep; 
  spos(s1) == spos(s2); grass(spos(s1)) == 0 
  spos(s2) == spos(s3); seng(s3) == 5; sdir(s3) == :N
end 
# Negative application condition
N = @acset_colim yLV begin 
  (s1,s2)::Sheep; w::Wolf; e::E
  spos(s1) == spos(s2); grass(spos(s1)) == 0 
  src(e) == wpos(w); tgt(e) == spos(s1)
end 
NAC = AppCond(homomorphism(L, N; monic=true), false)

# Overall rule
sheep_reprod = Rule(id(L), homomorphism(L,R; monic=true), ac=[NAC])

Rewrite rules are nifty ways of expressing some basic data operations (merging, copying, deleting, adding) and basic logic in a graphical / combinatorial way, i.e. requiring only data rather than general purpose code. But one quickly hits limits in expressivity for what can be accomplished by a single rewrite rule, and there remains the problem of how one structures the execution of many rewrite rules in an organized fashion.

Wiring diagram syntax and control flow boxes

If we view the rewrite rule as system that can be entered and exited in various ways, we might draw it like this:

During a simulation, we imagine that the ‘world state’ moves along wires in a diagram like above and is possibly altered by the boxes it passes through. For a deterministic simulation, after entering a box, we will then exit exactly one of the box’s outwires. Although the above box is an example of something that can alter the world state living on the wire, it has no internal state itself. In contrast, we can consider control flow boxes which cannot affect the state of the world yet can have their own state and choose which outwire to exit through as a function of their internal state and the world state.

For example, we can make a repeat3 box which sends the world out the first wire the first three times it run, and subsequently outputs on its second wire. Another box, coin, flips a pseudorandom coin to decide where its output goes. The following diagram communicates a program which first flips a coin, and (if heads) it attempts three times to apply the Reprod rule, ending immediately if at any point it is successfully applied.

There are many tools at our disposal to construct wiring diagrams like these using Catlab and AlgebraicRewriting. These include calling A⋅B to compose diagrams (which match head-to-tail) in sequence, and calling A⊗B to compose diagrams in parallel. Another powerful tool, which constructs the above diagram in one step, uses the fact that acyclic wiring diagrams can be expressed very naturally using a simple programming-like syntax, where variables correspond to wires, ‘calling a function’ corresponds to feeding wires into a box, and the special syntax [x₁,...,xₙ] corresponds to merging wires together:

mk_sched(
  # 1 *looped* argument 
  (r3_loop,),  
  # 1 normal argument
  (coin_in,), 
  # Bind these names to boxes / wiring diagrams defined elsewhere
  (C = coin, R3 = repeat3, R = sheep_reprod), 
  # Construct an acyclic wiring diagram
  quote 
    coin_yes, coin_no = C(coin_in)
    R3_input = [r3_loop, coin_yes]
    repeat3_looping, repeat3_finished = R3(R3_input)
    reprod_suc, reprod_fail = R(repeat3_looping)
    output = [reprod_suc, repeat3_finished, coin_no]
    # The 1st argument is fed back into `r3_loop`.
    return (reprod_fail,  output)        
end)

Our desired program was not, in fact, acyclic, but by asking for the first n outputs to be looped back into the first n inputs (where n is the length of the first argument to mk_sched), we have a general strategy for making diagrams with loops.

The Query box

The trajectory of the world state while executing a program looks like this:

This means it’s possible to take an agent A_i and interpret it in the ‘current’ state of the world, X_n, by composing it with the partial maps between X_i and X_n. This updating of an agent could result in a map which is total (i.e. the agent ‘survived’ the update process) or partial, which would happen if some part of the agent was deleted between step i and step n. We take advantage of this ability to update agents with the last major kind of box, the Query box.

These are yellow boxes which execute a subroutine for each agent of a particular shape. Once this set of matches is found, the query box stores them in its internal state. Each time we return through the second in port, we pop off the next agent in the queue and exit the second out port. Once this queue is empty, we exit out the first port with our original agent. (There is an edge case to consider: what if, while executing the actions of all the sub-agents from the query, our original agent is deleted? In this case we exit a third output door, which has no agent.)

For example, we may wish to organize our wolf-sheep-grass model as a while loop wrapping three for loops, doing some actions per sheep, per wolf, and per vertex.

In the figure above, ‘Daily’ refers to another program which performs the actions that are common to both sheep and wolves (e.g. rotating, moving, starving). These are originally defined for just sheep, but by observing the symmetry of wolves and sheep in our schema, we can use a \Delta data migration Swap to automatically translate a Sheep Daily program into a Wolf Daily program.

We may consider other ways of changing our agent type other than the Query box. A simple one is the Weakening box, which is specified by a morphism between agent shapes: B \rightarrow A. It converts A agents into B agents without changing the state of the world. This is because we can precompose this morphism with an agent A \rightarrow X. In particular, for any agent A we can use a weakening 0 \rightarrow A to discard focus on the current agent.