Exercises

The purpose of these exercises is to guide your efforts in learning AlgebraicJulia. Thus, some of these exercises are purposely underspecified; the specifics of the answer are not as important as the process of getting to that answer.

For instance, in the first couple exercises, we ask you to install Julia and do some basic tasks. These are exercises in computer systems administrations, not mathematics! Hopefully, everything goes smoothly with installation, but if not, also think of this as an exercise in how to debug computer systems, and don’t hesitate to ask for help.

Later exercises include some questions about how to design software; these too have very open-ended answers. Writing software is somewhat like doing mathematical research, in that as much or more time is spent thinking about what to prove as is spent actually proving it. In the context of software, this means that more of your time is spent designing the architecture of programs than in implementing algorithms whose specifications are known in advance. In computational category theory, this is especially true. So hopefully these exercises will get you started thinking about these questions, and perhaps you will come up with ideas and approaches that will be new to us!

We expect that you have some familiarity with some programming language (not necessarily Julia). But more importantly, we expect that you will use every resource at your disposal to work through these exercises:

The exercises are rated in difficulty from ★ (easiest) to ★ ★ ★ ★ ★ (open problem). Programming is always a time-consuming activity, so don’t be discouraged if even the easier exercises take a while to complete.

Part 1

This first part will be focused on getting familiar with Julia, and the AlgebraicJulia philosophy of doing category theory on the computer.

Follow the quick start instructions to install Julia, a code editor, and the git version control system.

Get Julia to print “Hello World”.

Install a Julia package, such as Catlab or AlgebraicDynamics, using the Julia package manager.

In my opinion, one of the biggest barriers to entry to software development for academics is how unintuitive version control is. If you aren’t familiar with git, find someone who is and walk through

  • Forking the ACT2023Tutorial repository
  • Clone your fork
  • Make a directory called solutions/$YOUR_NAME (replace $YOUR_NAME with a space-free sequence of characters that you feel describes yourself). Put some code in there!
  • stage your changes
  • commit your changes
  • push your changes to your fork
  • send a pull request to ACT2023Tutorial

This may seem intimidating; that’s why you need to find a friend!

We can represent the objects and morphisms in the skeleton of the category \(\mathsf{FinSet}\) using the Julia structs:

struct FinSet
  n::Int
end

struct FinFunction
  dom::FinSet
  codom::FinSet
  values::Vector{Int}
end

A, B = FinSet(3), FinSet(2)
f = FinFunction([1,2,2], A, B)

Here, we simply identify the finite set \(\{1,2,\ldots,n\}\) with its number of elements since set operations then operate at the speed of Julia integers.

Write a function that computes the product of two finite sets, along with the projection maps out.

A graph is a set-valued functor on the free category generated by the

Implement a graph data structure in Catlab either (a) using Catlab’s support for C-sets (@acset_type) or (b) more directly, using finite sets (FinSet) and functions (FinFunction). (Tip: Don’t call your data structure Graph.)

In the presentation, we saw an implementation of Euler’s method for numerically integrating a differential equation. This implementation is inefficient because it allocates a new vector every time we compute the derivative of the system.

Write an optimized implementation of Euler’s method that computes the derivative in place and only makes allocations when initializing the algorithm.

Hint: you can use @time f(x,y,z) in the REPL to check how many allocations a function f makes while running.

Part 2

Implement the dynamical system

\[ \dot{R} = \alpha R \]

using AlgebraicDynamics.

The @relation macro in Catlab is a convenient DSL for defining UWDs, but that’s all it is: the real data is stored in the acset that the macro produces. This exercise is about understanding the connection between the DSL and the data of the UWD.

  1. Write a call to the @relation macro that constructs the following UWD.
