Kurs:Programmieren in Aleph/Infix-Notation

Infix-Notation

Aleph bevorzugt die postfix-Notation. Allgemein wird jedoch die infix-Notation beorzugt, weil es "einfacher" ist. Einfach ist ein problematischer Begriff. Im Fall der unterschiedlichen Notationen ist "einfach" ein Synonym für gewohnt. Gewohnte Handlungen erscheinen einfacher, weil sie über lange Zeiträume hinweg geübt wurden. Übung bedeutet weniger Fehler, weniger Fehler bedeuten schnellere Umsetzung.

Auf diese unbestreitbaren Vorteile soll auch unter Aleph nicht verzichtet werden. Deshalb ist eine Kombination aus Java- und Aleph-Programmen vorhanden, die infix-Notation in Aleph ermöglicht.

Überlegungen zur Umsetzung der Infix-Notation

Die infix-Notation ist an viele Voraussetzungen gekoppelt. Viele davon werden überhaupt nicht mehr als solche wahrgenommen. Um den Anwender möglichst wenig einzuengen, hier die wichtigsten Voraussetzungen zur Interpretation von infix-Ausdrücken.

Es gibt unäre und binäre Operatoren.

So ist + stets binär, denn 3+4. Aber – kann unär sein, denn 3 + -4.

Unäre Operatoren sind stets prefix.

So muss 4! (Fakultät) als Funktion realisiert werden.

Operatoren haben Prioritäten.

Weil 3+4*5 = 23 und 3*4+5 = 35 ergibt.

Namen von Operatoren haben (fast immer) die Länge 1.

Die Ausnahmen sind "!=", "<>" für ungleich, "<=" für kleiner_oder_gleich und ">=" für größer_oder_gleich.

Eine weitere Gegebenheit ist noch vorhanden. Wird in dem Term eine Funktion mit einem Vorzeichen versehen, so ist stets der gelieferte Funktionswert gemeint und nicht die Funktion selbst.

Ein Beispiel:

$-\sin \left(x\right)=-1\cdot \sin \left(x\right)=0-\sin \left(x\right)=\sin \left(x+\pi \right)=\sin \left(x-\pi \right)...$

Weil sich derartige Probleme bei vielen Funktionen finden und Mehrdeutigkeiten immer zu Problemen führen, gilt bei Aleph

$-\sin \left(x\right)={\boldsymbol {neg}}\left(\sin \left(x\right)\right)$

bei "neg" handelt es sich um eine Funktion mit einem Argument. Der Name steht für negativ und nicht für Negation. Weil Zahlen in Aleph über eine Identitätsfunktion definiert sind, entspricht der kalkulatorische Term

$3+-4$

dem funktionalen Term

${\boldsymbol {id}}\left(3\right)+{\boldsymbol {neg}}\left({\boldsymbol {id}}\left(4\right)\right)$

Während der Programmierung wäre die Beachtung dieser Details eine Zumutung. Deshalb übernimmt ein Java-Programm namens "HandleTerm" die notwendigen Arbeiten.

Einrichten der infix-Notation

Weil Aleph keine Syntax kennt, sind Operatoren und Funktionen allein Sache der Programmierung. Bei der infix-Notation ist diese Freiheit allerdings nicht mehr gegeben, denn es gibt Regeln. Die bekannteste dürfte wohl "Punkt- vor Strichrechnung" sein. Es sind aber weitaus mehr. Trotzdem soll weiterhin ein möglichst hohes Maß an Freiheit vorhanden sein. Die Bezeichnungen der Operatoren und Funktionen bleiben dem Anwender überlassen. Diese Freiheit ist bei Funktionen weitgehend auch in anderen Sprachen vorhanden, bei Operatoren aber selten.

Dieser Abschnitt zeigt die Einrichtung einer einfachen Grundlage für die Umsetzung von infix- in postfix-Notation. Dabei werden auch Bezeichner verwendet, die im einfachen Aleph überhaupt nicht vorhanden sind. Sie können aber für die Entwicklung eigener Lösungen sehr hilfreich sein. Natürlich werden diese "Unbekannten" auf ihre Notwendigkeit hin untersucht und besprochen.

