# Programs

The module `Catlab.Programs`

provides domain-specific languages (DSLs) for constructing diagrams of various kinds. The DSLs, implemented as Julia macros, are based on the syntax of the Julia language but often interpret that syntax very differently from standard Julia programs. Conversely, this module offers preliminary support for generating Julia code from wiring diagrams.

There are two major macros for constructing wiring diagrams:

In addition, there is a family of related macros for constructing category-theoretic diagrams:

`@graph`

, for constructing a graph`@fincat`

, for presenting a category as a graph together with path equations`@finfunctor`

, for defining a functor between two finitely presented categories`@diagram`

, for defining a diagram in a category

Generalizing the last two macros, the modules provides DSLs for functorial data migration:

`@migrate`

, for migrating data between acsets`@migration`

, for defining data migrations between schemas

## API

`Catlab.Programs.GenerateJuliaPrograms`

— ModuleCompile or evaluate morphisms as Julia programs.

`Catlab.Programs.GenerateJuliaPrograms.Block`

— TypeA block of Julia code with input and output variables.

`Catlab.Programs.GenerateJuliaPrograms.CompileState`

— TypeInternal state for compilation of morphism into Julia code.

`Catlab.Programs.GenerateJuliaPrograms.compile`

— MethodCompile a morphism expression into a Julia function.

`Catlab.Programs.GenerateJuliaPrograms.compile_block`

— MethodCompile a morphism expression into a block of Julia code.

`Catlab.Programs.GenerateJuliaPrograms.compile_expr`

— MethodCompile a morphism expression into a Julia function expression.

`Catlab.Programs.GenerateJuliaPrograms.evaluate`

— MethodEvaluate a morphism as a function.

If the morphism will be evaluated only once (possibly with vectorized inputs), then direct evaluation will be much faster than compiling (via `compile`

) and evaluating a standard Julia function.

Compare with `functor`

.

`Catlab.Programs.ParseJuliaPrograms`

— ModuleParse Julia programs into morphisms represented as wiring diagrams.

`Catlab.Programs.ParseJuliaPrograms.parse_wiring_diagram`

— MethodParse a wiring diagram from a Julia function expression.

For more information, see the corresponding macro `@program`

.

`Catlab.Programs.ParseJuliaPrograms.@program`

— MacroParse a wiring diagram from a Julia program.

For the most part, this is standard Julia code but a few liberties are taken with the syntax. Products are represented as tuples. So if `x`

and `y`

are variables of type $X$ and $Y$, then `(x,y)`

has type $X ⊗ Y$. Also, both `()`

and `nothing`

are interpreted as the monoidal unit $I$.

Unlike standard Julia, the function call expressions `f(x,y)`

and `f((x,y))`

are equivalent. Consequently, given morphisms $f: W → X ⊗ Y$ and $g: X ⊗ Y → Z$, the code

```
x, y = f(w)
g(x,y)
```

is equivalent to `g(f(w))`

. In standard Julia, at most one of these calls to `g`

would be valid, unless `g`

had multiple signatures.

The diagonals (copying and deleting) of a cartesian category are implicit in the Julia syntax: copying is variable reuse and deleting is variable non-use. For the codiagonals (merging and creating), a special syntax is provided, reinterpreting Julia's vector literals. The merging of `x1`

and `x2`

is represented by the vector `[x1,x2]`

and creation by the empty vector `[]`

. For example, `f([x1,x2])`

translates to `compose(mmerge(X),f)`

.

This macro is a wrapper around `parse_wiring_diagram`

.

`Catlab.Programs.RelationalPrograms`

— ModuleParse relation expressions in Julia syntax into undirected wiring diagrams.

`Catlab.Programs.RelationalPrograms.RelationDiagram`

— TypeAbstract type for UWDs created by `@relation`

macro.

`Catlab.Programs.RelationalPrograms.TypedRelationDiagram`

— TypeTyped UWD created by `@relation`

macro.

`Catlab.Programs.RelationalPrograms.UntypedRelationDiagram`

— TypeUntyped UWD created by `@relation`

