Ascent: a Datalog style logic language embedded in Rust macros

Datalog rules written as a Rust macro

Ascent is a logic programming language, similar to Datalog, embedded in Rust via macros. That single sentence contains the whole design, and the interesting part is the embedding rather than the logic.

A program declares relations and the rules that populate them, and the macro turns that declaration into Rust code that computes a fixed point. The smallest example in the documentation computes the connected nodes of 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);
}

The syntax is deliberately close to Datalog, with a less-than sign and two hyphens for the rule arrow, and the relation declarations name the types of the columns. The rules are read left to right as consequences: a path exists if there is an edge, and a longer path exists if there is an edge followed by a path.

What makes it more than a Datalog interpreter is that the rules are compiled by a macro rather than interpreted at runtime, and the project is documented in two academic papers. The first is a CC paper on Ascent and on deductive inference via macros, and the second is an OOPSLA paper on the bring your own data structures to Datalog aspect. That is a useful signal about what kind of project this is: a research vehicle that happens to be usable, written by someone comfortable in the type theory literature.

Writing and running your first program

The getting started instructions are five steps, and they assume a Rust toolchain already exists.

The first step is to create a new project.

   cargo new my-ascent-project
   cd my-ascent-project

The second is to add the dependency, and the readme shows the manifest entry.

[dependencies]
ascent = "*"

The wildcard version is what the documentation shows, and it is not what you would put in a production manifest. The workspace manifest in the repository pins the version at 0.8.1, with the internal crates wired as path dependencies and the published version kept in step, so a real project should pin an explicit version rather than accept whatever is newest.

The third step is to write the program, and the complete example in the readme shows both the rules and how they are driven from Rust.

   fn main() {
      let mut prog = AscentProgram::default();
      prog.edge = vec![(1, 2), (2, 3)];
      prog.run();
      println!("path: {:?}", prog.path);
   }

The macro generates a struct named after the program, with one field per relation. You populate the input relations as ordinary Rust values, call run, and read the derived relations back off the struct. The fourth step is simply to run it.

   cargo run

That last detail is the part worth pausing on. The deduction is not a separate program you invoke, and it is not a query you send to a running service. It is code that is compiled into your binary, which is why the paper describes the approach as seamless deductive inference via macros.

Lattices: the part that goes beyond Datalog

Ascent supports computing fixed points of user-defined lattices, and this is the feature the documentation singles out as enabling programs that are not expressible in Datalog.

The mechanism is a keyword and a trait. The lattice keyword defines a lattice in Ascent, and the type of the final column of a lattice must implement the Lattice trait. A lattice behaves like a relation, except that when a new fact is discovered and a fact with the same leading columns is already in the database, the two final values are joined together to produce a single fact.

The documented example computes the lengths of shortest paths between nodes.

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));
}

The Dual type is the dual of the lattice, and the readme explains why it is used: given two path lengths for the same pair of nodes, only the minimum is kept. The pattern is a well known one in the shortest path literature, where a semiring is paired with its dual so that one pass handles both minimisation and maximisation, and the query syntax with the question mark on the second occurrence of the lattice is what selects the dual behaviour at that point in the rule.

For a reader who has written these fixpoint loops by hand, the value proposition is that the lattice algebra is expressed in types, and the compiler can check that the rules respect it. For a reader who has not, the Lattice trait is the thing to read first, because it is the contract your own types have to satisfy.

Parallel Ascent runs on rayon

Ascent is capable of producing parallel code, and the mechanism is a pair of macros. The ascent_par! macro produces a parallelised program, and ascent_run_par! is the parallel counterpart of the run macro.

The constraint is a type constraint rather than a flag. Column types must be Send and Sync for the parallel version to work, which is the honest requirement, because the generated code moves data between worker threads.

The parallelism itself comes from rayon, and the documentation says the level can be controlled either through rayon's ThreadPoolBuilder or with the RAYON_NUM_THREADS environment variable. That is a nice property for a library, because it means the number of workers is not baked into the generated program. An application that already uses rayon for other work can share a pool, and an operator can tune the thread count in a deployment without a rebuild.

The practical caution is that parallel deduction is a different performance story from parallel iteration. A fixpoint computation has a dependency structure, and work cannot start before its inputs are known, so the speedup depends on how much of the rule set can be evaluated independently. The readme does not quantify that, and the honest way to find out is to try the same program in both modes.

BYODS: choosing the data structure behind a relation