Parser bereitstellen

Der Parser ist sehr einfach gehalten und in Java programmiert. Für Aleph ist also ein Programm "in Maschinensprache". In den Kernel wurde es nicht aufgenommen, weil die Verwendung der infix-Notation prinzipiell auch ein Wechsel der Sprache ist. Für höhere Ansprüche - Entwicklung völlig neuer Programmiersprachen - sollte der hier vorhandene Parser als "Einstieg" angesehen werden. Der Einsatz von umfangreicheren Generatoren, wie z.B. javaCC ist dann einfacher. Der Mehraufwand ist allerdinge erheblich und sollte nicht unterschätzt werden.

In der Datei "infix.vvm" enthält bereits alle notwendigen Maßnahmen zur Bereitstellung des Parsers. Hier werden nur die wesentlichen Punkte betrachtet, um eigene Erweiterungen zu erleichtern.

"parsing.HandleTerm" classify instantiate

Zunächt wird eine Instanz des Parsers erzeugt. In diesem Objekt sind die Methoden zur Übersetzung von in- nach postfix vorhanden. Es sind noch keinerlei Namen vereinbart. Es besteht also auch hier völlige Freiheit.

Funktionen bereitstellen

Die Funktionen sind nur mit ihren Namenbekannt. Der Parser jat keinerlei Kenntnis, ob die hier vorhandenen "Zeichenketten" mit irgend einer Funktionalität belegt sind. Es ist nicht Aufgabe eines Parsers auf Inhalte zu achten. Alle Namen der Funktionen sind in einer eigenen Klasse gekapselt.

"parsing.Functions" classify instantiate
dup "append { String }" method app
"neg"  app             // diese "Funktion" ist Pflicht.
"not"  app
"abs"  app
"cos"  app
"cot"  app
"exp"  app
"ln"   app
"sin"  app
"sqrt" app
"tan"  app
"xyz"  app             // nur für das Beispiel vorhanden
"app" find drop forget // Methode vergessen, wenn gewünscht.

Für die Erweiterung der Liste mit Funktionen steht in der Klasse "Functions" die Methode "append" bereit. Damit diese Methode einfach in Aleph verwendet werden kann, wird sie als Command "app" ins Wörterbuch aufgenommen. Sind alle Funktionen bekannt, sollte das Command vergessen werden.

Die Funktion "neg" wurde bereits erwähnt.Der Parser geht allerdings von diesem Namen aus. Die Funktion "xyz" ist hohl (nix, dummy) und spielt bei den Operatoren als Beispiel eine wichtige Rolle. Die Funktionen müssen jetzt noch dem Parser zur Verfügung gestellt werden. Es genügt die "Functions" an entsprechender Stelle im Übersetzer zu speichern.

1 ndup       // Übersetzer nach oben duplizieren
"functions"  // Name des Fields
swap         // Übersetzer nach oben kopieren
store        // Übersetzer field functions Übersetzer -->  Übersetzer

Operatoren bereitstellen

Die Bereitstellung der Operatoren ist prinzipiell dem eben beschriebenen Vorgang ähnlich.

"parsing.Operators" classify instantiate
dup "append { String int }" method app
"("  100 app
")"  100 app
","  150 app // wichtig für Funktionsargumente
"<"  200 app
">"  200 app
"="  200 app
"!=" 200 app // fest veankert
"<>" 200 app // fest veankert
"<=" 200 app // fest veankert
">=" 200 app // fest veankert
"|"  300 app
"+"  300 app
"-"  300 app
"&"  400 app
"*"  400 app
"/"  400 app
"!"  500 app
"^"  500 app
"app" find drop forget // Methode vergessen
1 ndup "operators" swap store

Die Namen der Operatoren sind um ihre Priorität ("*" höher als "+", also Punkt- vor Strichrechnung) erweitert. Dieser Wert ist für eine korrekte Übersetzung sehr wichtig. In dieser Beschreibung wird noch auf die Mechanismen der Übersetzung eingegangen, damit eigene Operatoren auch mit der entsprechenden Gewichtung ausstatten werden können. Vier Operatoren haben Bezeichner aus zwei Zeichen. Sie wurden bereits im Abschnitt Gegebenheiten besprochen. Die Erkennung dieser Namen ist fest im Übersetzer verankert.

Funktionsargumente

Funktionen haben ein oder mehrere Argumente. Der ','-Operator (Komma) gestattet die Unterscheidung der Argumente. Der Parser berücksichtigt die Freiheiten von Aleph. So ist auch die Formulierung von Funktionen zulässig, deren Argumentanzahl unbekannt ist. Es ist also möglich, Argumentlisten beliebiger Länge an eine Funktion zu übergeben. Trotzdem muss die korrekte Zuordnung gewährleistet sein. Das Java-Programm "testParser" zeigt ein Beispiel mit der Funktion "xyz".

Die Realisation des ','-Operators in Aleph ist nicht festgelegt. Es ist Sache der individuellen Programmierung. Dabei sollte das Einsatzgebiet berücksichtigt werden. So kann die Übersetzung gleich mit einer Kompilierung versehen werden. Dann muss die Bearbeitung der Argumentlisten mit einem rekursiven Argumentzähler ausgestattet werden. Dann könnten Java-Methoden wie im Java-Quelltext aufgerufen werden. Es ist aber auch möglich von der Bekanntheit der Argumentanzahl auszugehen und den ','-Operator ohne Funktionalität einzusetzen.

Die korrekte Zuordnung der Argumente wird bei der Wandlung eines postfix- in einen prefix-Ausdruck deutlich. Am Ende der Datei "infix.vvm" ist ein Beispiel vorhanden, welches außerdem abschreckend wirken soll. Die Notation hat wohl doch keine unmittelbaren Einfluss auf die Lesbarkeit.

Von infix nach postfix

Ist nicht die infix-Notation Gegenstand der Besprechung? Ja! Jedoch besteht die Aufgabe darin, einen infix-Term in einen solchen mit postfix zu wadeln. Um die Wandlung zu verallgemeinern wird außerdem noch die prefix-Notation betrachtet. Die Probleme werden auch gleich anhand der letzten Notation angesprochen.

Werden Informatiker gefragt, wie ein Term denn übersetzt wird, kommt stets eine Antwort mit folgendem sinngemäßen Inhalt:

Es wird eine Baumstruktur aufgebaut, deren Knoten den Operatoren oder Operanden entsprechen.
Die Zweige enden in einem Operanden. Je nach Durchlaufen dieses Baums ergibt sich die Notation.

Tatsächlich arbeiten moderne Übersetzer-Generatoren mit dieser Baumstruktur. So einfach wie eben beschrieben verhält es sich aber nicht. Was ist mit "Punkt- vor Strichrechnung"? Das folgende Bild zeigt die beiden Bäume, die sich ergeben.

Die Bäume werden nun von oben nach unten durchlaufen. Verzweigungen werden zuerst nach links (vom Betrachter aus gesehen) betreten. Operatoren erzeugen immer einen geklammerten Term mit zwei Elementen und dem Operator links vor der Klammer.

linker Baum	rechter Baum
+()	*()
+(3, )	*(3, )
+(3, *())	*(3, +())
+(3, *(4, 5))	*(3, +(4, 5))

Der rechte Baum ist falsch. Allein der Aufbau einer Baumstruktur genügt offenbar nicht. Die Prioritäten der Operatoren werden nicht berücksichtigt. Der korrekte Baum ist auf der rechten Seite dargestellt.

