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.
In addition, this OOPSLA paper describes the "Bring Your Own Data Structures to Datalog" aspect of Ascent.
See the ascent/examples directory for a more complete set of examples.
ascent! {
relation edge(i32, i32);
relation path(i32, i32);
path(x, y) 1, 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.
```Rust
ascent! {
lattice shortest_path(i32, i32, Dual);
relation edge(i32, i32, u32);
shortest_path(x, y, Dual(*w)) ` is the dual of the lattice `T`. We use `Dual` 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)`.
### Parallel Ascent
Ascent is capable of producing parallel code. The macros `ascent_par!` and `ascent_run_par!` produce parallelized code.
Naturally, column types must be `Send + Sync` to work in parallel Ascent.
Parallel Ascent utilizes [`rayon`](https://crates.io/crates/rayon), so the parallelism level can be controlled either via `rayon`'s [`ThreadPoolBuilder`](https://docs.rs/rayon/latest/rayon/struct.ThreadPoolBuilder.html) or using the `RAYON_NUM_THREADS` environment variable (see [here](https://github.com/rayon-rs/rayon/blob/master/FAQ.md#how-many-threads-will-rayon-spawn) for more info).
### BYODS
BYODS (short for [Bring Your Own Data Structures to Datalog](https://dl.acm.org/doi/pdf/10.1145/3622840)) is a feature of Ascent that enables relations to be backed by custom data structures. This feature allows improving the algorithmic complexity of Ascent programs by optimizing the data structures used to back relations. For example, a program that requires transitive closure computation of a large graph could improve its performance by choosing a union-find based data structure `trrel_uf` (defined in [`ascent-byods-rels`](https://crates.io/crates/ascent-byods-rels)) for the transitive closure relation:
in `Cargo.toml`:
```toml
[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) , reflexive: bool) -> Vec {
ascent_run! {
relation r(i32, i32) = r;
relation tc(i32, i32);
tc(x, y) );
relation edge(i32, i32);
edge(x, y) (inp: impl Iterator) -> impl Iterator
where N: Ord + CloneAggregators can even be parameterized! For an example of a parameterized aggregator, lookup the definition of percentile in ascent::aggregators.
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.
ascent_source! and include_source!You can write Ascent code inside ascent_source! macro invocations and later include them in actual Ascent programs.
This allows reusing your Ascent code across different Ascent programs, and composing Ascent programs from different code "modules".
mod ascent_code {
ascent::ascent_source! { my_awesome_analysis:
// Ascent code for my awesome analysis
}
}
// elsewhere:
ascent! {
struct MyAwesomeAnalysis;
include_source!(ascent_code::my_awesome_analysis);
}
ascent_par! {
struct MyAwesomeAnalysisParallelized;
include_source!(ascent_code::my_awesome_analysis);
}
#![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], a run_timeout function is generated that stops after
the given amount of time.
The feature wasm-bindgen allows Ascent programs to run in WASM environments.
struct declarations can be added to the top of ascent! definitions. This allows changing the
name and visibility of the generated type and introduction of type/lifetime parameters and constraints.
ascent! {
struct GenericTC;
relation edge(N, N);
// ...
}Hint: If you get a "private type ... in public interface (error E0446)" warning, you can fix it by making the generated Ascent type private, as done in the above example.
No open issues yet, or sync has not completed.