2 releases
0.1.1 | Sep 1, 2023 |
---|---|
0.1.0 | Sep 1, 2023 |
#1527 in Procedural macros
Used in algorithmify
44KB
966 lines
Algorithmify
This is the main repository for the algorithmify
experimental library. This library is designed to create specifications for algorithms defined using Rust code.
algorithmify
is a platform that contains a token parser contained in the algorithmify_macros
crate. This crate leverages the power of the Rust macro system to define and expose the define_function_builder
macro that transforms a Rust function into a structural representation (or executable Abstract Syntax Tree) of the function. Such representation can can be executed by the Interpreter
that lives inside the algorithmify
crate.
As for right now the define_function_builder
macro only supports a very basic subset of the Rust syntax. That should be enough to define and test many basic algorithms that can be expressed in C
-like pseudocode and its equivalent Rust implementation. In the future the plan is to add the calculation of the algorithm complexity and other algorithm stats.
Installation
Use cargo add algorithmify
(for the AST and interpreter) and cargo add algorithmify_macros
(for the define_function_builder
macro) to use algorithmify
on your project.
Function builders
The main entry point for the algorithmify
interpreter is the Function
struct. This is a structural representation of a Rust function that has the define_function_builder
set on it.
The define_function_builder
declares and defines a function with the same name as the function it's placed on but with the __function_builder
postfix appeneded to it. Calling this builder functions returns a Function
instance that can be executed by the interpreter.
The following function definition:
#[define_function_builder]
fn sum(a: i32, b: i32) -> i32 {
a + b
}
Is expanded to:
fn sum__function_builder() -> algorithmify::Function {
algorithmify::Function::new(
<[_]>::into_vec( // argument list
#[rustc_box]
::alloc::boxed::Box::new(["a".to_owned(), "b".to_owned()]),
),
<[_]>::into_vec( // function body
#[rustc_box]
::alloc::boxed::Box::new([
algorithmify::expressions::Statement::Expression(
algorithmify::expressions::Expression::Operation(
Box::new(
algorithmify::expressions::Operation::Add(
algorithmify::expressions::Expression::Reference(
algorithmify::expressions::Reference::Variable(
"a".to_owned(),
),
),
algorithmify::expressions::Expression::Reference(
algorithmify::expressions::Reference::Variable(
"b".to_owned(),
),
),
),
),
),
),
]),
),
std::collections::HashMap::from([]), // contract directory
)
}
#[allow(unused_labels)]
#[allow(dead_code)]
fn sum(a: i32, b: i32) -> i32 {
a + b
}
Interpreter
As you can see in the previous section, the define_function_builder
macro defines a builder function that can be
executed like this:
fn addition_test() {
#[define_function_builder]
fn addition() -> i32 {
let mut a = 1;
a = a + 2;
a
}
assert_eq!(addition(), 3);
let expression = Interpreter::execute_function(addition__function_builder()).unwrap();
assert_eq!(expression, 3.into());
}
As you can see above, we execute the native Rust function first, and then we execute the builder function using the in-memory interpreter. The result is the same value of 3 in both cases, because the interpreter executes the equivalent instructions in memory.
Contracts
This is the main feature of the library. It allows to define a specification of an algorithm using contracts. The contracts are condition sets (pre, post and maintenance) that can be applied to the any of the loops within the algorithm to check its correctness.
The contracts are Rust functions that use the define_function_builder
macro, and that are included in the contract definition arguments of the define_function_builder
of the function that the contract is applied to.
The pre-condition is executed before the loop start, the maintenance condition after each loop cycle and post-condition after the loop finishes.
Here is an example of it, checking the correctness of an insertion sort implementation in Rust:
use algorithmify::Interpreter;
use algorithmify_macros::define_function_builder;
#[define_function_builder]
fn insertion_sort_pre_condition(i: usize) -> bool {
i == 1
}
#[define_function_builder]
fn insertion_sort_maintenance_condition<T: PartialOrd>(i: usize, vector: Vec<T>) -> bool {
let mut valid = true;
for j in 1..i {
if vector[j - 1] > vector[j] {
valid = false;
}
}
valid
}
#[define_function_builder]
fn insertion_sort_post_condition<T>(i: usize, vector: Vec<T>) -> bool {
i == vector.len()
}
#[define_function_builder {
main: {
pre_condition: insertion_sort_pre_condition,
post_condition: insertion_sort_post_condition,
maintenance_condition: insertion_sort_maintenance_condition
}
}]
fn insertion_sort<T>(mut vector: Vec<T>) -> Vec<T>
where
T: PartialEq + PartialOrd + Copy,
{
// start on the second element of the vector
'main: for i in 1..vector.len() {
let key = vector[i];
let mut j = i - 1; // start with the element before the selected key
while j > 0 && vector[j] > key {
vector[j + 1] = vector[j]; // move larger element to the right one by one
j = j - 1;
}
// insert the key into the space left after moving the larger
// elements to the right
vector[j + 1] = key;
}
vector
}
#[test]
pub fn test_insertion_sort() {
let expression = Interpreter::execute_function_with_args(
insertion_sort__function_builder(),
vec![vec![3usize, 12, 5, 6].into()],
)
.unwrap();
assert_eq!(insertion_sort(vec![3, 12, 5, 6]), vec![3, 5, 6, 12]);
assert_eq!(expression, vec![3usize, 5, 6, 12].into());
}
The test we have at the end verifies that the end results are the same, but the three condition
functions we declare as part of the contract are also executed and check the correct state of the algorithm during its execution.
Reference implementations
The algorithmify/test/algorithms
directory is where reference implmentations of many common algorithms will live. These implementation will all have contracts that verify the correctness of the algorithms.