Bäume und Stacks sind eng miteinander verwand. Es ist möglich, jede Raumstruktur auf einen Stack abzubilden und umgekehrt. Weil der Stack das "natürliche" Speichermedium von Aleph ist, wird sie auch im vorhandenen Parser benutzt. Eine Umsetzung des Java-Programms nach Aleph ist so einfacher. Es ist allerdings fraglich, ob eine Umsetzung überhaupt sinnvoll ist, wenn entsprechende Programe einfach benutzt werden können.

Übersetzung mit Stack

Der verwendete Parser arbeitet ohne Baumstruktur. Die Vorgehensweise ist strikt an die selbst erlernten (und daher gewohnten) Einzelschritte orientiert. Weil sich hier etwas "gemerkt" werden muss, arbeitet das Programm mit einem Stack. Was zuletzt in diesem Kurzzeitgedächtnis abgelegt wurde, ist zuerst wieder im Zugriff.

Die Bearbeitung der Terms (Quelle) erfolgt von links nach rechts. Die Bearbeitung des Stacks von oben nach unten. Das Programm ist höchstens mit zwei Elementen konfrontiert, die mit "Quellenelement" und "Stackelement" bezeichnet sind. Das Ergebnis wird mit "Ziel" bezeichnet, an das einzelne Elemente angehängt werden.

Hier die einfachen Regeln, nach denen der Übersetzer vorgeht:

Wenn Quellenelement kein Operator ist,

dann Quellenelement ins Ziel überführen, nächstes Quellenelement holen.

Wenn Stack leer ist,

dann Quellenelement auf Stack, nächstes Quellenelement holen.

Wenn Quellenelement "(" ist,

dann Quellenelement auf Stack, nächstes Quellenelement holen.

Wenn Quellenelement ")" ist und Stackelement "(" ist,

dann Stackelement entfernen, nächstes Quellenelement holen.

Wenn Priorität( Quellenelement) > Priorität( Stackelement),

dann Quellenelement auf Stack, nächstes Quellenelement holen.

Wenn Priorität( Quellenelement) <= Priorität( Stackelement),

dann Stack ins Ziel überführen.

Wenn Quelle LEER ist,

dann alle restlichen Stackelemente ins Ziel überführen.

Diese Regeln gestatten bereits die Übersetzung einfacher Terme. Leider werden keine Funktionen berücksichtigt. Ihre Namen wären von Variablen oder Konstanten nicht zu unterscheiden. Sollen auch noch Argumente berücksichtigt werden, die ja wieder Funktionen sein können, ist das gezeigte Regelwerk total überfordert.

Es zeigt sich jedoch, dass der gemachte Ansatz sehr flexibel ist. Bereits kleine Änderungen an den aufgestellten Regeln genügen für einen reibungslosen Ablauf. Um die Sache abzurunden wird alles in eine Schleife eingebettet.

Verfeinerte Regeln für die Wandlung von Infix nach postfix:

Solange die Quelle nicht leer ist
   Wenn das letzte Zeichen des Quellenelements kein Operator ist,
   dann Quellenelement ins Ziel überführen, nächstes Quellenelement holen.
   sonst
         Wenn Stack leer ist,
         dann Quellenelement auf Stack ablegen, nächstes Quellenelement holen.
         sonst
              Wenn das letzte Zeichen des Quellenelements '(' ist,
              dann Quellenelement auf Stack ablegen, nächstes Quellenelement holen.
              sonst
                   Wenn das letzte Zeichen des Quellenelements ')' ist
                        und das letzte Zeichen des Stackelements '(' ist,
                   dann Stackelement entfernen, nächstes Quellenelement holen.
                   sonst
                        Wenn Priorität des letzten Zeichens des Quellenelements > der Priorität des letzten Zeichens des Stackelements,
                        dann Quellenelement auf Stack ablegen, nächstes Quellenelement holen.
                        sonst
                             Stackelement ins Ziel überführen.
   Quelle ist leer
   Solange der Stack nicht leer ist
      Stackelement nach Ziel überführen.
   Stack ist leer

Diese 7 Regeln sind auch im Quelltext des Java-Programms als Kommentar vorhanden. Es dürfte sehr einfach sein sie zu erweitern oder eigenen Wünschen anzupassen.

