# Library Reference

## Syntax

`GATlab.Syntax.Scopes.Binding`

— Type`Binding{T}`

A binding associates some `T`

-typed value to a name.

`name`

is an optional distinguished name `value`

is the element

`GATlab.Syntax.Scopes.Context`

— TypeA `Context`

is anything which contains an ordered list of scopes.

Scopes within a context are referred to by *level*, which is their index within this list.

`Context`

s should overload:

`getscope(c::Context, level::Int) -> Scope`

`nscopes(c::Context) -> Int`

`hastag(c::Context, tag::ScopeTag) -> Bool`

`hasname(c::Context, name::Symbol) -> Bool`

`getlevel(c::Context, tag::ScopeTag) -> Int`

`getlevel(c::Context, name::Symbol) -> Int`

`alltags(c::Context) -> Set{ScopeTag}`

`GATlab.Syntax.Scopes.HasScope`

— TypeAn abstract type for wrappers around a single scope.

Must overload

`getscope(hs::HasScope) -> Scope`

`GATlab.Syntax.Scopes.HasScopeList`

— TypeA type for things which contain a scope list.

Notably, GATs contain a scope list.

Must implement:

`getscopelist(hsl::HasScopeList) -> ScopeList`

`GATlab.Syntax.Scopes.Ident`

— Type`Ident`

An identifier.

`tag`

refers to the scope that this Ident is bound in `lid`

indexes the scope that Ident is bound in `name`

is an optional field for the sake of printing. A variable in a scope might be associated with several names

`GATlab.Syntax.Scopes.LID`

— TypeA LID (Local ID) indexes a given scope.

Currently, scopes assign LIDs sequentially – this is not a stable guarantee however, and in theory scopes could have "sparse" LIDs.

`GATlab.Syntax.Scopes.Scope`

— Type`Scope{T}`

In GATlab, we handle shadowing with a notion of *scope*. Names shadow between scopes. Anything which binds variables introduces a scope, for instance a `@theory`

declaration or a context. For example, here is a scope with 3 elements:

```
x = 3
y = "hello"
z = x
```

Here z is introduced as an alias for x. It is illegal to shadow within a scope. Overloading is not explicitly treated but can be managed by having values which refer to identifiers earlier / the present scope. See GATs.jl, for example.

`GATlab.Syntax.Scopes.ScopeTag`

— TypeThe tag that makes reference to a specific scope possible.

`GATlab.Syntax.Scopes.ScopeTagError`

— Type`ScopeTagError`

An error to throw when an identifier has an unexpected scope tag

`GATlab.Syntax.Scopes.ScopedBinding`

— TypeType for printing out bindings with colored keys

`GATlab.Syntax.Scopes.getidents`

— MethodThis collects all the idents in a scope

`GATlab.Syntax.Scopes.getlid`

— MethodDetermine the level of a binding given the name

`GATlab.Syntax.Scopes.hasident`

— Method`hasident`

checks whether an identifier with specified data exists, by attempting to create it and returning whether or not that attempt failed.

`GATlab.Syntax.Scopes.ident`

— Method`ident`

creates an `Ident`

from a context and some partial data supplied as keywords.

Keywords arguments:

`tag::Union{ScopeTag, Nothing}`

. The tag of the scope that the`Ident`

is in.`name::Union{Symbol, Nothing}`

. The name of the identifier.`lid::Union{LID, Nothing}`

. The lid of the identifier within its scope.`level::Union{Int, Nothing}`

. The level of the scope within the context.`strict::Bool`

. If`strict`

is true, throw an error if not found, else return nothing.

`GATlab.Syntax.Scopes.idents`

— MethodThis is a broadcasted version of `ident`

`GATlab.Syntax.Scopes.rename`

— Method`rename(tag::ScopeTag, replacements::Dict{Symbol, Symbol}, x::T) where {T} -> T`

Recurse through the structure of `x`

, and change any name `n`

in scope `tag`

to `get(replacements, n, n)`

. Overload this function on structs that have names in them.

`GATlab.Syntax.Scopes.retag`

— Method`retag(replacements::Dict{ScopeTag, ScopeTag}, x::T) where {T} -> T`

Recurse through the structure of `x`

