Ein Interpreter für funktionale Spezifikationen

Ein Interpreter für die Definition und Auswertung von Funktionen.

Mai 02
Ein Interpreter für funktionale Spezifikationen Joachim Christ


Das Projekt “Calculator” wurde von seiner ursprünglichen Adresse in diesen Blog portiert. Die Dokumentation wurde aktualisiert und vervollständigt.

“Calculator” ist ein Interpreter mit variabler Arithmetik in verschiedenen Zahlensystemen.

Als Arithmetik stehen zur Verfügung: Gleitkomma-Arithmetik (‘float’), Bruch-Arithmetik und Ganzzahl-Arithmetik.

Durch die Gleitkomma-Arithmetik ist es möglich, z. B. trigonometrische Funktionen ('sin' oder 'cos') zu definieren. Wenn iterative Verfahren benutzt werden, um Näherungswerte von Funktionen wie die Quadratwurzel ('sqrt') zu berechnen, ist eine Arithmetik mit beliebiger Genauigkeit nicht zielführend. Deshalb werden Ergebnisse von Berechnungen aktuell auf 32 Stellen gerundet.

Die Gleitkomma-Arithmetik ist so umgesetzt, dass das Rechnen mit ganzen Zahlen immer ganze Zahlen als Ergebnis liefert.

In jeder Arithmetik-Variante werden zusätzlich ganze Zahlen in unterschiedlichen Zahlensystemen unterstützt.