Die Umsetzung im Detail

Zum Abschluß noch einmal der gesamte Aleph-Quelltext. Die besprochenen Vorgänge beim Parsen sind im Java-Programm. Hier ist nur die Anwendung beschrieben. Sie besteht aus drei Abschnitten.

Parser über die Funktionen in Kenntnis setzen. Es werden nur die Namen mitgeteilt. Informationen über Argumente, Parameter und deren Anzahl findet keine Berücksichtigung. Der Name "neg" muss vorhanden sein.

"parsing.HandleTerm" classify instantiate //           --> hndl
"parsing.Functions"  classify instantiate // hndl      --> fnct hndl
dup "append { String }" method app        // fnct hndl --> fnct hndl
"neg"  app
"not"  app
"abs"  app
"cos"  app
"cot"  app
"exp"  app
"ln"   app
"sin"  app
"sqrt" app
"tan"  app
"xyz"  app
"app" find drop forget // Methode vergessen

// Funktionen an HandleTerm binden.

1 ndup       // fnct hndl           --> hndl fnct hndl
"functions"  // hndl fnct hndl      --> name hndl fnct hndl
swap         // name hndl fnct hndl --> hndl name fnct hndl
store        // hndl name fnct hndl --> hndl

Parser über die Operatoren in Kenntnis setzen. Es werden nur die Namen mitgeteilt. Generell bestehen Operatoren aus einem Zeichen. Nur die hier vorhandenen Operatoren mit zwei Zeichen werden berücksichtigt.

"parsing.Operators"  classify instantiate // hndl      --> oper hndl
dup "append { String int }" method app    // oper hndl --> oper hndl

"("  100 app
")"  100 app
","  150 app
"<"  200 app
">"  200 app
"="  200 app
"!=" 200 app
"<>" 200 app
"<=" 200 app
">=" 200 app
"|"  300 app
"+"  300 app
"-"  300 app
"&"  400 app
"*"  400 app
"/"  400 app
"!"  500 app
"^"  500 app
"app" find drop forget // Methode vergessen

// Operatoren an HandleTerm binden.

1 ndup       // oper hndl           --> hndl oper hndl
"operators"  // hndl oper hndl      --> name hndl oper hndl
swap         // name hndl oper hndl --> hndl name oper hndl
store        // hndl name fnct hndl --> hndl

Für die einfache Anwendung in Aleph werden die Methoden zur Wandlung von "infix"-Termen als Commands ins Dictionary aufgenommen.

// Methoden zur schnellen Wandlung bereitstellen

dup                                 // hndl      --> hndl hndl
"postfix { String }" method postfix // hndl hndl --> hndl      (don't forget to forget !!!!!)
"prefix  { String }" method prefix  // hndl      -->           (don't forget to forget !!!!!)

Beispiel für die Wandlung eines infix-Terms nach post- und prefix. Die letzte Wandlung sei im Hinblick auf Alephs Fähigkeiten des Listprocessings schon mal gezeigt. Der infix-Term zeigt deutlich, wie unübersichtlich auch diese Notation sein kann.

"-xyz(-x<2,b>-(x+y),c,d)" //      --> infx
dup . " In POSTFIX " .    // infx --> infx
dup postfix .             // infx --> infx
newline .
dup . " In PREFIX  " .    // infx --> infx
prefix .                  // infx -->

newline . .S

Das Ergebnis dieser Übersetzung ist dann

-xyz(-x<2,b>-(x+y),c,d) In POSTFIX x neg 2 < b x y + neg > , c , d , xyz neg
-xyz(-x<2,b>-(x+y),c,d) In PREFIX  neg(xyz(<(neg(x),2),>(b,neg(+(x,y))),c,d))
Stack = [ ]

Funktionalität schaffen

Aleph bemüht sich so wenig Syntax wie möglich anzuwenden. Die infx-Notation ist mit diesem Anspruch kaum in Einklang zu bringen. Deshalb ist der hier verwendete Parser auch rein textueller Natur. Welche Operatoren und welche Funktionen benutzt werden ist allein der Anwendung unterworfen. Die Funktionalität ist nicht Sache des Parsers.