, swapping any instance of a ScopeTag `t`

with `get(replacements, t, t)`

. Overload this function on structs that have ScopeTags within them.

`GATlab.Syntax.Scopes.unsafe_pushbinding!`

— MethodAdd a new binding to the end of Scope `s`

.

`GATlab.Syntax.GATs.AbstractConstant`

— TypeWe need this to resolve a mutual reference loop; the only subtype is Constant

`GATlab.Syntax.GATs.AbstractDot`

— TypeWe need this to resolve a mutual reference loop; the only subtype is Dot

`GATlab.Syntax.GATs.AlgAccessor`

— Type`AlgAccessor`

The arguments to a term constructor serve a dual function as both arguments and also methods to extract the value of those arguments.

I.e., declaring `Hom(dom::Ob, codom::Ob)::TYPE`

implicitly overloads a previous declaration for `dom`

and `codom`

, or creates declarations if none previously exist.

`GATlab.Syntax.GATs.AlgAxiom`

— Type`AlgAxiom`

A declaration of an axiom

`GATlab.Syntax.GATs.AlgDeclaration`

— Type`AlgDeclaration`

A declaration of a constructor; constructor methods in the form of `AlgTermConstructors`

or the accessors for `AlgTypeConstructors`

follow later in the theory.

`GATlab.Syntax.GATs.AlgDot`

— TypeAccessing a name from a term of tuple type

`GATlab.Syntax.GATs.AlgEqSort`

— Type`AlgSort`

A sort for equality judgments of terms for a particular sort

`GATlab.Syntax.GATs.AlgFunction`

— TypeA shorthand for a function, such as "square(x) := x * x". It is relevant for models but can be ignored by theory maps, as it is fully determined by other judgments in the theory.

`GATlab.Syntax.GATs.AlgSort`

— Type`AlgSort`

A *sort*, which is essentially a type constructor without arguments

`GATlab.Syntax.GATs.AlgSorts`

— Type`AlgSorts`

A description of the argument sorts for a term constructor, used to disambiguate multiple term constructors of the same name.

`GATlab.Syntax.GATs.AlgStruct`

— Type`AlgStruct`

A declaration which is sugar for an AlgTypeConstructor, an AlgTermConstructor which constructs an element of that type, and projection term constructors. E.g.

```
struct Cospan(dom, codom) ⊣ [dom:Ob, codom::Ob]
apex::Ob
i1::dom->apex
i2::codom->apex
end
```

Is tantamount to (in a vanilla GAT):

```
Cospan(dom::Ob, codom::Ob)::TYPE
cospan(apex, i1, i2)::Cospan(dom, codom)
⊣ [(dom, codom, apex)::Ob, i1::dom->apex, i2::codom->apex]
apex(csp::Cospan(d::Ob, c::Ob))::Ob
i1(csp::Cospan(d::Ob, c::Ob))::(d->apex(csp))
i2(csp::Cospan(d::Ob, c::Ob))::(c->apex(csp))
apex(cospan(a, i_1, i_2)) == a
⊣ [(dom, codom, apex)::Ob, i_1::dom->apex, i_2::codom->apex]
i1(cospan(a, i_1, i_2)) == i_1
⊣ [(dom, codom, apex)::Ob, i_1::dom->apex, i_2::codom->apex]
i2(cospan(a, i_1, i_2)) == i_2
⊣ [(dom, codom, apex)::Ob, i_1::dom->apex, i_2::codom->apex]
cospan(apex(csp), i1(csp), i2(csp)) == csp
⊣ [(dom, codom)::Ob, csp::Cospan(dom, codom)]
```

`GATlab.Syntax.GATs.AlgTerm`

— Type`AlgTerm`

One syntax tree to rule all the terms.

`GATlab.Syntax.GATs.AlgTermConstructor`

— Type`AlgTermConstructor`

A declaration of a term constructor as a method of an `AlgFunction`

.

`GATlab.Syntax.GATs.AlgType`

— Type`AlgType`

One syntax tree to rule all the types.

`GATlab.Syntax.GATs.AlgTypeConstructor`

— Type`AlgTypeConstructor`

A declaration of a type constructor.

`GATlab.Syntax.GATs.Constant`

