crepe

Crêpe

Crepe est une bibliothèque qui vous permet d'écrire des programmes de logique déclarative dans Rust, avec une syntaxe de type données de données. Il fournit une macro procédurale qui génère un code efficace et sûr et interopération de manière transparente avec les programmes de rouille.

Caractéristiques

• Évaluation semi-naine
• Négation stratifiée
• Génération automatique d'indices pour les relations
• Appelez facilement les fonctions de rouille à partir des règles de datalog
• TypeSafe Way d'initialiser les relations @input
• Très rapide, compilé directement avec le reste de votre code de rouille

Exemple

Le programme ci-dessous calcule la fermeture transitive d'un graphique dirigé. Notez l'utilisation de la crepe! macro.

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

Sortir:

 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

Vous pouvez faire beaucoup plus avec la crêpe. L'exemple suivant montre comment vous pouvez utiliser la négation stratifiée, la syntaxe d'expression de Rust et l'évaluation semi-naïve pour trouver tous les chemins dans un graphique pondéré avec une longueur dans la plupart 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 ( ) ) ;
}

Sortir:

 Walk: 89203
NoWalk: 8207

Notes

D'après les tests initiaux, le code généré est très rapide. Les variantes de fermeture transitive pour les gros graphiques (~ 10 ⁶ relations) fonctionnent à une vitesse comparable au souffle compilé et utilisent une fraction du temps de compilation.

Pour les repères, consultez les benches/ répertoire. Les repères peuvent être exécutés à l'aide cargo bench .

Cette macro génère une structure Crepe dans le module actuel, ainsi que des structures pour toutes les relations déclarées. Cela signifie que pour intégrer la crêpe dans un programme plus grand, vous devez le mettre dans son propre module avec du code connexe. Voir la documentation pour plus d'informations.

Remerciements

Ce projet a été fortement inspiré par Souffle et Forulog, qui utilisent tous deux des modèles similaires de compilation de datalog pour une analyse statique.