Aufgabe:

Bitte nicht im Text weiterlesen! Erst diese Aufgabe lösen.

Warum funktioniert kein Funktionsaufruf?
Warum arbeiten die meisten Operatoren einwandfrei?
Was hat es mit der "neg"-Funktion auf sich und wo ist sie?

Dem Parser wurden Funktionsnamen übergeben, die zwar in die postfix-Notation gewandelt wrrden, die Aleph aber unbekannt sind. Wenn Aleph also einen "üersetzten" infix-Ausdruck ausführen soll, wird jede hier vorhandene Funktion als unbekannt bemängelt.

Zum Glück sind die meisten geforderten Funktionen in Java vorhanden. Es bereitet also keine großen Probleme, sie auch in Aleph zu benutzen. Sie sollen aber nicht nur "benutzt", sondern in den Sprachschatz aufgenommen werden

"java.lang.Math" classify               // Math ist die Klasse mit den Funktionen

// Funktionen

dup "abs{double}"         method abs    // Absolutwert
dup "acos{double}"        method arccos // Arcuscosinus
dup "asin{double}"        method arcsin // Arcussinus
dup "atan{double}"        method arctan // Arcustangens
dup "ceil{double}"        method ceil   // ceil (siehe Gaussklammer)
dup "cos{double}"         method cos    // cosinus
dup "exp{double}"         method exp    // e^x (e hoch x; x ist Argument)
dup "floor{double}"       method floor  // floor (siehe Gaussklammer)
dup "log{double}"         method ln     // Logarithmus naturalis
dup "max{double double}"  method max    // Maximum der beiden Argumente
dup "min{double double}"  method min    // Minimum der beiden Argumente
dup "pow{double double}"  method power  // x^y (erstes Argument hoch dem zweiten)
dup "random{}"            method random // Zufallszahl [0.0, 1.0[
dup "rint{double}"        method round  // Runden (Ergebnis ist vom Typ double)
dup "sin{double}"         method sin    // Sinus
dup "sqrt{double}"        method sqrt   // Quadarwurzel
dup "tan{double}"         method tan    // Tangens

// Konstanten

dup "E"  field euler                    // die Zahl e (Eulersche Zahl)
    "PI" field pi                       // die Kreiszahl

// Weitere Funktionen als Commands

: H                                     // echte Srungfunktion (Heaviside)
  dup 0 < if drop 0   exit endif
      0 = if      0.5 exit endif
  1
;

// Die "Funktion" neg

: neg
  -1 *
;

Operatoren anpassen

Einige Operatoren in Aleph haben rein mathematische Ausprägungen. So ist der unäre Negationsoperator "!" nicht vorhanden. Die Exponential-Operator "^" ist auch nicht im Wortschatz. Es müssen also einige Anpassungen vorgenommen werden.

: ! not ;   // Das Zeichen "!" ist jetzt ''auch'' der Negationsoperator
: ^ power ; // Das Zeichen "^" ist jetzt ''auch'' der Exponentialoperator

Es fehlen die Operatoren "(", ")" und ",". Die Klammern sind Angelegenheit des Parsers und benötigen keine Aufnahme in den Aleph-Wortschatz. Beim Komma ist die Sache komplizierter. Hier geht es um Argumente von Funktionen. Weil Aleph keine Beschränkungen vorsieht, muss jede Funktion mit beliebig vielen Argumenten zugelassen werden. Der ","-Operator ist als Hilfsmittel für die Programmierung vorgesehen. Eine entsprechende Sequenz könnte für die speichertechnische Behandlung der einzelnen Argumente sorgen. Dabei muss natürlich der rekursive Charakter von Argumentlisten berücksichtigt werden.

„Kurs:Programmieren in Aleph“

<< Rekursion | Infix-Notation | Grundlagen Listprocessing >>