Ein Interpreter für logische Klauseln

Ein Interpreter erweitert um die Unterstützung von logischen Klauseln.

Mai 19
Ein Interpreter für logische Klauseln Joachim Christ


Dieser Artikel führt den Beitrag Ein Interpreter für funktionale Spezifikationen inhaltlich fort.

Über Klauseln

Diese Hinweise zeigen die Historie und die wesentlichen Erweiterungen im Laufe der Entwicklung von logischen Klauseln.

Die Ableitung von logischen Klauseln erfolgt mithilfe von Aussagen (‘Prädikaten’), die u. a. über Strings (generell über ‘Atome’) getroffen werden.

  • Strings sind Ketten von Token, die in " eingeschlossen werden.

    Z. B.: "Peter Schmidt"

  • Strings können mit den bekannten Operatoren verglichen werden.

  • Strings können sowohl benutzt werden als Argumente von Variablen als auch als deren Werte.

    $eval vater( "Klaus" ) = "Peter"
    $eval sohn( "Hugo" ) = "Peter"

    Durch solche Zuweisungen werden auf eine formalisierte Art und Weise Aussagen gespeichert; im Beispiel eine Aussage wie “Der Vater von Klaus ist Peter”.

  • Abfragen nach gespeicherten Inhalten sind möglich:

    $eval vater( "Klaus" )vater( "Klaus" ) == "Peter"

    Die Frage, wer der Vater von Peter sei, kann jedoch nicht beantwortet werden, da dazu ein Wert für den Ausdruck vater( "Peter" ) notwendig wäre.

  • Wissen kann durch Ableitungsregeln hergeleitet werden.

    $rule vater( x$ ) == y$ :- sohn( y ) == x

    Dies bedeutet, dass aus der Tatsache “Der Sohn von Y ist X” gefolgert werden kann, dass “Der Vater von X ist Y” gilt. Der Operator ':-' kann von rechts nach links gelesen werden als ‘folgt’ bzw. in der Leserichtung von links nach rechts als ‘gilt wenn’.

  • Eine weitere Ableitungsregel ergänzt die bereits vorhandenen.

    $rule vater( x$ ) == y$ :- tochter( y ) == x

    Dabei wird die vorhandene Regel zu “Vater und Sohn” nicht gelöscht.

  • In Regeln können als Operatoren 'or' und 'and' benutzt werden.

    $rule mutter( x$ ) == y$ :- sohn( y ) == x or tochter( y ) == x

  • Das Kommando '$rules' zeigt alle bekannten Regeln an.

    Die Argumente von '$rules' sind analog denen von '$show'.

  • Das Kommando '$unrule' löscht Regeln.

    Die Argumente von '$unrule' sind analog denen von '$delete'.


  • ↵


    Bibliotheken
    Klausel Demo

    Befehle

    Bitte geben Sie ein Kommando oder einen Ausdruck ein und starten Sie die Verarbeitung durch '↵' oder durch Klicken des Icons.

    Sprachelemente

    Die folgenden Sprachelemente werden unterstützt:

    sentence = implication [ '?' implication ':' sentence ]

    Ein Ausdruck sentence wird berechnet und sein Wert ausgegeben.

    true ? 1 : 0 → 1
    false ? 1 : 0 → 0


    implication = logical ( '==' | '!=' ) logical

    V == W Logische Äquivalenz
    V != W Logische Antivalenz (exklusives oder)


    logical = compare ( 'and' | 'or' | 'xor' ) compare

    V and W Logisches Und
    V or W Logisches Oder
    V xor W Logisches Exklusives Oder


    compare = structural ( '==' | '!=' | '<' | '>' | '<=' | '>=') structural

    X == Y Gleichheit
    X != Y Ungleichheit
    X < Y Kleiner
    X <= Y Kleiner oder gleich
    X > Y Größer
    X >= Y Größer oder gleich


    structural = expression ( '|' | '**' ) expression

    X | Y Konkatenation von Objekten
    X ** Y Kartesisches Produkt von Objekten


    structural = expression ( '||' | '&&' | '^^' ) expression

    X || Y Vereinigung von Mengen
    X && Y Schnitt von Mengen
    X ^^ Y Ausschluß von Mengen


    expression = term ( '+' | '-' ) term

    X + Y Addition
    X - Y Subtraktion


    term = factor ( '*' | 'div' | 'mod' | '/' ) factor

    X * Y Multiplikation
    X / Y Division
    X div Y Gannzahlige Division
    X mod Y Rest bei ganzzahliger Division
    Zu beachten ist, dass die Operatoren 'div' und 'mod' auch mit Gleitkommazahlen aufgerufen werden können.


    factor = atom ( '~' | '&' | '&=' ) atom

    X ~ Y Selektion eines Elements aus einer Menge
    X ~ L Selektion von Elementen aus einer Menge
    X & Y Prüfung auf strenges Enthaltensein zweier Mengen
    X &= Y Prüfung auf Enthaltensein oder Gleichheit zweier Mengen


    atom = [ '+' | '-' ] ( '(' sentence ')' | scalar | unary factor | call )

    + X Positives Vorzeichen
    - X Negatives Vorzeichen
    ( X ) Klammerung eines Ausdrucks X
    z. B. 3 * ( 2 + 1 )


    atom = compound


    atom = string
    string = '"' { token } '"'

    Strings sind Ketten von Token, die in " eingeschlossen werden.

    "Peter Schmidt"


    call = variable | variable '=' sentence

    F = X Zuweisung des Wertes X an die Variable F


    scalar = numeric

    78.0009 Gleitkommazahl (“Float”)


    scalar = 'true' | 'false'

    true Logisches 'Wahr'
    false Logisches 'Falsch'


    compound = '()' | '(' subrange { ',' subrange } ')'
    subrange = sentence [ ':' sentence ]

    ( ) Leere Liste
    ( 1, 2, 1 ) Liste ( 1, 2, 1 )
    ( … X : Y ) Bereichsangabe in einer Liste
    z. B. ( 1, 10:12, 15 ) → ( 1, 10, 11, 12, 15 )


    compound = '#' name | '#' name '()'
    compound = '#' name '(' subrange { ',' subrange } ')'

    # q Leere Liste mit dem Namen “q”
    # q ( ) Leere Liste mit dem Namen “q”
    # q ( 1, 2, 1 ) Benannte Liste #q( 1, 2, 1 ) mit dem Namen “q”


    unary = 'not'

    not V Logisches Nicht


    unary = 'abs' | 'neg' | 'sign' | 'conv'

    abs X Absolutbetrag
    neg X Negativwert (analog negativem Vorzeichen)
    sign X Vorzeichen: 1, 0 oder -1
    conv X Y Konvertiert die Zahl Y ins Zahlensystem X


    unary = 'trunc' | 'frac'

    trunc X Ganzahliger Anteil
    z. B. trunc 32.78 → 32
    frac X Gebrochener Anteil
    z. B. frac 32.78 → 0.78


    unary = 'size' | 'card' | 'sum' | 'prod' | 'min' | 'max'

    size L Länge einer Liste
    card M Kardinalität einer Menge
    sum L Summe der Elemente einer Liste
    prod L Produkt der Elemente einer Liste
    min L Minimum der Elemente einer Liste
    max L Maximum der Elemente einer Liste


    unary = 'sort' | 'set' | 'unname'

    sort L Sortieren der Elemente einer Liste
    set L Umwandlung einer Liste in eine Menge
    unname B Umwandlung einer benannten Liste in eine unbenannte


    unary = 'head' | 'tail' | 'snake' | 'rattle' | 'permute' | 'reverse' | 'carousel'

    head L Erstes Element einer Menge
    z. B. head ( 1, 2, 3 ) → 1
    tail L Menge außer erstem Element
    z. B. tail ( 1, 2, 3 ) → ( 2, 3 )
    snake L Menge außer letztem Element
    z. B. snake ( 1, 2, 3 )→ ( 1, 2 )
    rattle L Letztes Element einer Menge
    z. B. rattle ( 1, 2, 3 ) → 3
    permute L Alle Permutationen einer Liste
    z. B. permute ( 1, 2 ) → ( ( 1, 2 ), ( 2, 1 ) )
    reverse L Umkehrung einer Liste
    z. B. reverse ( 1, 2, 3, 4 ) → ( 4, 3, 2, 1 )
    carousel L Alle Permutationen einer Liste, bei denen die Reihenfolge der Elemente erhalten bleibt
    z. B. carousel ( 1, 2, 3 ) → ( ( 1, 2, 3 ), ( 2, 3, 1 ), ( 3, 1, 2 ) )


    variable = name | name '(' sentence { ',' sentence } ')'

    X Aufruf einer Variable X
    F( X ) Funktionsaufruf F mit Parameter X
    z. B. fac( 3 ) Funktionsaufruf “Fakultät”


    variable = name '@' structural | name '@@' structural

    F @ L Funktionsaufruf F mit berechneter Liste L
    F @@ L Funktionsaufruf F für alle Elemente einer Liste L

    Kommandos

    Die folgenden Kommandos werden unterstützt:

    command = '$eval' sentence { ';' … }

    Ein Ausdruck sentence wird eingegeben und sein Wert berechnet und ausgegeben.


    command = '$define' name '(' param { ',' param } ')' '=' sentence { ';' … }

    Eine Funktion wird definiert. Bei jedem Aufruf einer Funktion wird der Wert der Funktion als Variable gespeichert (“tabling”).


    command = '$define' name '(' param { ',' param } ')' { ';' … }

    Eine Funktion ohne Rumpf ist eine sog. Konstruktorfunktion. Sie erzeugt eine gleichnamige benannte Liste.


    param = name [ type ] | '#' name '(' name { ',' name } ')'

    Benannte Listen werden als formale Parameter in einer Funktionsdefinition erlaubt.

    Dadurch wird eine benannte Liste ein Objekt einer Klasse und die Funktion eine Methode der Klasse. Das folgende Beispiel zeigt die Definition der Addition zweier Brüche, i.e., zweier rationaler Zahlen der Klasse q. Das Objekt “#q( 1, 2 )” steht dabei für den Bruch “½”.

    $define add( #q( a, b ), #q( c, d ) ) = #q( a*d + c*b, b*d )
    add( #q( 1, 2 ), #q( 1, 3 ) ) → #q( 5, 6 ) 1/2 + 1/3 → 5/6


    param = sentence | '#' name '(' sentence { ',' sentence } ')'

    Als formale Parameter in einer Funktionsdefinition können auch Ausdrücke verwendet werden.


    pattern = name | name '(' ( sentence | type ) { ',' ( sentence | type ) } ')'
    pattern = name '@@' structural

    Bei Zeilenkommandos kann mithilfe von Mustern pattern nach Einträgen im Speicher gesucht werden.

    X Zeige Variable
    F( 3 ) Zeige Funktionswert
    F( _ ) Zeige bekannte Funktionswerte mit skalaren Argumenten
    F( % ) Zeige bekannte Funktionswerte mit Listen als Argumenten
    F( % C ) Zeige bekannte Funktionswerte mit benannten Listen als Argumenten


    type = '_' | '%' | '%%' name | '$'

    Formale Parameter von Objekten (Funktionen oder Variablen) werden typgebunden. Bei der Definition eines Objekts wird der Typ des Parameters spezifiziert. Beim Aufruf wird das Objekt nur dann unifiziert, wenn der Typ des aktuellen Parameters mit dem des formalen Parameters übereinstimmt.

    '_' Für den Paraneter ist ein skalarer Wert erlaubt. Dies ist der Default.
    '%' Für den Paraneter ist eine Liste erlaubt.
    '%%' name Für den Paraneter ist eine benannte Liste vom angegebenen Typ erlaubt.
    '$' Für den Paraneter ist ein String erlaubt.


    command = '$show'
    command = '$show' search { ';' … }

    Es werden alle passenden Definitionen angezeigt.

    '$show' Alle Definitionen werden angezeigt.
    '$show' name Alle Definitionen werden angezeigt, die zu dem Namen gehören.
    '$show' search Alle Definitionen werden angezeigt, die dem Muster entsprechen.

    Hinweis: Das Kommendo '$show' unterstützt weder Vergleiche noch den Operator '@@'.


    search = name | name '(' type { ',' type } ')'

    Bei Zeilenkommandos kann mithilfe von Mustern pattern nach Einträgen im Speicher gesucht werden.

    F Zeige Definition
    F( _ ) Zeige Definition mit skalaren Argumenten
    F( % ) Zeige Definition mit Listen als Argumenten
    F( % C ) Zeige Definition mit benannten Listen als Argumenten


    command = '$list'
    command = '$list' rule { ';' … }

    Es werden alle passenden Inhalte aber keine Definitionen angezeigt.

    '$list' Alle Inhalte werden angezeigt.
    '$list' name Alle Inhalte werden angezeigt, die zu dem Namen gehören.
    '$list' pattern Alle Inhalte werden angezeigt, die dem Muster entsprechen.
    '$list' pattern '==' sentence Alle Inhalte werden angezeigt, die dem Muster und dem Wert entsprechen.
    '$list' pattern '!=' sentence Alle Inhalte werden angezeigt, die dem Muster aber nicht dem Wert entsprechen.


    command = '$rules'
    command = '$rules' search { ';' … }

    Es werden alle passenden Klauseln angezeigt. Die Argumente sind analog denen bei $show.


    command = '$find' rule | sentence { ';' … }
    command = '$findall' rule | sentence { ';' … }

    Es wird versucht, noch nicht bekannte Inhalte zu ermitteln. Dabei werden alle passenden Inhalte angezeigt.


    command = '$delete' search { ';' … }

    Es werden alle passenden Definitionen und deren Inhalte gelöscht.

    '$delete' name Alle Definitionen werden gelöscht, die zu dem Namen gehören.
    '$delete' search Alle Definitionen werden gelöscht, die dem Muster entsprechen.

    Hinweis: Das Kommendo '$delete' unterstützt weder Vergleiche noch den Operator '@@'.


    command = '$untable' rule { ';' … }

    Es werden alle passenden Inhalte aber keine Definitionen gelöscht.

    '$untable' name Alle Inhalte werden gelöscht, die zu dem Namen gehören.
    '$untable' pattern Alle Inhalte werden gelöscht, die dem Muster entsprechen.


    command = '$unrule' search { ';' … }

    Es werden alle passenden Klauseln und deren Inhalte gelöscht. Die Argumente sind analog denen bei $delete.


    command = '$help'

    Es wird der Hilfetext wie beim Start angezeigt.


    command = '$history'

    Alle bereits eingegebenen Kommandos werden angezeigt, so dass diese erneut aufgerufen und ausgeführt werden können.


    command = '$restart'

    Alle Inhalte und Anzeigen werden auf ihren initialen Zustand zurückgesetzt.


    variable = name | name '(' sentence { ',' sentence } ')'

    X Definition einer Variable
    fac( 3 ) Definition einer Funktion “Fakultät”


    variable = name '@' structural | name '@@' structural

    fac @ L Definition einer Funktion mit berechneter Liste L
    fac @@ L Definition einer Funktion für alle Elemente der Liste L


    rule = pattern ( '==' | '!=' | '<' | '>' | '<=' | '>=' ) sentence
    rule = pattern [ '==' '_' ]

    Bei Zeilenkommandos kann mithilfe von Regeln rule nach Einträgen im Speicher gesucht werden, die einen bestimmten Wert haben.

    X == 3 Zeige Variable, falls sie dem Wert entspricht
    fac( 3 ) == 6 Zeige Funktionswert, falls sie dem Wert entspricht
    fac( _ ) Zeige alle bekannten Funktionswerte, die dem Wert entsprechen

    Voriger Beitrag Nächster Beitrag