Ascent is a logic programming language (similar to Datalog) embedded in Rust via macros.
For more information, check out the CC paper on 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);
}
- Install Rust.
- Make a new Rust project:
cargo new my-ascent-project cd my-ascent-project
- Add
ascent
as a dependency inCargo.toml
:[dependencies] ascent = "0.2" # or: # ascent = {git = "https://github.com/s-arash/ascent"}
- Write some Ascent code in
main.rs
. Here is a complete example: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); }
- Run the program:
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 join
ed 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.
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));
}
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.
ascent!{
relation node(i32, Rc<Vec<i32>>);
relation edge(i32, i32);
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
:
use ascent::aggregators::*;
type Student = u32;
type Course = u32;
type Grade = u16;
ascent!{
relation student(Student);
relation course_grade(Student, Course, Grade);
relation avg_grade(Student, Grade);
avg_grade(s, avg as Grade) <--
student(s),
agg avg = mean(g) in course_grade(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:
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
.
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:
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.