crepe

كريب

CREPE هي مكتبة تتيح لك كتابة برامج منطقية التصريبية في Rust ، مع بناء جملة تشبه DataLog. يوفر ماكرو إجرائيًا يولد رمزًا آمنًا فعالًا ويمثل بسلاسة مع برامج الصدأ.

سمات

• تقييم شبه ذكي
• نفي طبقي
• التوليد التلقائي من المؤشرات للعلاقات
• استدعاء وظائف الصدأ بسهولة من داخل قواعد 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 ⁶ علاقات) بسرعة مماثلة إلى souffle المترجمة ، واستخدام جزء من وقت التجميع.

للحصول على المعايير ، انظر benches/ الدليل. يمكن تشغيل المعايير باستخدام cargo bench .

يولد هذا الماكرو بنية Crepe في الوحدة النمطية الحالية ، وكذلك بنية لجميع العلاقات المعلنة. هذا يعني أنه لدمج CREPE داخل برنامج أكبر ، يجب عليك وضعه في الوحدة النمطية الخاصة به مع التعليمات البرمجية ذات الصلة. انظر الوثائق لمزيد من المعلومات.

شكر وتقدير

كان هذا المشروع مستوحى بشدة من Souffle و Formulog ، والتي تستخدم نماذج مماثلة من تجميع Datalog للتحليل الثابت.