Algorithmify

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

algorithmify 是一个平台，其中包含在 algorithmify_macros 包中包含的令牌解析器。这个包利用Rust宏系统的功能来定义和公开 define_function_builder 宏，该宏将Rust函数转换为函数的结构表示（或可执行的抽象语法树）。这种表示可以由 algorithmify 包内的 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 目录中，将包含许多常见算法的参考实现。这些实现都将具有验证算法正确性的合约。