### 3 releases

new 0.1.2 | Sep 14, 2020 |
---|---|

0.1.1 | Sep 1, 2020 |

0.1.0 | Sep 1, 2020 |

#**55** in Procedural macros

**MIT/Apache**

45KB

841 lines

# Crepe

Crepe is a library that allows you to write declarative logic programs in Rust, with a Datalog-like syntax. It provides a procedural macro that generates efficient, safe code and interoperates seamlessly with Rust programs.

## Features

- Semi-naive evaluation
- Stratified negation
- Automatic generation of indices for relations
- Easily call Rust functions from within Datalog rules
- Typesafe way to initialize

relations`@`input - Very fast, compiled directly with the rest of your Rust code

## Example

The program below computes the transitive closure of a directed graph. Note
the use of the

macro.`crepe!`

`use` `crepe``::`crepe`;`
`crepe!` `{`
`@`input
`struct` `Edge``(``i32`, `i32``)``;`
`@`output
`struct` `Reachable``(``i32`, `i32``)``;`
Reachable`(`x`,` y`)` `<``-` Edge`(`x`,` y`)``;`
Reachable`(`x`,` z`)` `<``-` Edge`(`x`,` y`)``,` Reachable`(`y`,` z`)``;`
`}`
`fn` `main``(``)`` ``{`
`let` `mut` runtime `=` `Crepe``::`new`(``)``;`
runtime`.``extend``(``&``[`Edge`(``1``,` `2``)``,` Edge`(``2``,` `3``)``,` Edge`(``3``,` `4``)``,` Edge`(``2``,` `5``)``]``)``;`
`let` `(`reachable`,``)` `=` runtime`.``run``(``)``;`
`for` Reachable`(`x`,` y`)` `in` reachable `{`
`println!``(``"`node `{}` can reach node `{}``"``,` x`,` y`)``;`
`}`
`}`

Output:

`node ``1` can reach node `2`
node `1` can reach node `3`
node `1` can reach node `4`
node `1` can reach node `5`
node `2` can reach node `3`
node `2` can reach node `4`
node `2` can reach node `5`
node `3` can reach node `4`

You can do much more with Crepe. The next example shows how you can use
stratified negation, Rust expression syntax, and semi-naive evaluation to find
all paths in a weighted graph with length at most

.`MAX_PATH_LEN`

`use` `crepe``::`crepe`;`
`const` `MAX_PATH_LEN``:` `u32` `=` `20``;`
`crepe!` `{`
`@`input
`struct` `Edge``(``i32`, `i32`, `u32``)``;`
`@`output
`struct` `Walk``(``i32`, `i32`, `u32``)``;`
`@`output
`struct` `NoWalk``(``i32`, `i32``)``;`
`struct` `Node``(``i32``)``;`
Node`(`x`)` `<``-` Edge`(`x`,` `_``,` `_``)``;`
Node`(`x`)` `<``-` Edge`(``_``,` x`,` `_``)``;`
Walk`(`x`,` x`,` `0``)` `<``-` Node`(`x`)``;`
Walk`(`x`,` z`,` len1 `+` len2`)` `<``-`
Edge`(`x`,` y`,` len1`)``,`
Walk`(`y`,` z`,` len2`)``,`
`(`len1 `+` len2 `<=` `MAX_PATH_LEN``)``;`
NoWalk`(`x`,` y`)` `<``-` Node`(`x`)``,` Node`(`y`)``,` `!`Walk`(`x`,` y`,` `_``)``;`
`}`
`fn` `main``(``)`` ``{`
`let` n `=` `256``;`
`let` `mut` edges `=` `Vec``::`new`(``)``;`
`for` i `in` `0``..`n `{`
`for` j `in` `0``..`n `{`
`if` `rand``::``random``::``<``f32``>``(``)` `<` `0.``02` `{`
edges`.``push``(`Edge`(`i`,` j`,` `5``)``)``;`
`}`
`}`
`}`
`let` `mut` runtime `=` `Crepe``::`new`(``)``;`
runtime`.``extend``(`edges`)``;`
`let` `(`walk`,` nowalk`)` `=` runtime`.``run``(``)``;`
`println!``(``"`Walk: `{}``"``,` walk`.``len``(``)``)``;`
`println!``(``"`NoWalk: `{}``"``,` nowalk`.``len``(``)``)``;`
`}`

Output:

`Walk``:` `89203`
NoWalk`:` `8207`

## Notes

From initial testing, the generated code is very fast. Variants of transitive closure for large graphs (~1000 nodes) run at comparable speed to compiled Souffle, and at a fraction of the compilation time.

This macro generates a

struct in the current module, as well as structs
for all of the declared relations. This means that to integrate Crepe inside a
larger program, you should put it in its own module with related code. See the
documentation for more information.`Crepe`

## Acknowledgements

This project was heavily inspired by Souffle and Formulog, which both use similar models of Datalog compilation for static analysis.

#### Dependencies

~1.4–1.9MB

~43K SLoC