Turbo Toolbox

home *** CD-ROM | disk | FTP | other *** search

/ Turbo Toolbox / Turbo_Toolbox.iso / spezial / 01 / newton / newton.doc < prev next >

Wrap

Text File | 1987-06-24 | 62.6 KB | 1,073 lines

Symbolverarbeitung ! Der Weg zur intelligenten Maschine? Turbo-Prolog lernt Analytik. Funk- tionen werden nicht mehr numerisch, sondern symbolisch differenziert und integriert. Ein Programm, auf das Schüler und Naturwissenschaftler schon lange gewartet haben. ------------------------------------ Eine Definition ------------------------------------ Mancher wird sich angesichts der Überschrift wohl fragen: "Was soll das denn jetzt schon wieder sein, Symbole ?" Aber keine Angst, ich ha- be nicht vor, jemanden mit theoreti- schen Formalismen aus der Informatik zu quälen. Dies könnte ich auch aus Mangel an derartiger Bildung gar nicht. Meine naive, aber trotzdem in dem Analytikprogramm erfolgreiche Definition lautet etwa folgender- maßen: Ein Symbol ist ein Objekt, das einen oder mehrere Werte haben kann. Diese können selber wiederum Symbole oder Atome sein. Unter einem Atom verstehe ich hierbei einen Wert, der selbst kein Symbol oder Atom mehr zum Wert hat. Ein Hinweis für Leser, die von kon- ventionellen Programmiersprachen ge- prägt sind: Man muß sich hier von dem strengen Gegensatz Variable - Wert lösen. In dieser Definition, wie auch allgemein in AI-Sprachen, ist mit einem Wert nicht ein Zahlen- wert oder eine Zeichenkette gemeint, sondern einfach ein Wort, mit dem eine Variable (Symbol) gebunden wird. Wenn der Wert die richtige Ge- stalt hat (kein Zahlenwert), kann er selbst wieder als Variable gehand- habt und an einen Wert gebunden wer- den. Bevor ich jegliche Klarheit besei- tige, ein Beispiel aus dem täglichen Leben: Als Symbol nehmen wir Geld. Dies kann, unterschiedlich für ver- schieden Personen, z.B. folgenden Werte haben: Stück_Papier, Nahrung, Vergnügen, Arbeits_Gegenwert, Geld_- Münze,... Wie man sieht, ist z.B. Nahrung wiederum ein Symbol, daß verschiedene Werte (Bedeutungen) ha- ben kann. Ein atomarer Wert könnte z.B. Geld_Münze sein, falls die Per- son, die mit dem Symbol Geld arbei- tet, eine Münze in ihrer Vorstel- lungswelt nicht weiter strukturiert. (Siehe auch die graphische Darstel- lung dieses Beispiels als Baum.) ------------------------------------ Eine Abbildung unserer Begriffswelt ------------------------------------ Es sieht so aus, als könnte man mit einer solchen Datenstruktur die Vor- gehensweise des menschlichen Gedäch- nisses (Assoziationsketten und Bäu- me) ziemlich gut nachbilden. Jetzt stellt sich natürlich die Frage, wie man solche Datenstrukturen einer mentalen Maschine auf einem physika- lischen Gerät wie einem Computer ab- bildet. Ein 'nur BASIC-Program- mierer' wird vielleicht sagen: "Geht gar nicht.". Kenner von Pascal-ähn- lichen Sprachen werden sich wohl etwas in dem Bart murmeln wie "Lis- tenstrukturen aus Zeigern mit vari- anten Records als Knoten" und die Sache wegen zu großem Umfangs wieder fallen lassen. Hingegen wird die Abbildung solcher Strukturen in AI-Sprachen wie Pro- log, Lisp und Logo geradezu simpel. In der Lisp/Logo-Version wäre ein Symbol ein Wort, das als Wert eine Liste besitzt, die ein oder mehrere Symbole oder Atome enthält. Diese Symbole in der Liste enthalten wie- derum Listen, in denen... In Turbo-Prolog müssen wir, im Ge- gensatz zu Lisp, Logo und "klassi- schen" Prolog-Dialekten, vorher ein wenig deklarieren (Prolog-Puristen mögen mir verzeihen, daß ich diesen Dialekt wählte, allerdings paßte er als einziger problemlos in meinen Etat und auf meinen Rechner!). Wie die zu Beginn erfolgte formale Defi- nition vermuten ließ, ist das Ganze eine hochgradig rekursive Angelegen- heit. Im Programm würde das folgen- dermaßen aussehen: DOMAINS SymbolListe = ein_Symbol* /* Eine Liste von Symbolen */ ein_Symbol = atom(STRING) OR Symbole(SymbolListe) OR einSymbol(ein_Symbol) Das die eigentlichen Werte (STRING <=> Atome, SymbolListe, ein_Symbol) noch in Funktoren (atom, Symbole, einSymbol) eingebunden werden, hat hier nur programmiertechnische Grün- de. Dazu weiter unten anhand des Programms mehr. Nun gut, wenn man nun eine Möglich- keit hat, unsere Begriffswelt abzu- bilden, könnte man auch versuchen, Prädikate zu formulieren, die Rela- tionen und Wechselwirkungen von Ob- jekten (Symbolen) beschreiben. Für den nicht Prolog-Bewanderten: Ein Prädikat ist ein Faktum oder eine Regel, das Relationen zwischen Ob- jekten beschreibt. Implizit kann ein Prädikat eine Transformation eines Objekts enthalten. Beispiele: Ein Faktum mit Relationsbeschreibung ist ist_aelter(Vater,Sohn). Die Parameter sind hier Variablen, 'Vater' und 'Sohn' würden also die Namen zweier Personen enthalten. Eine Regel mit Transformation wäre ziehe_Wurzel(Wert,Ergebniss). In 'Wert' stände eine Zahl, und nach Anwendung des Prädikats enthielt 'Ergebniss' das Resultat der Rech- nung. Die expliziete Vereinbarung der Regeln für die Prädikate, hier z.B. das Ziehen der Wurzel, findet in Prolog im Klauselteil des Pro- grammes statt. Auf diese Weise müßte man ein Pro- gramm formulieren können, das eine gute Portion gesunden Menschenver- stand besitzt und Lösungen für alle Probleme der Begriffswelt finden könnte. Ansätze dieser Art wurden auch schon in der Frühgeschichte der EDV pro- biert und führten im Prinzip sogar zum Erfolg. Einer der prominentesten Vertreter dieser Entwicklungen war der "General Problem Solver". Bei diesem Programm mußte man einen An- fangszustand in einer Welt definie- ren, den gewünschten Endzustand und die Operatoren (Prädikate), die auf die Objekte (Symbole) der Welt an- gewandt werden konnten. Das Programm funktionierte wunderbar, aber der Aufwand für die Formulierung der Ob- jekte und Operatoren wuchs bei stei- gender Weltgröße sehr schnell ins Unerträgliche. Zudem ist ein Pro- blem, das man exakt formulieren kann, eigentlich schon keines mehr. Daraus kann man den Schluß ziehen, daß die Idee gut war, aber die An- wendung verkehrt (Frei nach Hugo Hacker: "Eine Lösung hatte ich, aber leider nicht das passende Problem dafür."). ------------------------------------ Eine kleinere Welt ------------------------------------ Sehr viel praxisorientierter wird die Angelegenheit, wenn man in einer Welt arbeitet, deren Objekte und Re- geln (Operatoren) überschaubar sind, wo aber die Anwendung der Regeln für den Menschen unübersichtlich und kompliziert ist. Hier muß wieder mal die Mathematik herhalten, wobei ich mir das Gebiet der Differential- und Integralrech- nung herausgeguckt habe. Mein Anlie- gen ist also ein Programm zu formu- lieren, das einen beliebigen, analy- tischen Funktionsausdruck ableiten oder die Stammfunktion davon bilden kann. Jemand, dessen Mathematik-Un- terricht schon etwas länger zurück liegt, und dem der Sinn der Differ- ential-/Integralrechnung entfallen ist, sollte in den mathematischen Erläuterungen nachsehen. Das universelle Symbol dieser Welt habe ich term genannt. Damit meine ich Funktionssymbole, Operatoren, Variablen, numerische und symboli- sche Konstanten sowie die unendlich vielen Verknüpfungen, die mit diesen termen möglich sind. (Schon wieder eine Rekursion!) ------------------------------------ Es wird konkret ------------------------------------ Als erstes habe ich in dem DOMAINS- Teil die atomaren Größen mit term identifiziert. Diese atomaren Größen sind Konstanten (z.B. a), numerische Konstanten (z.B. 3.14) oder Varia- blen (z.B. X). Diese Größen sind als Funktoren definiert, die durch ihren Inhalt einen konkreten Wert bekom- men. Die numerische Konstante 3.14 würde also als nconst(3.14) darge- stellt - und die Variable X würde als var("X") geschrieben. Der erste rekursive term ist der Funktor funk mit zwei Argumenten. Dieser Funktor dient zur Darstellung von Funktionen. Das erste Argument ist dabei ein STRING, der den Namen der Funktion enthält: z.B. "sin" oder "exp". Das zweite Argument ist wiederum ein term. Die Funktoren für die Grundrechenarten sind gleich doppelt rekursiv, da sie zwei terme als Argumente haben. Zu guter Letzt habe ich noch den Funktor npot definiert, der Potenzen mit konstantem Exponenten be- schreibt. Das erste Argument ist der term, der potenziert wird. Das zwei- te Argument, der Exponent, ist auch als term definiert, obwohl dieser, als Konstante, eigentlich eine ato- mare Größe sein müßte. Man darf aber nicht vergessen, daß ein konstanter Exponent sich aus symbolischen und numerischen Konstanten zusammenset- zen kann. Diese gewisse Eigenwillig- keit der Potenzen taucht auch bei ihrer mathematischen Behandlung wie- der auf. Zusätzlich habe ich noch eine Domäne (Datentyp) nach definiert. Diese steht für die Variable, nach der ab- geleitet oder integriert werden soll. ------------------------------------ Eine angemessene Darstellung ? ------------------------------------ Mancher wird sich jetzt fragen, ob dies eine sinnvolle Darstellung von mathematischen Termen ist. Zum Bei- spiel wird aus dem relativ simplen Term (X+Y)*(U-W)/Z in dieser Funktor-Notation ein Monstrum wie div(mal(plus(var("X"),var("Y")), minus(var("U"),var("W"))), var("Z")). Der große Vorteil dieser Notation ist aber, daß man sich an keiner Stelle bei der Formulierung der Re- geln für Ableitungen und Stammfunk- tionen Gedanken über die Priorität von mathematischen Operatoren machen muß. Man muß also Regeln wie "Punkt- rechnung vor Strichrechnung", Klam- merungen und ähnliches nicht weiter berücksichtigen, da man es immer nur mit einem Funktor mit höchstens zwei Argumenten zu tun hat, die naturge- mäß dieselbe Priorität haben. Wie man sieht, ist so ein term impliziet eigentlich eine Baumstruktur. Natürlich ist es niemandem zuzumu- ten, einen komplizierteren Term in dieser Notation einzugeben. Da könn- te man die Sache ja gleich wieder "zu Fuß" rechnen. Daher habe ich noch einen Parser (eigentlich schon ein Mini-Compiler) programmiert, der aus der "normalen" Notation in die Baumnotation und zurück übersetzt. Hierbei taucht dann das Prioritäts- problem doch wieder auf. Anscheinend gilt auch hier das Prinzip der Inva- rianz der Schwierigkeit. Auf gut Deutsch: Man kann die Sache angehen wie man will, es ist und bleibt schwierig. Aber dazu weiter unten mehr. ------------------------------------ Jetzt wird gerechnet ! ------------------------------------ Der ganze Vorgang des Ableiten und Stammfunktion bilden wird von einem einzigen Prädikat 'stammf_ableit' erledigt, das für beide "Richtungen" wirksam sein soll. Das Prädikat hat drei Parameter: Erstens einen term für die Stammfunktion, zweitens einen Ausdruck 'nach', der die Variable bezeichnet, nach der inte- griert/differenziert werden soll - und drittens einen term für die Ableitung. Im Klauselteil für dieses Prädikat werden als erstes die Regeln für die atomare Größen definiert. Hier tau- chen auch gleich die ersten Schwie- rigkeiten für die Umkehrung der Ab- leitung auf. Zum Beispiel habe ich zuerst die Regel "Irgendeine Kon- stante nach irgendwas abgeleitet er- gibt 0" naiv als stammf_ableit( const(_),_,nconst(0)) formuliert. Der Unterstrich "_" re- präsentiert hier die Anonyme Variable, also einen Wert, der für die Regel unbedeutend ist. Diese Re- gel funktioniert für die Ableitung auch einwandfrei, ist aber leider auf keinen Fall umkehrbar! Der Rechner müßte sich ja für die Bil- dung der Stammfunktion nach dieser Regel irgendeine Konstante aus dem Begriffsvakuum zaubern. In solchen Fällen muß man also anhand der Bin- dung der Variablen entscheiden, in welche Richtung die Klausel arbeiten soll und für die Umkehrung eine ei- gene Regel formulieren. Hier benennt man für die Umkehrung irgendeine Konstante als const(const) (siehe Listing). Dieses Manko der Regeln sollte man aber nicht Prolog anlas- ten, da es eher eine Folge der ma- thematischen Regeln ist. Diese sind nie konzipiert worden, unmittelbar umgedreht zu werden (sinngemäße Um- kehrung ist natürlich kein Problem). Übrigens, noch ein Hinweis: An Stellen, wo im Programm ein STRING stehen muß, kann man sich in Turbo- Prolog die Anführungsstriche sparen, wenn der STRING aus einem einzigen, kleingeschriebenen Wort besteht. Dies habe ich auch entsprechend aus- genutzt. Bei den Klauseln der atomaren Größen, sowie bei allen folgenden Klauseln, habe ich an das Ende des Regelteils einen Cut ("!") gesetzt. Dies bewirkt, daß keine der folgen- den Klauseln mehr "probiert" wird, falls der Regelteil einer Klausel erfolgreich bis zum Ende durchlaufen wurde. Bei den ersten beiden Regeln ist dies z.B. unbedingt notwendig. Falls die erste Regel erfolgreich durchgeführt wurde (Ableitung bil- den), darf die zweite Regel auf kei- nen Fall mehr angewand werden (Stammfunktion bilden). Bei vielen anderen Klauseln ist dies nicht notwendig, da meistens ohnehin auf einen Fall nur genau eine Regel paßt. Falls aber doch mehrere Regeln anwendbar sind, bewirkt der Cut, daß genau eine Lösung gefunden wird. Man muß die Regeln natürlich so anord- nen, daß zuerst die Spezialfälle und dann die allgemeinen Fälle behan- delt werden. Gerade bei rekursiven Klaueln bringt der Cut in dieser Form (theoretisch) eine enorme Ver- besserung des Laufzeitverhaltens und des Speicherbedarfs, da unnötiges Backtracking, das sonst fakultativ (im mathematischen Sinne) auftreten würde, vermieden wird. Theoretisch deshalb, da das Programm auch ohne diese nicht unbedingt nötigen Cuts so schnell läuft, daß kaum eine Re- aktionszeit auftritt. Im Listing folgen dann die Regeln für zweistellige Operatoren, sprich Grundrechenarten. Im Klauselkopf er- kennt man ohne Mühe die Regeln wie- der, die in der Mini-Formelsammlung der mathematischen Erläuterung ange- geben sind. Gemäß der Rekursivität der Datenstruktur sind auch die Re- geln rekursiv. D.h. am Ende der Klausel werden erst die Ableitungen der Argumente des Funktors gebildet, welche anschliessend im Kopf der Klausel regelgerecht verknüpft wer- den. Für die Ableitung der Potenzen sind gleich mehrere Regeln angegeben. Die erste Regel führt eigentlich nur ei- ne Vereinfachung (x1 = x) vor der Ableitung durch. Eigentlich sollte so eine Regel im dafür zuständigen Programmteil stehen. Es bot sich aber nun einmal an, diese hierhin zu setzten. Die zweite Regel beschreibt die Ableitung von Potenzen, die als Exponent nur eine numerische Kon- stante haben, gemäß den Ableitungs- regeln. Die dritte Regel schließlich ist für die Ableitung von Potenzen mit zusammengesetzten Exponenten zu- ständig. Danach folgen die Regeln für die Ab- leitung von Funktionen gemäß der Bildung des Produkts aus innerer mal äußerer Ableitung. Ich habe hier ex- plizit für jede Funktion eine eigene Regel geschrieben. Man könnte das Ganze kompakter schreiben, indem man mit zwei Listen arbeitet, wobei die eine die Funktionen und die andere an den entsprechenden Stellen die Ableitungen enthält. Da dies aber der Übersicht und dem Verständnis kaum förderlich ist, habe ich dies an dieser Stelle unterlassen. Damit hat man den Formalismus der Ableitungsbildung mit weniger als 50 Prolog-Zeilen formuliert, wobei die Umkehrung, also die Bildung der Stammfunktion, schon voll berück- sichtigt ist. ------------------------------------ Integration, Umkehrung der Differenzierung ? ------------------------------------ Wenn man nun versucht, das Prädikat 'stammf_ableit' zur Bildung von Stammfunktionen einzusetzen, wird man selbst bei Termen, deren Inte- grationsregeln implizit in den Klauseln enthalten sind, in der Re- gel eine böse Überraschung erleben. Die Systemmeldungen reichen dabei von "no solution" bis "Stack over- flow". Der Grund dafür ist eigentlich recht einleuchtend. Wenn man sich den rechten Teil der Klauselköpfe (Ab- leitung) anschaut, stellt man fest, daß dort in aller Regel terme ste- hen, wo mit einer inneren Ableitung oder Konstante multipliziert wird. Dieses Muster paßt dann natürlich nicht auf die einfachen terme, deren Stammfunktion man gerne haben möchte (das Matching funktioniert nicht). Man ist also wohl oder übel gezwun- gen, die Umkehrung der Regeln noch- einmal explizit hinzuschreiben. Als weitere Regel für die Integra- tion von Produkten habe ich die par- tielle Integration eingeführt. Hier wird mit dem Prädikat part_I ge- prüft, ob eine partielle Integration erfolgsversprechend ist, also ob ei- ner der Multiplikanden eine Potenz, Variable oder ähnliches ist. Dabei muß sich der anderer Multiplikant mit den vorhandenen Regeln integrie- ren lassen. Wenn ein term diesen Be- dingungen genügt, wird die partielle Integration angewand und versucht, das daraus resultierende neue Inte- gral (siehe "Mathematische Erläuter- ungen") rekursiv zu integrieren. Auf die Substitutionsregel habe ich verzichtet, da dies für ein Pro- gramm, das in einer Zeitschrift ab- gedruckt werden soll, zu umfangreich geworden wäre. Statt dessen habe ich das Programm mit einer gewissen Ta- belle an Standardintegralen ausge- rüstet, die von jedem, der ein ent- sprechendes Tabellenwerk (z.B. Br°n- stedt) zu Hause hat, beliebig erwei- tert werden kann. Für den prakti- schen Einsatz des Programms sollte man diese Tabelle vielleicht dyna- misch mit einem DATABASE-Prädikat erzeugen. Auf diese Weise kann man das Programm lernfähig machen, so daß einmal gelöste Integrale nicht neu berechnet werden müssen. Um Enttäuschungen vorzubeugen, muß ich hier gleich klarstellen, daß das Programm in dieser Form mit Sicher- heit nicht alle Integrale lösen kann, die ein Mathematiker unter An- wendung aller Tricks und Kniffe 'hinkriegt'. Hier unterlag ich auch vom Programmumfang gewissen Ein- schränkungen - ganz davon abgesehen, daß es jahrelange Detailarbeit ist, so ein Programm leidlich perfekt zu machen. Aber statt an der Meldung "no solution" zu resignieren, würde ich versuchen, das Programm ständig zu verbessern. ------------------------------------ Vereinfachung von Termen ------------------------------------ Wenn man die Ableitungs- und Inte- grationsregel in der oben beschrie- benen Form anwendet, kriegt man zwar (hoffentlich!) korrekte Lösungen - diese sehen aber ziemlich wüst und merkwürdig aus. Der Grund dafür ist, daß das Programm terme, die ein Mensch bei der Rechnung stillschwei- gend unter den Tisch fallen läßt, bis zum bitteren Ende mitschleppt. Solche terme sind z.B. Multiplika- tion mit 1, Addition von 0, Multi- plikation mit 0 etc. Um solche "toten Zweige" aus dem term-Baum zu entfernen, habe ich ein Prädikat vereinfache geschrieben, welches mit den Hilfsprädikaten ver- einfache1 und vereinfache2 den Baum wiederholt bearbeitet und dabei Ver- einfachungsregeln anwendet. Die wie- derholte Anwendung ist notwendig, da z.B. bei der rekursiven Vereinfa- chung der beiden Operanden des Funk- tors mal einer der beiden Multipli- kanten denn Wert 1 annehmen könnte. Die damit hinfällige Multiplikation kann aber nur in einem weiteren Durchgang vereinfacht werden. Ein unmittelbarer rekursiver Aufruf könnte zu Endlosschleifen führen, falls die Multiplikation halt doch nicht vereinfacht werden kann. Als Abbruchkriterium dient die Abfrage, ob sich der Baum bei der Verein- fachung geändert hat. Da dies aber auch durch ineffektive term-Ver- tauschungen der Fall sein kann, wird die Anzahl der Wiederholungen mitge- zählt und bei einer gewissen Grenze terminiert. Die eigentlichen Regeln zur Verein- fachung sind allesamt recht simpler Natur. Allerdings scheint ihre An- zahl exponentiell mit der gewünsch- ten Güte zu steigen. Zudem tauchen fast alle Regeln doppelt auf, da die Kommutativität explizit berücksich- tigt werden mußte (zum Problem der Vertauschbarkeit von Operanden habe ich mich auch beim Parser ausgelas- sen, s.u.). Das eigentliche Problem bei der Ver- einfachung ist, alle Regeln zu be- rücksichtigen, wobei es auch Schwierigkeiten macht, die richtige Reihenfolge zu finden. Der "Verein- facher" ist in dieser Form mit Si- cherheit noch nicht perfekt. Es gibt sicherlich noch etliche Sonderfälle, die nur schlecht berücksichtigt wur- den. Hier bin ich für Verbesserungs- vorschläge ganz offen. (Das "Ding" ist allerdings auch so schon lang genug.) Daß solche "Vereinfacher" Riesenap- parate werden können, sieht man an Programmen wie "REDUCE" und "MU- SIMP". Ersteres ist ein Großrechner- Lisp-Programm, das soviel Speicher- platz braucht, daß man es mit einer normalen Benutzerberechtigung über- haupt nicht zum Laufen kriegt. Das Zweite ist auch ein mathematisches Programm für die Apple II-Serie, dessen Hauptanteil angeblich von solch einem Vereinfacher ausgemacht wird. ------------------------------------ Der Parser ------------------------------------ Wie schon erwähnt, kann es niemandem zugemutet werden, mathematische Terme in der in diesem Programm ver- wendeten Baumnotation einzugeben. Die Umwandlung analytischen Notation ---> Baumnotation und zurück wird von dem als Parser bezeichneten Programmteil vorgenommen. Dieser Parser ist eigentlich schon ein Mini-Compiler, da er - formal be- trachtet, von einer Sprache in eine andere Übersetzt. Dem entsprechend schwierig war er zu realisieren (er hat mich fast in den Wahnsinn ge- trieben). Die Problematik rührte zum einen aus der Berücksichtigung der Operator-Prioritäten und zum anderen aus der Nicht-Umkehrbarkeit des Par- sing her. Zum Übersetzen in die Baumnotation sieht die prizipielle Vorgehensweise wie im folgenden beschrieben aus: 1. Aus dem Term-String werden alle Leerzeichen entfernt (entferne_Leer- zeichen). 2. Der String wird in eine Token- liste zerlegt (string_tokenliste). Ein Token ist hier ein Wort (z.B. "sin"), eine Zahl oder ein Sonder- zeichen (z.B. "*","/","(",")",...) 3. Von dem Prädikat tokenliste_term wird als erstes überprüft, ob die Tokenliste einem gültigen term ent- spricht. Das Prädikat richtiger_Term überprüft hier nur, ob die Anzahl der öffnenden Klammern gleich der Anzahl der schließenden Klammern ist. Der Syntax-Check kann natürlich nach Bedarf beliebig erweitert wer- den. Fehler bei der Klammerschach- telung sind aber erfahrungsgemäß die häufigsten. Durch den Cut wird erreicht, daß im Fehlerfall das kom- plette Parsing failed, abgebrochen wird. 4. Es folgt die Behandlung der ato- maren Größen. Hier wird im Kopf der Klausel geprüft ob die Tokenliste nur noch ein Element enthält. Dieses wird dann in sein ╨quivalent der Baumnotation umgesetzt. An dieser Stelle terminieren also alle Rekur- sionen. Hinweis: Mancher wird hier die Be- handlung der symbolischen Konstanten vermissen. Selbige würden nach die- sem Mechanismus als Variablen im Baum auftauchen. Dies habe ich an dieser Stelle in Kauf genommen, um mir das Mitschleppen der vom Be- nutzer gewünschten Variablen als ei- nen weiteren Parameter durch alle Klauseln des Parsers zu ersparen. Die entsprechende Ersetzung durch Konstanten wird zentral von dem Prä- dikat replace vorgenommen. 5. Wenn die Tokenliste mit einer öffnenden Klammer beginnt, und nach der schliessenden Klammer nichts mehr folgt, wird das Argument in den Klammern extrahiert (aeussere_Klam- mern), rekursiv dem Parsing unter- worfen und der daraus erhaltene term zurückgegeben. 6. Falls hingegen nach der schlies- senden Klammer noch etwas folgt (Op|Rest), wird der führende Klam- merterm komplett zu einem String zu- sammengezogen und tokenliste_term mit diesem String als "Kopf" und Op|Rest als "Rest" rekursiv aufge- rufen. 7. Die Behandlung von Funktionen und Potenzen erfolgt vollkommen analog zu den Klammertermen. Der vor der Klammer stehende 'Name' wird auf Zu- gehörigkeit zu einer Liste von gül- tigen Funktionsbezeichner geprüft. Diese Liste ist übrigens umfangrei- cher als notwendig, aber ich werde den Parser wohl auch noch in anderen Programmen einsetzen. 8. Nun wird die Kontrolle des Parsing an split_in_P_Liste über- geben, dessen Aufgabe es ist, die Liste in Teile aufzuteilen, die nur noch mit Punktrechnungen verknüpft sind. Im Detail: a) Wenn die ankommende Liste nur noch aus drei Teilen besteht, wird geprüft, ob das zweite Element ein Punktrechnungsoperator (ist_Punktop) ist. Falls dies zutrifft, wird der Kopf wieder in eine Tokenliste zer- legt und rekursiv 'geparsed'. Das dritte Element, das ja eine atomare Größe sein muß, wird gleichfalls ge- parsed. Die Ergebnisse des rekursi- ven Parsing werden mit einem dem Operator entsprechenden Funktor ver- knuepft (verknuepf). b) Das Gleiche wird durchgeführt, wenn die Liste zwar mehr als drei Elemente enthält, aber der Teil nach dem Operator einem selbständigen term entspricht. Selbstständige terme sind Funktionen, Klammerterme und Potenzen (ist_iso_term). c) Wenn der ankommende Operator ein "+" ist, kann man den führenden und nachfolgenden (rekursiv geparsten) term schon miteinander verknüpfen, da das "+" die niedrigste Priorität hat und demgemäß alle anderen Ver- knüpfungen schon stattgefunden ha- ben. d) Wenn ein "-" ankommt, kann man gleichfalls schon verknüpfen, falls das Parsing des Restes keinen Strichrechnungs-Funktor ergibt. Sonst könnte z.B. passieren, daß man a-b+c zu minus(a,plus(b,c)) verknüpft, was aber in normaler Notation a-(b+c) entspräche. e) Ansonsten werden die ersten drei Elemente der Liste, falls diese nicht den Beginn einer Funktion, eines Klammerterms oder einer Potenz signalisieren, "zusammengepackt" und wiederum mit dem Rest der Liste ge- parsed. f) Sonst werden Funktionen, Potenzen und Klammerterme extrahiert und mit dem ersten Listenelement und dem Operator verpackt. Darauf folgt wieder der rekursive Aufruf mit diesem neuen Listenkopf und dem Rest. g) Zu guter letzt erfolgt die Be- handlung für den Fall, daß man am Ende des Ausdrucks angekommen ist (nur noch drei Listenelemente), wo der Kopf dieser Restliste wieder geparsed und mit dem letzten Element verknüpft wird. 9. Das Prädikat split_in_S_Liste geht analog vor, um nur mit Strich- rechnung verknüpfte Terme zu zerle- gen. Damit ist der Parser für die Rich- tung analytische Notation ---> Baum- notation fertig. ------------------------------------ Eine schwierige Umkehrung ------------------------------------ Leider habe ich bei diesem Prädikat keine Möglichkeit gefunden, die Um- kehrbarkeit unmittelbar zu berück- sichtigen. Dies scheint bei solchen Parsing-Aufgaben auch ein prinzi- pielles Problem zu sein. Dazu könn- ten ja mal einige theoretisch inte- ressierte Programmierer einen Bei- trag liefern. Ich habe der Einfach- heit halber für die Umkehrung eigene Klauseln geschrieben, wobei die oben erwähnten Klauseln für die atomaren Größen natürlich beidseitig wirken. Die Klauseln für die Richtung Baum- notation ---> analytische Notation sind allesamt recht einfach. Sie brauchen sich in dem Baum nur rekur- siv bis zu den atomaren Größen vor- arbeiten und dabei die Namen von Variablen, Konstanten etc. ausgeben, wobei an den richtigen Stellen Klam- mern eingefügt werden müssen. Wenn man sich die Klauseln ansieht, artet das Ganze in eine fürchterliche Ver- kettung von Tokenlisten mit dem Prädikat append aus. Wo die Klammern bei Funktionen und Funktions-ähn- lichen termen (Potenzen) gesetzt werden müssen, ist trivial. Interessant sind eigentlich nur drei Fälle: 1.) Beim Auftreten des Funktor div muß der zweite Operand geklammert werden, falls er ein Punkrechnungs- oder Strichrechnungsoperator ist. 2.) Beim Auftreten eines Punktrech- nungsfunktor, der ein oder zwei Strichrechnungsfunktoren enthält, müssen diese geklammert werden. 3.) Beim Auftreten des Funktor minus muß der zweite Operand geklammert werden, wenn er ein Strichrechnungs- funktor ist. Ein Sonderfall sind terme wie 0-x, die aus dem Parsingprozeß resultie- ren und als -x ausgegeben werden müssen. Leider mußte ich für jede der diver- sen Kombinationen, die auftreten können, eine eigene Klausel schrei- ben, wobei diese natürlich alle fast gleich aussehen (Typ für's eintip- pen: Kopierfunktion des Editors). Dafür gibt es nur einen Grund: Man kann dem elektronischen Trottel das Kommutativgesetz (Vertauschbarkeit von Operanden) nicht anständig bei- bringen, da keine schlüssige Mög- lichkeit existiert, das Vertauschen von Operanden zu terminieren. Man könnte natürlich immer die Ver- tauschungen mitzählen, was aber nicht gerade elegant ist. Sei's drum, die zusätzliche Tippar- beit ist bei Einsatz der Kopierfunk- tion minimal - und das Programm wird durch solche lineare Programmierung eher schneller. ------------------------------------ Das Hauptprogramm ------------------------------------ Auf eine großartige Benutzerober- fläche habe ich bei diesem Programm verzichtet, da es mir im wesent- lichen auf den Aspekt der Symbolver- arbeitung ankam. Das Prädikat start' definiert nur ein Fenster mit Über- schrift, in dem ein Buchstabenmenue mit den Optionen "A)bleiten", "I)n- tegrieren", "V)ereinfachen" und "Q)uit" ausgegeben wird. Nach Anwahl eines Menüpunktes kann man seinen Funktionsterm eingeben (z.B. a*x*y + b/(a*y)), wird nach den verwendeten Variablen gefragt (z.B. x y") und muß gegebenenfalls die Variable eingeben, nach der differenziert oder integriert werden soll. Das Ergebniss wird dann ausge- druckt. ------------------------------------ Rapid Prototyping ------------------------------------ Wenn man das Programm in seiner Gesamtheit betrachtet, kriegt man gelegentlich den Eindruck, daß ein hoher Grad an Redundanz vorhanden ist, d.h. daß es für einen bestimm- ten Fall oft mehrere Programmstellen gibt, wo dieser berücksichtigt wird. Dies resultiert aus der Vorgehens- weise, mit der ich Prolog-Programme schreibe. Hierbei denke ich mir ein Konzept für ein Prädikat aus und realisiere die dazugehörigen Klauseln. Beim Austesten des Prädikats benutze ich, falls ein Fehler auftritt, die Trace-Funktion und korrigiere den Fehler dann, indem ich z.B. noch eine zusätzliche Klausel einführe. Diese Vorgehensweise birgt natürlich das Risiko von Redundanzen in sich, weil man dabei die Gesamtheit des Programmes aus dem Auge verliert. Ich muß hier vorab klarstellen, daß ich durchaus ein Anhänger der struk- turierten Programmierung bin - schließlich habe ich einige Jahre hauptsächlich in Pascal program- miert. Aber wir leben nicht mehr im Lochkarten-Zeitalter, wo jeder Feh- ler im Programm zu Umlaufzeiten in der Größenordnung von Stunden führ- te. Im Gegenteil, schon seit Jahren macht sich das Problem der Software- Krise bemerkbar. Immer mehr Leute benutzen Computer jeder Größenord- nung und fordern dafür Individual- software, die von den Programmierern so schnell nicht geliefert werden kann. Aus dieser Perspektive ist die Philosophie des "Rapid Prototyping" nur positiv zu bewerten. Moderne AI- Programmiersysteme unterstützen durch ihre Interaktivität die schnelle Entwicklung von Programm- Prototypen ganz hervorragend, wobei diese Prototypen interaktiv - auch im Dialog mit dem Anwender, ver- bessert werden. Diese Vorgehensweise führt zu sehr kurzen Entwicklungs- zeiten von Programmen, wobei diese durch das Tracing unter Umständen sogar fehlerfreier sind, als her- kömmlich entwickelte Programme. Zumindest für mich hat diese Ent- wicklungsstrategie noch einen wich- tigen, vielleicht den allerwichtig- sten Vorteil: Das Programmieren wird wieder kreativer! Ich fühlte mich, nachdem ich ein Struktogramm ent- worfen und dieses z.B. in Pascal um- gesetzt hatte, oftmals zur Codier- maschine degradiert und sehnte mich nach den Zeiten der Basic- und Assemblerhackerei zurück. Die ganze Programmiererei wurde in ein weit- gehend automatisiertes Schema-F ge- packt, wo kein Platz mehr für spon- tane Ideen und Spielereien war. In diesem Sinne pfeife ich auf die paar kB Speicher und Millisekunden Ausführungszeit, die mir durch Re- dundanzen und ähnliches verloren ge- hen. Diese fallen heutzutage, wo schon bessere Home-Computer ihren Speicher in MegaByte messen und in Geschwin- digkeitsregionen von einigen MIPS (Millionen Instruktionen pro Sekun- de) vordringen, nicht mehr ins Ge- wicht. ------------------------------------ Resume ------------------------------------ Ich weiß nicht, ob mein Computer durch die Symbolverarbeitung einen Hauch von Intelligenz bekommen hat. Mein Problem ist hier wieder, daß der "Zauber" solcher Programme nicht wirkt, wenn man weiß, wie sie funk- tionieren. Bekannte von mir, bemer- kenswerter Weise auch Leute, die nu- merische Probleme programmieren, zeigen sich von dem Programm doch beeindruckt. Der Umfang des Pro- grammes wurde schon auf hunderte von Seiten Quellcode geschätzt - aller- dings ohne Kenntniss der angewandten Sprache. Eines ist auf jeden Fall klar: Die Kiste kann mittlerweile besser inte- grieren und differenzieren als ich. (Martin Schlöter)