crepe

Crepe

CREPE es una biblioteca que le permite escribir programas lógicos declarativos en Rust, con una sintaxis similar a la data de datos. Proporciona una macro de procedimiento que genera código eficiente y seguro e introduce perfectamente con los programas de óxido.

Características

• Evaluación semi-sin
• Negación estratificada
• Generación automática de índices para relaciones
• Llamar fácilmente a las funciones de óxido de las reglas de datos
• Forma de tipos de relaciones @input
• Muy rápido, compilado directamente con el resto de su código de óxido

Ejemplo

El siguiente programa calcula el cierre transitivo de un gráfico dirigido. ¡Tenga en cuenta el uso del 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 ) ;
    }
}

Producción:

 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

Puedes hacer mucho más con crepe. El siguiente ejemplo muestra cómo puede usar la negación estratificada, la sintaxis de la expresión de óxido y la evaluación semi-NAIVE para encontrar todas las rutas en un gráfico ponderado con longitud como máximo 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 ( ) ) ;
}

Producción:

 Walk: 89203
NoWalk: 8207

Notas

A partir de las pruebas iniciales, el código generado es muy rápido. Las variantes de cierre transitivo para gráficos grandes (~ 10 ⁶ relaciones) se ejecutan a una velocidad comparable a Souffle compilado y usan una fracción del tiempo de compilación.

Para puntos de referencia, consulte los benches/ directorio. Los puntos de referencia se pueden ejecutar con cargo bench .

Esta macro genera una estructura Crepe en el módulo actual, así como estructuras para todas las relaciones declaradas. Esto significa que para integrar CREPE dentro de un programa más grande, debe ponerlo en su propio módulo con código relacionado. Consulte la documentación para obtener más información.

Expresiones de gratitud

Este proyecto se inspiró fuertemente en Souffle y Formulog, que utilizan modelos similares de compilación de datos para el análisis estático.