algebraicjulia / catlab.jl Goto Github PK

GraphViz.jl has broken since Julia v0.7. It seems to be unmaintained and it is beyond my powers to maintain it.

The simplest way forward is to remove the optional dependency on GraphViz.jl and call dot directly as in this project.

This would allow reflection capabilities for instances, plus lead to a cleaner solution of #4.

Typeclass.jl does this, inspired by Graphs.jl.

Support horizontal (left-to-right) layout of Graphviz wiring diagrams.

Mainly a matter of creating suitable HTML-like labels.

When you make wiring diagrams that use mcopy or create, you don't get any visual indication of that happening in graphviz diagram. Is this a limitation of GraphViz, or am I doing something wrong?

As @jpfairbanks has pointed out in #2, Catlab includes a Formula data type for representing mathematical expressions (e.g. sin(x) or x^2+1) as expression trees. Catlab is not trying to be a conventional computer algebra system like Mathematica or SymPy. Rather, this data type exists to facilitate communication with such systems.

The package ModelingToolkit.jl also has a data type for expressions, as do presumably other packages in the Julia ecosystem. Is it possible to converge on a shared representation?

Currently the code for parsing and code generation are fused together in the @signature and @syntax macros. There should be a clean separation between the macros and the underlying functionality. This will enable a programmatic API for creating, inspecting, and manipulating signatures and syntax systems.

Related to but more general than #5

Support nested wiring diagrams in wiring diagram layout and draw them in the Compose.jl and TikZ backends.

This would enable visualizing wiring diagrams for (non-compact) closed monoidal categories, the most important example being cartesian closed categories. Interest expressed in #12.

We don't have much long-form documentation yet, but the API docs, in the form of docstrings, aren't bad. I should use https://github.com/JuliaDocs/Documenter.jl to generate nice HTML documentation.

As of #35 and #38, we have basic support for converting wiring diagrams representing morphisms in a symmetric monoidal category into syntactic expressions. Extend this support to wiring diagrams with copies, merges, deletions, and creations, corresponding to morphisms in (co)cartesian categories and related doctrines.

The Julia Actions organization has lots of info on how to do this. Documenter.jl also has instructions.

Use Requires.jl, instead of my hacked together @optional_import macro, to integrate with optional dependencies like GraphViz.jl and TikzPictures.jl.

Since Julia v0.7, the Nullable{T} type has been moved from base Julia to an external package, in favor of writing Union{T,Nothing}.

