Rappresenta una regola in un set di regole

6

Come rappresentare le regole per un motore di regole come oggetti?

Una regola sarebbe

if (booleanExpression(input)) then a chain of generic actions" else next rule

... dove le azioni generiche potrebbero essere ad es. passare l'input a una diversa catena di regole, restituendo una conclusione (terminando l'analisi con il risultato) o raccogliendo dati aggiuntivi, anche se probabilmente altre azioni potrebbero rivelarsi necessarie.

Ora il problema di analizzare a parte le condizioni booleane arbitrarie (supponiamo di avere una classe booleanExpression pienamente funzionante disponibile), come sarebbe un tale oggetto Rule, e in particolare, come sarebbe l'oggetto Ruleset contenente una griglia ordinata e interconnessa di questi sembrano, in particolare in una struttura che sarà possibile elaborare dal motore attuale. (se le strutture dati non rendono ovvio come dovrebbero elaborarle tali motori, forse un suggerimento anche a riguardo?)

Questo sarà scritto in C ++ ma anche una risposta indipendente dal linguaggio è molto gradita.

Questo è un derivato della mia domanda su Event Correlator , che sembra essere senza risposta semplicemente perché è troppo ampio per essere affrontato in una sola risposta, quindi sto cercando di dividere il problema in blocchi più piccoli, più piccoli.

    
posta SF. 04.01.2013 - 15:31
fonte

4 risposte

3

Dato che hai già definito cos'è una regola, la struttura dei dati corrispondente sarebbe semplice (pseudo-codice):

class Rule {
  Condition condition;
  ActionSet positiveActions, negativeActions
}

Tuttavia, come indicato dal riferimento a un gruppo di regole , la parte interessante dei motori di regole è il processo di selezione delle regole e la loro strategia di esecuzione. Ho paura che ci siano tante varianti quante credi che potrebbero esserci - più alcune.

Generalmente, le regole di un motore di regole, almeno per circa la dozzina di motori di regole che ho visto, non contengono una parte "else". L'idea delle regole è che hanno qualche condizione quando si applicano, ma se non si applicano, allora semplicemente non vengono applicate. Quindi, lo sviluppo del motore si riduce a due compiti principali:

  1. Determina quali regole sono applicabili

    Numerosi documenti di ricerca sono disponibili su questo. La selezione delle regole applicabili dipende molto dalla struttura dei dati utilizzata per rappresentare le tue regole. Se si vuole veramente consentire condizioni booleane arbitrarie, allora chiaramente non si può determinare nulla a meno che la condizione non venga valutata su tutti i possibili input. Quindi, la maggior parte dei motori di regole ha alcuni oggetti / predicati / vincoli / qualunque-le-cose-sono-chiamate, che è necessario utilizzare per la parte della regola che lo rende applicabile. Ciò consente al motore di selezionare intelligentemente (leggi: in modo efficiente) da tutte le regole e inserire quelle applicabili.

    Ecco un esempio più concreto di come qualcosa del genere potrebbe apparire in f.ex. Prolog:

    MySignal(_, true, false) :- do_something

    MySignal(_, true, true) :- do_something_else

    Chiaramente un'implementazione può abusare del fatto che queste regole si applicano solo a MySignal e solo nel caso in cui il secondo argomento sia true . Quindi, è possibile migliorare la ricerca delle regole con una tabella di ricerca dedicata per MySignal .

    Si noti che oltre alle regole c'è un altro aspetto molto importante, vale a dire l'input o più in generale, i dati su cui queste regole dovrebbero funzionare. Nella maggior parte dei motori di regole, è inoltre possibile modificare questi dati mediante l'applicazione di regole (ad esempio, si inizia con qualcosa, quindi le regole aggiungono nuove cose a quei dati). In questo esempio, l'input dovrebbe essere memorizzato in modo tale da poter determinare in modo efficiente se è presente un input MySignal (di nuovo potrebbe essere prevista una sorta di tabella di ricerca).

    Questa gestione degli input richiede anche una connessione alle tue regole. Nei motori di regole questo viene eseguito tramite gli oggetti / predicati / ecc. Sopra indicati, o tramite variabili logiche. In altre parole: le azioni che la regola deve eseguire dipenderanno generalmente dall'input e, in quanto tale, l'input deve essere passabile in qualche modo alle azioni. Considerare più concretamente il seguente esempio:

    MySignal(X, false, false) :- print(X)

  2. Determina la strategia di esecuzione delle regole applicabili

    La maggior parte dei motori ricade in una banale strategia top-to-bottom qui, come in, viene applicata la prima regola testuale nel file delle regole che corrisponde all'ingresso. Anche qui puoi andare arbitrariamente complesso. Solo alcuni esempi di diverse possibili strategie:

    • Prolog aggiunge il backtrack alla strategia di esecuzione della regola in modo che un errore porti a un'altra regola utilizzata durante il backtracking.
    • Le annotazioni prioritarie apportate alle regole possono essere utilizzate per ricavare una priorità e da quella dell'ordine di esecuzione.
    • Le probabilità possono anche essere annotate, portando a un motore di regole probabilistiche che seleziona dalle regole applicabili tramite un PRNG.
    • Sono anche possibili semplici strategie, come semplicemente l'esecuzione della prima regola trovata o tutte le regole applicabili (quest'ultima funziona solo se le regole non consumano l'input).

