Ascent is a logic programming language (similar to Datalog) embedded in Rust via macros.
```Rust ascent!{ relation edge(i32, i32); relation path(i32, i32);
path(x, y) <-- edge(x, y); path(x, z) <-- edge(x, y), path(y, z); } ```
bash
cargo new my-ascent-project
cd my-ascent-project
ascent as a dependency in Cargo.toml:
toml
[dependencies]
ascent = {git = "https://github.com/s-arash/ascent"}
# or:
# ascent = "0.1"
Write some Ascent code in main.rs. Here is a complete example:
```rust
use ascent::ascent;
ascent!{
relation edge(i32, i32);
relation path(i32, i32);
path(x, y) <-- edge(x, y); path(x, z) <-- edge(x, y), path(y, z); }
fn main() { let mut prog = AscentProgram::default(); prog.edge = vec![(1, 2), (2, 3)]; prog.run(); println!("path: {:?}", prog.path); } ```
bash
cargo run
Ascent supports computing fixed points of user-defined lattices. The lattice keyword defines a lattice in Ascent. The type of the final column of a lattice must implement the Lattice trait. A lattice is like a relation, except that when a new lattice fact (v1, v2, ..., v(n-1), vn) is discovered, and a fact (v1, v2, ..., v(n-1), v'n) is already present in the database, vn and v'n are joined together to produce a single fact.
This feature enables writing programs not expressible in Datalog. For example we can use this feature to compute the lengths of shortest paths between nodes in a graph.
```Rust
ascent!{
lattice shortest_path(i32, i32, Dual
shortest_path(x, y, Dual(*w)) <-- edge(x, y, w);
shortestpath(x, z, Dual(w + l)) <-- edge(x, y, w), shortestpath(y, z, ?Dual(l)); } ```
In this example, Dual<T> is the dual of the lattice T. We use Dual<T> because we are interested in shortest paths, given two path lengths l1 and l2 for any given pair of nodes, we only store min(l1, l2).
The syntax is designed to be familiar to Rust users. In this example, edge is populated with non-reflexive edges from node. Note that any type that implements Clone + Eq + Hash can be used as a relation column.
```Rust
ascent!{
relation node(i32, Rc
edge(x, y) <-- node(x, neighbors), for &y in neighbors.iter(), if x != y; } ```
Ascent supports stratified negation and aggregation. Aggregators are defined in ascent::aggregators. You can find sum, min, max, count, and mean there.
In the following example, the average grade of students is stored in avg_grade:
```Rust use ascent::aggregators::*; type Student = u32; type Course = u32; type Grade = u16; ascent!{ relation student(Student); relation coursegrade(Student, Course, Grade); relation avggrade(Student, Grade);
avggrade(s, avg as Grade) <-- student(s), agg avg = mean(g) in coursegrade(s, _, g); } ```
You can define your own aggregators if the provided aggregators are not sufficient. For example, an aggregator for getting the 2nd highest value of a column can have the following signature:
Rust
fn second_highest<'a, N: 'a>(inp: impl Iterator<Item = (&'a N,)>) -> impl Iterator<Item = N>
where N: Ord + Clone
Aggregators can even be parameterized! For an example of a parameterized aggregator, lookup the definition of percentile in ascent::aggregators.
ascent_run!In addition to ascent!, we provide the ascent_run! macro. Unlike ascent!, this macro evaluates the ascent program when invoked. The main advantage of ascent_run! is that local variables are in scope inside the Ascent program. For example, we can define a function for discovering the (optionally reflexive) transitive closure of a relation like so:
Rust
fn tc(r: Vec<(i32, i32)>, reflexive: bool) -> Vec<(i32, i32)> {
ascent_run!{
relation r(i32, i32) = r;
relation tc(i32, i32);
tc(x, y) <-- r(x, y);
tc(x, z) <-- r(x, y), tc(y, z);
tc(x, x), tc(y, y) <-- if reflexive, r(x, y);
}.tc
}
In the above example, we initialize the relation r directly to shorten the program.