ACSet Refactor

[olynch]

At its core, an acset is just

• A finite set of primary keys for each object in the schema
• A FinDomFunction for every morphism, (which can be indexed)

I think that we should embrace this simplicity, and move to a struct acset that has two fields:

• parts: a named tuple indexed on objects that gives a FinSet for each object
• subparts: a named tuple indexed on morphisms that gives a FinDomFunction for each morphism. I don't know if we have this for FinDomFunctions, but we should have indexing happening at the morphism level, instead of at the acset level; there should be an interface for morphisms that allows mutating them, and then morphisms that are indexed will handle their own indexing. This should not affect performance too much, and it will be hugely simpler to implement.

As optimizations, we may want to use something slightly different than the existing FinDomFunction, which stores its domain and codomain, because we already store the domain and codomain somewhere else, but the basic idea still holds.

At declaration time (i.e. @acset_type) one can choose the concrete types of each FinDomFunction for each morphism as well as the concrete types of each FinSet for each object.

This refactor will probably only affect CSetDataStructures, and will not result in the breakage of any external interfaces.

Benefits will include:

• It will be straightforwards to implement GPUACSets (pronounced juhpowchets), via just making FinDomFunctions that have as backing storage CUDAArrays, or similary
• This will cover the use case of LACSets: LACSets will simply be acsets whose primary keys are a FinSet of symbols, or perhaps a FinSet of tuples of symbols, etc. Additionally, limits will be delegated to the FinSet level: if we say that the product of two FinSets of symbols is a FinSet of pairs of symbols, this will be automatically propagated to the acset level.
• This approach will straightforwardly generalize into functors from C to Rel,Vect, etc, or 2-functors into Pos (by assigning each object to a poset).
• We will be able to try out different indexing strategies to optimize performance
• Serialization of acsets will seamlessly delegate to serialization of the underlying FinDomFunctions, which can be tuned easily.

[epatters]

I don't know if we have this for FinDomFunctions, but we should have indexing happening at the morphism level

I believe we do have indexing for both FinFunctions and FinDomFunctions, first implemented for the sake of conjunctive queries on C-sets.

[olynch]

Oh, awesome!

[epatters]

Anyway, I like the idea of this design!

[jpfairbanks]

I like this refactor too. I think pushing more responsibility onto the FinFunctions makes sense and we should keep an eye to alternative semantics while you design this. Doing C-Markov or C-Poset should be able to reuse a lot of the schema handling code. If we build more of the ACSet code on top of clearer expectations about what interface the components have to provide, then we might be able to get started on what part of the ACSet implementation is semantics independent.

[epatters]

This has been effectively accomplished #681, except that instead of refactoring acsets to use FinFunctions, acsets use Columns, which are "functions without (co)domains" but with support for indexing. FinFunctions will then be refactored to use columns (#706).