Unfortunately, the more pleasant syntax T? for such "maybe types" has not yet arrived (see JuliaLang/julia#22682). When it does, we should migrate from Nullables to maybe types.

It is inconvenient to write

A = ob(FreeCategory, :A)
B = ob(FreeCategory, :B)
f = hom(:f, A, B)
...

when working interactively or writing unit tests. Create a macro for defining generators and injecting them into the global namespace.

Analogous to the var function in SymPy.

There are several places in the macro code--GAT.parse_signature_body and Meta.parse_function--where we discard any user supplied docstrings. We should keep them and re-attach them in an appropriate place.

The implementation in Catlab is

@signature MonoidalCategoryWithDiagonals(Ob,Hom) => BicategoryRelations(Ob,Hom) begin
  # Dagger category.
  dagger(f::Hom(A,B))::Hom(B,A) <= (A::Ob,B::Ob)
  
  # Self-dual compact closed category.
  dunit(A::Ob)::Hom(munit(), otimes(A,A))
  dcounit(A::Ob)::Hom(otimes(A,A), munit())
end

but your paper Knowledge Representation in the Bicategory of Relations has this table

It looks like a lot of this is missing, like codiagonal and logical. Are these morphisms defined somewhere else? It looks like AbelianBicategoryRelations has the codiagonal but it is called plus/coplus instead of merge/copy.

@signature BicategoryRelations(Ob,Hom) => AbelianBicategoryRelations(Ob,Hom) begin
  # Second diagonal and codiagonal.
  mplus(A::Ob)::Hom(otimes(A,A),A)
  mzero(A::Ob)::Hom(munit(),A)
  coplus(A::Ob)::Hom(A,otimes(A,A))
  cozero(A::Ob)::Hom(A,munit())
end

Is that understanding right?

Multiple inheritance of signatures would be useful in many situations, e.g. to say that dagger compact category inherits from both dagger category and compact closed category. As usual in these matters, we must handle diamond inheritance, precedence, etc.

Creating terms in a syntax system is simple for users but difficult to do in a generic programmatic way, due to issues like the names of generator constructors and the occasional need to dispatch on expression type. This leads to code as in commit 73f9fa0. There should be a simple, efficient way to do this without crawling the module object.

Somewhat related to #5.

We now have several Jupyter notebooks providing long-form, tutorial-style documentation. They do not version control cleanly, and it is easy to forget to update them, because executing them is not part of the build process.

I think Literate.jl, which is reminiscent of R Markdown, could provide a good solution to both problems. We can generate and execute Juypter notebooks during the build process, and also generate Markdown files suitable for Documenter.jl.

I think this is a bug in v0.3.

MWE:
The following code returns a MethodError: no method matching dagger(::WiringDiagram)

X,Y = Ob(FreeBicategoryRelations, :X, :Y)
f = Hom(:f, X,Y)
to_wiring_diagram(f) #works
to_wiring_diagram(dagger(f)) #errors

Is this a real bug?

After a substituting a box with a wiring diagram (via substitute!), the new IDs of the boxes in the original diagram are undefined. In practice, they are determined by an implementation detail of LightGraphs. Instead, the order of the boxes should be preserved, meaning that if box i is replaced with a diagram with k boxes, the new boxes should have IDs i, ..., i+k-1.

This can be achieved in various ways, but ideally there would be some support for it in LightGraphs (see sbromberger/LightGraphs.jl#1246) and MetaGraphs.

Abstract wiring diagrams use an attributed digraph as internal data structure. When I first implemented abstract wiring diagrams, there was no standard data structure for attributed graphs, so I hacked up the abandoned Networks.jl:

https://github.com/epatters/Catlab/blob/d12ebff8a73932f7a429ebca4988da96fe990a60/src/diagram/external/Networks.jl

Since then, the MetaGraphs.jl package has been created by the JuliaGraphs community. I should switch to it.

Hi @epatters, this package looks awesome and I am interested in using it, is there anything blocking an update to Julia 1.0?

The syntax system needs expressions for representing equality between morphisms or other terms. In a bicategory of relations, we also need expressions for subsumptions.

Both equalities and subsumptions can be thought of as 2-morphisms in a locally posetal 2-category. Thus, it's natural to reuse the existing GAT and syntax machinery. The main issue to address is that the 2-morphisms are "unnamed": there exists at most one equality between two terms.

We need a serialization format for expressions. Dependent types make the situation more complicated than usual in computer algebra. To start, we can explicitly represent all generator definitions in the expression, skirting the issue of redundancy and size blowup that can arise with presentations.

The (de)serialization logic should be very similar to the existing functor() method; we should try to reuse or abstract it.

As for the format itself, let's start with S-expressions encoded as JSON.

Adopt GraphML as the standard serialization format for wiring diagrams. It is the only graph serialization format I know of that is both

• reasonably well supported by existing tools (NetworkX, yEd, etc.), and
• supports the advanced features required for wiring diagrams, namely ports and nested graphs.

The recent support for converting wiring diagrams to syntactic expressions suggests an interesting new algorithm laying out wiring diagrams:

1. Convert the diagram into an expression.
2. Use the tree structure of the expression to recursively lay out the subdiagrams.

The algorithm will differ substantially from Graphviz's layered-based drawing. It will be closer to algorithms for drawing series-parallel digraphs (Di Battista et al, 1999, Graph drawing, Sec 3.2: Series-parallel digraphs).

This project will require significant effort but is conceptually straightforward. There are three phases:

1. Write a backend-agnostic layout algorithm that computes the sizes and positions of the boxes and the end points and control points of the wires.
2. Create a TikZ backend, replacing the current Catlab.Graphics.TikZWiringDiagrams, which is hacky and bad and breaks TikZ. The only tricky part will be dealing with font metrics. Done correctly, the process will be automatic but the results publication-grade.
3. Create a new backend with minimal dependencies (no LaTeX or external programs), possibly based on Compose.jl.

The Diagram submodule includes code for both manipulating wiring diagrams as data structures and visualizing them using Graphviz, TikZ, etc. Split it into two submodules, say WiringDiagrams and Graphics.

@epatters, I would like to build programming languages from finitely presented SMCs. It looks like the Algebra.Networks module seems to be the best place to start. The goal would be one function L = language(::Presentation) which gives L::Language so that you can use a macro to define wiring diagrams in that category L. Then the @model macro would produce a Hom in the doctrine associated with the presentation object.

Here is an example of how it could work.

struct Presentation
    d::Doctrine
    obs::Vector{Ob{:generator}}
    homs::Vector{Hom{::generator}}
end

struct Language
   ...
end

p = Presentation(FreeBiproductCategory,
     Ob(FreeBiproductCategory, :A, :B, :C)
     [Hom(:f, A, B), Hom(:g, B, B), Hom(:h, otimes(B,B))]
)
L = language(p)
m = @model L (x[1], x[2]) begin
x[1] = f(x[1])
x[2] = g(x[2])
x[1] = h(x[1], x[2])
return x[1]
end
to_wiring_diagram(m) |> to_graphviz

to denote the hom expression m::Doctrine.Hom{T} = f\otimes g ; h
What would it take to get this working?

Write a respectable README explaining what this project is about.

I am wondering why support for the Julia LTS v1.0 was dropped. It being the current Long-term Support release seems like it should be supported in the package. Is there anything in the package that is only going to work in Julia v1.1?

Certain modules, such as for wiring diagrams, are approaching a reasonable degree of API stability. It would be good to improve the API docs. This means following the Julia docstring conventions and using Documenter.jl features such as @ref and @id, which I have not been consistently doing.

The Algebra module is misnamed. A purpose of the module is to make contact with conventional computer algebra (hence "algebra"), but category theory is also a branch of algebra, so the name on its own is totally ambiguous. Furthermore, the module has other purposes, such as code generation.

What this module is really about is generating concrete mathematical functions, typically real- or vector-valued, from morphism expressions or wiring diagrams. Currently the focus is on low-dimensional functions, but it could be straightforwardly expanded to include higher-dimensional ones (neural networks).

The new name should somehow reflect this.

All syntactic manipulations are hand-coded. We don't have very many yet, so it's not a big deal, but proceeding in this way will become increasingly annoying as we develop more capabilities. I'd like a generic rewriting system with all the good stuff: pattern matching, unification, etc.

The @syntax macro should support typed rewrite rules with a pleasant syntax, e.g., pattern => replacement.

The algebraic networks module includes experimental code for reverse-mode automatic differentiation, using ReverseDiffSource.jl. This package looks dead (no updates in two years) and has been broken since Julia v0.6.

We should either fix or rip out our auto-diff code. Unfortunately, it's not clear what to replace it with, as this corner of the Julia ecosystem is in churn right now.

Instances (@instance) cannot be documented because there is nothing to attach the docstring to. It should be possible to document them, even if it involves creating a stub type or module.

Currently all syntax systems get exactly one generator constructor for each type. In effect, this gives the free category on a countably infinite set of generators.

More flexibility is required. We might want only a single generator, or more generally a fixed set of generators, for a given type. We might want multiple kinds of generators for a single type, say numerical constants and symbols. All this should be possible.

Generate Graphviz DOT files for abstract wiring diagrams.

As a followup to #52, we should investigate whether loops in Julia programs can be converted into traces (feedback) in the wiring diagrams. In a cartesian monoidal category, traces are the same as fixed point operators and so are closely related to recursion and looping.

This question was raised on Twitter. Also mentioned was Conor McBride's Syrup, a pedagogical programming language for Boolean circuits with a strong flavor of monoidal categories. However, I can't find anything in the Syrup documentation about looping.

Companion issue to #39. In contrast to substitute!, there is some inherent arbitrariness to the order of the boxes created by encapsulate!, but it should at least be the case that encapsulating a contiguous sequence of boxes puts in the new box in the right place.

Currently, we use functions like read_graphml both to read from files and to read from a Julia object (XMLDocument), and similarly for write_graphml. This leaves no place for reading from a string.

I like how NetworkX handles this. Use read_ for reading from a file and parse_ for reading from a string or other object, and similarly for write_ and generate_. Adopt this convention across the project.

The TikZ wiring diagrams now look pretty good, with one important exception: the placement of wire decorations (arrowheads, in compact closed categories; labels, in general) is poor. As a result, manual adjustment of the labels is sometimes needed for complex diagrams.

The problem arises because correct placement of wire decorations is not functorial, unlike the rest of rendering algorithm. Rather, decoration placement is a global operation. For example, a composition of identity morphisms should get a single label and/or arrow, not one for each identity in the composition.

Abstract wiring diagrams should support arbitrary graph-level data, just like boxes support node-level data and wires support edge-level data, through a value attribute.

In GraphML, this data will be stored as <data> sub-elements of <graph>.

We now have code to serialize wiring diagrams as GraphML, JSON, and, via semanticflowgraph, also RDF. We can also export wiring diagrams in Graphviz dot format.

Currently all these methods use their own schemes for assigning IDs to boxes, ports, and wires. This should be done in a consistent way, because consistency is a good thing and, more importantly, to allow cross-referencing between formats, e.g., when attaching a layout computed by Graphviz to another format.

Is there a doctrine for Hypergraph Categories?

https://golem.ph.utexas.edu/category/2018/02/hypergraph_categories_of_cospa.html

Draw outer boxes and nested wiring diagrams in Graphviz. The following technique may be helpful:

https://web.archive.org/web/20171106012412/http://www.graphviz.org:80/content/point-edge-cluster

Followup to #11.

We want a module for converting morphisms in a symmetric monoidal category to and from programs, by which I mean expressions with variables in the style of type theory. This module will replace what is currently called Catlab.Algebra (#37), and will be called something like Catlab.Programs.

Desired features:

• Morphisms to expression trees, as in conventional CAS
  • Implemented by Formula type
  • See also #36
• Morphisms from expression trees
  • Not yet implemented
• Morphisms to Julia programs
  • Currently implemented as "algebraic networks"
  • Should be made more general, to support other code generation tasks
• Morphisms (as wiring diagrams) from Julia programs (in subset of Julia language)
  • Not yet implemented
  • See #51

I will follow up shortly with ideas about design and implementation.

In wiring diagrams, copies and merges are represented implicitly by multiple wires, while deletions and creations are represented by the absence of wires. This implicit representation is usually the most convenient (effectively giving normal forms for diagonals and codiagonals) but sometimes we want to make the morphisms explicit, representing them by junction nodes as in string diagrams.

Write a function to insert the junction nodes where appropriate. A good first step towards implementing both #42 and #43.

We should have a procedure to test for isomorphism of wiring diagrams and, when an isomorphism exists, exhibit the corresponding matchings of boxes and wires.

A possible approach is to first find an isomorphism of the underlying directed graphs, using existing software, and then check if the induced map on boxes is a wiring diagram isomorphism. At the time of this writing, LightGraphs has experimental support for isomorphism testing.

This would be a good first issue for someone who likes graph algorithms. It should require only a basic knowledge of Catlab's wiring diagram API.

I am running into some issues including Catlab as a dependency in one of my projects. I can confirm I am using Catlab v0.2.1. I'm not sure why this is happening when I include Catlab as a dependency in the project because the code seems to show Requests as a dependency. This is the error I am getting:

┌ Info: Precompiling Catlab [134e5e36-593f-5add-ad60-77f754baafbe]
└ @ Base loading.jl:1192
ERROR: LoadError: LoadError: ArgumentError: Package Catlab does not have Requires in its dependencies:
- If you have Catlab checked out for development and have
  added Requires as a dependency but haven't updated your primary
  environment's manifest file, try `Pkg.resolve()`.
- Otherwise you may need to report an issue with Catlab
Stacktrace:
 [1] require(::Module, ::Symbol) at ./loading.jl:836
 [2] include at ./boot.jl:317 [inlined]
 [3] include_relative(::Module, ::String) at ./loading.jl:1044
 [4] include at ./sysimg.jl:29 [inlined]
 [5] include(::String) at /home/micah/.julia/packages/Catlab/Eu6aA/src/Catlab.jl:1
 [6] top-level scope at none:0
 [7] include at ./boot.jl:317 [inlined]
 [8] include_relative(::Module, ::String) at ./loading.jl:1044
 [9] include(::Module, ::String) at ./sysimg.jl:29
 [10] top-level scope at none:2
 [11] eval at ./boot.jl:319 [inlined]
 [12] eval(::Expr) at ./client.jl:393
 [13] top-level scope at ./none:3
in expression starting at /home/micah/.julia/packages/Catlab/Eu6aA/src/graphics/Graphics.jl:4
in expression starting at /home/micah/.julia/packages/Catlab/Eu6aA/src/Catlab.jl:6

Failed to precompile Catlab [134e5e36-593f-5add-ad60-77f754baafbe] to /home/micah/.julia/compiled/v1.0/Catlab/fBQ1G.ji.

Stacktrace:
 [1] error(::String) at ./error.jl:33
 [2] compilecache(::Base.PkgId, ::String) at ./loading.jl:1203
 [3] _require(::Base.PkgId) at ./loading.jl:960
 [4] require(::Base.PkgId) at ./loading.jl:858
 [5] require(::Module, ::Symbol) at ./loading.jl:853
 [6] top-level scope at In[2]:1

When I add Catlab to the project using:

(v1.0) pkg> activate .                                                                                        
                                                                                                              
(SemanticModels) pkg> add Catlab

it gets added to the Manifest.toml like this, which does not have the Requires package in the dependency list:

[[Catlab]]
deps = ["AutoHashEquals", "DataStructures", "JSON", "LightGraphs", "LightXML", "Match", "MetaGraphs", "Nullables", "Parameters", "Pkg", "Reexport", "Test", "Unicode", "UnionFind"]
git-tree-sha1 = "c63918dd0fdc5b3e36461ca687a129e1103a5b62"
uuid = "134e5e36-593f-5add-ad60-77f754baafbe"
version = "0.2.1"

Wiring diagrams form an operad, and operadic composition is just substitution. The current imperative interface for substitution (substitute!, encapsulate!) should be complemented by a functional interface phrased in the language of operads (ocompose, maybe).

In order that the operad laws be satisfied, we will need to resolve #39.