crepe

Креп

Crepe-это библиотека, которая позволяет вам писать декларативные логические программы в Rust с помощью Datalogy-подобного синтаксиса. Он предоставляет процедурный макрос, который генерирует эффективный, безопасный код и беспрепятственно взаимодействует с программами ржавчины.

Функции

• Полу-найская оценка
• Стратифицированное отрицание
• Автоматическая генерация индексов для отношений
• Легко вызовать функции ржавчины из правил Datalog
• Typesafe способ инициализации отношений @input
• Очень быстро, скомпилирован непосредственно с остальной частью кода ржавчины

Пример

Программа ниже вычисляет переходное закрытие направленного графика. Обратите внимание на использование 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 ) ;
    }
}

Выход:

 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

Вы можете сделать гораздо больше с крепе. В следующем примере показано, как вы можете использовать стратифицированное отрицание, синтаксис выражения ржавчины и полуавивую оценку, чтобы найти все пути на взвешенном графике с длиной в большинстве 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 ( ) ) ;
}

Выход:

 Walk: 89203
NoWalk: 8207

Примечания

Из первоначального тестирования сгенерированный код очень быстрый. Варианты транзитивного закрытия для больших графиков (~ 10 ⁶ отношений) выполняются на сопоставимой скорости для скомпилированного суфля, и используют долю времени компиляции.

Для тестов см. benches/ каталог. Цитрицы можно запускать с помощью cargo bench .

Этот макрос генерирует структуру Crepe в текущем модуле, а также структуры для всех объявленных отношений. Это означает, что для интеграции крепа в более крупную программу вы должны поместить его в свой собственный модуль с соответствующим кодом. Смотрите документацию для получения дополнительной информации.

Благодарности

Этот проект был в значительной степени вдохновлен суфле и формулугом, в которых используются аналогичные модели компиляции Datalog для статического анализа.