Pro Logik: Prolog für Einsteiger, Teil 5
In den letzten vier Folgen dieser Serie wurden die grundlegenden Programmiertechniken der Sprache Prolog vorgestellt. Dabei wurde auch gezeigt, wie sich Prolog von anderen Programmiersprachen, insbesondere den imperativen, abhebt. In dieser letzten Folge geht es um eine etwas größere Anwendung. Dabei werden die bisher eingeführten Techniken in einem Programm benutzt. Außerdem soll die Leichtigkeit und Kürze, mit der sich eine komplexere Aufgabe in Prolog lösen läßt, anhand eines Beispiels gezeigt werden.
In den vorangegangenen Folgen wurden unter anderem die Verarbeitung von Datenstrukturen und die Anwendung von Metaprädikaten vorgestellt. In dieser fünften und letzten Folge soll ein Compiler als etwas größeres Beispiel vorgestellt werden. Ein Compiler ist als Beispiel aus mehreren Gründen gut geeignet. Erstens können hier einige der bisher besprochenen Techniken gleichzeitig in einem Programm verwendet werden. Zweitens zeigt ein Compiler, wie traditionell als kompliziert eingestufte Programme in Prolog doch recht kurz und übersichtlich formuliert werden können. Und drittens kann der implementierte Compiler bzw. die durch ihn implementierte Programmiersprache ergänzend bei der Prolog-Programmierung benutzt werden.
Functions as first class citizens
Dieses Motto dient oft als Beschreibung einer Klasse von Programmiersprachen, die eine gewisse Verwandtschaft mit Prolog besitzen. Es sind die sogenannten funktionalen Sprachen. Sie basieren zwar nicht auf der Logik, sind aber auch von einem formalen Kalkül abgeleitet, nämlich von dem lambda-Kalkül. Im Gegensatz zu einem in Prolog geschriebenen Programm, das aus einer Sammlung von Prädikaten besteht, ist ein funktionales Programm aus Funktionen aufgebaut. Ähnlich wie in Prolog gibt es keine Schleifenkonstrukte, sondern es wird stattdessen die Rekursion als wesentliches Sprachmittel benutzt. Im Gegensatz zu Prolog ist in funktionalen Sprachen kein Rücksetzen (backtracking) und nur eine eingeschränkte Form der Unifikation möglich. Als Ausgleich dazu ist das Formulieren von höherwertigen Ausdrücken (siehe letzte Folge) völlig unproblematisch, es sind also keine Metaprädikate oder etwas ähnliches notwendig. Daher kommt auch das Motto „Functions as first class citizens“. In funktionalen Sprachen kann man mit Funktionen auf eine Art und Weise umgehen, in der man in anderen Sprachen Zahlen benutzt.
Im folgenden wird zuerst die funktionale Sprache vorgestellt, die von dem Beispiel-Compiler übersetzt werden soll. Anschließend kommen wir zur Erläuterung der Funktionsweise des Compilers.
Funktionen über alles
Eine Programmdatei unserer funktionalen Sprache (FL) wird auch ein Skript genannt und besteht aus Funktionsdefinitionen und Hauptausdrücken. Beim Compilieren eines Skripts werden die Funktionen übersetzt und der erzeugte Code in die Prolog-Datenbank aufgenommen. Hauptausdrücke werden auch übersetzt, sofort im Anschluß daran ausgeführt und das Ergebnis der Berechnung ausgegeben. Tritt während des Übersetzungsvorgangs ein Fehler auf, wird dieser gemeldet und die Übersetzung abgebrochen.
Die Grammatik der Sprache FL ist in Tabelle 1 abgebildet. Sie wird dort in EBNF (Extended Backus Naur Form) dargestellt, die kurz erläutert werden soll. Zeichenketten, die genau so in einem FL-Programm vorkommen, sind in einfache Anführungsstriche eingeschlossen. Alle nicht in Anführungsstriche eingeschlossenen Buchstabenfolgen sind Nichterminalsymbole, die irgendwo in der Grammatik auf der linken Seite auftauchen und dabei definiert werden. Das einzige Nichtterminalsymbol, für das das nicht zutrifft, ist Script. Dies ist das Startsymbol der Grammatik und bildet somit den Ausgangspunkt für jedes korrekte FL-Programm. In jeder Grammatikregel wird das definierte Nichtterminal durch das Symbol (sprich: bebecomes) von dem Regelrumpf getrennt. Das Symbol „I“ (senkrechter Strich) steht für alternative Regelteile. Der Ausdruck „'a' | 'b'“ heißt also „'a' oder 'b'“. In eckige Klammern eingeschlossene Ausdrücke sind optional. Es steht also „['a']“ für „'a' oder nichts“. Ausdrücke, hinter denen ein Stern steht, können beliebig oft (auch nullmal) stehen. Somit steht „'a'*“ für (leere Zeichenkette), „a“, „aa“, „aaa“ usw. Zu guter Letzt gibt es noch Ausdrücke mit einem doppelten senkrechten Strich, wie zum Beispiel „'a' || 'b'“. Diese stehen für eine beliebige Wiederholung des linken Ausdrucks, wobei zwischen den einzelnen Wiederholungen je einmal der rechte Ausdruck stehen muß. Der linke Ausdruck muß dabei allerdings mindestens einmal Vorkommen. Das Beispiel steht also für „a“, „aba“, „ababa“ usw. Außerdem stehen in der Grammatik aus Tabelle 1 noch natürlichsprachliche Beschreibungen in spitzen Klammem („<“ bzw. „>“).
Nach dieser Einführung in die verwendete EBNF wollen wir uns aber endlich der Sprache FL widmen. Wie schon gesagt, besteht ein Skript aus einer Reihe von Gleichungsdefinitionen und Hauptausdrücken. Ganze Blöcke von Gleichungsdefinitionen werden durch das Schlüsselwort def eingeleitet. Die einzelnen Gleichungen werden durch Strichpunkte (‘;’) voneinander getrennt und ein kompletter Block durch einen Punkt (‘.’) abgeschlossen. Jede Gleichung besteht aus einem Kopf und einem Rumpf. Optional kann noch ein Guard vorhanden sein, auf dessen Bedeutung wir allerdings erst später zurückkommen werden. Der Kopf einer Gleichung wird vom Rumpf durch ein Gleichheitszeichen (‘=’) getrennt. Der Rumpf besteht aus einem Ausdruck, der syntaktisch genauso wie ein Hauptausdruck aufgebaut ist. Ein Gleichungskopf beginnt mit dem Funktionsnamen, der von einer möglicherweise leeren Liste von Mustern (engl.: patterns) gefolgt wird, die untereinander und von dem Funktionsnamen durch Doppelpunkte (’:’) abgetrennt sind. Die Muster stellen hier die Argumente der Gleichung dar. Dieselbe Schreibweise mit den Doppelpunkten wird in FL auch bei Funktionsaufrufen benutzt. Warum hier statt der gewohnten Klammem diese etwas eigenartig anmutende Notation verwendet wird, werden wir später noch detailliert besprechen. Ein Ausdruck der Form f:X:Y:Z ist also vorerst als f(X, Y, Z) zu lesen. Nach all diesen Beschreibungen nun erst einmal ein kleines Beispiel in FL:
def
fac:0 = 1;
fac:N = fac:(N - 1) * N.
fac:5.
Hier wird die Fakultätsfunktion durch zwei einfache Gleichungen definiert. Die erste besagt schlicht und ergreifend, daß die Fakultät von null gleich eins ist. Die zweite beschreibt die bekannte Rekursionsformel der Fakultät, d.h. die Fakultät von n ist gleich n mal der Fakultät von n-1. Der an diese Definition anschließende Hauptausdruck fac:5 berechnet die Fakultät von fünf. An diesem Beispiel sieht man auch schon den grundlegenden Aufbau von Mustern und (Haupt-)Ausdrücken. Muster bestehen in erster Linie aus Variablen und Zahlen. Sie können allerdings auch Datenstrukturen enthalten. In unserer kleinen Beispielsprache FL sind dies allerdings nur Listen, wobei die aus Prolog bekannte Schreibweise für Listen verwendet wird. Ausdrücke können zusätzlich zu den Variablen, Zahlen und Datenstrukturen (auch nur Listen) noch arithmetische Operationen (’+’, ’-’, ’*’, ’/’, ‘mod’) und Funktionsaufrufe in der schon beschriebenen Doppelpunktschreibweise enthalten. Des weiteren können zu einem Ausdruck noch sogenannte lokale Bindungen gehören. Diese werden dann mit dem Schlüsselwort where vom Ausdruck abgetrennt. Jede Bindung besteht aus einem Pattern, einem Gleicheitszeichen (‘=’) und einem Ausdruck. Die einzelnen Bindungen werden untereinander durch Kommas (‘,’) getrennt. Zum Zeitpunkt ihrer Auswertung werden die rechten Seiten berechnet und die Ergebnisse mittels Pattern-Matching (siehe letzte Folge) an die Muster auf der linken Seiten gebunden. Im einfachsten Fall steht auf der linken Seite einer Bindung einfach eine Variable, an die der Wert der Berechnung des Ausdrucks gebunden wird. Die Bindung ist nur innerhalb aller lokalen Bindungen, die in demselben where-Konstrukt weiter hinten stehen, und in dem Ausdruck links vom where gültig. Ein Beispiel, in dem die obige Definition der Funktion fac benutzt wird, ist wie folgt:
X * X where X = fac:7.
Hier wird das Ergebnis der Berechnung der Fakultät von sieben mit sich selbst multipliziert.
Wie schon erwähnt, sind Listen die einzige Datenstruktur, die in FL unterstützt wird. Prinzipiell wären natürlich auch allgemeine Terme wie in Prolog möglich. Diese Einschränkung wurde aber gewählt, um den Compiler möglichst klein zu halten. Ein kleines Beispiel für listenverabeitende Funktionen sind app und len.
def
app:[]:L = L;
app:[X|Xs]:L = [X|app:Xs:L];
len:[] = 0;
len:[_|L] = 1 + len:L.
Dabei hängt app zwei Listen zu einer zusammen, und len berechnet die Länge einer Liste.
Script ::= ((Definition | Expr)
Definition ::= 'def' (Rule ||
Rule ::= Head ['\' Guard] '=' Body.
Head ::= Atom (':' Pattern)*.
Pattern ::= Variable
| Number
| ListPattern.
ListPattern ::= '[' [(Pattern || (','') [ '|' Pattern]] ']'.
Guard ::= <Prolog-Anfrage>.
Body ::= Expr.
Expr ::= Sum 'where' (Binding || ',').
Binding ::= Pattern '=' Expr.
Sum ::= [Sum SumOp] Product.
Product ::= [Product ProdOp] Primitive.
Primitive ::= Variable
| Number
| Atom (':' Expr)*
| List
| '(' Expr ')'.
List ::= '['' [(Expr || ',') ['|' Expr]] ']'.
SumOp ::= '+' | '-'.
ProdOp ::= '*' | '/' | 'mod1'.
Atom ::= <Wie in Prolog>.
Number . ::= <Wie in Prolog>.
Variable ::= <Wie in Prolog>.
Comment ::= <Wie in Prolog>.
Tabelle 1: EBNF-Grammatik von FL
Gut bewacht
Die Auswahl einer Gleichung beim Funktionsaufruf geschieht in FL durch Pattern-Matching. Die Muster der Gleichungen werden von oben nach unten mit den übergebenen Argumenten verglichen, und die erste passende wird dann gewählt. Im Gegensatz zu Prolog liegt eine Gleichungsauswahl unwiderruflich fest, sobald sie einmal getroffen wurde, also kein Rücksetzen (backtracking). Wegen der Einschränkung auf Pattern-Matching (statt Unifikation) können keine Variablen in den Argumenten des Aufrufs, sondern nur die in den Gleichungen gebunden werden. Anders ausgedrückt: Durch die Parameter können keine Ergebnisse an den Aufrufer zurückgegeben werden. Dafür liefert jede Funktion aber ein Funktionsergebnis an ihren Aufrufer zurück. Da dieses Ergebnis auch eine Liste aus mehreren Werten sein kann, ist auch die Rückgabe von mehr als einem Ergebnis pro Funktionsaufruf möglich.
Trotzdem lassen sich einige Probleme mit den bisher vorgestellten Mechanismen noch nicht lösen. Durch das Pattern-Matching ist es zum Beispiel nicht möglich, festzustellen, ob ein übergebener Wert größer oder kleiner als Null ist. Für solche relationalen Tests können in FL einfach Prolog-Anfragen benutzt werden. Diese werden in Form eines Guards in die funktionalen Gleichungen eingesetzt. Ein Guard ist eine beliebige, eventuell geklammerte Prolog-Anfrage, die von der Pattern-Liste eines Gleichungskopfs durch Backslash (‘\‘) abgetrennt wird und noch vor dem Gleichheitszeichen steht. Eine Gleichung, die einen Guard besitzt, wird nur ausgewählt, wenn die Patterns passen und der Guard, d.h. die entsprechende Prolog-Anfrage, gelingt.
def
abs:N \ (N < 0) = -N;
abs:N = N.
In der ersten Gleichung der Funktion abs wird ein Guard benutzt, um zu testen, ob das Argument N kleiner Null ist. In komplizierteren Beispielen ist es auch möglich, daß der Guard durch sein Gelingen nicht nur Einfluß auf die Gleichungsauswahl nimmt, sondern auch Ergebnisse zurückliefert, die dann im Rumpf der Gleichung benutzt werden. Ein Beispielprogramm, das sowohl die Guards benutzt als auch mehr als ein Ergebnis (in einer Liste) zurückgibt, ist in Listing 1 abgebildet. Die Funktion minmax ermittelt das Maximum und Minimum der übergebenen Liste und liefert beides in einer Liste aus zwei Elementen zurück.
Gut gewürzt
Curry ist nicht nur der Name einer Gewürzmischung, die dazu benutzt wird, um den Geschmack indischen Essens in europäischen Küchen (meist recht erfolglos) nachzuahmen, sondern auch der Name eines Mathematikers. Dieser hat eine recht originelle Sichtweise von Funktionen ausführlich untersucht. Dabei wird jede Funktion grundsätzlich als einstellig angesehen. Die Addition ist dabei also keine zweistellige, sondern eine einstellige Funktion, die als Ergebnis wieder eine Funktion liefert. Diese Ergebnisfunktion ist dann wiederum einstellig. Somit liefert die Anwendung der Addition auf die Zahl 1 eine Funktion, die Eins zu ihrem (einzigen) Argument hinzuzählt, sobald sie angewendet wird. Eine Anwendung der Addition auf zwei Argumente sieht man dann zunächst nur als eine Anwendung auf das erste Argument. Diese Anwendung liefert eine neue Funktion, die sofort auf das zweite Argument angewendet wird. Dies wiederum führt dazu, daß das erste Argument (das Teil dieser von der Addition gelieferten Funktion ist) auf das ursprünglich zweite addiert wird. In FL kann man diesen Mechanismus wie folgt benutzen:
def
add:X:Y = X + Y.
Inc:7 where Inc = add:1.
Der Ausdruck add:1 liefert hier als Ergebnis eine neue Funktion, die Eins zu ihrem Argument zählt, also die Inkrementfunktion, und bindet sie an die Variable Inc. Diese Inkrementfunktion wird dann in Inc:7 auf die Zahl 7 angewendet. So gesehen ist die Addition nun also eine höherwertige Funktion, da ihr Ergebnis wiederum eine Funktion ist. Nach Herrn Curry nennt man diese Sichtweise von Funktionen auch Currying. Ein Problem des Curryings ist die Schreibweise für Funktionsanwendungen. Traditionell geschieht dies durch eine bloße Gegenüberstellung von Funktion und Argument, also zum Beispiel add 1 2 statt add(1,2). Diese Gegenüberstellung kann in der Operatorgrammatik von Prolog allerdings nicht realisiert werden, daher verwenden wir in FL den Doppelpunkt zum Trennen von Funktion und Argument. Mit etwas mehr Aufwand könnte man natürlich auch in Prolog eine Grammatik verwenden, die ohne die Prolog-Operatoren verarbeitet wird. Doch das würde wieder einmal den Rahmen dieses Artikels sprengen.
In funktionalen Programmiersprachen können Funktionen also ganz einfach als Argument an andere Funktionen übergeben werden oder wiederum das Ergebnis einer Funktion sein. Dies führt oft zu sehr eleganten und kompakten Schreibweisen für teilweise doch recht komplexe Funktionen, wie an den Beispielen in Listing 2 zu sehen ist. Dort wird eine Funktion map definiert. Diese wendet ihr erstes Argument (der Einfachheit halber wird hier wieder von ersten, zweiten usw. Argumenten gesprochen), das eine Funktion sein muß, auf eine Liste an. Dies geschieht derart, daß die Funktion auf jedes Element der Liste einmal angewendet wird und die Liste der Ergebnisse das Resultat von map bildet. Durch das Currying können jetzt sehr einfach Funktionen geschrieben werden, die die Fakultät aller Elemente einer Liste berechnen (faclist) oder jedes Listenelement einfach um Eins erhöhen (inclist).
Soviel zu der funktionalen Sprache FL. Bevor wir zur Besprechung des Compilers kommen, noch kurz eine rückblickende Motivation für die gemischte Verwendung funktionaler und logischer Sprachen. Schaut man sich manche Prolog-Programme einmal etwas genauer an, sieht man, daß große Teile oft rein funktionaler Natur sind, d.h. alle Berechnungen werden ohne Rücksetzen (Backtracking) und ohne die Verwendung freier logischer Variablen ausgeführt. Trotzdem wird auch in diesen Programmstücken der komplette Formalismus von Prolog mitgeschleift. Der Einsatz funktionaler Sprachen schafft an solchen Stellen übersichtlichere Programme. Außerdem können dann höherwertige Funktionen oft vorteilhaft eingesetzt werden. Durch die Verwendung der funktionalen Sprache FL, die mit Hilfe eines Prolog-Systems implementiert wird und Prolog-Anfragen als Guards zuläßt, ist nun ein gemischter Einsatz von funktionalen und logischen Sprachen möglich. Somit können die Vorteile beider Programmierweisen genutzt werden.
Der Compiler
Als nächstes wenden wir uns dem Compiler zu. Er soll nicht in allen Einzelheiten besprochen werden. Die verwendeten Techniken haben wir schließlich zum großen Teil schon in vorangegangenen Folgen vorgestellt. Hier wird also im wesentlichen auf die Grobstruktur des Compilers und die Realisierung von funktionalen Werten eingegangen. Doch zunächst noch ein paar Worte zum Programm selber. Es ist in Listing 3 abgebildet. Da das in der letzten Folge vorgestellte if-then-else-Prädikat, das durch den Operator ’->’ dargestellt wird, auch hier Verwendung findet, muß dessen Definition (siehe Folge 4) noch dazugeladen werden, wenn man TOY-Prolog benutzt. Dies ist bei MAXON-Prolog nicht nötig, aber durch einen Bug in der File-Verwaltung muß hier die Definition des Prädikats fl_compile/1 etwas geändert werden. Diese geänderte Version ist in Listing 4 abgebildet und muß die Version aus Listing 3 ersetzen.
Das Prädikat fl_compile/1 erwartet als Argument einen Dateinamen. Die Datei wird dann gelesen und übersetzt. Dabei werden alle Gleichungsdefinitionen (eingeleitet durch def) übersetzt und in die Datenbank aufgenommen. Alle Hauptausdrücke werden übersetzt, sofort ausgewertet und ihr Ergebnis ausgegeben. Das Prädikat processFile/0 bearbeitet eine ganze Datei mit Hilfe einer Generatortechnik, d.h. ein Prädikat (der Generator) erzeugt einen Wert, den ein anderes Prädikat verarbeitet. Ein anschließendes fail/0 löst das Rücksetzen (backtracking) aus, so daß der Generator noch einen Wert erzeugen kann, der dann wieder verarbeitet wird. Anschließend erfolgt wieder das Rücksetzen. Dies Spielchen setzt sich fort, bis der Generator erschöpft ist, d.h. keine neuen Werte mehr liefern kann. In processFile/0 ist read/1 der Generator, der einen Term nach dem anderen aus der Eingabedatei liest, und eval/1 verarbeitet diese Terme. Die zweite Klausel von processFile/0 dient nur dazu, daß processFile/0 schlußendlich gelingt, nachdem der Generator erschöpft ist.
Das Prädikat eval/1 unterscheidet zwischen Gleichungsdefinitionen (beginnen mit def), die von der zweiten Klausel verarbeitet werden, und einzelnen Ausdrücken (Hauptausdrücken), die die dritten Klausel bearbeitet. Gleichungsdefinitionen werden dabei in zwei Phasen übersetzt. Zuerst deklariert man alle darin definierten Funktionen mit dem Prädikat declare/1. Dies geschieht durch das Löschen aller eventuell schon vorhandenen Funktionen gleichen Namens und das Erzeugen eines Eintrags fl_symbols(Name, Arity) in der Datenbank für jede Funktion, wobei Name der Funktionsname und Arity die Stelligkeit der Funktion ist. Anschließend werden die Gleichungen dann durch define/1 übersetzt und in die Datenbank eingetragen.
In der Deklarationsphase wird declareOne/1 für jede Gleichung aufgerufen. Die erste Klausel von declare dient dabei nur dem Abfangen von freien logischen Variablen, die in einer syntaktisch inkorrekten Eingabe Vorkommen können und den Compiler sonst in eine Endlosschleife führen würden. Ansonsten ermittelt Prädikat declareOne/1 mittels getHeadNameAndArity/3 Namen und Stelligkeit der Funktion, der die aktuell übersetzte Gleichung angehört. Falls schon ein Eintrag einer Funktion gleichen Namens da ist [wird mit retract(fl_symbols(Name,OldArity)) festgestellt], werden deren Gleichungen alle mit removeEquas/2 entfernt. Auf alle Fälle wird zum Abschluß mittels assertz/1 ein neuer Eintrag von fl_symbols/2 erzeugt. Ist in einer Definition mehr als eine Gleichung zu einer Funktion enthalten, so schadet das nichts. Beim Abarbeiten der ersten dieser Gleichungen wird eine eventuell schon vorhandene alte Funktion entfernt. Die weiteren Gleichungen entfernen den zur Funktion gehörigen fl_symbols/2-Eintrag immer wieder, aber sie erzeugen ihn sofort danach neu. Das Prädikat removeEquas/2 benutzt im übrigen eine Generatortechnik, die ähnlich zu der in processFile/0 ist. Allerdings ist hier retract/1 der Generator.
Schemata
Bevor wir nun auf die Definitionsphase eingehen, soll kurz das Schema vorgestellt werden, nach dem die Übersetzung der einzelnen Gleichungen verläuft. Eine Gleichung kann zwei unterschiedliche Formen haben: Head\Guard = Body oder Head = Body. Ersteres wird in HeadCode :- Guard,!, BodyCode und letzteres in HeadCode :-!, BodyCode übersetzt. Der Cut ('!') ist notwendig, da innerhalb von Gleichungen kein Rücksetzen (backtracking) möglich ist. Eine einmal getroffene Gleichungsauswahl ist also nicht mehr rückgängig zu machen. Der Guard muß deshalb auch vor dem Cut stehen, da er ja noch Teil der Gleichungsauswahl ist und fehlschlagen kann. Der Guard kann ohne weitere Übersetzungsschritte direkt in die erzeugte Klausel eingesetzt werden, da er sowieso schon eine Prolog-Anfrage darstellt. In FL hat ein Gleichungskopf (ohne Guard) Head die folgende allgemeine Form Name : Pat_1: ... : Pat_N, wobei keine Argumente-Patterns da sein können (N größer gleich 0). Dies wird in den folgenden Prolog-Klauselkopf (oben HeadCode genannt) übersetzt Name (Pat_1, ..., Pat_N, ResultVar). Dabei dient ResultVar als Rückgabeparameter für den Funktionswert der übersetzten Gleichung. Innerhalb des für den Gleichungsrumpf Body erzeugten Codes BodyCode muß also das Ergebnis der Berechnung an ResultVar gebunden werden. Jede übersetzte Gleichung wird zum Schluß mittels assertz/1 in die Datenbank aufgenommen.
Diese Schemata werden defineOne/1 implementiert. Dazu werden der Gleichungskopf (ohne Guard) mit dem Prädikat compileHead/3 und der Rumpf mit compileExpr/3 übersetzt. Aus dem übersetzten Rumpfcode entfernt man dann noch mittels stripTrue/2 überflüssige true/0-Aufrufe, ähnlich wie dies auch in der letzten Folge geschah. In dem Prädikat compileHead/3 wird mit einer Akkumulatortechnik (siehe Folge 3) gearbeitet. Das ist nötig, da von diesem Prädikat eine Art Listenumkehr durchgeführt wird. Umgekehrt wird in diesem Fall die Reihenfolge der Argumente. Die Notwendigkeit zum Umkehren der Argumentreihenfolge geht nicht aus dem oben vorgestellten Übersetzungsschema für die Gleichungsköpfe hervor, sondern es ist vielmehr in der Assoziativität des Doppelpunkt-Operators (':’) begründet. Dieser wird mit op(100, yfx, ':') am Anfang von Listing 3 deklariert. Ein Ausdruck der Form f:X:Y wird also (f:X):Y geklammert. Um den Univ-Operator (‘=..’; siehe Folge 4) anwenden zu können und einen Klauselkopf wie f(X, Y, ResultVar) zu erhalten, ist aber eine Liste der Form [f, X, Y, ResultVar] nötig, die man auch [f/[X/[Y/[ResultVar/[]]]]] (siehe Folge 1) schreiben könnte. Diese ist aber genau in die andere Richtung geklammert, wie (f:X):Y. Deshalb wird das zweite Argument von compileHead/3 als Akkumulator verwendet, der initial nur die Variable ResultVar enthält. Die Ergebnisliste, auf die dann nur noch der Univ-Operator (‘=..’) angewendet werden muß, wird im dritten Argument geliefert.
Ausdrücke (auch Hauptausdrücke) werden von dem Prädikat compileExpr/3 übersetzt. Es führt eine Fallunterscheidung über die Form des zu übersetzenden Ausdrucks durch, der im ersten Argument übergeben wird. Im zweiten Argument wird ein Term (meist nur eine Variable) zurückgegeben, der beim Ausführen des erzeugten Codes das Ergebnis der Auswertung des Ausdrucks enthält. Im dritten Argument wird schließlich der erzeugte Code zurückgegeben. Die ersten zwei Klauseln von compileExpr/3 dienen der Übersetzung von Variablen und Zahlen. Beide werden ohne weitere Änderungen in den Code übernommen. Die dritte und vierte Klausel übersetzt Listen. Dazu werden in der vierten Klausel einfach der Ausdruck, der den Listenkopf, und der, der den Listenrest bildet, rekursiv von compileExpr/3 übersetzt. Die fünfte Klausel dient zum Übersetzen von Ausdrücken, die lokale Bindungen (where) enthalten. Diese werden dazu mit compileBinds/2 übersetzt. Wichtig ist dabei, daß der Code zur Berechnung der lokalen Bindungen vor dem Code des Ausdrucks, der sich links vom where befindet, steht (schließlich müssen die Bindungen zuerst ausgeführt werden). Einzelne Bindungen werden mit compileBind/2 übersetzt. Dabei wird der Ausdruck rechts vom Gleichheitszeichen einer Bindung ganz normal mit compileExpr/3 übersetzt. Der Ergebnisterm wird dann an das Muster, das rechts vom Gleichheitszeichen steht, gebunden. Falls dieses Muster nur eine Variable ist, wird die explizite Bindung allerdings wegoptimiert (zweite Klausel von compileBind/2), indem der Ergebnisterm direkt in die Variable geschrieben wird. Dazu wird die Variable als zweites Argument an compileExpr/3 übergeben (hier bewährt sich also nun die Tatsache, daß man in Prolog dasselbe Argument eines Prädikats mal als Eingabe- und mal als Ausgabeargument sehen kann).
Doch zurück zu compileExpr/3. Die sechste und siebte Klausel dient der Übersetzung von Funktionsaufrufen. Diese wollen wir aber noch kurz zurückstellen und erst die Behandlung arithmetischer Operationen behandeln, die von der achten Klausel übersetzt werden. Diese überprüft, daß ein legaler arithmetischer Operator verwendet wird, und übergibt den Ausdruck zur weiteren Verarbeitung an compileArithExpr/3. Da diese Ausdrücke im erzeugten Prolog-Code mit Hilfe des Prädikats is/2 berechnet werden, das selbst komplette Ausdrücke verarbeiten kann, sollen arithmetische Ausdrücke, wie „34+5-7“ natürlich nicht aufgespalten, sondern in einem is/2 berechnet werden. Andererseits können in einem solchen Ausdruck natürlich ein Funktionsaufruf oder lokale Bindungen Vorkommen. Diese müssen dann aus dem Ausdruck herausgezogen und durch die Terme ersetzt werden, die zur Laufzeit das Ergebnis des Funktionsaufrufs bzw. des Ausdrucks in der lokalen Bindung enthalten. Ein Beispiel ist etwa 7(fac:5)-2. Dieser Ausdruck soll in etwas wiefac(5,Fac), Result is 7*Fac-2 übersetzt werden. Dabei wird der Funktionsaufruf fac:5 herausgezogen und durch die Variable Fac ersetzt, die das Ergebnis des Funktionsaufrufs enthält. Das Prädikat compileArithExpr/3 macht nichts anderes, als einen arithmetischen Ausdruck in seine Komponenten zu zerlegen, Funktionsaufrufe und ähnliches herauszuziehen, durch die Ergebnisterme zu ersetzen und das Ganze wieder zusammenzubauen. Dabei wird in der zweiten und dritten Klausel zwischen unären (einstelligen) und binären (zweistelligen) Operatoren unterschieden. Die Zerlegung und das Zusammenbauen der Terme geschieht mit dem Univ-Operator (‘=..’).
Funktionswandlung
Zu guter Letzt kommen wir zur Übersetzung von Funktionen. Das Hauptproblem stellt hier wohl das Currying dar, da Prolog keinen vergleichbaren Mechanismus besitzt und auch nicht so einfach mit höherwertigen Funktionen umgehen kann. Betrachtet man sich die Verwendungsmöglichkeiten in FL mal etwas genauer, so sieht man, daß es im Grunde vier verschiedene Fälle von Funktionsanwendungen gibt. Der erste ist der einfachste: Ein Funktionsname wird auf genau die Zahl von Argumenten angewendet, die er benötigt, um ganz normal ausgewertet zu werden. Zum Beispiel add:3:4 mit dem add aus Listing 2. Der Fall kann in einen ganz normalen Aufruf des zugehörigen Prädikats umgewandelt werden. Im zweiten Fall wird eine Funktion auf zu wenige Parameter angewendet (Currying macht’s möglich), etwa wie in add:1. Das Ergebnis ist in diesem Fall eine neue Funktion, die diesmal keinen Namen hat, sondern das Ergebnis einer Berechnung ist. Dieser Fall schafft sicherlich echte Probleme, wir verschieben seine Behandlung noch ein wenig. Im dritten Fall wird eine Funktion auf zuviele Parameter angewendet. Dieser Fall ist recht unkritisch, denn wenn die Funktion n-stellig ist, kann man sie einfach mit den ersten n Parametern ganz normal aufrufen. Das Ergebnis dieses Aufrufs muß dann eine Funktion sein und führt direkt zum vierten Fall, in dem eine Funktion, die das Ergebnis einer vorhergehenden Berechnung ist, auf ein oder mehrere Argumente angewendet wird, wie etwa im Beispiel Inc:5 where Inc = add:1. Hier enthält die Variable Inc einen funktionalen Wert. Dieser vierte Fall hängt eng mit dem zweiten zusammen. Dort wird ein Funktionswert erzeugt, und im vierten Fall wird er benutzt. Alle Probleme sind also gelöst, wenn solche funktionalen Werte (sprich: Werte, die Ergebnis einer Berechnung sind und selber Funktionen darstellen, wie etwa das Ergebnis von add:1) vernünftig dargestellt und behandelt werden können. In Prolog liegt die Darstellung als Term natürlich sehr nahe. Dieser Term muß die Funktion enthalten, die aufgerufen werden soll, sobald genug Argumente da sind, eine Liste der noch fehlenden Argumente und eine Variable, an die das Ergebnis des Funktionsaufrufs gebunden wird. Als Funktor für solche Terme wird einfach fn/3 gewählt. Das Ergebnis von add:1 ist dann so etwas wie fn([Y], add(1, Y, Result), Result). Die Liste [Y] enthält die noch fehlenden Argumente. Der Term add( 1, Y, Result) wird mit dem Metaprädikat call/1 (siehe Folge 4) aufgerufen, sobald alle Argumente vorhanden sind. Das Ergebnis dieses Aufrufs ist dann an die Variablen Result gebunden. Eine Anwendung einer solchen Funktion (unser Fall vier) geschieht nun zur Laufzeit durch ein spezielles Prädikat fnApply/3. Dieses erhält als erstes Argument einen funktionalen Wert, der eine Funktion darstellt, als zweites Argument eine Liste der Argumente, auf die die Funktion angewendet werden soll, und im dritten Argument wird das Ergebnis der Funktionsanwendung zurückgeliefert.
Die Übersetzung eines Funktionsaufrufs gemäß dieser vier Fälle wird von den Prädikaten precompileFunCall/6, compileFunCall/5 und buildArgList/5 durchgeführt. Dabei dient precompileFunCall/6 dazu, die Anzahl der Argumente eines Aufrufs Arity und die Funktion des Aufrufs Fun zu bestimmen. Außerdem wird, ähnlich wie schon bei compileHead/3, die Reihenfolge der Argumente mittels der Akkumulatortechnik umgedreht, und es werden die Argumente übersetzt und durch die Terme, die das Ergebnis der entsprechenden Auswertungen enthalten, ersetzt. Der Code, der dabei erzeugt wird, wird im sechsten Argument zurückgeliefert und dann vor dem eigentlichen Aufruf plaziert. Nach dieser Vorübersetzung wird die eigentliche Codeerzeugung von compileFunCall/5 durchgeführt. Diese Prädikat führt im wesentlichen eine Fallunterscheidung gemäß der oben aufgeführten vier Fälle durch. In der ersten Klausel (erster Fall) stimmt die Anzahl der vorhandenen Argumente (Arity) mit der Anzahl der Argumente überein, mit der die Funktion definiert wurde (DefArity). Dies führt dann zu einem standardmäßigen Funktions- bzw. Prädikatenaufruf. Im zweiten Fall (zweite Klausel) wird zwar auch der Code für einen normalen Aufruf erzeugt, dieser wird dann aber als zweites Argument (Goal) Bestandteil eines Terms, der fn/3 als Funktor besitzt. Die Liste der noch offenen Argumente ist hier CurriedArgs und wird von buildArgList/5 geliefert. Der dritte Fall (dritte Klausel) führt zu einem gewöhnlichen Aufruf mit den ersten DefArity-Argumenten. Die Anwendung des Ergebnisses dieses Aufrufs (TempResultVar) auf die restlichen Argumente (RmdArgs) wird dann durch einen rekursiven Aufruf von compileFunCall/5 übersetzt, der immer den vierten Fall (letzte Klausel) auswählt. Dieser erzeugt im wesentlichen einen Aufruf des Laufzeitprädikats fnApply/3.
Das Prädikat buildArgList/5 dient lediglich dem Aufbau der Argumentliste des Prädikats, in das ein Funktionsaufruf übersetzt wird. Dabei wird der Ergebnisparameter (ResultVar) hinten angehängt. Außerdem werden zuviele oder zuwenig vorhandene Argumente dadurch behandelt, daß die übrigen Argumente bzw. eine Liste von Variablen für die fehlenden Argumente im letzen Argument von buildArgList/5 (DiffArgs) zurückgeliefert werden.
Noch besser
Nachdem die wesentlichen Elemente des Compilers vorgestellt wurden, soll noch kurz auf mögliche Verbesserungen des Übersetzungsvorgangs und der Sprache FL eingegangen werden. Ein wesentlicher Schwachpunkt im Übersetzungsvorgang ist die recht einfache Fehlerbehandlung. Erstens werden viele Fehler nicht erkannt, und zweitens wird nach dem Erkennen eines Fehlers sofort abgebrochen. Besser wäre, soviel wie möglich von der Eingabe noch zu übersetzen, außerdem sollte die Position, an der ein Fehler aufgetreten ist, besser kenntlich gemacht werden. Zusätzlich sollte zum Beispiel überprüft werden, daß in Mustern keine Funktionsaufrufe oder ähnliches vorkommen. Außerdem wird bisher immer direkt die Unifikation zum Pattern-Matching verwendet. Streng genommen müßten aber Tests eingeführt werden, die überprüfen, daß keine Variablen in den Argumentpositionen des Aufrufers gebunden werden. Zudem sollte überprüft werden, daß in den Funktionsrümpfen keine ungebundenen Variablen Vorkommen, und der Name eines Prädikats, das eine FL-Funktion implementiert, sollte eventuell so verändert werden, daß er nicht aus Versehen mit einem im Prolog verwendeten Prädikat kollidiert.
Zur Verbesserung der Sprache FL wären im Prinzip drei Punkte zu nennen. Erstens wäre ein if-then-else Konstrukt in der Sprache sehr nützlich. Die Übersetzung davon könnte ähnlich aussehen, wie dies in Folge 4 vorgeschlagen wurde. Außerdem sollten allgemeine Datenstrukturen und nicht nur Listen zugelassen werden. Dazu ist es dann allerdings nötig, zwischen Namen von Funktionen und Datenkonstruktoren, also Funktoren von Datenstrukturen, zu unterscheiden. Dies kann über eine explizite Deklaration der Datenkonstruktoren geschehen, oder es wird festgelegt, daß alle nicht in fl_symbols/2 gespeicherten Namen Datenkonstruktoren bezeichnen. Zu guter Letzt wäre es noch nett, wenn man lokale Funktionen definieren könnte. Dies müßte dann innerhalb von lokalen Bindungen geschehen. Dazu müßte man den Übersetzungsvorgang allerdings etwas erweitern. Die lokalen FL-Funktionen müßten in globale Prolog-Prädikate transformiert und ihre freien Variablen entsprechend behandelt werden, dabei müssen dann natürlich auch wieder Namenskonflikte verhindert werden.
The End
Nun sind wir am Ende der Prolog-Serie angelangt. Da sie den großen Bereich des logischen Programmierens natürlich nur anreißen konnte, stehen im folgenden noch ein paar Literaturhinweise. Das Standardwerk zum Einstieg in Prolog ist sicherlich „Programming in Prolog“ [2]. Es führt anhand vieler Beispiele sehr systematisch in alle Grundtechniken der Prolog-Programmierung ein und ist in einem recht lockeren Stil geschrieben. Das Buch „The Art of Prolog“ [3] beginnt zwar auch bei den Grundlagen, aber es führt sehr viel weiter und schließt auch fortgeschrittene Programmiermethoden ein. Zudem ist es etwas formaler aufgebaut. Wer in dieser Folge Interesse an funktionalen Programmiersprachen gefunden hat, dem sei „Introduction to Functional Programming“ [1] ans Herz gelegt. Dies Buch führt sehr systematisch in den Stil funktionalen Programmierens ein und schafft es, eine gewisse Faszination für die Eleganz dieser Art der Programmierung zu vermitteln. Des weiteren ist der Autor selbstverständlich wieder für Kritik, Anregungen und Fragen offen, die an die folgende Adresse gerichtet werden können:
Manuel Chakravarty Wilhelm-Leuschner-Str.2 7500 Karlsruhe 21
Literatur :
[1] BirdIWadler: „Introduction to Functional Programming“, Prentice Hall
[2] Clocksin/ Mellish: „Programming in Prolog“, Springer
[3] Sterling/Shapiro: „The Art of Prolog“, MIT Press
def
minmax: [X|Xs] = minmax0 Xs:X:X;
minmax0:[]:Min:Max = [Min, Max];
minmax0:[X|Xs]:Min:Max \ (X < Min) = minmax0 :Xs:X:Max;
minmax0:[X|Xs]:Min:Max \ (X > Max) = minmax0 :Xs:Min:X;
minmax0:[_|Xs]:Min:Max = minmax0 :Xs:Min:Max.
Min + Max
where
[Min, Max] = minmax: [5, 1, 8, 2, 0. 2].
Listing 1: Maximum-Minimum-Berechnung in FL
def
fac:0 = 1;
fac:N = fac:(N - 1) * N;
add:X:Y = X + Y;
map:F:[] = [];
map:F[X|Xs] = [F:X|map:F:Xs];
faclist:L = map:fac:L;
inclist:L = map:(add:1):L.
Listing 2: Beispiele in FL
% FL nach Prolog Compiler
%
% Autor: Manuel Chakravarty
%
% (c) 1991 by MAXON Computer GmbH
% Operatordeklarationen
%
:- op(1150, yfx, 'where').
:- op(1150, fx, 'def').
:- op(650, xfx, '\').
:- op(100, yfx, ':').
% Kommandolevel
% =============
% compile fl(FileName) — Compiliert die Datei
% "FileName".
%
compile_fl(FName) :-
see(FName),
processFile,
seen.
processFile :-
repeat,
(read(Term) -> true; Term = end),
(Term = end
-> true
; (eval(Term), fail)).
**Listing 3: Der FL-Compiler**
% eval(Term) — Evaluiert den übergebenen Term.
%
eval(Var) :- var(Var), !,
raiseError(freeVar).
eval((def Defs)) :- !,
declare(Defs),
define(Defs).
eval(Expr) :-
compileExpr(Expr, Result, Main),
call(Main),
write(Result), nl.
% Deklarationsphase
% =================
% declare(Defs) -- Deklariert die übergebene
% Liste von Definitionen.
%
declare(Var) :- var(Var), !,
raiseError(freeVar).
declare((Def; Defs)) :- !,
declareOne(Def),
declare(Defs).
declare(Def) :-
declareOne(Def).
declareOne(Var) :- var(Var), !,
raiseError(illegalDef(Var)).
declareOne(Head = Body) :- !,
getHeadNameAndArity(Head, Name, Arity),
(retract(fl_symbols(Name, OldArity))
-> removeEquas(Name, OldArity)
; true),
assertz(fl_symbols(Name, Arity)).
declareOne(IllegalDef) :-
raiseError(illegalDef(IllegalDef))
getHeadNameAndArity(Head \ Guard, Name, Arity) :-
!,
getHeadNameAndArity(Head, Name, Arity).
getHeadNameAndArity(Fun : Arg, Name, M) :- !,
getHeadNameAndArity(Fun, Name, N), M is N + 1.
getHeadNameAndArity(Name, Name, 0) :-
atom(Name), !.
getHeadNameAndArity(IllegalName, _, _) :-
raiseError(illegalFunName(IllegalName)).
% removeEquas(Name, Arity) — Löscht alle
% zu einem Namen gehörenden Gleichungen
%
removeEquas(Name, OldArity) :-
ArgNum is OldArity + 1,
functor(Template, Name, ArgNum),
retract((Template :- _)),
fail.
removeEquas(_, _).
% Übersetzungsphase
% =================
% define(Defs) — Übersetzt und speichert,
% die übergebene Liste von Definitionen.
%
define(Var) :- var(Var), !,
raiseError(freeVar).
define((Def; Defs)) :- !,
defineOne(Def),
define(Defs).
define(Def) :-
defineOne(Def).
defineOne(Var) :- var(Var), !,
raiseError(illegalDef(Var)).
defineOne(Head \ Guard = Body) :- !,
compileHead(Head, [Result], HeadList),
HeadCode =.. HeadList,
compileExpr(Body, Result, BodyCode),
stripTrue(BodyCode, StrippedCode),
assertz((HeadCode :- (Guard, !),
(StrippedCode),
true))
defineOne(Head = Body) :- !,
compileHead(Head, [Result], HeadList),
HeadCode =.. HeadList,
compileExpr(Body, Result, BodyCode),
stripTrue(BodyCode, StrippedCode),
assertz((HeadCode :- !,
(StrippedCode), true)).
defineOne(IllegalDef) :-
raiseError(illegalDef(IllegalDef)).
stripTrue(true, true) :- !.
stripTrue((true, Goal), StrippedGoal) :- !,
stripTrue(Goal, StrippedGoal).
stripTrue((Goal, true), StrippedGoal) :- !,
stripTrue(Goal, StrippedGoal).
stripTrue((Goal1, Goal2),
(StrippedGoal1, StrippedGoal2)) :- !,
stripTrue(Goal1, StrippedGoal1),
stripTrue(Goal2, StrippedGoal2).
stripTrue(Goal, Goal).
% Übersetzung von Funktionskopfen
compileHead(Var, _, _) :- var(Var), !,
fail.
compileHead(Fun : Arg, Args, Result) :- !,
compileHead(Fun, [Arg|Args], Result).
compileHead(Name, Args, [Name|Args]) :-
atom(Name).
% Übersetzung von Ausdrucken
% compileExpr(Expr, ResultTerm, Code) —
% Übersetzt den Ausdruck "Expr". Ergebnis
% ist der Term "ResultTerm" der im Code
% "Code" das Ergebnis repräsentiert.
%
compileExpr(Var, Var, true) :- var(Var), !.
compileExpr(Number, Number, true) :- integer(Number), !.
compileExpr([], [], true) :- !.
compileExpr([ElemlElems], [ElemCode|ElemsCode],
(ElemPreCode, Code)) :- !,
compileExpr(Eiern, ElemCode, ElemPreCode),
compileExpr(Elems, ElemsCode, Code).
compileExpr((Expr where Bindings), ResultVar,
(BindCode, ExprCode)) :- !,
compileBinds(Bindings, BindCode),
compileExpr(Expr, ResultVar, ExprCode).
compileExpr(Fun : Arg, ResultVar,
(ArgsCode, Code)) :- !,
precompileFunCall(Fun : Arg, [], RootFun,
Arity, Args, ArgsCode),
compileFunCall(RootFun, Arity, Args,
ResultVar, Code).
compileExpr(FunName, ResultVar, Code) :-
atom(FunName), !,
compileFunCall(FunName, 0, [], ResultVar,
Code).
compileExpr(Expr, Result,
(Code, Result is ResultExpr)) :-
Expr =.. [Op|Args],
(Op = '+' ; Op = '-'' ; Op = '*'' ;
Op = '/' ; Op = 'mod'), !,
compileArithExpr(Expr, ResultExpr, Code).
compileExpr(ErrorCode, _, _) :-
raiseError(illegalCode(ErrorCode)).
% compileArithExpr (Expr, NewExpr, Code) —
% Übersetzt einen arithmetischen Ausdruck
% "Expr" in einen neuen Ausdruck
% "NewExpr" und einen "Code".
%
compileArithExpr(Var, Var, true) :- var(Var), !.
compileArithExpr(Expr, Result, Code) :-
Expr =.. [Op, Arg],
(Op = '+' ; Op = '-'), !,
compileArithExpr(Arg, ArgResult, Code),
Result =.. [Op, ArgResult].
compileArithExpr(Expr, Result, (Code1, Code2)) :-
Expr =.. [Op, Arg1, Arg2],
(Op = '+' ; Op = '-' ; Op = '*' ;
Op = '/' ; Op = 'mod'), !,
compileArithExpr(Arg1, Arg1Result, Code1),
compileArithExpr(Arg2, Arg2Result, Code2),
Result =.. [Op, Arg1Result, Arg2Result].
compileArithExpr(Expr, Result, (Code1, Code2)) :—
Expr = [Op|Args],
(Op = '+' ; Op = '-' ; Op = '*'' ;
Op = '/' ; Op = 'mod'), !,
raiseError(illegalArith(Expr)).
compileArithExpr(Expr, Result, Code) :-
compileExpr(Expr, Result, Code).
% Übersetzung von Funktionsaufrufen
% precompileFunCall(FunCall, ArgsIn, Fun,
% Arity, ArgsOut, Code)
% Vorübersetzung eines Funktionsausrufs
% "FunCall". Zerlegung in die Funktion "Fun",
% ihre Argumente "ArgsOut" und die Anzahl
% der Argumente "Arity". Der aus den
% Argumenten herausgezogenen Code steht in
% "Code" "ArgsIn" dient als Akkumulator
%
precompileFunCall(FunRoot, Args, FunRoot, 0,
Args, true) :- var(FunRoot), !.
precompileFunCall(Fun : Arg, ArgsIn, FunRoot, M,
ArgsOut,
(ArgPreCode, MorePreCode)) :-
!,
compileExpr(Arg, ArgCode ArgPreCode),
precompileFunCall(Fun, [ArgCode|ArgsIn],
FunRoot, N, ArgsOut,
MorePreCode),
M is N + 1.
precompileFunCall(FunRoot, Args, FunRoot, 0, Args,
true).
% compileFunCall(Fun, Arity, Args, ResultVar,
% Code) — Übersetzt die
% Anwendung von "Fun" auf die Argumente "Args".
% Anzahl der Argumente ist "Arity".
% Das Ergebnis der Anwendung wird in
% "Code" an "ResultVar" gebunden.
%
compileFunCall(FunName, Arity, Args, ResultVar,
FunCall) :-
atom(FunName),
fl_symbols (FunName, DefArity),
DefArity = Arity, !,
buildArgList(DefArity, Args, ResultVar,
Arglist, _),
FunCall =.. [FunName|ArgList].
compileFunCall (FunName, Arity, Args, ResultVar,
ResultVar = fn(CurriedArgs, Goal,
CallResultVar)) :-
atom(FunName),
fl_symbols(FunName, DefArity),
DefArity > Arity, !,
buildArgList(DefArity, Args,
CallResultVar, ArgList,
CurriedArgs),
Goal =.. [FunName|ArgList].
compileFunCall(FunName, Arity, Args, ResultVar,
(FunCall, SndCall)) :-
atom(FunName), !,
fl_symbols(FunName. DefArity),
buildArgList(DefArity, Args,
TempResultVar, ArgList,
RmdArgs),
FunCall =.. [FunName|ArgList],
RmdArity is Arity - DefArity,
compileFunCall(TempResultVar, RmdArity,
RmdArgs, ResultVar, SndCall).
compileFunCall(Fun, _, Args, ResultVar,
(FunCode, fnApply(FunResult, Args,
ResultVar))) :-
compileExpr(Fun, FunResult, FunCode).
% buildArgList(Arity, Args, ResultVar, ArgList,
% DiffArgs) — Baut die
% Argumentliste für Funktionsanwendungen auf. Dabei
% wird das Vorhandensein von zuvielen oder zuwenig Argumenten
% korrekt behandelt.
%
buildArgList(0, Args, ResultVar, [ResultVar],
Args) :- !.
buildArgList(N, [], ResultVar, [NewVar|ArgList],
[NewVar|Vars]) :- N > 0, !,
N1 is N - 1,
buildArgList(N1, [], ResultVar, ArgList,
Vars).
buildArgList(N, [Arg|Args], ResultVar,
[Arg|ArgList], RmdArgs) :-
N1 is N - 1,
buildArgList(N1, Args, ResultVar,
ArgList, RmdArgs).
% Übersetzung von lokalen Bindungen
% compileBinds(Binds, Code) -- Übersetzt
% eine Liste lokaler Bindungen.
%
compileBinds(Var, _) :- var(Var), !,
raiseError(freeVar).
compileBinds((Bind, Binds),
(BindCode, BindsCode)) :- !,
compileBind(Bind, BindCode),
compileBinds(Binds, BindsCode).
compileBinds(Bind, BindCode) :-
compileBind(Bind, BindCode).
compileBind (Var, _) :- var (Var), !,
raiseError(freeVar).
compileBind (Var = Expr, Code) :- var (Var), !,
compileExpr(Expr, Var, Code).
compileBind(Pattern = Expr,
(Code, Pattern = ResultVar)) :- !,
compileExpr(Expr, ResultVar, Code).
compileBind(IllegalBind, _) :-
raiseError(lllegalBinding (IllegalBind)).
% Fehlerbehandlung
% ================
raiseError(freeVar) :- !,
showErr('Encountered free variable').
raiseError(illegalCode(ErrCode)) :- !,
showErr('Illegal expression', ErrCode).
raiseError(illegalFunName(ErrCode)) :- !,
showErr('Illegal fun. name', ErrCode).
raiseError(illegalBinding (ErrCode) ) :- !,
showErr('Illegal binding', ErrCode).
raiseError(illegalDef(ErrCode)) :- !,
showErr('Illegal definition', ErrCode).
raiseError(illegalArith(ErrCode)) :- !,
showErr('Illegal arithmetic expression', ErrCode).
raiseError(illegalFunRuntime(ErrCode) ) :- !,
showErr('Must be function ', ErrCode).
showErr(Msg)
nl, display('»> '), display(Msg),
display (' "'), nl, nl,
abort.
showErr(Msg, Reason) :-
nl, display('»> '), display(Msg),
display(' "'), write(Reason),
display('"!'), nl, nl,
abort.
% Laufzeitroutinen
% ===============
% fnApply(Fun, Args, Result) — Wendet den
% funktionalen Wert "Fun" auf die Liste von Argumenten "Arg" an.
% Das Ergebnis wird in "Result"
% geliefert
%
fnApply(Fun, Args, Result) :-
clone(Fun, ClonedFun),
fnApplyNoClone(ClonedFun, Args, Result).
fnApplyNoClone(fn([Var], Goal, ResultVar),
[Arg|Args], Result) :- !,
Var = Arg,
call(Goal),
(Args = []
-> Result = ResultVar
; fnApply(ResultVar, Args, Result)).
fnApplyNoClone(fn([Var|Vars], Goal, ResultVar),
[Arg|Args], Result) :- !,
Var = Arg,
fnApplyNoClone(fn(Vars, Goal, ResultVar),
Args, Result) .
fnApplyNoClone(IllegalFun, _ , _) :-
raiseError(illegalFunRuntime(IllegalFun)).
% clone(Term, ClonedTerm) — Macht eine
% Kopie des Terms "Term", die dem Orgmalterm
% komplett entspricht, allerdings sind alle unterschiedlichen
% Variablen durch neue
% (unterschiedliche) ersetzt worden.
%
clone(Term, ClonedTerm)
asserta(fl_clone(Term)),
retract(fl_clone(ClonedTerm)) , ! .
compile_fl(FName) :-
seeingh(OldIn),
open(File, FName),
seeh(File),
processFile,
seeh(OldIn),
close(File)
Listing 4: Alternatives fl_compile/1 Prädikat (MAXON-Prolog)