┌─────┬──────┐
│ Box │ name │
├─────┼──────┤
│   1 │    R │
│   2 │    S │
│   3 │    T │
└─────┴──────┘
┌──────┬─────┬──────────┐
│ Port │ box │ junction │
├──────┼─────┼──────────┤
│    1 │   1 │        2 │
│    2 │   1 │        1 │
│    3 │   2 │        3 │
│    4 │   2 │        1 │
│    5 │   3 │        4 │
│    6 │   3 │        1 │
└──────┴─────┴──────────┘
┌───────────┬────────────────┐
│ OuterPort │ outer_junction │
├───────────┼────────────────┤
│         1 │              2 │
│         2 │              3 │
│         3 │              4 │
└───────────┴────────────────┘
┌──────────┬──────────┐
│ Junction │ variable │
├──────────┼──────────┤
│        1 │        w │
│        2 │        x │
│        3 │        y │
│        4 │        z │
└──────────┴──────────┘
  1. Construct the above UWD manually using the API for UWDs (add_box!, set_junction!) or the lower-level API for acsets (add_part(s)!, set_part(s)!). It might be helpful to know that the Julia type of the UWD return by the @relation macro is RelationDiagram.

Implement a dynamical system modeling the trajectory of a pendulum.

This exercise has two parts; first you must come up with an ordinary differential equation that models a pendulum; here you need a bit of physics. Then you must write down this system in AlgebraicDynamics.

Using a graph data structure created in the Part 1 exercise or the one already available in Catlab.Graphs, implement a graph traversal algorithm, such as depth-first search or breadth-first search, using the acsets API (subpart, incident).

Union-find data structures are used to represent equivalence relations on finite sets in computer science. In Julia, there is an implementation of union-find called IntDisjointSets in the DataStructures.jl package.

Use this data structure to find the connected components of a graph, by making src(e) and tgt(e) be in the same equivalence class for each edge e.

Implement composition of cospans using union-find.

Macros in Julia, such as the @relation macro, are a useful tool for creating embedded domain-specific languages (DSLs) with special notation.

Write a macro that creates a graph using a Graphviz-like syntax:

g = @make_graph begin
  a
  b
  c
  a -> b
  b -> c
end

Hint: Use the dump function to see what a Julia expression looks like internally.

Part 3

A discrete dynamical system (DDS) consists of a set \(X\) of states and a function \(\phi: X \rightarrow X\) defining the transition from one state to the next. Given this, the schema for a discrete dynamical system (DDS) has a single object object equipped with a single non-identity morphism. Implement this schema in Catlab. Then, instantiate an acset with data that represents the following DDS:

Figure 1: A simple discrete dynamical system.

Suppose that there are populations of rocks, populations of papers, and populations of scissors. Predation happens to each based on the classic pattern; i.e. scissors eat papers, papers eat rocks, and rocks eat scissors.

Write down a model for a pairwise interaction between two implements based on Lotka-Volterra dynamics, and then compose three copies of that model to produce a three-population system.

Suppose that you have a doubly nested undirected wiring diagram of resource sharers. By this, I mean you have an undirected wiring diagram, where each box contains an undirected wiring diagram, and each box of this contains a resource sharer.

Then you can put together these resource sharers in two different ways. The first is by composing each of the inner undirected wiring diagrams, so that the outer wiring diagram now has a resource sharer in each box, and then composing the outer undirected wiring diagram. In other words, call oapply on each inner wiring diagram, and then call oapply on the other diagram.

The second way is to first collapse the nesting, by composing the two layers of wiring diagrams into one big wiring diagram, and then compose all of the resource sharers at one. In other words, call ocompose on the UWD of UWDs, and then call oapply on the remaining UWD with a resource sharer in each box.

Both methods of composition should ultimately result in the same composed resource sharer.

This is analogous to the law for a monad algebra:

Verify this rule by testing it out in code; construct a nested undirected wiring diagram, and then try out both ways of composing it.

Any Petri net induces a dynamical system where the state space is \(\mathbb{R}^S\) (\(S\) is the set of species), and the vector field is given by mass action semantics (see Chapter 2: The rate equation). In AlgebraicPetri, we have a function called vectorfield which produces a function that computes the vector field for the mass action equations. Use this function (or for an extra challenge, reimplement this function) to turn an arbitrary Petri net into a resource sharer that exposes all of the populations of the species. Then pick a Petri net, turn it into a resource sharer, and compose it with another resource sharer of your choice.

Now think about the following question. You can compose Petri nets together by gluing their species together. If you compose Petri nets and then take the dynamical system given by mass action on the composed Petri net, is that the same dynamical system as turning each Petri net into a resource sharer and then composing the resource sharers? Prove or give a counterexample.

Figure out a good mathematical abstraction for, and implement nested acsets in Julia.

For some thoughts on what this might mean, see: