crepe

เครป

Crepe เป็นห้องสมุดที่ให้คุณเขียนโปรแกรมลอจิกที่ประกาศใน Rust ด้วยไวยากรณ์เหมือนดาต้าล็อก มันมีมาโครขั้นตอนที่สร้างรหัสที่มีประสิทธิภาพปลอดภัยและทำงานร่วมกันอย่างราบรื่นกับโปรแกรมสนิม

คุณสมบัติ

• การประเมินกึ่งไร้เดียงสา
• การปฏิเสธแบบแบ่งชั้น
• การสร้างดัชนีอัตโนมัติเพื่อความสัมพันธ์
• เรียกฟังก์ชั่นสนิมได้อย่างง่ายดายจากภายในกฎ datalog
• วิธีที่ต้องการในการเริ่มต้นความสัมพันธ์ @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 ⁶ ความสัมพันธ์) ทำงานด้วยความเร็วที่เทียบเคียงได้กับการรวบรวม souffle และใช้เศษส่วนของเวลาการรวบรวม

สำหรับมาตรฐานดู benches/ ไดเรกทอรี มาตรฐานสามารถเรียกใช้ได้โดยใช้ cargo bench

แมโครนี้สร้างโครงสร้าง Crepe ในโมดูลปัจจุบันเช่นเดียวกับโครงสร้างสำหรับความสัมพันธ์ที่ประกาศทั้งหมด ซึ่งหมายความว่าการรวมเครปภายในโปรแกรมที่ใหญ่กว่าคุณควรใส่ไว้ในโมดูลของตัวเองด้วยรหัสที่เกี่ยวข้อง ดูเอกสารสำหรับข้อมูลเพิ่มเติม

กิตติกรรมประกาศ

โครงการนี้ได้รับแรงบันดาลใจอย่างมากจาก Souffle และ Formulog ซึ่งทั้งคู่ใช้โมเดลการรวบรวม Datalog ที่คล้ายกันสำหรับการวิเคราะห์แบบคงที่