Über Calculator

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

  • Neben Zahlen können auch Variable benutzt werden.

    An Variable können Werte zugewiesen werden. Diese und ihre Werte werden verwaltet und in einem internen Gedächtnis gehalten. Die Namen von Variablen setzen sich aus Buchstaben, Ziffern und '_' zusammen.

  • Namen dürfen auf Ziffern enden.

    Neben Namen wie '_abc' oder 'klaus' sind auch erlaubt: '_abc12' oder 'klaus1'. Verboten sind 'coffee2go' bzw. 'b2_c2'.

  • Beginnt der Name einer Variablen mit dem Zeichen '_', so wird diese Variable bei der Anzeige der gespeicherten Werte verborgen.

  • Mit der Syntax “F = X” kann ein Wert X an eine Variable F zugewiesen werden.

  • Zusätzlich zu den Operatoren für Zahlen werden Operatoren für logische Ausdrücke ('boolean') unterstützt.

    Zu nennen sind hier die Operatoren: 'and', 'or' oder 'not'.

  • Wegen weiterer logischer Operatoren sind die folgenden Ersetzungen zu beachten:
    Äquivalenz V == W
    Antivalenz (xor) V != W
    Implikation (⇒) not V or W
    V ? W : true
    Replikation (⇐) V or not W
    W ? V : true

  • Es können Funktionen mit Parametern definiert werden.

    Somit ist es möglich, mathematische Funktionen wie “Fakultät” oder “Fibonacci” zu benutzen. Zur Optimierung werden Ergebnisse von bereits berechneten Funktionswerten gespeichert. Damit reduziert sich der Aufwand zur Berechnung von z. B. Fibonacci-Zahlen erheblich und die Beschreibung der Funktion muss nicht zur Optimierung abgewandelt werden.

    Hier sei angemerkt, dass Funktionen mit unterschiedlicher Anzahl von Parametern als unterschiedlich betrachtet werden. D. h., dass die Meldung bei abweichender Parameteranzahl ein nicht existierendes Objekt reklamiert, nicht eine falsche Parameteranzahl.

    Eine Funktion f(1) unterscheidet sich demnach von f(1, 2).

  • Funktionsdefinitionen werden so abgespeichert, wie sie vom Anwender eingegeben wurden und können angeklickt werden, so dass sie editiert werden können.

  • Neben der Benutzung von Funktionen (“$eval fac(2)”), um das Ergebnis einer Funktion anzuzeigen, kann nach dem Argument gesucht werden, das einen vorgegebenen Funktionswert liefert (“$find fac(_) = 24”).

    Dabei wertet “$eval” einen Ausdruck aus, “$list” zeigt alle Inhalte im Speicher an und “$find” versucht, eine weitere Lösung zu finden.

  • Ergebnisse, die den Wert 'false' haben, werden gänzlich nicht angezeigt; sie werden aber gespeichert.

    Bei Ergebnissen, die den Wert 'true' haben, wird “'==' 'true'” nicht angezeigt.

  • Zur Optimierung wird die sogenannte ‘lazy evaluation’ benutzt.

    Dies bedeutet, dass z. B. eine Verknüpfung mit 'and' nicht mehr weiter ausgewertet wird, wenn der erste Operand 'false' ist. Analog werden die Operatoren 'or' bzw. B '?' X ':' Y behandelt.

  • In Zeilen sind Kommentare erlaubt.

    Diese beginnen mit '//' und gehen bis zum Zeilenende. In '/*' und '*/' eingefasste Zeichenketten werden ebenso als Kommentare überlesen. Solche Kommentare sind überall erlaubt, wo ein ';' stehen darf und ersetzen diesen.

  • Jeder Eingabe, bei der es sich nicht um ein Kommando handelt, wird das Kommando '$find' vorangestellt.
    eval 12 == 13 → false
    find 12 == 13 Keine Anzeige.
    eval 12 == 12 → true
    find 12 == 12 → 12 == 12

  • Das Kommando '$findall' sucht alle Ergebnisse einer Abfrage.

    Demgegenüber sucht '$find' nur ein weiteres bisher unbekanntes Ergebnis.

  • Beim Aufruf des Kommandos '$find' wird jeweils eine neue Lösung angezeigt und dann die Suche ausgesetzt.

    Durch wiederholtes Aufrufen desselben Kommandos wird die Suche fortgesetzt, bis alle Lösungen gefunden sind.

  • Bei den Kommandos '$list' und '$find' kann nach einem Ergebniswert mithilfe aller Vergleichsoperatoren gesucht werden.

    Wird die Suchbedingung “== sentence” weggelassen, so entspricht dies “== _”, also dem Vergleich mit einem beliebigen Wert.

  • Über Zeilenkommandos werden spezielle Operationen für Variable oder Funktionen aufgerufen.

    Z. B. zum Anzeigen ('$list') oder Löschen ('$untable') von Variablen. Bzw. zum Anzeigen ('$show') oder Löschen ('$delete') von Funktionen.

  • Das Kommando '$show' zeigt nur Definitionen an, wohingegen das Kommando '$list' lediglich Werte von Variablen oder Funktionen anzeigt, aber nicht deren Definitionen.

  • Das Kommando '$untable' löscht lediglich Werte von Variablen, aber nicht deren Definitionen.

    Demgegenüber löscht das Kommando '$delete' sowohl Funktionen als auch zugehörige Werte von Variablen.

  • Die Funktion 'neg' ist analog zur Benutzung eines negativen Vorzeichens '-'.

  • Bei allen Kommandos, die Argumente akzeptieren, können mehrere Argumente durch Semikolon ';' getrennt hintereinander gesetzt werden.

  • Wird hinter einem Semikolon bei Kommandos ein '$' geschrieben, so wird ein anderes Kommando gewählt..

  • Bei den Kommandos '$show' und '$list' kann nur der Name eines Objekts angegeben werden, um alle Einträge unter diesem Namen anzuzeigen.

    Dies kann jedoch weder für '$delete' noch für '$untable' ausgenutzt werden.

  • Das Kommando '$history' zeigt alle bereits eingegebenen Kommandos an, so dass diese erneut aufgerufen und ausgeführt werden können.
  • Über Zahlensysteme

    Diese Hinweise zeigen die Historie und die wesentlichen Erweiterungen im Laufe der Entwicklung bei Zahlen in verschiedenen Zahlensystemen.

  • Eine ganze Zahl in einem bestimmten Zahlensystem wird in { und } eingeschlossen. Alternativ kann (::) für {} geschrieben werden.

  • Innerhalb der geschweiften Klammern steht zunächst die Basis der Zahl; danach stehen durch : getrennt die Ziffern der Zahl im gewählten Zahlensystem.

    Z. B. steht also {2:100} für 4 (Dualsystem zur Basis 2) oder {16:ff} für 255 (Hexadezimalsystem zur Basis 16). Die Basis des Zahlensystems wird immer im Dezimalsystem ausgedrückt.

  • Es sind Zahlensysteme zur Basis 2 bis 36 erlaubt.

    Als Ziffern werden zuerst '0' bis '9' und dann 'a' bis 'z' verwendet. Die Zahl {36:zz} ist demnach äquivalent zu {10:1295}.

  • Der Operator xor ist neu und kann auf logische Werte angewendet werden.

  • Die logischen Operatoren not, and, or und xor können auf Dualzahlen angewendet werden.

  • Liegen die Operanden für logische Operatoren nicht im Dualsystem vor, so werden sie ins Dualsystem konvertiert.

  • Die Eingabe 3 and 1 ist nicht erlaubt; wohingegen aber {10:3} and {10:1} oder {2:11} and {2:1} erlaubt sind und {2:1} als Ergebnis liefern.

  • Die Vergleichs-Operatoren ==, !=, …, < und <= können auf Zahlen in beliebigen Zahlensystemen angewendet werden.

  • Dies gilt auch für die arithmetischen Operatoren +, , *, /, div und mod.

  • Ebenso gilt dies für die Vorzeichen + und .

  • Stimmen die Zahlensysteme von zwei Operanden eines Operators nicht überein, so wird die zweite Zahl ins Zahlensystem der ersten Zahl konvertiert.

  • Die Eingabe {10:3} + {2:1} liefert {10:4} als Ergebnis, wohingegen die Eingabe {2:1} + {10:3} als Ergebnis {2:100} liefert.

  • Auch die Funktionen neg, abs und sign sind für Zahlen in beliebigen Zahlensystemen definiert.

  • Die neue Funktion conv dient dazu, eine Zahl aus einem Zahlensystem in ein anderes Zahlensystem zu konvertieren.

    Das erste Argument ist das neue Zahlensystem (als Dezimalzahl); das zweite Argument ist die zu konvertierende Zahl.

    Z. B. conv 10 {2:1111}{10:15}

  • Über Listen

    Diese Hinweise zeigen die Historie und die wesentlichen Erweiterungen bei Listen.

  • Listen werden in runde Klammern '(' und ')' eingeschlossen.

    Dabei steht '()' für die leere Liste.

  • Es gilt, dass einstellige Listen und skalare Werte kontextabhängig ineinander konvertiert werden.

  • Die Spezifikation einer (unbenannten) Liste als Parameter erfolgt über '%'.

  • Listen könnnen benannt werden.

    Um eine Liste zu benennen, wird ihr '#' und ihr Name vorangestellt.

    #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”

  • Im Gegensatz zu unbenannten Listen bringen benannte Listen ihre Bedeutung mit sich.

    Dadurch können generische Operatoren wie “+” definiert werden, deren Wirkungsweise vom Typ der Liste abhängt.

    #q( 1, 3 ) + #q( 1, 2 ) Rationale Zahlen → #q( 5, 6 ) ↔ 5/6
    #c( 1, 3 ) + #c( 1, 2 ) Komplexe Zahlen → #c( 2, 5 ) ↔ 2 + 5i
    #v( 1, 3 ) + #v( 1, 2 ) Vektoren → #v( 2, 5 ) ↔ ( 25 )
    #q( 1, 3 ) * #q( 1, 2 ) Rationale Zahlen → #q( 1, 6 )
    #c( 1, 3 ) * #c( 1, 2 ) Komplexe Zahlen → #c( -5, 5 )
    #v( 1, 3 ) * #v( 1, 2 ) Vektoren (Kreuzprodukt) → undefiniert

  • Die Spezifikation einer benannten Liste als Parameter erfolgt über '%%' und deren Namen.

  • Benannte Listen werden als formale Parameter in einer Funktionsdefinition erlaubt.

    Zu beachten ist, dass jedoch eine Defintion f( x%%q ) durch f( #(q( 1, 2 ) ) überschrieben wird.

  • Um eine strengere Typprüfung erreichen zu können, werden sog. Konstruktorfunktionen eingeführt.

    Eine solche Funktion hat keinen Rumpf. Sie erzeugt eine gleichnamige benannte Liste. Die Konstruktorfunktion erzeugt also aus einer Liste eine benannte Liste.

    Bei der Notation eines Literals einer benannten Liste #q( … ) wird überprüft, ob es dafür eine kompatible Konstruktorfunktion gibt.

  • Im Rahmen der strengeren Typprüfung sind nur Vergleiche auf Gleichheit und Ungleichheit von benannten Listen erlaubt.

  • Parameter von Objekten (Funktionen oder Variablen) sind typgebunden.

    Bei der Definition eines Objekts wird der Typ des Parameters spezifiziert. Beim Aufruf wird das Objekt nur dann gefunden, wenn der Typ des aktuellen Parameters mit dem des formalen Parameters übereinstimmt.

    Dies bedeutet, dass ein Name nicht nur mit unterschiedlichen Aritäten bekannt sein kann, sondern auch mit unterschiedlichen Parametertypen überladen werden kann.

    Eine Funktion f(1) unterscheidet sich demnach sowohl von f( (1, 2) ) als auch von f( #q(1,2) ).

  • Für die Verarbeitung von Listen werden die im Folgenden erläuterten Operatoren bereit gestellt.

    Die Wirkungsweise bei benannten Listen ist identisch, die Eigenschaft der Benennung geht jedoch verloren.

  • Der Operator '|' hängt Listen hintereinander.
    1 | ( 1, 2 ) → ( 1, 1, 2 )
    ( 1, 2 ) | 3 → ( 1, 2, 3 )
    ( 1, 2 ) | ( 3, 4 ) → ( 1, 2, 3, 4 )

  • Der Operator '~' entnimmt Elemente aus einer Liste.
    ( 1, 2 ) ~ 1 → 1
    3 ~ ( 1, 2 ) → ( 3 )
    ( 4, 5 ) ~ ( 2, 3 ) → ( 5 )
    ( 4, 5, 7 ) ~ ( 2, 3 ) → ( 5, 7 )
    ( 4, 5, 7 ) ~ ( 1, 3 ) → ( 4, 7 )

  • Die Funktion 'size' liefert die Länge einer Liste.
    size ( 4, 5, 7 ) → 3

  • Die Funktionen 'sum' bzw. 'prod' liefern die Summe bzw. das Produkt aller Listenelemente.
    sum ( 4, 5, 7 ) → 16
    prod ( 4, 5, 7 ) → 140

  • Mithilfe der Operatoren '==' und '!=', werden Listen verglichen.

    Als erstes Kriterium wird dabei die Länge der Liste herangezogen. Bei gleicher Länge werden die Elemente verglichen.

    1 == ( 1, 2 ) → false
    ( 1, 2 ) == 3 → false
    ( 1, 2 ) == ( 1, 2 ) → true
    ( 2, 1 ) == ( 1, 2 ) → false
    ( 1, 2, 3 ) == ( 1, 2 ) → false

    Die Operatoren '<', '>', '<=' und '>=' werden analog behandelt.

  • Mithilfe der Operatoren '==' und '!=', werden auch benannte Listen verglichen.
    #q( 1 ) == 1 → false
    #q( 1, 2 ) == #q( 1, 2 ) → true
    #q( 2, 1 ) == #q( 1, 2 ) → false
    #q( 1, 2 ) == #w( 1, 2 ) → false

    Die Operatoren '<', '>', '<=' und '>=' stehen nicht zur Verfügung.

  • Die Operatoren '+', '-', '*', '/', … werden für Listen nicht unterstützt.

    Eine wichtige Ausnahme stellt dabei eine Liste der Länge eins dar. Bei arithmetischen Operationen wird mit dem ersten Element der Liste gerechnet.

    0.5 * ( 2 + 2 ) → 2

  • Die Funktion 'sort' sortiert eine Liste.
    sort ( 7, 4, 5 ) → ( 4, 5, 7 )

  • Die Funktionen 'min' bzw. 'max' liefern das Minimum bzw. das Maximum aller Listenelemente.
    min ( 4, 5, 7 ) → 4
    max ( 4, 5, 7 ) → 7

  • Die Funktionen 'head', 'tail', 'snake' und 'rattle' liefern spezielle Teile von Listen.
    head ( 4, 5, 7 ) → 4
    tail ( 4, 5, 7 ) → ( 5, 7 )
    snake ( 4, 5, 7 ) → ( 4, 5 )
    rattle ( 4, 5, 7 ) → 7

  • Die Funktion 'permute' liefert alle Permutationen der eingegebenen Listen.
    permute ( 1, 2 ) → ( ( 1, 2 ), ( 2, 1 ) )

  • Die Funktion 'reverse' liefert die Umkehrung der eingegebenen Listen.
    reverse ( 1, 2, 3, 4 ) → ( 4, 3, 2, 1 )

  • Die Funktion 'carousel' liefert alle Permutationen, bei denen die Reihenfolge der Elemente erhalten bleibt.
    carousel ( 1, 2, 3 ) → ( ( 1, 2, 3 ), ( 2, 3, 1 ), ( 3, 1, 2 ) )

  • Im Rahmen der strengeren Typprüfung sind folgende Operatoren für benannte Listen verboten: 'sort', 'sum', 'prod', 'min' und 'max'.

    Die Operatoren '|', 'tail' und 'snake' können beliebige benannte oder unbenannte Listen verarbeiten und behalten einen eindeutigen Namen bei.

  • Der Operator ':' dient dazu, in eine Liste eine Folge von Zahlen aufzunehmen.

    Er ist nur innerhalb einer Liste erlaubt.

    ( 2, 3:5, 9 ) → ( 2, 3, 4, 5, 9 )
    ( 2, 5:3, 9 ) → ( 2, 5, 4, 3, 9 )

  • Der Operator '@' dient dazu, eine Funktion einmal aufzurufen.

    Dabei wird eine berechnete Liste als Parameter übergeben. Im Beispiel wird angenommen, dass die Variable 'x' den Wert '( 2, 3 )' habe.

    fac @ 2 ⇔ fac( 2 ) → 2
    fac @ fac @ 4 ⇔ fac( fac( 4 ) ) → 620448401733239439360000
    pow @ ( 3, 1 ) ⇔ pow( 3, 1 ) → 3
    pow @ x ⇔ pow( 2, 3 ) → 8

  • Der Operator '@@' dient dazu, eine Funktion wiederholt aufzurufen.

    Dabei erfolgt für jedes Element einer Liste ein Aufruf der Funktion.

    fac @@ ( 5, 6 ) ⇔ ( fac( 5 ), fac( 6 ) ) → ( 120, 720 )
    pow @@ ( (2,1), (2,4), (3,1), (3,4) ) ⇔ ( pow(2,1), pow(2,4), pow(3,1), pow(3,4) ) → ( 2, 16, 3, 81 )

    Hinweis: Dieser Operator darf nur als Argument eines Kommandos benutzt werden.

  • Der Operator '**' berechnet das kartesische Produkt zweier Listen.
    ( 1 ) ** ( 3, 4 ) → ( (1,3), (1,4) )
    ( 1, 2 ) ** ( 3, 4 ) → ( (1,3), (1,4), (2,3), (2,4) )
    ( 1 ) ** ( 3, 4 ) ** ( 5, 6 ) → ( (1,3,5), (1,4,5), (1,3,6), (1,4,6) )
  • Über Mengen

    Diese Hinweise zeigen die Historie und die wesentlichen Erweiterungen bei Mengen.

  • Mengen sind spezielle Listen, in denen jedes Element nur einmal auftreten kann.

    Mengen werden in runde Klammern '#set(' und ')' eingeschlossen. Dabei steht '#set()' für die leere Menge. Eine Menge stellt demnach einen Sonderfall einer benannten Liste (mit dem Name 'set') dar.

  • Die Funktion 'set' sortiert eine Liste und bereinigt sie um doppelte Einträge, konvertiert also eine Liste in eine Menge.
    set( 4, 5, 7, 4, 5 ) → #set( 4, 5, 7 )

  • Für die Verarbeitung von Mengen werden die im Folgenden erläuterten Operatoren bereit gestellt.

  • Der Operator '||' bildet die Vereinigungsmenge.
    1 || ( 1, 2 ) → ( 1, 2 )
    ( 1, 2 ) || 3 → ( 1, 2, 3 )
    ( 1, 2 ) || ( 3, 4 ) → ( 1, 2, 3, 4 )

  • Der Operator '&&' bildet die Schnittmenge.
    1 && ( 1, 2 ) → ( 1 )
    ( 1, 2 ) && 3 → ( )
    ( 1, 2 ) && ( 1, 3 ) → ( 1 )

  • Der (nicht kommutative) Operator '^^' schließt Elemente der zweiten Menge aus der ersten Menge aus.
    1 ^^ ( 1, 2 ) → ( )
    ( 1, 2 ) ^^ 1 → ( 2 )
    ( 1, 2 ) ^^ ( 1, 3 ) → ( 2 )
    ( 1, 3 ) ^^ ( 1, 2 ) → ( 3 )

  • Der Operator '&' prüft, ob eine Menge (streng) in einer zweiten Menge enthalten ist.

    Demgegenüber prüft der Operator '&=', ob eine Menge in einer anderen enthalten oder gleich mit dieser ist.

    1 & ( 1, 2 ) → true
    3 & ( 1, 2 ) → false
    ( 1, 2 ) & 3 → false
    ( 1, 2 ) & ( 1, 2, 3 ) → true

  • Die Funktion 'card' liefert die Kardinalität einer Menge.
    card( 2, 1, 2 ) → 2

  • Mithilfe der Operatoren '==' und '!=', werden Mengen verglichen.
    1 == set( 1, 2 ) → false
    set( 1 ) == 1 → false
    set( 1, 2 ) == set( 1, 2 ) → true
    set( 2, 1 ) == set( 1, 2 ) → true
    set( 1, 2, 3 ) == set( 1, 2 ) → false
  • Über die Definition von Funktionen

    Das Kommando $define definiert oder erweitert eine Funktion.


    $define f( x ) = x

    Dies definiert eine Funktion f. Diese Funktion erlaubt einen Parameter, der skalar sein muss.

    Intern wird diese Funktion unter dem “Namen” f(_) gespeichert.

    $eval f( 12 ) → 12


    $define f( x, y ) = x * y

    Die Funktion f wird hiermit überladen. Ab jetzt kann die Funktion auch mit zwei Parametern − beide skalar − aufgerufen werden.

    Intern wird diese Funktion unter dem “Namen” f(_,_) gespeichert.

    $eval f( 6, 24 ) → 144


    $define f( x % ) = sum x

    Die Funktion f wird hiermit überladen. Ab jetzt kann die Funktion auch mit einem Parameter und zwar einer Liste aufgerufen werden.

    Intern wird diese Funktion unter dem “Namen” f(%) gespeichert.

    $eval f( ( 1:10 ) ) → 55


    $eval f( #q( 1, 2 ) )

    Dieser Aufruf benötigt eine Funktion mit dem internen Namen f(%%q). Da eine solche nicht definiert ist, erfolgt eine Fehlermeldung. Bei einem Aufruf werden die Parameter streng überprüft.

    Jedoch gilt: $eval f( unname #q( 1, 2 ) ) → 3


    $define f( x %% q, y %% q ) = #q( x~1 * y~2 + y~1 * x~2, x~2 * y~2 )

    Die Funktion f wird hiermit weiter überladen und kann nun auch zwei Parameter vom Typ Liste mit Namen q bearbeiten. Hinweis: Bei dieser Funktion handelt es sich um die Addition zweier Brüche.

    Intern wird diese Funktion unter dem “Namen” f(%%q,%%q) gespeichert.

    $eval f( #q(1,2), #q(1,3 )) → #q( 5, 6 )


    $define f( #q( z1, n1 ), #q( z2, n2 ) ) = #q( z1 * n2 + z2 * n1, n1 * n2 )

    Diese Definition ersetzt die obige, denn auch ihr interner Name ist f(%%q,%%q).

    $eval f( #q(1,2), #q(1,3 )) → #q( 5, 6 )


    $define g( x, y ) = ( x, y ) == ( 2, 3 ) ? 2 : x == 2 ? y : y == 3 ? x : x * y

    Dies ist eine korrekte Definition einer Funktion. Doch was bedeutet sie?


    $define g( x, y ) = x * y
    $define g( 2, y ) = y
    $define g( x, 3 ) = x
    $define g( 2, 3 ) = 2

    Die Definition einer Funktion kann in mehreren Schritten notiert werden.

    Dabei erweitert jede neue Spezifikation die ursprüngliche Definition um eine weitere Abfrage. Schlußendlich liegt dem System also die identische Definition vor, wie sie eingangs gegeben wurde, jedoch schrittweise und für den Anwender nachvollziehbar.

    Die Reihenfolge, in der das System die einzelnen Definitionen heranzieht, kann nur eingeschränkt vorgegeben werden. Das System versucht zunächst, eine Definition zu finden, die in allen Parametern mit Festwerten übereinstimmt (im Beispiel: ( 2, 3 )). Danach werden solche Definitionen herangezogen, die teilweise Festwerte und teilweise freie Parameter vorgeben. Trifft keine solche zu, wird schlußendlich die Definition benutzt, die auf allen Stellen freie Parameter erlaubt (im Beispiel: ( x, y )).


    $define g( x, x ) = 2 * x

    Über dieses Verfahren sind auch Spezifikationen möglich, die ausdrücken, dass mehrere Parameter identisch sein sollen.


    $define g( x, y ) = ( x + 2 ) * y

    Diese Definition überschreibt die zuvor gegebene Definition g( x, y ) = x * y.

    Darüberhinaus können jedoch Teildefinitionen nicht einzeln gelöscht werden. Die Löschung der Funktion g löscht alle Teildefinitionen.

    Über die Auswertung von Funktionen

    Mit den Kommandos $eval, $list sowie $find stehen verschiedene Formen der Auswertung zur Verfügung.

    $eval fac( 7 )

    Werte die Funktion aus und zeige das Ergebnis an.


    $eval fac @@ ( 1, 2, 3, 5:6 )

    Werte die Funktion für alle Elemente der Liste aus und zeige die Ergebnisse an.


    $list fac( _ )

    Zeige alle bekannten Ergebnisse der Funktion an. Es werden nur Ergebnisse von Funktionen mit skalaren Parametern berücksichtigt.


    $list fac @@ ( 1, 2, 3, 5:6 )

    Zeige alle Ergebnisse der Funktion für Argumente aus der angegebenen Menge an, sofern diese bekannt sind.


    $list fac( 6 )

    Zeige das Ergebnis der Funktion für das Argument an, sofern dieses bekannt ist.


    $list fac( 3 ) == 6

    Zeige das Ergebnis der Funktion für das Argument an, sofern dieses bekannt ist und mit dem Ergebniswert übereinstimmt.

    Hier sind alle Vergleichsoperatoren erlaubt.


    $list fac( _ ) == 24

    Zeige alle bekannten Ergebnisse der Funktion an, sofern diese mit dem Ergebniswert übereinstimmen.

    Auch hier sind alle Vergleichsoperatoren erlaubt.


    $find fac( 6 )

    Analog: $eval fac( 6 ).


    $find fac @@ ( 1, 2, 3, 5:6 )

    Analog: $eval fac @@ ( 1, 2, 3, 5:6 ).


    $find fac( 3 ) == 6

    Analog: $eval fac( 3 ) und anschließend $list fac( 3 ) == 6.


    $find fac @@ ( 1:24 ) == 24

    Analog: $eval fac @@ ( 1:24 ) und anschließend $list fac @@ ( 1:24 ) == 24.

    In diesem Beispiel gibt der Anwender sein Wissen vor, dass eine Suche nur für die Argumente 1 bis 24 ausgeführt werden muss.


    $find fac @@ ( 1:sqrt( 24 ) ) == 24

    Analog: $eval fac @@ ( 1:sqrt( 24 ) ) und anschließend $list fac @@ ( 1:sqrt( 24 ) ) == 24.

    Hier ist das Wissen des Anwenders optimaler, als die Suche beim Erreichen des Werts 5 abgebrochen werden kann.


    $find fac( _ ) == 24

    In diesem Fall wird versucht, die Lösung zu finden.

    Durch Bestimmen der Funktionsergebnisse für die Argumente 1 und 2 wird vermutet, ob die Funktion aufsteigt oder absteigt. Wenn sie aufsteigend ist, wird solange der nächst höhere Wert berechnet, bis entweder das Ergebnis erreicht oder überschritten ist. Sollte die Funktion unterdessen nicht mehr aufsteigen, wird die Suche abgebrochen.

    Anschließend wird $list fac( _ ) = 24 aufgerufen.

    Für absteigende Reihen wird analog vorgegangen.


    $find fac( _ ) == 24

    Die zugrundeliegende Problematik ist die Herleitung der Umkehrfunktion zur “Fakultät”.

    Eine Lösung z. B. in Prolog kann nur berechnet werden, wenn Zusatzmoduln zur iterativen Einschränkung des Lösungsraums benutzt werden.

    Im Wesentlichen ist die Idee dabei, zuerst einmal zu berücksichtigen, dass nur solche Zahlen in Frage kommen, die als Divisor des Dividenden 24 bei einer ganzzahligen Division den Rest 0 ergeben. Somit kommt als Lösungsmenge lediglich 1..24 in Frage.

    Das Problem der Lösung der Umkehrfunktion fac-1(24) reduziert sich im übernächsten Schritt auf die Lösung des Problems für 12 mit der dazugehörigen Lösungsmenge 3..12. Danach bereits schrumpft bei Betrachtung von 4 die Lösungsmenge auf 4..4.

    Über abstrakte Datentypen

    Ein abstrakter Datentyp besteht aus einem Wertebereich und darauf definierten Operationen. Die Menge der Operationen bezeichnet man auch als Schnittstelle des Datentyps.

    Abstrakte Datentypen werden über benannte Listen abgebildet.


    In der ersten Variante erfolgt die Abbildung über rekursive Strukturen:


    $define stack()

    Die Definition eines leeren Stacks ist in beiden Varianten identisch. Es wird eine Konstruktorfunktion benutzt.


    $define stack( x, y %% stack )

    Die Ablage eines Elements auf den Stack erfolgt, indem eine neue rekursive Stufe aufgebaut wird. Auch dies leistet eine Konstruktorfunktion.


    $define top( #stack( x, y %% stack ) ) = x

    Der Zugriff auf das zuletzt abgelegte Element erfolgt über die Umkehrung des Konstruktors.


    $define pop( #stack( x, y %% stack ) ) = y

    Der Zugriff auf den verbleibenden Stack erfolgt über die Umkehrung des Konstruktors.


    $eval stack( 1, stack( 2, stack() ) )

    Hier wertet sich der Ausdruck wie folgt aus: #stack( 1, #stack( 2, #stack() ) ).


    In der zweiten Variante erfolgt die Abbildung über einstufige Listen:


    $define stack()
    $define stack( y % )

    Die Definition eines leeren Stacks ist in beiden Varianten identisch. Die zweite Form dient dazu, diese Abbildung des Stacks als Literal schreiben zu können.


    $define stack( x, y %% stack ) = x | y

    Die Ablage eines Elements auf den Stack erfolgt über die eingebaute Listenfunktion.


    $define top( x %% stack ) = head x

    Der Zugriff auf das zuletzt abgelegte Element erfolgt über die eingebaute Listenfunktion.


    $define pop( x %% stack ) = tail x

    Der Zugriff auf den verbleibenden Stack erfolgt über die eingebaute Listenfunktion.


    $eval stack( 1, stack( 2, stack() ) )

    Hier wertet sich der Ausdruck wie folgt aus: #stack( 1, 2 ).


    ↵


    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


    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.


    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 = '$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 = '$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