open_hypergraphs/
lib.rs

1//! # Open Hypergraphs
2//!
3//! An
4//! [OpenHypergraph](crate::open_hypergraph::OpenHypergraph)
5//! is a [GPU-accelerated](#gpu-acceleration) datastructure for representing
6//! large networks (circuits) of operations having multiple inputs and outputs.
7//! For example:
8//!
9//! ```text
10//!       ─────────────┐    ┌───┐    ┌───┐
11//!                    └────│   │    │   │────
12//!                         │ + │────│ Δ │
13//!           ┌───┐    ┌────│   │    │   │────
14//!       ────│ - │────┘    └───┘    └───┘
15//!           └───┘
16//! ```
17//!
18//! The above term represents the expression `(x + (-y), x + (-y))`, where `Δ : 1 → 2` is an
19//! explicit copying operation.
20//! Note that multiple outputs are "native" to the representation: in the textual description, the
21//! arithmetic expression is repeated twice, while copying is explicit in the open hypergraph representation.
22//!
23//! # Theory & Example
24//!
25//! Open Hypergraphs are a representation of *cospans of hypergraphs* which correspond directly to
26//! morphisms of a symmetric monoidal category presented by generators and equations.
27//!
28//! Pragmatically, this means one can define a set of objects (e.g. types) and operations (e.g. functions),
29//! and represent terms over those generators.
30//!
31//! For example, we can define a simple expression language of arithmetic over integers and
32//! constrct the example term above as follows:
33//!
34//! ```rust
35//! use open_hypergraphs::prelude::*;
36//!
37//! #[derive(PartialEq, Eq, Debug, Clone, Copy)]
38//! enum Operation {
39//!     Negate,
40//!     Add,
41//!     Copy,
42//! }
43//!
44//! #[derive(PartialEq, Eq, Debug, Clone)]
45//! enum Object {
46//!     Int,
47//! }
48//!
49//! // Return the type (inputs and outputs) of the specified op
50//! fn op_type(op: Operation) -> (SemifiniteFunction<Object>, SemifiniteFunction<Object>) {
51//!     use Operation::*;
52//!     use Object::*;
53//!
54//!     // Objects (or "types") in an open hypergraph are *lists* of generating types.
55//!     // 'int' is the singleton list Int
56//!     let int = SemifiniteFunction::new(VecArray(vec![Int]));
57//!     // ... 'int2' is the list `Int ● Int` - the `●` denotes *tensor product* in the category;
58//!     // you can think of `X₁ ● X₂ ● ... ● Xn` as a list of generating objects `[X₁, X₂, ..., Xn]`.
59//!     let int2 = SemifiniteFunction::new(VecArray(vec![Int, Int]));
60//!
61//!     match op {
62//!         // `Negate : Int → Int` has 1 integer input and 1 integer output
63//!         Negate => (int.clone(), int),
64//!         // `Add : Int ● Int → Int` a binary operation
65//!         Add => (int2, int),
66//!         // `Copy : Int → Int ● Int` has a single integer input, but *two* outputs.
67//!         Copy => (int, int2),
68//!     }
69//! }
70//!
71//! // Create the OpenHypergraph corresponding to a given op
72//! fn op(op: Operation) -> OpenHypergraph<Object, Operation> {
73//!     let (s, t) = op_type(op);
74//!     OpenHypergraph::singleton(op, s, t)
75//! }
76//!
77//! // Construct the example term ((x + (-y), x + (-y))
78//! fn example_term() -> OpenHypergraph<Object, Operation> {
79//!     use Operation::*;
80//!     use Object::*;
81//!     let int = SemifiniteFunction::new(VecArray(vec![Int]));
82//!     let id = OpenHypergraph::identity(int);
83//!     id.tensor(&op(Negate)).compose(&op(Add)).unwrap().compose(&op(Copy)).unwrap()
84//! }
85//! ```
86//!
87//! # GPU Acceleration
88//!
89//! The
90//! [OpenHypergraph](crate::open_hypergraph::OpenHypergraph) datastructure is a flat, array-based
91//! representation which works on both CPU and GPU.
92//!
93//! Algorithms and datastructures are all parametrised by a type `K` implementing
94//! [ArrayKind](crate::array::ArrayKind).
95//! This type is used to represent a kind `K : * → *` rather than a concrete type.
96//! For example, the kind of [`Vec`]-backed arrays is given by
97//! [VecKind](crate::array::vec::VecKind),
98//! and type aliases for this backend are exported in
99//! [the prelude](crate::prelude).
100//!
101//! To add a new array backend, create a new type implementing
102//! [ArrayKind](crate::array::ArrayKind).
103
104pub mod array;
105pub mod category;
106pub mod finite_function;
107pub mod indexed_coproduct;
108pub mod operations;
109pub mod semifinite;
110
111pub mod hypergraph;
112pub mod open_hypergraph;
113
114pub mod eval;
115pub mod functor;
116pub mod layer;
117
118pub mod prelude {
119    //! Type alises for Open Hypergraphs using the [`VecKind`] array backend.
120    pub use crate::array::vec::*;
121    pub use crate::category::*;
122
123    pub type OpenHypergraph<Obj, Arr> = crate::open_hypergraph::OpenHypergraph<VecKind, Obj, Arr>;
124    pub type Hypergraph<Obj, Arr> = crate::hypergraph::Hypergraph<VecKind, Obj, Arr>;
125    pub type FiniteFunction = crate::finite_function::FiniteFunction<VecKind>;
126    pub type SemifiniteFunction<T> = crate::semifinite::SemifiniteFunction<VecKind, T>;
127    pub type IndexedCoproduct<F> = crate::indexed_coproduct::IndexedCoproduct<VecKind, F>;
128}
open_hypergraphs/lib.rs

open_hypergraphs/
lib.rs
