crepe

Krepp

Crepe ist eine Bibliothek, in der Sie deklarative Logikprogramme in Rust mit einer datalogähnlichen Syntax schreiben können. Es bietet ein prozedurales Makro, das einen effizienten, sicheren Code erzeugt und nahtlos mit Rostprogrammen unterbrochen wird.

Merkmale

• Semi-naive Bewertung
• Geschichtete Negation
• Automatische Generierung von Indizes für die Beziehungen
• Rufen Sie einfach Rostfunktionen innerhalb von Datalog -Regeln an
• TypeSafe Weg, um @input -Beziehungen zu initialisieren
• Sehr schnell, direkt mit dem Rest Ihres Rostcode zusammengestellt

Beispiel

Das folgende Programm berechnet den transitiven Verschluss eines angegebenen Diagramms. Beachten Sie die Verwendung des crepe! Makro.

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

Ausgabe:

 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

Sie können viel mehr mit Crepe machen. Das nächste Beispiel zeigt, wie Sie geschichtete Negation, Rost-Expressionsyntax und semi-naive-Bewertung verwenden können, um alle Pfade in einem gewichteten Diagramm mit Länge höchstens MAX_PATH_LEN zu finden.

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

Ausgabe:

 Walk: 89203
NoWalk: 8207

Notizen

Aus den ersten Tests ist der generierte Code sehr schnell. Varianten des transitiven Verschlusses für große Diagramme (~ 10 ⁶ Beziehungen) laufen mit vergleichbarer Geschwindigkeit zum kompilierten Souffle und verwenden einen Bruchteil der Kompilierungszeit.

Für Benchmarks finden Sie die benches/ Verzeichnisse. Die Benchmarks können mit cargo bench ausgeführt werden.

Dieses Makro erzeugt eine Crepe -Struktur im aktuellen Modul sowie Strukturen für alle deklarierten Beziehungen. Dies bedeutet, dass Sie es in ein eigenes Modul mit dem zugehörigen Code in einen eigenen Modul in ein größeres Programm in einen größeren Programm integrieren sollten. Weitere Informationen finden Sie in der Dokumentation.

Anerkennung

Dieses Projekt wurde stark von Souffle und Formullog inspiriert, die beide ähnliche Modelle der Datalog -Kompilierung für die statische Analyse verwenden.