8 unstable releases (3 breaking)
0.4.0  Aug 22, 2022 

0.3.0  Jun 18, 2022 
0.2.1  May 14, 2022 
0.2.0  Apr 1, 2022 
0.0.1 

#13 in Programming languages
515 downloads per month
70KB
1.5K
SLoC
Logic programming in Rust
Ascent is a logic programming language (similar to Datalog) embedded in Rust via macros.
For more information, check out the CC paper on Ascent.
Examples
Computing all the connected nodes in a graph
ascent! {
relation edge(i32, i32);
relation path(i32, i32);
path(x, y) < edge(x, y);
path(x, z) < edge(x, y), path(y, z);
}
Using Ascent
 Install Rust.
 Make a new Rust project:
cargo new myascentproject cd myascentproject
 Add
ascent
as a dependency inCargo.toml
:[dependencies] 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
Features
Lattices
Ascent supports computing fixed points of userdefined 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 (v_{1}, v_{2}, ..., v_{(n1)}, v_{n}) is discovered, and a fact (v_{1}, v_{2}, ..., v_{(n1)}, v'_{n}) is already present in the database, v_{n} 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)
.
Conditions and Generative Clauses
The syntax is designed to be familiar to Rust users. In this example, edge
is populated with nonreflexive 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;
}
Negation and Aggregation
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
.
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:
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.
Macro definitions
It may be useful to define macros that expand to either body items or head items. Ascent allows you to do this.
You can find more about macros in Ascent macros here.
Misc

#![measure_rule_times]
causes execution times of individual rules to be measured. Example:ascent! { #![measure_rule_times] // ... } let mut prog = AscentProgram::default(); prog.run(); println!("{}", prog.scc_times_summary());
Note that
scc_times_summary()
is generated for all Ascent programs. With#![measure_rule_times]
it reports execution times of individual rules too. 
With
#![generate_run_timeout]
, arun_timeout
function is generated that stops after the given amount of time. 
The feature
wasmbindgen
allows Ascent programs to run in WASM environments. 
struct
declarations can be added to the top ofascent!
definitions. This allows changing the name of the generated type and introduction of type/lifetime parameters and constraints.ascent! { struct GenericTC<N: Clone + Eq + Hash>; relation edge(N, N); // ... }
Dependencies
~1.6–3.5MB
~70K SLoC