macro.

`Catlab.Programs.RelationalPrograms.parse_relation_diagram`

— MethodParse an undirected wiring diagram from a relation expression.

For more information, see the corresponding macro `@relation`

.

`Catlab.Programs.RelationalPrograms.@relation`

— MacroConstruct an undirected wiring diagram using relation notation.

Unlike the `@program`

macro for directed wiring diagrams, this macro departs significantly from the usual semantics of the Julia programming language. Function calls with $n$ arguments are now interpreted as assertions that an $n$-ary relation holds at a particular point. For example, the composite of binary relations $R ⊆ X × Y$ and $S ⊆ Y × Z$ can be represented as an undirected wiring diagram by the macro call

```
@relation (x,z) where (x::X, y::Y, z::Z) begin
R(x,y)
S(y,z)
end
```

In general, the context in the `where`

clause defines the set of junctions in the diagram and variable sharing defines the wiring of ports to junctions. If the `where`

clause is omitted, the set of junctions is inferred from the variables used in the macro call.

The ports and junctions of the diagram may be typed or untyped, and the ports may be named or unnamed. Thus, four possible types of undirected wiring diagrams may be returned, with the type determined by the form of relation header:

- Untyped, unnamed:
`@relation (x,z) where (x,y,z) ...`

- Typed, unnamed:
`@relation (x,z) where (x::X, y::Y, z::Z) ...`

- Untyped, named:
`@relation (out1=x, out2=z) where (x,y,z) ...`

- Typed, named:
`@relation (out=1, out2=z) where (x::X, y::Y, z::Z) ...`

All four types of diagram are subtypes of `RelationDiagram`

.

`Catlab.Programs.DiagrammaticPrograms`

— ModuleDSLs for defining categories, diagrams, and related structures.

Here "diagram" means diagram in the standard category-theoretic sense, not string diagram or wiring diagram. DSLs for constructing wiring diagrams are provided by other submodules.

`Catlab.Programs.DiagrammaticPrograms.@diagram`

— MacroPresent a diagram in a given category.

Recall that a *diagram* in a category $C$ is a functor $F: J → C$ from a small category $J$ into $C$. Given the category $C$, this macro presents a diagram in $C$, i.e., constructs a finitely presented indexing category $J$ together with a functor $F: J → C$. This method of simultaneous definition is often more convenient than defining $J$ and $F$ separately, as could be accomplished by calling `@fincat`

and then `@finfunctor`

.

As an example, the limit of the following diagram consists of the paths of length two in a graph:

```
@diagram TheoryGraph begin
v::V
(e₁, e₂)::E
(t: e₁ → v)::tgt
(s: e₂ → v)::src
end
```

Morphisms in the indexing category can be left unnamed, which is convenient for defining free diagrams (see also `@free_diagram`

). For example, the following diagram is isomorphic to the previous one:

```
@diagram TheoryGraph begin
v::V
(e₁, e₂)::E
(e₁ → v)::tgt
(e₂ → v)::src
end
```

Of course, unnamed morphisms cannot be referenced by name within the `@diagram`

call or in other settings, which can sometimes be problematic.

`Catlab.Programs.DiagrammaticPrograms.@fincat`

— MacroPresent a category by generators and relations.

The result is a finitely presented category (`FinCat`

) represented by a graph, possibly with path equations. For example, the simplex category truncated to one dimension is:

```
@fincat begin
V, E
(δ₀, δ₁): V → E
σ₀: E → V
σ₀ ∘ δ₀ == id(V)
σ₀ ∘ δ₁ == id(V)
end
```

The objects and morphisms must be uniquely named.

`Catlab.Programs.DiagrammaticPrograms.@finfunctor`

— MacroDefine a functor between two finitely presented categories.

Such a functor is defined by sending the object and morphism generators of the domain category to generic object and morphism expressions in the codomain category. For example, the following functor embeds the schema for graphs into the schema for circular port graphs by ignoring the ports:

