Uses old Rust 2015
|0.1.5||May 21, 2021|
|0.1.4||Jul 13, 2020|
|0.1.3||Sep 25, 2019|
|0.1.2||Dec 17, 2018|
|0.1.0||Nov 30, 2018|
#250 in Algorithms
24 downloads per month
Bex is a rust library for working with boolean expressions (expression trees, decision diagrams, etc.)
This crate lets you build a complicated abstract syntax tree (or logic circuit schematic, if you prefer) by working with individual Bit structs, or vectors that act like integers.
You can also "solve" these AST structures by converting them into various canonical represations:
- reduced, ordered, binary decision diagrams (ROBDDs) -- a normal form consisting of if-then-else triples that essentially act like compressed truth tables
- algebraic nomal form -- an "xor of ands" polynomial form
- (more coming in the future)
J and Bex vs Primorial 15 is about converting "simple" factoring problems into boolean expressions and solving them with bex.
- actually use semantic versioning for releases :)
- better metrics collection for benchmarking
- generalize the BDD swarm implementation to work for ANF
- various solver optimizations
- better graphviz rendering
- other general improvements
For more detail, see plans.org.
SwapSolver, a new substitution solver that (like any
SubSolver) works by iteratively replacing virtual variables (representing AST nodes) with their definitions inside a BDD. What's new here is that
SwapSolvercontinuously re-orders the variables (rows) in the BDD at each step so that the substitution is as efficient as possible.
XVHLScaffold, a data structure for decision-diagram-like graphs, that allows accessing each row individually. This structure should be considered extremely experimental, and may change in the future (as it does not currently use
NIDfor node references).
swarmmodule that contains a small framework for distributing work across threads. It is used by the
SwapSolverto swap BDD rows in parallel, and follows the same design as
BddSwarm, which will likely be ported over to this framework in the future.
opsmodule for representing boolean expressions in something like reverse Polish notation. The
Ops::RPNconstructor will likely replace
ast::Opas the representation of nodes in
ast::ASTBasein a future version, since
Ops::RPNcan represent arbitrary boolean functions with any number of inputs.
For full changelog, see CHANGELOG.md.