ascent

Ascent supports computing fixed points of user-defined lattices using the lattice keyword. A lattice behaves like a relation, but when a new fact is discovered, the values in the final column are joined together using the Lattice trait implementation. This allows for computations like shortest paths.

Example using Dual<T> to find shortest paths (where Dual stores the minimum value):

ascent! {
   lattice shortest_path(i32, i32, Dual<u32>);
   relation edge(i32, i32, u32);

   shortest_path(x, y, Dual(*w)) <-- edge(x, y, w);

   shortest_path(x, z, Dual(w + l)) <-- 
      edge(x, y, w), 
      shortest_path(y, z, ?Dual(l));
}

Ascent supports a feature called "Bring Your Own Data Structures" (BYODS), which allows you to provide custom data structure implementations for logic programming tasks.

To learn how to implement and use custom data structures, refer to the steensgaard example located in the ascent-byods-rels/examples/steensgaard directory.

See example in: ./ascent-byods-rels/examples/steensgaard

Ascent is a logic programming language embedded in Rust via macros. To use it, follow these steps:

1. Ensure Rust is installed.
2. Create a new project: cargo new my-ascent-project && cd my-ascent-project.
3. Add ascent to your Cargo.toml dependencies:

   [dependencies]
   ascent = "*"

4. Use the ascent! macro in your source code to define relations and rules.

cargo new my-ascent-project
cd my-ascent-project
# Add ascent = "*" to Cargo.toml

BYODS (Bring Your Own Data Structures) allows relations to be backed by optimized custom data structures using the #[ds(...)] attribute. This can significantly improve algorithmic complexity.

Example using trrel_uf from the ascent-byods-rels crate to optimize transitive closure:

Dependencies:

[dependencies]
ascent-byods-rels = "*"
ascent = "*"

use ascent_byods_rels::trrel_uf;

ascent! {
   relation edge(Node, Node);
   
   #[ds(trrel_uf)] // Makes the relation transitive
   relation path(Node, Node);
   
   path(x, y) <-- edge(x, y);
}

Depending on the required access pattern, you can wrap a TrRelIndCommon<T> in different reader types that implement the RelIndexRead and RelIndexReadAll traits:

• TrRelInd0: Optimized for reading by a single key T. index_get returns an iterator over all y such that (x, y) exists.
• TrRelInd1: Optimized for reading by the second element (reverse lookup). index_get returns an iterator over all x such that (x, y) exists.
• TrRelIndFull: Provides full access to the relation. Supports contains_key for checking if a specific (x, y) tuple exists and iter_all to iterate over every tuple in the relation.
• TrRelIndNone: A fallback reader that iterates over all tuples via a flat map, used when specific indexing is not applicable.

To find elements that have been added to an equality relation since its last 'freeze' or state change, you can use the following methods on CEqRelIndCommon<T>:

• Synchronous: Use iter_all_added() to get an iterator over pairs (&T, &T) that exist in the current combined state but were not present in the old state.
• Parallel: Use c_iter_all_added() to get a ParallelIterator (via rayon) for high-performance processing of added elements across multiple threads.

These methods are useful for incremental updates where you only want to process the delta between two states of the relation.

The BinRelToTernary struct is used to represent a ternary relation $(T_0, T_1, T_2)$ by mapping a primary key $T_0$ to a binary relation TBinRel between $T_1$ and $T_2$.

It supports optional reverse indexing for efficient lookups on $T_1$ and $T_2$ via reverse_map1 and reverse_map2 respectively. This is useful when you need to query the relation by any of its three components.

use ascent::internal::ToRelIndex;
// T0, T1, T2 must implement Clone + Hash + Eq
// TBinRel must implement ByodsBinRel<T0 = T1, T1 = T2>
let ternary_rel = BinRelToTernary::<T0, T1, T2, TBinRel> {
    map: my_hashmap,
    reverse_map1: Some(my_reverse_map1),
    reverse_map2: Some(my_reverse_map2),
};

In the ascent-byods-rels package, TrRel2IndCommon<T0, T1> serves as the underlying storage structure for ternary relations. It uses a HashMap to map a primary key T0 to a relation containing pairs of T1. It can optionally maintain reverse maps (reverse_map1 and reverse_map2) to allow efficient querying by the second or third elements of the ternary relation.

Key components:

• map: HashMap<T0, TrRelIndCommon<T1>>
• reverse_map1: Option<HashMap<T1, AltHashSet<T0>>> (maps T1 to sets of T0)
• reverse_map2: Option<HashMap<T1, AltHashSet<T0>>> (maps T1 to sets of T0)