crepe

Tapioca

Crepe é uma biblioteca que permite escrever programas de lógica declarativa em Rust, com uma sintaxe do tipo Datalog. Ele fornece uma macro processual que gera código eficiente e seguro e interoperina perfeitamente com os programas de ferrugem.

Características

• Avaliação semi-nebulosa
• Negação estratificada
• Geração automática de índices para relações
• Chame Funções de ferrugem facilmente de Regras de Datalog
• TypeAfe maneira de inicializar as relações @input
• Muito rápido, compilado diretamente com o resto do seu código de ferrugem

Exemplo

O programa abaixo calcula o fechamento transitivo de um gráfico direcionado. Observe o uso do 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 ) ;
    }
}

Saída:

 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

Você pode fazer muito mais com crepe. O próximo exemplo mostra como você pode usar a negação estratificada, a sintaxe da expressão da ferrugem e a avaliação semi-neca para encontrar todos os caminhos em um gráfico ponderado com comprimento na maioria 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 ( ) ) ;
}

Saída:

 Walk: 89203
NoWalk: 8207

Notas

A partir dos testes iniciais, o código gerado é muito rápido. Variantes de fechamento transitivo para gráficos grandes (~ 10 ⁶ relações) são executados em velocidade comparável ao suflê compilado e usam uma fração do tempo de compilação.

Para benchmarks, consulte os benches/ diretório. Os benchmarks podem ser executados usando cargo bench .

Essa macro gera uma estrutura Crepe no módulo atual, bem como estruturas para todas as relações declaradas. Isso significa que, para integrar o crepe dentro de um programa maior, você deve colocá -lo em seu próprio módulo com código relacionado. Consulte a documentação para obter mais informações.

Agradecimentos

Este projeto foi fortemente inspirado no suflê e no formulog, que usam modelos semelhantes de compilação de dados para análise estática.