— Type`Constant`

A Julia value in an algebraic context. Type checked elsewhere.

`GATlab.Syntax.GATs.Eq`

— Type`Eq`

The type of equality judgments.

`GATlab.Syntax.GATs.GAT`

— Type`GAT`

A generalized algebraic theory. Essentially, just consists of a name and a list of `GATSegment`

s, but there is also some caching to make access faster. Specifically, there is a dictionary to map ScopeTag to position in the list of segments, and there are lists of all of the identifiers for term constructors, type constructors, and axioms so that they can be iterated through faster.

GATs allow overloading but not shadowing.

`GATlab.Syntax.GATs.GATContext`

— Type`GATContext`

A context consisting of two parts: a GAT and a TypeCtx

Certain types (like AlgTerm) can only be parsed in a GATContext, because they require access to the method resolving in the GAT.

`GATlab.Syntax.GATs.GATSegment`

— Type`GATSegment`

A piece of a GAT, consisting of a scope that binds judgments to names, possibly disambiguated by argument sorts.

This is a struct rather than just a type alias so that we can customize the show method.

`GATlab.Syntax.GATs.InCtx`

— MethodGet the canonical type + ctx associated with a type constructor.

`GATlab.Syntax.GATs.InCtx`

— MethodGet the canonical term + ctx associated with a method.

`GATlab.Syntax.GATs.Judgment`

— TypeA GAT is conceptually a bunch of `Judgment`

s strung together.

`GATlab.Syntax.GATs.MethodApp`

— Type`MethodApp`

An application of a method of a constructor to arguments. We need a type parameter `T`

because `AlgTerm`

hasn't been defined yet, but the only type used for `T`

will in fact be `AlgTerm`

.

`method`

either points to an `AlgTermConstructor`

, an `AlgTypeConstructor`

or an `AlgAccessor`

,

`GATlab.Syntax.GATs.MethodResolver`

— Type`MethodResolver`

Right now, this just maps a sort signature to the resolved method.

When we eventually support varargs, this will have to do something slightly fancier.

`GATlab.Syntax.GATs.TypeScope`

— Type`TypeScope`

A scope where variables are assigned to `AlgType`

s. We use a wrapper here so that it pretty prints as `[a::B]`

instead of `{a => AlgType(B)}`

`Base.show`

— MethodCommon methods for AlgType and AlgTerm

`GATlab.Syntax.ExprInterop.fromexpr`

— MethodCoerce GATs to GAT contexts

`GATlab.Syntax.ExprInterop.toexpr`

— MethodThis only works when `seg`

is a segment of `theory`

`GATlab.Syntax.GATs.equations`

— MethodGet equations for a term or type constructor

`GATlab.Syntax.GATs.equations`

— MethodImplicit equations defined by a context.

This function allows a generalized algebraic theory (GAT) to be expressed as an essentially algebraic theory, i.e., as partial functions whose domains are defined by equations.

References:

- (Cartmell, 1986, Sec 6: "Essentially algebraic theories and categories with finite limits")
- (Freyd, 1972, "Aspects of topoi")

This function gives expressions for computing the elements of `c.context`

which can be inferred from applying accessor functions to elements of `args`

.

Example:

equations({f::Hom(a,b), g::Hom(b,c)}, {a::Ob, b::Ob, c::Ob}, ThCategory)

ways*of*computing = Dict(a => [dom(f)], b => [codom(f), dom(g)], c => [codom(g)], f => [f], g => [g])

`GATlab.Syntax.GATs.normalize_judgment`

— MethodThis is necessary because the intuitive precedence rules for the symbols that we use do not match the Julia precedence rules. In theory, this could be written with some algorithm that recalculates precedence, but I am too lazy to write that, so instead I just special case everything.

`GATlab.Syntax.GATs.parse_scope!`

— Method`f(pushbinding!, expr)`

should inspect `expr`

and call `pushbinding!`

0 or more times with two arguments: the name and value of a new binding.

`GATlab.Syntax.GATs.sortcheck`

— Method`sortcheck(ctx::Context, t::AlgTerm)`

Throw an error if a the head of an AlgTerm (which refers to a term constructor) has arguments of the wrong sort. Returns the sort of the term.