```
@finfunctor TheoryGraph ThCPortGraph begin
V => Box
E => Wire
src => src ⨟ box
tgt => tgt ⨟ box
end
```

`Catlab.Programs.DiagrammaticPrograms.@free_diagram`

— MacroPresent a free diagram in a given category.

Recall that a *free diagram* in a category $C$ is a functor $F: J → C$ where $J$ is a free category on a graph, here assumed finite. This macro is functionally a special case of `@diagram`

that provides a syntactic variant for equality expressions. Rather than interpreting them as equations between morphisms in $J$, equality expresions can be used to introduce anonymous morphisms in a "pointful" style. For example, the limit of the following diagram consists of the paths of length two in a graph:

```
@free_diagram TheoryGraph begin
v::V
(e₁, e₂)::E
tgt(e₁) == v
src(e₂) == v
end
```

`Catlab.Programs.DiagrammaticPrograms.@graph`

— MacroConstruct a graph in a simple, declarative style.

The syntax is reminiscent of Graphviz. Each line a declares a vertex or set of vertices, or an edge. For example, the following defines a directed triangle:

```
@graph begin
v0, v1, v2
fst: v0 → v1
snd: v1 → v2
comp: v0 → v2
end
```

Vertices in the graph must be uniquely named, whereas edges names are optional.

`Catlab.Programs.DiagrammaticPrograms.@migrate`

— MacroContravariantly migrate data from one acset to another.

This macro is shorthand for defining a data migration using the `@migration`

macro and then calling the `migrate`

function. If the migration will be used multiple times, it is more efficient to perform these steps separately, reusing the functor defined by `@migration`

.

For more about the syntax and supported features, see `@migration`

.

`Catlab.Programs.DiagrammaticPrograms.@migration`

— MacroDefine a contravariant data migration.

This macro provides a DSL to specify a contravariant data migration from $C$-sets to $D$-sets for given schemas $C$ and $D$. A data migration is defined by a functor from $D$ to a category of queries on $C$. Thus, every object of $D$ is assigned a query on $C$ and every morphism of $D$ is assigned a morphism of queries, in a compatible way. Example usages are in the unit tests and the AlgebraicJulia blog (TODO: link). What follows is a technical reference.

Several categories of queries are supported by this macro:

- Trivial queries, specified by a single object of $C$. In this case, the macro simply defines a functor $D → C$ and is equivalent to
`@finfunctor`

or`@diagram`

. *Conjunctive queries*, specified by a diagram in $C$ and evaluated as a finite limit.*Gluing queries*, specified by a diagram in $C$ and evaluated as a finite colimit. An important special case is*linear queries*, evaluated as a finite coproduct.*Gluc queries*(gluings of conjunctive queries), specified by a diagram of diagrams in $C$ and evaluated as a colimit of limits. An important special case is*duc queries*(disjoint unions of conjunctive queries), evaluated as a coproduct of limits.

The query category of the data migration is not specified explicitly but is inferred from the queries used in the macro call. Implicit conversion is performed: trivial queries can be coerced to conjunctive queries or gluing queries, and conjunctive queries and gluing queries can both be coerced to gluc queries. Due to the implicit conversion, the resulting functor out of $D$ has a single query type and thus a well-defined codomain.

Syntax for the right-hand sides of object assignments is:

- a symbol, giving object of $C$ (query type: trivial)
`@product ...`

(query type: conjunctive)`@join ...`

(alias:`@limit`

, query type: conjunctive)`@cases ...`

(alias:`@coproduct`

, query type: gluing or gluc)`@glue ...`

(alias:`@colimit`

, query type: gluing or gluc)

Thes query types supported by this macro generalize the kind of queries familiar from relational databases. Less familiar is the concept of a morphism between queries, derived from the concept of a morphism between diagrams in a category. A query morphism is given by a functor between the diagrams' indexing categories together with a natural transformation filling a triangle of the appropriate shape. From a practical standpoint, the most important thing to remember is that a morphism between conjunctive queries is contravariant with respect to the diagram shapes, whereas a morphism between gluing queries is covariant. TODO: Reference for more on this.