Algorithmify

这是algorithmify实验性库的主要仓库。这个库旨在使用Rust代码创建算法规范。

algorithmify是一个平台，它包含一个由algorithmify_macros crate中的token解析器。这个crate利用Rust宏系统的力量来定义和暴露define_function_builder宏，该宏将Rust函数转换为函数的结构表示（或可执行的抽象语法树）。这种表示可以由algorithmify crate内部的Interpreter执行。

到目前为止，define_function_builder宏只支持Rust语法的一个非常基本的子集。这应该足以定义和测试许多可以用类似C的伪代码及其等效的Rust实现表达的基本算法。未来的计划是添加算法复杂度计算和其他算法统计。

安装

使用cargo add algorithmify（用于AST和解释器）和cargo add algorithmify_macros（用于define_function_builder宏）在你的项目中使用algorithmify。

函数构建器

algorithmify解释器的主要入口点是Function结构。这是具有define_function_builder设置的Rust函数的结构表示。

define_function_builder声明并定义一个与放置在其上的函数具有相同名称的函数，但后面附加了__function_builder后缀。调用此构建器函数返回一个可以由解释器执行的Function实例。

以下函数定义

#[define_function_builder]
fn sum(a: i32, b: i32) -> i32 {
    a + b
}

扩展为

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
}

解释器

正如您在前一节中看到的那样，define_function_builder 宏定义了一个可以像这样执行的建设者函数

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

如您在上面看到的那样，我们首先执行原生的Rust函数，然后使用内存解释器执行建设者函数。两种情况下得到的结果都是相同的值3，因为解释器在内存中执行等效的指令。

合约

这是库的主要功能。它允许使用合约来定义算法的规范。合约是一组条件集（前、后和维护），可以应用于算法中的任何循环以检查其正确性。

合约是使用 define_function_builder 宏的Rust函数，并且包含在应用合约的函数的 define_function_builder 合约定义参数中。

前条件在循环开始前执行，维护条件在每个循环周期后执行，后条件在循环完成后执行。

以下是一个例子，检查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());
}

我们最后的测试验证最终结果是相同的，但我们声明的三个作为合约一部分的 condition 函数也被执行，并检查算法在执行过程中的正确状态。

参考实现

algorithmify/test/algorithms 目录将存放许多常见算法的参考实现。这些实现都将具有验证算法正确性的合约。