`GATlab.Syntax.GATs.sortcheck`

— Method`sortcheck(ctx::Context, t::AlgType)`

Throw an error if a the head of an AlgType (which refers to a type constructor) has arguments of the wrong sort.

`GATlab.Syntax.GATs.structs`

— MethodGet all structs in a theory

`GATlab.Syntax.GATs.substitute_funs`

— MethodReplace all functions with their desugared expressions

`GATlab.Syntax.GATs.substitute_term`

— MethodReplace idents with AlgTerms.

`GATlab.Syntax.ExprInterop.fromexpr`

— MethodParse, e.g.:

```
(a,b,c)::Ob
f::Hom(a, b)
g::Hom(b, c)
h::Hom(a, c)
h′::Hom(a, c)
compose(f, g) == h == h′
```

`GATlab.Syntax.ExprInterop.fromexpr`

— Function`fromexpr(c::Context, e::Any, T::Type) -> Union{T,Nothing}`

Converts a Julia Expr into type T, in a certain scope.

`GATlab.Syntax.ExprInterop.toexpr`

— Function`toexpr(c::Context, t) -> Any`

Converts GATlab syntax into an Expr that can be read in via `fromexpr`

to get the same thing. Crucially, the output of this will depend on the order of the scopes in `c`

, and if read back in with a different `c`

may end up with different results.

`GATlab.Syntax.TheoryInterface.GAT_MODULE_LOOKUP`

— ConstantWhen we declare a new theory, we add the scope tag of its new segment to this dictionary pointing to the module corresponding to the new theory.

`GATlab.Syntax.TheoryInterface.fqmn`

— MethodFully Qualified Module Name

`GATlab.Syntax.TheoryInterface.mk_struct`

— Method## Models

`GATlab.Models.ModelInterface.ImplementationNotes`

— Type`ImplementationNotes`

Information about how a model implements a `GATSegment`

. Right now, just the docstring attached to the `@instance`

macro, but could contain more info in the future.

`GATlab.Models.ModelInterface.implements`

— Method`implements(m::Model, tag::ScopeTag) -> Union{ImplementationNotes, Nothing}`

If `m`

implements the GATSegment referred to by `tag`

, then return the corresponding implementation notes.

`GATlab.Models.ModelInterface.parse_instance_body`

— MethodParses the raw julia expression into JuliaFunctions

`GATlab.Models.ModelInterface.qualify_function`

— MethodAdd `WithModel`

