Tiefen der Mathematik: Formel-Interpretation
In der letzten Ausgabe packten wir einen leistungsfähigen Taschenrechner auf die TOS-Diskette. Seine Besonderheit war die Auswertung von Formeln. In diesem Artikel erfahren Sie Wissenswertes rund um die Erzeugung des dafür notwendigen Pcode.
Auf der TOS-Diskette finden Sie das Programm »Fplot«. Dieser Funktionsplotter ist in Turbo C 2.0 geschrieben, aber sicher finden auch Programmierer anderer Sprachen darin Anregungen. Fplot erwartet die Eingabe einer Formel (etwa: sin(3xpi) + cos(sqrt(7.32) + 2) und stellt diese dann graphisch dar. Zu diesem Zweck muß Fplot die Formel mehrere Male berechnen, eine vernünftige Rechengeschwindigkeit ist also unabdingbar. Die Formel für jede Berechnung immer wieder zeichenweise zu analysieren, dauert natürlich eine kleine Ewigkeit. Es empfiehlt sich also, diese in einen Code zu übersetzen, den der Computer schneller bearbeitet. Alle modernen Interpreter gehen ebenso vor und auch die meisten Compiler erzeugen vor der eigentlichen Maschinensprache einen Zwischencode, den sogenannten »Pcode«.
Vorbild Mensch
Zunächst Grundsätzliches zur Formel-Interpretation. Die nächstliegende Frage lautet: Wie geht der Mensch bei der Berechnung einer schriftlichen Aufgabe vor? Hierzu ein Beispiel: Wer sich mit unseren Rechenregeln noch nicht so genau auskennt, arbeitet die Formel »3-2x2-1« einfach von links nach rechts durch und teilt sie in drei Abschnitte: 3-2=1, 1x2=2 und 2-1=1 -und fällt prompt über die Regel »Punkt vor Strich«. Was macht ein begabter Mathematiker mit der gleichen Formel? Er beachtet im voraus die Prioritäten: -2x2=-4, -4-1 =-5, 3-5=-2. Das »Genie« unterscheidet sich also vom »Hirni« dadurch es vor der Bearbeitung eine Rechenschritts nachsieht, ob nicht schon ein Befehl mit höherer Priorität vorhanden ist.
Bei genauerer Betrachtung teilt sich der zweite Versuch in drei Aufgaben.
- Die Zeichen müssen als Zahl oder Befehl erkannt werden (»lexikalische Analyse«)
- Erkanntes im Gedächtnis behalten
- Ergebnis merken
Für die lexikalische Analyse müssen die Grundstrukturen einer Formel bekanntsein. Im Beispiel 3.0-2.0x2.0-1.0 genügen zwei Strukturen: 3.0, 2.0 und 1.0 sind Zahlen, »-« und »x« sind üperatoren. Für das Speichern von Zahlen, Operatoren und Ergebnissen bietet sich ein LIFO-Stack an. Die Abkürzung »LIFO« kommt - wie bei Computern üblich - aus dem Englischen (»Last In First Out-Stack«) und heißt übersetzt etwa: »zuletzt rein, zuerst raus«. Das zuletzt auf dem Stapel abgelegte Element ist zugleich das Erste, das ihn wieder verläßt.
Östliche Schreibweisen
Wenn wir nun die Zwischenergebnisse nicht ausrechnen, sondern nur den Vorgang aufschreiben, kommt folgendes dabei heraus: »3 2 2 x - 1 -«. Forth-Kennern und Besitzern von HP-Taschenrechnern sollte diese Schreibweise bekannt sein. Sie nennt sich UPN (Umgekehrt Polnische Notation). UPN ist optimal für die Formelbearbeitung durch einen Computer geeignet, da in ihr die Priorität eines Operators vollkommen egal ist und so komplizierte Klammergebilde entfallen. Wie in unserem ersten Beispiel, kann sie einfach von links nach rechts bearbeitet werden - diesmal sogar mit richtigem Ergebnis: Merke 3, merke 2, merke 2, rechne 2x2 und merke 4, rechne 3-4 und merke -1, rechne -1-1 und fertig.
Am einfachsten wäre es natürlich, wenn wir in unserem Programm die Formeln gleich in UPN eingeben würden. Aus verständlichen Gründen ist dies aber nur eingefleischten Mathematikern zuzumuten. Notieren wir den UPN-Code nicht als ASCII-Text, sondern in einer für den Computer leichter verdaulichen Form, haben wir den lang ersehnten Pcode.
Soweit die Grundlagen. Das Programm »Fplot« besteht aus den zwei Modulen »fplot.c« und »evalute.c«. In »fplot.c« lümmeln sich das GEM-Gerüst und der Funktionsplotter. Da beide Programmteile nicht unser Hauptthema bilden, widmen wir uns gleich ausführlich des Pudels Kern in »evalute.c«. Mit diesem Modul wandeln Sie Formeln wie »40xSIN(X/25) -r0.6xSIN(Xx3/25)« in Pcode und berechnen diesen natürlich. Das Hauptprogramm kommuniziert mit »evalute.c« nur über die beiden Funktionen »make__pcode« und »evalute«, unter Verwendung der Variablen »fehler«.
Wieder Name schon verrät, produziert make__pcode aus einer übergebenen Zeichenkette einen Pcode. Stößt make__pcode auf einen Fehler in der Formel, enthält »fehler« einen entsprechenden Wert und der Rückgabewert der Funktion ist Null. Hat alles geklappt, meldet make__pcode den Wert 1 uns sichert den erzeugten Pcode in dem globalen Array namens »pcode«.
Einbindung in Programme
C-Kenner wundern sich jetzt vielleicht über die Definition von pcode als Integer-Array. Einziger Grund hierfür ist die Bequemlichkeit, nicht auf ungerade Adressen achten zu müssen.
Ist der Pcode erfolgreich generiert, kommt die Funktion evalute ins Spiel. Da das letzte Beispiel eine Variable enthält (»X«), übergeben wir x in diesem Fall als double. Bei erfolgreicher Ausführung gibt evalute den errechneten Wert ebenfalls als double zurück. Fehlermeldungen übergibt die Funktion ebenfalls mit-hilfe der Variable »fehler«. Um das Modul evalute.c in eigenen Programmen zu verwenden, benötigen Sie nur die zwei Programmzeilen:
#include <eval.h>
/* Header-Datei einbinden */
extern int fehler;
/* Variable »fehler« deklarieren */
make__pcode setzt alle wichtigen Zeiger auf die Startbedingungen und ruft dann den eigentlichen Schwerarbeiter »compile« auf. Da diese Funktion rekursiv arbeitet, sich also des öfteren selbst aufruft, landet mit der Funktion »c__push« auf dem Stack zunächst eine Markierung für ein lokales Ende. Die Funktion »hole__befehl« sucht nach dem ersten Befehl in der übergebenen Formel.
Formelanalyse
Erinnern Sie sich noch an die lexikalische Analyse?
Genau das ist die Aufgabe von hole__befehl. Diese Funktion hält an der aktuellen Position in der Formel Ausschau nach einem bekannten Muster. Erkennt hole__befehl einen Operator, eine Zahl oder eine Variable, gibt die Funktion die Nummer des Befehls (»Typ«) als Integer zurück. Die verschiedenen Befehle sind zu Anfang von evalute.c definiert. Nachdem nun der Befehl bekannt ist, sind weitere Schritte in seiner Verarbeitung zu entscheiden: Ist der aktuelle Befehl eine Nummer oder eine Variable, wird dieser sofort als Pcode ausgegeben. Die Ausgabe eines Befehls als Pcode erledigt die Funktion »out__pcode«.
Für spätere Syntaxanalysen müssen wir allerdings noch einen Hinweis auf dem Stack hinterlassen. Alle Befehle, die einen numerischen Wert enthalten wie etwa Variablen, Rechenergebnisse und Zahlen, sind auf dem Stack als Ergebnis (ERG) hinterlegt. Die Funktion »auf__Stack« befördert den Befehl auf den
Stack und holt bereits den nächsten Befehl via »hole__ befehl« aus der Formel. Da unser Programm ja ein begabter Mathematiker sein soll, muß es die Prioritäten der Operatoren (»+«,»-«, »x«,»/«,»"«) berücksichtigen. Hatte der letzte Befehl eine höhere Priorität als der aktuelle, wird zuerst der letzte Befehl als Pcode ausgegeben. Den Pcode für Operatoren und Funktionen (SIN, COS, usw) erzeugt die Funktion »out__befehl«. Sie prüft auch gleichzeitig auf korrekte Syntax. Einen kleinen Haken hat aber noch der Operator -, das Minuszeichen kann auch als Negation gedacht sein. Ist der zuletzt auf den Stack beförderte Befehl keine Zahl, muß die Negation gemeint sein. Etwas komplizierter sind öffnende Klammern. Am einfachsten können wir diese Klippe umschiffen, indem wir den Text in der Klammer als eigene Formel ansehen und die Funktion compile einfach noch einmal starten.
Syntaxanalyse
Trifft compile auf eine schließende Klammer, übergibt sie alle Befehle, die sich bis zur Markierung eines lokalen Endes auf dem Stack befinden, an die Funktion out__befehl. Da schließende Klammern und das Ende der Formel gleiche Behandlung zur Folge haben, darf eine letzte, abschließende Klammer durchaus fehlen: Die Berechnung des Ausdrucks 3x(2/(2-1) bleibt korrekt. Als letzte Möglichkeit könnte es sich beim aktuellen Befehl um eine Funktion (etwa SIN, COS,...) handeln. Funktionen bearbeitet das Programm im Prinzip wie öffnende Klammern, nur geschieht dies in der Routine out__befehl.
Ist die komplette Formel abgearbeitet, liegt der erzeugte Pcode nun im globalen Array pcode zur Berechnung durch die Funktion evalute vor. Da der Funktionsplotter die aktuellen Koordinaten in der Rechnung berücksichtigt, erhält evalute diese im Parameter »vari«. Dieser Wert ersetzt später die Variable »X«. Wer in seiner Anwendung von evalute keine Variablen benötigt, übergibt einen beliebigen Wert oder entfernt den betreffenden Programmteil einfach. Beim Wunsch nach mehr Variablen ist eine entsprechende Routine notwendig, deren Programmierung aber keine größeren Schwierigkeiten bereiten dürfte. Nach dieser Vorarbeit kann der Pcode nun sequentiell von evalute abgearbeitet werden. Da die Pcode-Befehle aus Integerzahlen bestehen, sind diese einfach über eine »Switch«-Anweisung zu dekodieren. Aus Gründen der Geschwindigkeit ist die Stapelverarbeitung in evalute nicht so elegant wie in compile gelöst. Statt »push« und »pop« wird der Stack als einfaches double array angelegt und direkt über die Variable »stacktop« angesprochen.
Schnelle Funktionen
Beim Auftreten eines mathematischen Fehlers (zum Beispiel »Division durch 0«), setzen die Fließkommafunktionen von Turbo C die externe Variable »errno« auf einen entsprechenden Wert. Wenn kein Fehler entdeckt wurde, gibt evalute das Rechenergebnis als double zurück. Übrigens: evalute erreicht über 75% der Rechengeschwindigkeit von reinem C-Code! Wer schon im Quelltext gespickt hat, ist auf bisher noch nicht oder nur kurz erwähnte Funktionen gestoßen: »c__push« und »c__pop« verwalten den Stack von compile: c__push befördert einen Befehl auf den Stack, c__pop holt ihn wieder herunter. Die Funktion »ist__funktion« wird von hole__befehl benötigt und sucht in der Formel nach Funktionsaufrufen (SIN, COS, usw).
Diese Funktion arbeitet trotz ihres vielleicht irreführenden Aussehens sehr schnell. Bei einer einmaligen Übersetzung fällt dieser Geschwindigkeitsvorteil noch nicht besonders ins Gewicht, aber beim Übersetzen von vielen Formeln kommt er zum Tragen. Dies gilt auch für die Funktion »s__gleich«, die Strings vergleicht. Ist der Anfang von S1 gleich S2 und folgt auf das Wort in S1 ein Trennzeichen (Space, Klammer, usw.) wird TRUE zurückgeliefert, ansonsten FALSE. Wem bereits die Augen zufallen, der kann jetzt aufatmen, wir sind am Ende angelangt. Uns bleibt nur noch, Ihnen viel Spaß und, Erfolg bei der Umsetzung von eigenen Ideen zu wünschen. (ah)
Richard Kurz