7 releases
0.2.5 | Feb 16, 2022 |
---|---|
0.2.4 | Jan 19, 2022 |
0.1.0-dev | Dec 3, 2021 |
#949 in Parser implementations
430KB
7.5K
SLoC
Crate asdi
Another Simplistic Datalog Implementation (in Rust).
This package provides a data model to represent Datalog programs in memory, a parser for the textual representation, and some evaluation implementations. For more information see the ASDI book.
The text representation parser is a separate feature, so if you only need to construct and evaluate programs using the API you may opt out of the Pest parser and support.
Status
- Library API mostly stable, the next effort will be to make the construction API more ergonomic.
- Library Documentation good top-level documentation but very little else right now.
- Parser full support for the core language as well as pragmas, require more unit tests.
- I/O relations are now connected to the file input/output pragmas, the
io
module includes traits for reading/writing relations as well as basic JSON and CSV support. - Evaluation currently have a naïve and a stratified semi-naïve implementation.
Example
parent(xerces, brooke).
parent(brooke, damocles).
ancestor(X, Y) ⟵ parent(X, Y).
ancestor(X, Y) ⟵ parent(X, Z) ⋀ parent(Z, Y).
?- ancestor(xerces, X).
use asdi::edb::{Attribute, Predicate};
use asdi::idb::{Atom, Query, Term, Variable};
use asdi::Program;
use std::str::FromStr;
fn ancestor_example() {
// See https://en.wikipedia.org/wiki/Datalog
let mut ancestors = Program::default();
let parent_predicate = Predicate::from_str("parent").unwrap();
{
let parent = ancestors
.add_new_relation(
parent_predicate.clone(),
vec![Attribute::string(), Attribute::string()],
)
.unwrap();
parent
.add_as_fact(["xerces".into(), "brooke".into()])
.unwrap();
parent
.add_as_fact(["brooke".into(), "damocles".into()])
.unwrap();
};
let ancestor_predicate = Predicate::from_str("ancestor").unwrap();
let var_x: Term = Variable::from_str("X").unwrap().into();
let var_y: Term = Variable::from_str("Y").unwrap().into();
let var_z: Term = Variable::from_str("Z").unwrap().into();
ancestors
.add_new_rule(
ancestor_predicate.clone(),
[var_x.clone(), var_y.clone()],
[Atom::new(parent_predicate.clone(), [var_x.clone(), var_y.clone()]).into()],
)
.unwrap();
ancestors
.add_new_rule(
ancestor_predicate.clone(),
[var_x.clone(), var_y.clone()],
[
Atom::new(parent_predicate, [var_x.clone(), var_z.clone()]).into(),
Atom::new(ancestor_predicate.clone(), [var_z, var_y]).into(),
],
)
.unwrap();
ancestors
.add_new_query(ancestor_predicate, ["xerces".into(), var_x])
.unwrap();
println!(">{}<", ancestors);
}
Crate features
Feature | Default | Enables |
---|---|---|
graphviz |
Yes | Graph representation for dependency graphs and stratification |
parser |
Yes | Parsing of textual representation |
tabular |
Yes | Tabular output for views |
io |
Yes | collects all the common I/O formats |
io_csv |
Indirectly | Delimited line format support |
io_json |
Indirectly | JSON format support |
io_text |
Indirectly | Native text format (write only) support |
Changes
Version 0.2.5
- The focus is largely on documentation, both rustdoc and mdbook.
- Book now contains much better concrete documentation and UML for most major model areas.
- Some API changes as the documentation uncovered inconsistencies.
- Significant changes in the visitor and writer areas.
Version 0.2.4
- Completed work to support stratification, including precedence graphs.
- Added new
StratifiedEvaluator
implementation that performs stratification as well as using the semi-naive evaluation scheme. - Added Criterion-based benchmarks for evaluation implementations.
- Separated query trait from relational operations.
- Minor changes in API for consistency.
Version 0.2.3
- Added new "*=" operator for regular expressions
- Renamed the variants of
LiteralInner
/Literal
to beRelational
andArithmetic
to convey meaning, not just type. - Renamed
Relations
toRelationSet
andRules
toRuleSet
. - Renamed
PredicateSet
toNameReferenceSet
and used for variables also; this also addedAttributeNameRef
type for clarity. - Updated the highlight.js datalog language definition for comment and operator changes.
- Replaced more uses of the term "comparison (operator)?" with arithmetic literal
- Fixed more Clippy warnings.
Version 0.2.2
- Made changes to syntax to align more closely with traditional Datalog, as well as Soufflé:
- using
%
instead of#
for line comments, - added
/*
and*/
for block comments, - removed the need for a
@
prefix on the boolean constantstrue
andfalse
, - using
.
instead of@
for pragmas. - ASDI still uses separate
assert
andinfer
pragmas rather than Soufflé's singledecl
. - Also, to keep pragmas regular with other statements they end in a
.
whereas in Soufflé they do not.
- using
- Fixed parsing errors in CSV and JSON files, mainly parsing strings (include/exclude quotes).
Version 0.2.1
- Added traits for consistency across types.
- Added a predicate cache to reduce duplication.
- Finished the file input and output for relations.
- Cleaned up the error module and added functions for error construction.
Version 0.2.0
- New internal structures and library layout.
- Less cloning, but still too much.
- Finished top-level documentation, more to come.
Version 0.1.0
- Not published, used for own verification only.
Version 0.1.0-dev
- Initial release, mostly to verify CI infrastructure through to crates.io
Dependencies
~2.6–5.5MB
~87K SLoC