param first, if this is not an old instance (it shouldn't have it already) Qualify method name to be in theory module Qualify args to struct types Add `context`

kwargs if not already present

`GATlab.Models.ModelInterface.to_call_impl`

— MethodCompile an AlgTerm into a Julia call Expr where termcons (e.g. `f`

) are interpreted as `mod.f[model.model](...)`

.

`GATlab.Models.ModelInterface.typecheck_instance`

— MethodThrow error if missing a term constructor. Provides default instances for type constructors and type arguments, which return true or error, respectively.

`GATlab.Syntax.TheoryMaps.migrator`

— MethodGiven a Theory Morphism T->U and a model Mᵤ which implements U, obtain a model Mₜ which wraps Mᵤ and is a model of T.

Future work: There is some subtlety in how accessor functions should be handled. TODO: The new instance methods do not yet handle the `context`

keyword argument.

`GATlab.Models.ModelInterface.@instance`

— MacroUsage:

```
struct TypedFinSetC <: Model{Tuple{Vector{Int}, Vector{Int}}}
ntypes::Int
end
@instance ThCategory{Vector{Int}, Vector{Int}} [model::TypedFinSetC] begin
Ob(v::Vector{Int}) = all(1 <= j <= model.ntypes for j in v)
Hom(f::Vector{Int}, v::Vector{Int}, w::Vector{Int}) =
length(f) == length(v) && all(1 <= y <= length(w) for y in f)
id(v::Vector{Int}) = collect(eachindex(v))
compose(f::Vector{Int}, g::Vector{Int}) = g[f]
dom(f::Vector{Int}; context) = context.dom
codom(f::Vector{Int}; context) = context.codom
end
struct SliceCat{Ob, Hom, C <: Model{Tuple{Ob, Hom}}} <: Model{Tuple{Tuple{Ob, Hom}, Hom}}
c::C
end
@instance ThCategory{Tuple{Ob, Hom}, Hom} [model::SliceCat{Ob, Hom, C}] where {Ob, Hom, C<:Model{Tuple{Ob, Hom}}} begin
end
```

`GATlab.Models.SymbolicModels.GATExpr`

— TypeBase type for expressions in the syntax of a GAT. This is an alternative to `AlgTerm`

used for backwards compatibility with Catlab.

We define Julia types for each *type constructor* in the theory, e.g., object, morphism, and 2-morphism in the theory of 2-categories. Of course, Julia's type system does not support dependent types, so the type parameters are incorporated in the Julia types. (They are stored as extra data in the expression instances.)

The concrete types are structurally similar to the core type `Expr`

in Julia. However, the *term constructor* is represented as a type parameter, rather than as a `head`

field. This makes dispatch using Julia's type system more convenient.

`Base.nameof`

— MethodGet name of GAT generator expression as a `Symbol`

.

If the generator has no name, returns `nothing`

.

`GATlab.Models.SymbolicModels.constructor_name`

— MethodName of constructor that created expression.

`GATlab.Models.SymbolicModels.functor`

— MethodFunctor from GAT expression to GAT instance.

Strictly speaking, we should call these "structure-preserving functors" or, better, "model homomorphisms of GATs". But this is a category theory library, so we'll go with the simpler "functor".

A functor is completely determined by its action on the generators. There are several ways to specify this mapping:

Specify a Julia instance type for each GAT type, using the required

`types`

tuple. For this to work, the generator constructors must be defined for the instance types.Explicitly map each generator term to an instance value, using the

`generators`

dictionary.For each GAT type (e.g., object and morphism), specify a function mapping generator terms of that type to an instance value, using the

`terms`

dictionary.

The `terms`

dictionary can also be used for special handling of non-generator expressions. One use case for this capability is defining forgetful functors, which map non-generators to generators.

FIXME

`GATlab.Models.SymbolicModels.generator_like`

— MethodCreate generator of the same type as the given expression.

`GATlab.Models.SymbolicModels.parse_json_sexpr`

— MethodDeserialize expression from JSON-able S-expression.

If `symbols`

is true (the default), strings are converted to symbols.

`GATlab.Models.SymbolicModels.show_latex`

— MethodShow the expression in infix notation using LaTeX math.

Does *not* include `$`

or `\[begin|end]{equation}`

delimiters.

`GATlab.Models.SymbolicModels.show_sexpr`

— MethodShow the syntax expression as an S-expression.

Cf. the standard library function `Meta.show_sexpr`

.

`GATlab.Models.SymbolicModels.show_unicode`

— MethodShow the expression in infix notation using Unicode symbols.

`GATlab.Models.SymbolicModels.symbolic_instance_methods`

— MethodJulia function for every type constructor, accessor, and term constructor. Term constructors can be overwritten by `overrides`

.

`GATlab.Models.SymbolicModels.syntax_module`

— MethodGet syntax module of given expression.

`GATlab.Models.SymbolicModels.to_json_sexpr`

— MethodSerialize expression as JSON-able S-expression.

The format is an S-expression encoded as JSON, e.g., "compose(f,g)" is represented as ["compose", f, g].

`GATlab.Models.SymbolicModels.@symbolic_model`

— Macro@symbolic_model generates the free model of a theory, generated by symbols.

This is backwards compatible with the @syntax macro in Catlab.

One way of thinking about this is that for every type constructor, we add an additional term constructor that builds a "symbolic" element of that type from any Julia value. This term constructor is called "generator".

An invocation of `@symbolic_model`

creates the following.

- A module with a struct for each type constructor, which has a single type

parameter `T`

and two fields, `args`

and `type_args`

. Instances of this struct are thought of as elements of the type given by the type constructor applied to `type_args`

. The type parameter refers to the term constructor that was used to generate the element, including the special term constructor `:generator`

, which has as its single argument an `Any`

.

For instance, in the theory of categories, we might have the following elements.

```
using .FreeCategory
x = Ob{:generator}([:x], [])
y = Ob{:generator}([:y], [])
f = Hom{:generator}([:f], [x, y])
g = Hom{:generator}([:g], [y, x])
h = Hom{:compose}([f, g], [x, x])
```

- Methods inside the module (not exported) for all of the term constructors and

field accessors (i.e. stuff like `compose, id, dom, codom`

), which construct terms.

- A default instance (i.e., without a model parameter) of the theory using the

types in this generated model. Methods in this instance can be overridden by the body of `@symbolic_model`

to perform rewriting for the sake of normalization, for instance flattening associative and unital operations.

- Coercion methods of the type constructors that allow one to introduce generators.

```
x = ThCategory.Ob(FreeCategory.Ob, :x)
y = ThCategory.Ob(FreeCategory.Ob, :y)
f = ThCategory.Hom(:f, x, y)
```

Note that in both the instance and in these coercion methods, we must give the expected type as the first argument when it cannot be infered by the other arguments. For instance, instead of

`munit() = ...`

we have

`munit(::Type{FreeSMC.Ob}) = ...`

and likewise instead of

`ThCategory.Ob(x::Any) = ...`

we have

`ThCategory.Ob(::Type{FreeCategory.Ob}, x::Any) = ...`

Example:

```
@symbolic_model FreeCategory{ObExr, HomExpr} ThCategory begin
compose(f::Hom, g::Hom) = associate_unit(new(f,g; strict=true), id)
end
```

This generates:

```
module FreeCategory
export Ob, Hom
using ..__module__
module Meta
const theory_module = ThCategory
const theory = ThCategory.Meta.theory
const theory_type = ThCategory.Meta.T
end
struct Ob{T} <: __module__.ObExpr{T} # T is :generator or a Symbol
args::Vector
type_args::Vector{GATExpr}
end
struct Hom{T} <: __module__.HomExpr{T}
args::Vector
type_args::Vector{GATExpr}
end
dom(x::Hom) = x.type_args[1]
codom(x::Hom) = x.type_args[2]
function compose(f::Hom, g::Hom; strict=true)
if strict && !(codom(f) == dom(g))
throw(SyntaxDomainError(:compose, [f, g]))
end
Hom{:compose}([f, g], [dom(f), codom(g)])
end
function id(x::Ob)
Ob{:id}([x], [x, x])
end
end
# default implementations
function ThCategory.dom(x::FreeCategory.Hom)::FreeCategory.Ob
FreeCategory.dom(x)
end
function ThCategory.Ob(::Type{FreeCategory.Ob}, __value__::Any)::FreeCategory.Ob
FreeCategory.Ob{:generator}([__value__], [])
end
function ThCategory.id(A::FreeCategory.Ob)::FreeCategory.Hom
FreeCategory.id(A)
end
function ThCategory.compose(f::FreeCategory.Hom, g::FreeCategory.Hom; strict=true)
associate_unit(FreeCategory.compose(f, g; strict), id)
end
```

## Utilities

`GATlab.Util.MetaUtils`

— ModuleGeneral-purpose tools for metaprogramming in Julia.

`GATlab.Util.MetaUtils.JuliaFunctionSigNoWhere`

— TypeFor comparing JuliaFunctionSigs modulo the where parameters

`GATlab.Util.MetaUtils.concat_expr`

— MethodConcatenate two Julia expressions into a block expression.

`GATlab.Util.MetaUtils.generate_docstring`

— MethodWrap Julia expression with docstring.

`GATlab.Util.MetaUtils.generate_function`

— MethodGenerate Julia expression for function definition.

`GATlab.Util.MetaUtils.parse_docstring`

— MethodParse Julia expression that is (possibly) annotated with docstring.

`GATlab.Util.MetaUtils.parse_function`

— MethodParse Julia function definition into standardized form.

`GATlab.Util.MetaUtils.parse_function_sig`

— MethodParse signature of Julia function.

`GATlab.Util.MetaUtils.replace_symbols`

— MethodReplace symbols occuring anywhere in a Julia expression.

`GATlab.Util.MetaUtils.replace_symbols`

— MethodReplace symbols occurring anywhere in a Julia function (except the name).

`GATlab.Util.MetaUtils.strip_lines`

— MethodRemove all LineNumberNodes from a Julia expression.