BYODS, short for bring your own data structures to Datalog, is the feature that the OOPSLA paper describes and the part of Ascent most likely to matter for real workloads.

The idea is that relations in a Datalog program do not have to be stored in a default structure. BYODS enables relations to be backed by custom data structures, and the documentation frames the benefit as improving the algorithmic complexity of Ascent programs by optimising the data structures used to back relations.

The example given is a transitive closure over a large graph, which is exactly the case where the default representation is wasteful, since a transitive closure relation has quadratically many facts. The union-find based structure is called trrel_uf and lives in a separate crate, ascent-byods-rels, which is added as its own dependency.

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

The relation is then marked with an attribute that names the provider.

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);
}

The attribute directs the Ascent compiler to use the data structure provider defined in that module for the path relation. The documentation links a complete example that dramatically speeds up Ascent computations, in the byods directory of the repository, and a separate BYODS.MD document with the details.

The cost of the feature is that you are now writing a trait implementation that the compiler relies on, so the correctness of the speedup depends on that implementation, and the maintenance cost moves onto whoever provides the data structure.

ascent_run!, conditions, negation and aggregation

Three smaller features complete the language surface, and each of them addresses something a Datalog user would otherwise have to work around.

The ascent_run! macro evaluates the ascent program when it is invoked, and its main advantage is that local variables are in scope inside the program. The documentation uses this to write a function that discovers the optionally reflexive transitive closure of a relation.

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
}

Conditions and generative clauses are the second feature. The syntax is designed to be familiar to Rust users, and the example populates an edge relation from a node relation using a for loop over the neighbours and an if condition, which is the escape hatch for rules that are not pure conjunctions. Any type that implements Clone, Eq and Hash can be used as a relation column, which is a looser bound than you might expect and means your own domain types can be stored directly.

The third is negation and aggregation. Ascent supports stratified negation and aggregation, with the aggregators defined in the ascent::aggregators module, where sum, min, max, count and mean are provided. The documentation shows the average grade of students stored in a relation, which is the canonical example of an aggregate over a join.

Stratified is the operative word for negation. It means negation is allowed where the program structure permits it, rather than for arbitrary rules, and that restriction is what keeps the fixed point computation well defined.

Where Ascent is the wrong tool

Four limitations, and the first one is about packaging rather than the language.

The project publishes no GitHub releases. The crate is on crates.io and the workspace version is 0.8.1, so a version exists, but there is no tagged release history in the repository to point at, and the documentation itself shows a wildcard dependency version, which is a signal that the versioning story is not the project's strongest suit. For a research crate that is fine. For a dependency in a service that has to be reproducible and auditable, it is friction you have to absorb.

The second is that the whole thing is macro based, and the cost of that is in the error messages. A mistyped rule or a type mismatch becomes a compilation error inside a macro expansion, and the diagnostics you get are the compiler's view of generated code rather than a message about the rule you wrote. For a language that is still pre-1.0, that is a real tax on learning.

The third is the size of the commitment. Lattices require you to implement a trait, BYODS requires you to implement a data structure provider, and both are contracts with the compiler. The payoff is real for the problems those features were designed for, and it is disproportionate for a problem that a twenty line fixpoint loop would solve.

The fourth is scope of use. Ascent computes relations and fixed points. It is not a query language over your existing data, it does not integrate with a database, and it is not a replacement for a workflow engine. If what you want is to express a rule once and have it applied to data that already lives somewhere else, this is the wrong level of abstraction.

The repository layout also hints at the project's character: the workspace members are the byods crate and the three core crates, with separate test and WebAssembly test directories excluded from the workspace, and alongside them sit MACROS.MD, BYODS.MD and a changelog. This is a well documented research implementation, and the documentation is where the answers are.

Editorial conclusion

Ascent is the right tool for a Rust engineer who needs a declarative layer over a graph, a dependency graph or a set of constraints and wants the rules to be checked and optimised at compile time, and for research work on incremental deduction. It is the wrong tool for a production service that needs a stable dependency with tagged releases, and for a problem where a hand written fixpoint loop would be twenty lines. Before adopting, read MACROS.MD and BYODS.MD, check that the crate version on crates.io matches the 0.8.1 in the workspace, and try one of the examples in the ascent/examples directory before you commit to the macro based workflow.

Frequently asked questions

Official sources

1. Issues
2. License: MIT
3. README
4. s-arash/ascent on GitHub