Quindi in sostanza la tua domanda si riduce al modo in cui vuoi andare: un motore di regole in piena regola o una semplice combinazione filtro-mappa.

Solo per completezza, ecco un falso approccio basato su regole che potrebbe essere applicabile al tuo caso (pseudo-codice funzionale, senza altra parte, ma dovrebbe essere chiaro). In questo caso, la selezione della regola è semplicemente per verificare che l'input soddisfi la condizione e la strategia di esecuzione consiste nell'applicare tutte le regole applicabili nel loro ordine testuale:

let I be the list of inputs
let R be a list of rules
I map (i => R filter ( r => r.condition(i) == true ) map ( r => r.action(i) )

Ovviamente, la complessità del runtime è molto negativa con l'aumento del numero di regole a causa della necessità di dover controllare ogni combinazione di condizioni e input. Dopo tutto, una caratteristica fondamentale dei motori di regole è che forniscono alcuni mezzi per affrontare questa esplosione combinatoria.

Se sei interessato ai motori di regole appropriati, ecco alcune parole chiave aggiuntive per iniziare la tua ricerca su come implementarle: semantica operativa basata su regole, RETE, unificazione

    
risposta data 04.01.2013 - 16:21
fonte
2

Bene, come invocherete questa cosa?

Supporrei che fosse qualcosa del genere:

for (auto rule: ruleset) {
    if (rule.matches(context)) {
        if (rule.execute() == Stop)
            break # so rules can stop early
        # else: default action is to continue
    }
}

Quindi hai un oggetto con due metodi

bool Rule::matches(Context const& input) { return booleanExpression(input); }
void execute() {
    for (auto action: actions) action.execute();
}

È questo il genere di cose che stai cercando? Questo funziona banalmente per un semplice set di regole lineari (un po 'come iptables, anche se ha bisogno di ramificazioni), ma per un albero decisionale, una delle azioni disponibili deve essere "valutare ricorsivamente questa sottostruttura annidata". Sarà più semplice dimostrarlo con un piccolo set di regole di esempio, se ne hai uno.

    
risposta data 04.01.2013 - 16:18
fonte
2

Ti suggerisco di provare ad andare via usando espressioni booleane reali e capire quali azioni o eventi stai facendo al "sistema" che stai sviluppando. Se stai usando le if-statement potresti anche usare un linguaggio di scripting.

C'era una volta ho creato un DSL in formato JSON che definiva le regole come azioni o eventi anziché utilizzare espressioni booleane. Ho scelto JSON perché il codice DSL è stato generato da un back-end Web e sarebbe stato utilizzato in un front-end web javascript.

Considera una serie di opzioni che un utente può utilizzare nell'interfaccia utente di un designer, tutte individualmente identificabili con un nome. L'interfaccia utente del designer per l'esempio seguente saranno le auto che l'utente può selezionare. In pratica, il DSL assomigliava a questo:

// an array of rules
"rules": [
    // rule number 1
    { 
        // the originating option of the event or action
        "source": "car_1",

        // the option(s) that receives of the action or event
        "destination": ["color_yellow", "color_blue"],

        // the event or action that should happen
        // in this case the destination should be disabled
        "action": "disable",

        // what to roll back to if the destination was selected
        "instead": "color_red"  
    },
    // rule number 2, same as above but used to 
    // demonstrate chaining
    {
        "source": "roof_sunroof",
        "destination": "color_red",
        "action": "disable",
        "instead": "color_green"
    },
    ... and so on         
]

In questo esempio, nella prima regola: se l'utente ha selezionato l'opzione "car_1", le opzioni di colore "color_yellow" e "color_blue" saranno disabilitate (perché quella particolare auto non è disponibile nei colori giallo e blu). Nella seconda regola, se l'utente seleziona "roof_sunroof", l'opzione di "color_red" è disabilitata.

Nel frattempo il front-end prende questo file JSON e crea tutte le opzioni sull'interfaccia utente e usa l'array di regole per determinare quali eventi configurare.

Le azioni e gli eventi sono stati implementati in modo tale da essere concatenabili con il set di regole, quindi se una sorgente si disabilitava e l'opzione di rollback era disabilitata, l'evento cercava invece cosa ripristinare. Nell'esempio sopra se è stata selezionata l'opzione "roof_sunroof" e quindi "car_1", l'applicazione prima tenterebbe di eseguire il rollback su "color_red" (che è disabilitato) e quindi su "color_green". Se ci fossero delle dipendenze circolari, molto probabilmente sarebbe un bug nella DSL piuttosto nell'interfaccia utente del designer. Nota che gli eventi applicano le regole senza la necessità di costruire un albero complesso.

Sul lato back-end, è più semplice rappresentare le regole come oggetti se sono definizioni per un DSL. Certo, se segui il percorso dell'istruzione if, puoi mantenere la regola come script di testo.

    
risposta data 04.01.2013 - 16:32
fonte
1

Questo è un po 'obliquo alla tua domanda, ma mi sembra che in questo caso ciò di cui stai parlando sia in realtà la creazione di un linguaggio specifico di dominio: se inizi a fare ricerche, troverai tutti i tipi di articoli interessanti. Martin Fowler fornisce un buon punto di partenza.

Le DSL sono un'area molto utile da cui essere consapevole e qualcosa che penso che vedremo molto di più nei prossimi anni.

    
risposta data 04.01.2013 - 15:42
fonte

Leggi altre domande sui tag