PROLOG 10: Gratis-Reise durch die Welt der KI

PROLOG, die vieldiskutierte Computersprache der fünften Generation ist für ST-Benutzer nun auch in der Public Domain Software der ST-Redaktion erhältlich. Was macht diese Sprache so mächtig, daß sie als Programmiersprache im Projekt der fünften Computergeneration eingesetzt werden soll? Lohnt es sich schon wieder mit einer neuen Sprache zu beschäftigen, oder soll man bei seinem geliebten C, Pascal oder Basic bleiben? Und ist das Public Domain Prolog (TOY Prolog) nur ein Spielzeug, wie sein Name anzudeuten scheint? Antworten finden Sie im folgenden Artikel.

Etwas Historie

Die Computersprache der ersten Generation ist die nackte Maschinensprache. In dieser Sprache wurden die ersten Computer direkt durch Setzen an Kippschaltern programmiert. Die Entwicklung symbolischer Assembler hat dann in der zweiten Generation zu einem erheblichen Anstieg in der Produktivität der Programmierung geführt. Für Anwender außerhalb der Informatik wurden Computer erst mit der Entwicklung der Hochsprachen interessant. Eine der ersten Sprachen dieser dritten Generation ist das legendäre, in den Naturwissenschaften immer noch beliebte FORTRAN (FORmular TRANslator). Das aus dem Microcomputerbereich nicht wegzudenkende BASIC (Beginners All purpose Svmbolic Instruction Code) ist im übrigen ein vereinfachter FORTRAN Ableger. Mit dem Auftauchen der rekursionsfähigen Sprachen PASCAL (nach Blaise Pascal, frz. Mathematiker) und C (die dritte Version der von D. Ritchie entwickelten Sprache), die die Methode der strukturierten Programmierung unterstützen, war die vierte Softwaregeneration geboren. Allerdings ist der Anstieg in der Produktivität der Programmierung durch die Einführung der Sprachen der vierten Generation längst nicht so dramatisch gewesen, wie noch bei der Einführung der Sprachen der zweiten und dritten Generation. Die in der letzten Ausgabe diskutierte Sprache LISP nimmt hier eine gewisse Sonderstellung ein. Sie gehört neben FOTRAN zu den ältesten Computersprachen und hat dennoch so fortschrittliche Sprachelemente wie Rekursion und funktionale Programmierung zu bieten. Um Mißverständnissen vorzubeugen, möchte ich darauf hinweisen, daß hier nur von der Produktivität des Programmierens die Rede ist, nicht von der Effizienz des laufenden Programms. In dieser Hinsicht dürften auch weiterhin Assemblerprogramme (bzw. Maschinenprogramme) nicht zu schlagen sein. Niemand wird denn wohl auch bestreiten können, daß die Entwicklung eines Algorithmus in einer Hochsprache schneller gelingen wird, als die (genauso mögliche) entsprechende Entwicklung in Assembler. Ein Vergleich in der Programmiereffizienz von BASIC und PASCAL wird da wohl (je nach persönlicher Einstellung) weniger eindeutig ausfallen. C bringt hier gegenüber PASCAL fast keine Vorteile und MODULA, ADA etc. bringen auch keine elementar neuen Sprachkonzepte ein, sondern setzen eher auf Standardisierung von Algorithmen. Ganz anders dagegen der Ansatz von PROLOG, der bewußt vom vielgeliebten Algorithmusbegriff abweicht.

PROLOG - PROgrammieren in LOGik

Mit dieser neuen Programmiersprache der fünften Generation, kommt man dem Traum des Computerbenutzers nahe, ohne Erlernung einer Sprache den Computer nutzen zu können. Dies wird möglich, weil Prolog bereits einen Suchalgorithmus eingebaut hat, der selbständig abläuft, und der dem Benutzer ein gegenüber den Sprachen der vierten Generation völlig neues Lösungskonzept abverlangt. In der Tat sollte man als langjähriger Benutzer algorithmischer Programmiersprachen am besten zunächst alles vergessen was man bisher gelernt hat. Das erworbene Wissen um Algorithmen und Datenstrukturen, den beiden Zauberworten der vierten Generation, behindert den PROLOG Anfänger nämlich eher als das es nutzt. Der Prolog Programmierer braucht sich um den imperativen Ballast seines Problems (wie soll der Computer mein Problem lösen?) also nicht mehr zu kümmern. Statt dessen deklariert (erklärt) er dem Computer die logische Struktur des Problems (PROLOG ist eine deklarative Sprache), lehnt sich zurück und harrt der Lösungen, die der Computer findet. Deshalb werden wir die Begriffe Algorithmus, Datenstruktur, Prozedur und Funktion zunächst aus dem Gedächtnis streichen und durch neue, dem Programmieren in Prolog besser entsprechende Begriffe ersetzen.

Prädikate, Klauseln, Regeln und Fakten

Grundlage des Programmierens in Prolog sind die Hornschen Klauseln, eine Sonderform der Prädikatenlogik, bei der der Kopf der Klausel (der linke Teil einer Klausel, siehe weiter unten) nur aus dem Namen (dem Funktor) und den Argumenten bestehen darf. Den Aufbau eines Prädikates zeigt Abb. 1. Den gleichen Sachverhalt können Sie auch in der Dokumentation von TOY-Prolog nachlesen, aber dort ist er in der dem Normalverbraucher nicht ganz vertrauten Backus-Naur-Form (BNF) angegeben. Die einzelnen Definitionen, grammatischen Regeln und Direktiven werden mit FTilfe logischer Verknüpfungen (den Junktoren nicht, und, oder; in PROLOG: not,;) zu Klausen zusammengefaßt. Verschiedene Klauseln des gleichen Prädikats werden so interpretiert, daß bei nicht zutreffender Klausel die nächste untersucht wird. Das bedeutet, daß die verschiedenen Klauseln durch oder verknüpft sind. Wenn es nun in der Menge der Klauseln eines Prädikates (alle mit gleichem Namen und gleicher Anzahl von Argumenten) ein einziges gibt, für das die Klausel zutrifft, dann hat also das ganze Prädikat Erfolg. Wie in der Logik auch, können Prädikate, Klauseln etc. nur den Zustand zutreffend (true, Erfolg) oder nicht zutreffend (fail, Mißerfolg) einnehmen. Der Prolog Interpreter arbeitet bei der Zustandsbestimmung eines Prädikates nun nach folgenden Regeln, die man Resolution nennt.

Abb.1: Zusammensetzung von Praedikaten aus Klauseln, Fakten und Regeln

  1. PROLOG versucht, die verschiedenen Klauseln eines aufgerufenen Prädikates in den Zustand true zu versetzen (Man spricht auch von Erfolg). Hierzu beginnt der Interpreter mit der im Programmtext zuoberst stehenden Klausel und arbeitet dann die nächste Klausel des gleichen Prädikates ab, solange es ihm nicht gelungen ist, die gerade bearbeitete Klausel in den Wahrheitszustand true zu versetzen. Hatte der Prolog Interpreter irgendwann Erfolg, wird das Prädikat in den Zustand wahr gesetzt und die evtl, folgenden Klauseln des Prädikates werden nicht mehr bearbeitet (Sie sind ja durch oder miteinander verbunden). Die Anordnung der Klauseln eines Prädikates ist also unter Umständen sehr bedeutsam.

  2. Hatte Prolog keinen Erfolg mit der Bearbeitung aller Klauseln eines Prädikates, so wird das Prädikat in den Wahrheitszustand fail gesetzt.

  3. Zur Bestätigung des Wahrheitsgehaltes einer Klausel übernimmt Prolog selbständig den Rastervergleich (Unifikation) und Einsetzung aller Variablen (Instanzierung). Existieren mehrere Lösungen, dann werden diese mit Hilfe eines eingebauten Backtracking Mechanismus aufgesucht. Dieser kann vom Benutzer allerdings auch extra unterbrochen werden, etwa wenn man nur an der ersten Lösung interessiert ist.

  4. Alle Variablen sind (wie in der Logik üblich) lokal an die Klausel gebunden, in der sie Vorkommen.

Das hört sich komplizierter an als es ist. Für Programmieranfänger ist es auch im allgemeinen einfacher mit PROLOG anzufangen, als für Leute, die schon durch den Umgang mit algorithmischen Sprachen „verdorben“ wurden. Man braucht bei den Prädikaten nämlich nur an einen juristischen Vertrag zu denken, der erfüllt ist, wenn eine Klausel des Vertrages zutrifft. In diesem Sinne ist ein Prolog-Programm ein Gebilde aus Verträgen (Prädikaten), die aus einzelnen Klauseln bestehen. Und wie in jedem Vertrag, gibt es auch in PROLOG Regeln, die einen Sachverhalt definieren. Die simpelste Regel ist das Fakt. Es ist eine nicht weiter zu belegende Tatsache.

Der syntaktische Aufbau von Fakten und Regeln

Wie gesagt: das einfachste Prädikat ist das Fakt. Es hat einen Namen (Funktor), der mit einem Kleinbuchstaben beginnen muß. Optional ist eine Parameterliste. Jede Klausel muß mit einem Punkt abgeschlossen werden, also auch das Fakt.

Beispiele für Fakten:

atari. vater(august). vater(august,emil). kind(emil).

Die Namen der Fakten (atari, vater, august, emil, kind) sind nicht weiter strukturiert und heißen deshalb wie in LISP Atome. Wie man sieht, kann der gleiche Funktor „vater“ für zwei verschiedene Fakten benutzt werden. So läßt sich vater(august) als das Fakt interpretieren, daß ein gewisser Herr mit dem Namen august Vater eines Kindes ist. Das Fakt vater(august,emil) hingegen hält fest, das ein gewisser Herr august Vater von emil ist. Obwohl beide Aussagen verwandt scheinen, so sind sie für Prolog doch gänzlich verschieden. Wir müssen bei der Benutzung eines Prädikates stets die Anzahl der Parameter (die Stelligkeit oder Arität) des Prädikates berücksichtigen. Also sind vater/1 (/1 ist die Stelligkeit des Prädikates. Beispiel: vater(august).) und vater/2 (Stelligkeit 2. Beispiel: vater(august,emil).) zwei völlig verschiedene Prädikate, trotz gleichen Namens (Funktor). Die Stelligkeit von atari in der obigen kleinen Datenbank ist demnach 0. Natürlich enthält die Vater-Kind Beziehung in der kleinen Beispieldatenbank überflüssige Informationen. Beispielsweise ist bereits aus dem Fakt vater(august, emil) klar, daß emil das Kind von august sein muß. Also wird man die Datenbank mit den Fakten zu einer Wissensbank mit Fakten und Regeln machen, indem man das Prädikat kind aus dem Prädikat vater/2 mit Hilfe einer Regel schließt:

Regel:
X ist ein Kind, wenn das zweite Argument des zweistelligen Prädikates vater mit X in Übereinstimmung gemacht (instanziert) werden kann.

Oder anders ausgedrückt, wenn es eine Person Y gibt, die mit X zusammen im Fakt vater/2 in der Datenbank steht (vater(august,emil).), dann ist X das Kind von Y. Hier übernehmen X und Y die Funktion von Variablen, d.h. sie stehen stellvertretend für ein Objekt. Bitte beachten Sie: in PROLOG beginnen alle Variablennamen mit einem Großbuchstaben. Im Gegensatz zu den imperativen Sprachen der vierten Generation lassen sich Variablen keine Werte zuordnen. Diese werden in PROLOG vielmehr instanziert (vom Interpreter im Rahmen eines Muster- oder Rastervergleiches zugewiesen), d. h. innerhalb einer Klausel kann eine Variable nur einmal einen Wert erhalten, danach behält sie diesen bis zum Verlassen der Klausel dem Gültigkeitsbereich der Variablen). Diese referentielle Transparenz ist es auch, die im übrigen PROLOG für die Computerbauer der 5. Computergeneration so interessant macht, weil sie parallele Datenverarbeitung ermöglicht. Die Regel für das Kind ließe sich in PROLOG folgendermaßen formulieren:

kind(X) :- vater(Y,X).

Hierin bedeutet kind(X) den Regelkopf und (durch :- getrennt) vater(Y,X) den Regelrumpf. Man liest die Regel am besten so: Es gilt: X ist kind, wenn vater von Y und X gilt. Fragen wir nun nach dem Prädikat kind(emil), so wird uns PROLOG yes antworten, weil der Interpreter in der Datenbank das Prädikat vater/2 findet. Er bringt nämlich die Variable Y mit dem Fakt august in Übereinstimmung und den Inhalt der Variablen X aus dem Kopf (emil) mit dem Inhalt der Variablen X aus dem Fakt der Datenbank (emil). Da der Rastervergleich Erfolg hat, hat auch das Prädikat vater/2 Erfolg. Und somit auch das Prädikat kind(emil). Die im Verlauf des Rastervergleiches in Übereinstimmung gebrachte Variable Y (august) unterschlägt Prolog, weil diese Variable nicht im Prozedurkopf, also in der Anfrage (dem goal) enthalten war.

Unifizierung und Instanzierung

Diese beiden Begriffe wurden bisher schon erwähnt und sollen nun etwas näher erläutert werden. Es sind die Fachausdrücke für einen Muster- oder Rastervergleich von Datenstrukturen in Prolog und die damit verbundene Zuordnung von Daten an Variable. Wie bereits gesagt unterscheidet sich Prolog von den imperativen Sprachen der vierten Generation u. a. durch den Gebrauch von Variablen, die im Sinne der Logik Platzhalter für irgendetwas darstellen. Demnach gibt es in Prolog auch keine Datenstrukturen, die (wie in Pascal oder C) deklariert werden müssen und über deren korrekte Verwendung ein strenger Typencheck wacht (Es sei an dieser Stelle ein bissiger Seitenhieb auf Turbo Prolog aus dem MS-DOS Lager erlaubt, welches durch die Hintertür diesen Vorteil wieder zunichte macht). Vielmehr kann jede Prolog Variable mit jedem legalen Prolog Term instanziert werden. Die Unifizierung verwendet die Instanzierung von Variablen lediglich als Elementaroperationen. Unter Unifizierung versteht man also einen allgemeinen Mustervergleich zweier Prolog Terme. Hierbei gibt es keinen „L-Wert“ und „R-Wert“, d. h. die beiden Prolog Terme die unifiziert werden sollen sind gleichberechtigt. Eine Unifizierung kann dann drei Ergebnisse haben:

  1. Beide Terme sind bereits gleich, d. h. sie haben sowohl die gleiche Struktur, als auch die gleichen Konstanten, Unterstrukturen oder Variablen Einsetzungen an den gleichen Stellen. Dann beschränkt sich der Rastervergleich auf diesen Vergleich und ist damit erfolgreich.

  2. Es gibt Unterschiede zwischen den Termen. Diese können aber dadurch beseitigt werden, das in einem oder beiden Termen geeignete Variablen mit Fakten oder Termen aus der Wissensbank in Übereinstimmung gebracht werden. Prolog führt dann diese Einsetzungen durch und der Rastervergleich schließt erfolgreich ab.

  3. Können die Unterschiede nicht wie in 2) beseitigt werden, dann werden keine Einsetzungen vorgenommen und der Rastervergleich endet erfolglos.

Abb. 2 zeigt einige der möglichen Fälle.

Listen in PROLOG

Wie in LISP, so sind auch in PROLOG die Listen ein ganz wesentliches Datenelement. Im Gegensatz zu Lisp, werden in Prolog die Listen in eckige Klammern gesetzt. Die leere Liste schreibt man natürlich als [ ]. Die einzelnen Listenelemente werden durch Komma getrennt. Folglich ist [bar, casino] eine Liste mit atomaren Konstanten, die die zu vermeidenden Orte im Labyrinth von Listing 3 enthält. Eine nicht leere Liste hat stets die Form [kopf | rest]. Hierin bedeutet kopf das erste Element der Liste (in LISP: CAR) und rest bedeutet eine Liste (notfalls die leere Liste) mit den restlichen Elementen der Liste (in LISP: CDR). Im eben genannten Beispiel wäre rest also gleich [casino]. In Prolog Notation würde man sagen, köpf ist mit bar instanziert und rest mit [casino]. Auf die leere Liste paßt natürlich nut [], und der Versuch [kopf|rest] mit der leeren Liste zu instanzieren würde mißlingen.

Programmieren in PROLOG

Bevor ich mit der Besprechung des PD Prolog beginne, noch einige Anmerkungen zum generellen Umgang mit Prologprogrammtexten. Jedes Programm besteht aus einer Sammlung von Prädikaten, die sich gegenseitig aufrufen. Im allgemeinen sind in einem Prolog Programm eine große Anzahl von Fakten als Wissensbasis vorhanden. Die anderen Prädikate sind meistens Regeln (Für die Erläuterung von grammatischen Regeln und Direktiven reicht hier der Platz nicht aus). Eines dieser Prädikate übernimmt den Start des Programms und sorgt für den eigentlichen Ablauf. Nehmen wir als Beispiel das einstellige Prädikate vater/1. Nehmen wir ferner an, daß folgende Datenbank vorliegt:

vater(august). vater(otto). vater(eduard).

Also sind august, otto und eduard Väter. Beachten Sie die Kleinschreibung, die august, otto und eduard als atomare Konstanten ausweist. Stellen wir nun die Frage, wer alles als Vater bekannt ist, so müssen wir ja alle Ergebnisse von august bis eduard erhalten. Dies besorgt der in Prolog ständig aktive Backtrackingmechanismus. Das Protokoll der Anfrage sähe dann etwa so aus (eigene Eingaben fett, Antworten des Computers kursiv):

vater(X).

X = august ; % Das Semikolon ist
X = otto ; % vom Benutzer ein-
X = eduard ; % gegeben. Als logi-
no % sches „ODER“ for-
?- % dert es den PROLOG Interpreter
% auf Alternativen zu
% finden. Das no bedeutet: keine weite- % ren Alternativen.

Abb. 3: Boxenmodell eines Prolog Praedikats nach Schnupp.

Das bedeutet, daß der Prolog Interpreter nach Erhalt des Semikolons in die Suchprozedur für das Prädikat vater/1 erneut zurückgeschickt wird, um weitere Einsetzungen für die Variable X zu finden, d. h., daß alle in dem entsprechenden Prädikat vorgenommenen Einsetzungen ungültig werden. Abb. 3 zeigt die aus [8] entnommene Skizze des Boxenmodells eines Prolog Prädikates. Das Prädikat wird aufgerufen und hat die Möglichkeit des Erfolges oder Mißerfolges. Im ersten Fall verläßt der Prolog Interpreter das Prädikate durch den Erfolg Ausgang und ruft ggf. das nächste Prädikat auf. Im zweiten Fall wird der Mißerfolg Ausgang benutzt. Dieser führt (falls vorhanden) zu dem Prädikat zurück, von dem das momentane Prädikat gerufen wurde. Das vorhergehende Prädikat wird dabei durch den Nochmal Eingang betreten, da dieses Prädikat ja offensichtlich schon einmal Erfolg hatte (sonst wären wir nicht im darauffolgenden Prädikat gelandet). Der Nochmal Eingang wird nicht nur bei Mißerfolg des nachfolgenden Prädikates betreten, sondern auch dann wenn (wie im obigen vater/1 Beispiel) durch Eingabe eines vom Benutzer die Suche nach alternativen Lösungen verlangt wird. Deshalb ist der Weg in den Nochmal Eingang in Abb. 3 auch nicht gestrichelt gezeichnet. Abb. 4 zeigt die Lösungssuche des Prolog Interpreters bei der Suche nach Lösungen zu vater(X) im Boxenmodell. Aus Platzgründen verzichte ich hier auf die Erläuterung von Produktionsregeln. Diese sind für den Anfänger nicht ganz einfach zu verstehen. Eine sehr gute Einführung findet sich im Buch von Schnupp [8].

Umgang mit dem PD Prolog

Die ersten Gehversuche sollte man sicherlich direkt im Prolog Interpreter versuchen. Also klickt man TOY.PRG an. Damit startet der innere Interpreter, der nach Angaben des Autors in C und Assembler geschrieben ist. Die Originalversion des TOY-Prolog ist übrigens in Pascal geschrieben und ist bei den Verfassern [9] nachlesbar. Anschließend wird der äußere Interpreter geladen, der im File SYSFILE.TOY vorliegt. Man erkennt das Laden daran, daß jetzt der Schriftzug Booting... und das Logo auf dem Bildschirm erscheinen. Anschließend meldet sich Prolog mit der Meldung TOY - Prolog listening ?-. Das ?- signalisiert Prologs warten auf Befehle. Versucht man nun das einfache vater/1 Prädikat nachzuvollziehen, so muß man zunächst die Datenbasis eingeben. Dies ermöglicht das Prädikat assert/1 oder assertz/1. Beide nehmen das Argument (ein legaler Prolog Term) in die Datenbank auf. assert/1 fügt das Argument an den Anfang der Datenbank hinzu, assertz/1 dagegen an das Ende. Im Anhang der Dokumentation ist übrigens die Tastenbelegung beschrieben, die im SYSFILE.TOY bereits vorgenommen ist. Und so entfällt auch das lästige Tippen von assert (vater(august)). etc. Man drückt die Insert-Taste und schon steht assert( auf dem Bildschirm, bereit zur Aufnahme eines Prolog Termes in die Datenbank (an den Anfang). Die Tastenbelegung finde ich ganz praktisch, aber wer die Tastenbelegung verändern möchte, hat die Möglichkeit das im SYSFILE.TOY mit Hilfe eines Editors zu tun. Nach Eingabe der Datenbank (abschließenden Punkt nicht vergessen!) kann man dann die verschiedenen Lösungen von vater(X). durch Eingabe des anfordern. Man wird schnell feststellen, daß der Umgang mit dem Interpreter nicht gerade bequem ist. Zur Erstellung einer umfangreichen Wissensbasis wird man deshalb schnell zu einem Editor greifen, in dem der Text editiert werden kann. Das Einlesen der Wissensbasis in den Interpreter erfolgt dann mit Elille des consult(Filename). Prädikates. Das Ende des Lesevorganges erkennt Prolog allerdings nicht am EOF-Code des Files. Man muß dem Prädikat con-sult/1 das Ende des Lesevorganges ausdrücklich durch end. bekanntgeben. Dann erst erscheint wieder das Prolog Prompt ?- und Prolog ist zur Beantwortung unserer Anfragen bereit. Die Syntax des PD-Prolog ist nahezu identisch mit der Syntax des DEC-10 Dialektes, dem de facto Standard. Die geringen Abweichungen sind in der Dokumentation festgehalten und betreffen nur wenige Prädikate (z. B. pname). Trotzdem wird der Anfänger beim Nacharbeiten der Literatur oder des nachfolgenden Beispiels feststellen, daß eine Benutzer-Shell angenehm wäre. Natürlich sollte man den Editor, den Prolog Interpreter und die "'.TOY Files in eine RAM-Disk kopieren, wobei die PD-Diskette Nr. 5 mit ihrer RAM-Disk und ihrem COPY Programm hervorragende Dienste leistet.

Der Entwicklungszyklus sieht dann folgendermaßen aus:

  1. Aufruf von ED.TOS (o. ä.). Eingabe des Sourcefilenamens. Eingabe des Programmtextes.
  2. Abspeichern des Programmtextes.
  3. Anklicken des TOY.PRG Files.
  4. Konsultieren des Sourcefiles.
  5. Beenden des Prolog Dialoges mit stop.

Während der Entwanzungsphase wäre es angenehm, sich das lästige Eintippen des Sourcefilenamens und das Konsultieren desselben zu ersparen. Die im LISP Artikel [7] beschriebene Benutzershell MENU + erfüllt den ersten Teil des Wunsches, da aber TOY ein PRG File ist, akzeptiert es keine Argumentzeile, wie die TTP Programme. Ich habe deshalb den äußeren Interpreter in SYSFILE.TOY so geändert, daß beim Starten von TOY. PRG die im File DEFAULT stehende Datei automatisch beim Start von TOY.PRG konsultiert wird. Listing 1 und Listing 2 zeigen die entsprechenden Änderungen im MENU.INF und im SYSFILE.TOY File. Die Hinweise im Listing 1 sind zwar nur für die Besitzer des MENU+ Programms interessant, Listing 2 gibt aber vielleicht den Benutzern anderer Shells ein paar nützliche Hinweise.

Lernen am Beispiel

Ich habe sicherlich von den Realtime-Programmierer eine Menge Geduld verlangt, aber jetzt geht’s los. Listing 3 zeigt den Quellcode eines Prolog Programmes, das auf einer Anregung von [4] beruht. Ein Ehemann soll von der Arbeit in der Firma nach Hause gehen und die neueste Ausgabe von ST-Computer mitbringen. Natürlich sollen die gefährlichen Orte wie Spielcasino oder Bar vermieden werden. Einmal besuchte Orte sollen nicht noch einmal besucht werden. Dabei mache ich von den Grafikroutinen des GEM, die TOY-PROLOG zur Verfügung stellt, Gebrauch. Abb. 5 zeigt ein Bildschirmfoto vom einzigen möglichen Weg. Der Anfänger sollte hier Phantasie entwickeln und beispielsweise einige Fakten in der Datenbasis in anderer Reihenfolge eingeben. Um das Straßennetz zu ändern, brauchen lediglich andere Koordinaten für die Orte eingegeben zu werden. Natürlich läßt sich auch die topologische Struktur des Graphen ändern, indem man die Fakten straße/1 ändert. Allerdings sollte man die Koordinaten von ort (firma,__,_) und ort(wohnung,_,__) nicht ändern, da sonst die Anordnung der Start- und Zielpfeile mit verändert werden müßte. Für eine ausführliche Besprechung des Programms ist hier leider kein Platz.

Natürlich benötigt man in Prolog keine Zeilennummern. Daß die Listings trotzdem damit versehen wurden dient lediglich zur besseren Orientierung beim Abtippen und soll helfen Fehler zu vermeiden.

Eigenschaften des PD Prolog

Das TOY Prolog ist eine recht vollständige Implementation des DEC-10 Dialektes. Der größte Teil der Implementation ist dabei im äußeren Interpreter untergebracht, so daß die Geschwindigkeit nicht berauschend ist. Die rekursive Quicksort Routine (Listing 4) benötigte für das Sortieren einer Integer Liste mit 100 Elementen 12 s und liegt damit im Bereich des XLISP Interpreters (siehe [7]) aus der PD. Viel störender ist dagegen die Beschränkung auf Integer Arithmetik. Natürlich ist PROLOG (wie LISP) keine Sprache die vornehmlich für arithmetische Datenverarbeitung gedacht ist. Das schreiben auch Clocksin und Mellish [1] in ihrem Standardwerk. Dennoch ist eine Gleitkommaarithmetik aus einer Sprache nicht wegzudenken. So soll die angekündigte neue Version von MPROLOG für den ST u. a. auch einfach genaue Gleitkommaarithmetik (letzte Information: auch doppelt genaue Darstellung) erlauben. Das System besitzt einen Debug-modus und einzelne Prädikate lassen sich mit dem Prädikat spy/1 auch in ihrer Wirkung ganz gut beobachten, da aber TOY-Prolog alle Variablen in interner Schreibweise ausgibt, habe ich es als übersichtlicher empfunden auf die Benutzung des Debuggers zu verzichten und bei Bedarf im Programm eigene Fehlermeldungen unterzubringen. Das ist besonders Anfängern zu empfehlen, die den Weg eines Prolog Programmes nachvollziehen wollen. Ansonsten aber hat man ein komplettes Prolog System vor sich, mit dem sich unter Benutzung eines eigenen Editors und einer eigenen Shell und der RAM-Disk und dem COPY Programm aus der PD recht komfortabel arbeiten läßt, wenn man die in Listing 2 angegebenen Änderungen am SYSFILE.TOY durchführt. Sonst ist die Bedienung umständlich, aber dem Erlernen von PROLOG steht nichts im Wege außer einem guten Lehrbuch.

Literatur

Im Literaturverzeichnis sind einige Lehrbücher über Prolog aufgeführt. Dem Prolog Neuling, der zudem Wert auf eine praxisbezogene Einführung Wert legt, sei das 1986 erschienene Buch von Schnupp [8] empfohlen. Der Autor erläutert an Hand praxisorientierter Beispiele die Vorteile von Prolog. Theoretische Erörterungen bleiben auf ein absolutes Minimum reduziert. Dies ist wohl das am leichtesten verständliche deutschsprachige Buch über Prolog. Sehr positiv ist der übersichtliche Anhang zu werten, in dem die Syntax der DEC-10 Prolog Prädikate definiert und an Beispielen erläutert wird. Der Prolog Neuling hat hier eine übersichtliche Informationsquelle, die erheblich mehr Informationswert besitzt als die sehr axio-matische BXF aus der Dokumentation in der PD.

Wer sich in Prolog schon etwas eingearbeitet hat, dem sei das Buch von Giannesini [5] empfohlen. Man sollte sich allerdings vom Eingangsthema des Buches (der Speisekarte eines Restaurants) nicht täuschen lassen. Danach kommt es ziemlich dick theoretisch. Und das auch noch in der Syntax von PROLOG II, dem Dialekt, welcher der Nachfolger des Ur-Prolog der GIA (Groupe d’Intelligence Artificielle) Unitersität von Aix-Marseille [3] ist. Dem an der Logik interessierten Programmierer hat dieses Buch natürlich mehr zu bieten, zumal es die wesentlichen Begriffe aus der Logik (sofern sie benötigt werden) zu Beginn des jeweiligen Kapitel definiert. Beide deutschsprachigen Bücher enthalten im Anhang noch einen Hinweis auf die jeweils anderen Prolog Dialekte DEC-10 bzw. Prolog II und micro-Prolog.

Schon aus historischen Gründen sollte man auf die Lektüre des Klassikers von Clocksin und Mellish nicht verzichten [1], Dieses Buch hat immerhin auch den in TOY-Prolog verwendeten DEC-10 Dialekt definiert.

Schließlich möchte ich noch auf das Buch von Kluzniak [9] hinweisen, auf dem die vorliegende ST Version beruht und welches ein komplettes Source Listing (in Pascal) für den inneren Interpreter enthält. Hier findet man eine sehr ausführliche Anatomie des vorliegenden Prolog Interpreters, die in Bezug auf Sorgfalt und Vollständigkeit keinen Wunsch mehr offenläßt.

Ein ganz besonderer Leckerbissen ist das Buch von Coelho [2]. Hier findet man ein breites Spektrum von Prolog Programmen aus allen möglichen Interessengebieten zusammengetragen. Leider ist es nicht ganz einfach zu erhalten.

Fazit

Wie ich bereits früher erwähnt habe [6], ist Prolog eine der Computersprachen, die für das FCGS-Projekt gewählt wurden. Einer der Gründe ist die eingangs erwähnte referentielle Transparenz von Prolog. Diese Eigenschaft ist die Grundvoraussetzung für den Einsatz von paralleler Datenverarbeitung, damit sichergestellt ist, daß sich der Wert einer Variablen im Prozeß 1 nicht ändert, während sich parallel dazu Prozessor 2 im Prozeß 2 mit der gleichen Variablen beschäftigt. Und da die Entscheidungsbäume im Bereich der künstlichen Intelligenz rasch in den Himmel wachsen, ist neben der Einführung von Heuristiken (auf Erfahrung beruhenden Verfahren) die Entwicklung von Multiprozessorsystemen mit Parallelverarbeitung eine absolute Notwendigkeit und im FCGS-Projekt vorgesehen. Es ist daher wohl nicht zu umgehen sich mit Prolog zu beschäftigen, will man nicht den Anschluß an die kommende Entwicklung verlieren. Zudem macht diese Prolog Implementation durch die Einbindung der GEM-Routinen außerordentlich viel Spaß. Bleibt zum Schluß nur die definitive Festlegung des Leserprädikates clever/1:

clever(Leser) .- liest(Leser,st),
programmiert_in(Leser,prolog).

Mit anderen Worten: unverzüglich eine Diskette formatieren und zusammen mit DM 5,- plus Spesen an die ST-Redaktion schicken und die PD Diskette Nr. 11 verlangen. Besonders erfreulich ist natürlich auch die Ankündigung zweier kommerzieller Prolog Interpreter (MPROLOG und das PROLOG des Heim-Verlages), auf die man jetzt schon gespannt sein darf.

Literaturangabe:

[1] Clocksin, W. F., C. S. Mellish. Programming in Prolog. Springer Verlag, Berlin 1984.

[2] Coelho, H., J. C. Cotta und L. M. Pereira. How to solve it with Prolog. Laboratorio Nacional de En-genharia Civil, Lissabon 1982.

[3] Colmerauer, A., H. Kanoui, P. Roussel und R. Pasero. Un Systeme de communication homme-machine en franfais. Groupe d’In-telligence Artificielle, Universite d’Aix-Marseille. 1972.

[4] Cuadrado, Clara Y. und John L. Cuadrado. Prolog goes to work. BYTE August 1985, Vol. 10, No. 8. p. 151

[5] Giannesini, F., H. Kanoui, R. Pasero und M. van Ceneghem. PROLOG. Addison Wesley Verlag (Deutschland), 1986.

[6] Sarnow, K. Künstliche Intelligenz - Einführung. ST-Computer 11/86 p. 40.

[7] Sarnow, K. XLISP - Report. ST-Computer 1/87

[8] Schnupp, P. PROLOG Einführung in die Programmierpraxis. Carl Hanser Verlag, München 1986.

[9] Kluzniak, F. und Szpakowicz. Prolog for Programmers. Acade-mic Press, London 1985.

####################################
#                                  #
# Standard C MENU+ info file       #
#                                  #
# Copyright (c) 1986 Metacomco plc #
#                                  #
####################################
#
# Tools menu item definitions
#
# Form: <item name> = <command line definition>
#


TOOLS

EDIT	= {command_dir}\ED.TTP {path}\{file}.{type} (editor_opts)
PROLOG	= {command_dir}\TOY.PRG

#
# File menu item definitions t
#
# Form: <item name> = <file pattern>
#

FILE

Choose     = *.*
Choose PRO = *.PRG

#
# Option menu item definitions
#
# Form: (Option name> = (initial value)
#

OPTIONS

CURRENT_DIR	= C:
PATH		= C:
COMMAND_DIR	= C:
EDITOR_OPTS =
COMPILER_OPTS =

'ear' :
	'see'('start').
	' nl' .
	'display'('TOY Prolog listening:') .
	'nl' .
	'tag' ('loop') . []

Listing 2a: Änderungen im File SYSFILE.TOY.

see('c:default'),read(Datei),consult(Datei),seen.

Listing 2b: Inhalt des Files START, der von TOY-Polog während es bootens gelesen wird.

Abb.5: Problem des heinkehrenden Ehemannes(-frau?)

%Problem des heimkehrenden Ehegatten

%Fakten über die Orte

ort(wohnung, 440, 230). 
ort(oper, 400,100). 
ort(casino, 360, 210). 
ort(parkplatz, 300, 80). 
ort(fontäne, 300, 140). 
ort(bahnhof, 250, 230). 
ort(bar, 170, 180). 
ort(kiosk, 260, 290). 
ort(firma, 200, 130).

%----------------------------------------------------------------

%Fakten über die Straßen.

straße(firma,bar).	straße(bahnhof,kiosk).
straße(firma,fontäne).	straße(casino,kiosk).
straße(bar,kiosk).	straße(casino,wohnung).
straße(fontäne,bahnhof).	straße(oper,wohnung).
Straße(fontäne,casino).	straße(kiosk,wohnung).
straße(fontäne.oper) .
straße(fontäne,parkplatz).

%----------------------------------------------------------------

vermeide([bar,casino]). %Ist besser!

%----------------------------------------------------------------

gehe(Hier,Da)
	vermeide(Gefahren), 
	pfad(Hier,Da,Gefahren,[Hier]).

%----------------------------------------------------------------

pfad(Hier,Da,Gefahren,Spur)
	Hier == Da,
	member(kiosk,Spur),
	bell,
	write('Möglicher Weg:'), nl, 
	reverse_write(Spur), 
	rch, !, 
	fail.
pfad(Hier,Da,Gefahren,Spur) :-
	(
		straße(Hier,Zwischen)
	:
		straße(Zwischen,Hier)
	),
	not member(Zwischen,Gefahren), 
	not member(Zwischen,Spur), 
	lösche([Zwischen|Spur]), 
	zustand([Zwischen|Spur]),
	( modus(einzelschritt), rch; not modus(einzelschritt) ), 
	pfad(Zwischen,Da,Gefahren,[Zwischen!Spur]).

%----------------------------------------------------------------

%Markiert die besuchten Orte im derzeitigen Suchzustand

zustand([]). 
zustand([Kopf|Rest]) :-
	zustand(Rest), 
	ort(Kopf,X,Y), 
	grf_f_type(1),
	kreis(X,Y), sum(X1,18,X), grf_text(X1,Y,Kopf).

%----------------------------------------------------------------

%Löscht die nicht besuchten Orte

lösche(Spur) :-
	ort(Name,X,Y),
	not member(Name,Spur),
	grf_f_type(2),
	kreis(X,Y), sum(X1,18,X), grf_text(X1,Y,Name), 
	fail. 
lösche(_).

%----------------------------------------------------------------

%Ausgabe einer Liste in umgekehrter Richtung

reverse_write([]). 
reverse_write([Kopf|Rest]) 
	reverse_write(Rest), 
	write(Kopf), nl.

%----------------------------------------------------------------

%Aufruf dieses Prädikates startet das Programm!

start(Modus) assert(modus(Modus)), Start.

start :- cls, grf_mode, grf_f_type(2), grf_f_style(1), logo,
		grf_t_height(4), verbindung, karte, gehe(firma,wohnung).

%----------------------------------------------------------------

logo grf_t_height(20), grf_text(250,20,'Straßenplan').

%----------------------------------------------------------------

%Dieses Prädikat zeichnet einen Kreis mit dem Radius 20

kreis(X, Y) :- grf_circle(X, Y, 20).

%----------------------------------------------------------------

%Dieses Prädikat zeichnet den Stadtplan

karte :- ort(Name, X, Y) , kreis(X, Y) , sum(X1,18,X), 
			grf_text(X1,Y,Name), fail.
karte.

%----------------------------------------------------------------

% Zeichnet die Straßenverbindungen Verbindung

grf_l_width(7), grf_l_ends(0,1), grf_pline([150,70,190,115]), 
grf_pline([440,230,500,300]), grf_l_ends (0,0), 
straße(Von,Nach), ort(Von,X1,Y1), ort(Nach,X2,Y2), 
	grf_pline([X1,Y1,X2,Y2]), fail.
verbindung.

%----------------------------------------------------------------

:- cls, write('Starten des Programms mit "Start."'), nl,
	write('Nachdem ein Weg gefunden ist, meldet sich die Glocke.'), nl,
	write('Wollen Sie im Einzelschrittverfahren die Lösungssuche verfolgen,'), nl
	write('dann geben Sie "Start (einzelschritt)." ein.'), nl,
	write('Sie müssen dann vor jedem Schritt die "RETURN" Taste drücken.'), nl.
end.

Künstliche Intelligenz

Kleines Prolog Lexikon

Adjunktion - Verknüpfung zweier logischer Terme durch ODER. Der zugehörige Junktor wird in PROLOG durch das Semikolon ausgedrückt. Beispiel: mensch(X) männlich(X);weiblich(X). Ein Mensch ist entweder männlichen oder weiblichen Geschlechtes.

Applikative Sprache - Sprache, in welcher der Algorithmus in den Hintergrund tritt zugunsten der logischen Struktur des Problems. Oftmals auch als loser Oberbegriff für alle deklarativen Sprachen.

Argument - Die Parameter eines Funktors. 2. B. a,b,c in f(a,b,c).

Arität - Anzahl der Argumente eines Funktors. f(a,b,c) hat also die Arität 3.

Atom - Ein konstantes Datensymbol. Muß mit einem Kleinbuchstaben beginnen.

Deklarative Sprachen - Als Gegensatz zu imperativen Sprachen zu verstehen. Man unterscheidet relationale und funktionale Sprachen.

Direktive - Direkt auszuführendes Goal. Beginnt mit :-

Fakt - Klausel, die nur aus Funktor und Argument besteht. Ein Fakt drückt aus, das der durch Funktor und Argument vorgestellte Zusammenhang wahr ist.

Funktionale Sprachen - Sprachen, bei denen das Ergebnis sich aus der Folge von Funktionen und ihren Argumenten ergibt. Jede Kombination von ARgumenten hat ein eindeutiges Funktionsergebnis.

Funktor - Der Name einer Regel oder eines Faktes. Im Fakt vater(egon) ist vater der Funktor.

Goal - Ziel, die Anfrage, die Prolog veranlaßt, die Datenbasis zu durchforsten.

Imperative Sprachen - Die „klassischen“ Sprachen mit dem Schwergewicht auf dem Algorithmusbegriff. Neben der Strukturanalyse für das zu lösende Problem muß sich der Programmierer noch mit dem Weg beschäftigen, wie der Computer die Lösung erarbeiten soll. Jeder einzelne Schritt auf dem Lösungsweg muß dem Computer befohlen werden.

Instanzierung - Bindung einer Variablen an einen Wert (Atom, Liste, Struktur). Nach erfolgter Bindung ist die Variable bis zum Verlassen des Prädikates in dem die Bindung erfolgte nicht mehr rückgängig zu machen. Versucht der Prolog Interpreter per Backtracking neue Instanzierungen vorzunehmen, verläßt er deshalb erst das Prädikat um es durch den Nochmal Eingang erneut zu betreten. Danach steht einer erneuten Instanzierung nichts mehr im Wege.

Junktor - Zeichen, welches eine logische Verknüpfung | repräsentiert. In PROLOG sind die Junktoren von Negation, Adjunktion und Konjunktion repräsentiert als not , und ;.

Konjunktion - Verknüpfung logischer Terme durch UND. In PROLOG wird der Junktor als Komma repräsentiert. Beispiel:see(’datei’),read(X),seen. Eine Direktive zum Lesen der Variable X: Öffne die Datei ’datei’ und lies X und schließe die Datei wieder.

Nebeneffekte - Anweisungen die irgendetwas am Zustand eines Programmes verändern (ohne Neues hinzufügen) haben Nebeneffekte. Beispielsweise ist C eine sehr nebeneffektreiche Sprache. Die Anweisung + +X + = Y — enthält gleich drei Nebeneffekte. Erst wird X inkrementiert, anschließend Y hinzuaddiert und dann wird Y noch inkrementiert, anschließend Y hinzuaddiert und dann wird Y noch inkrementiert. Auch Prolog enthält Anweisungen mit Nebeneffekten. Beispielsweise bewirkt das Prädikat write/1 neben dem Erfolg oder Mißerfolg als Nebeneffekt das Erscheinen des Argumentes auf dem Bildschirm (oder in der Datei).

Referentielle Transparenz - Programmiersprachen mit r. T. verhindern, daß eine Variable im Laufe eines Programms verschiedene Werte annimmt. So ist in Prolog eine Variable entweder nicht instanziert oder sie ist instanziert. Im ersten Fall ist die Bindung eines Wertes (oder Struktur) an die Variable möglich. Ist die Variable erst einmal instanziert, ist eine weitere Instanzierung nicht mehr möglich. Da die Instanzierung der Variablen vom Prolog Interpreter vorgenommen wird, ist kein Mißbrauch möglich.

Regel - Klausel, bestehend aus Regelkopf von der Form eines Faktes gefolgt von :- und dem Regelrumpf. Der Regelrumpf besteht aus logischen Verknüpfungen von Fakten und Regeln.

Relationale Sprachen - Prolog ist ein Vertreter dieser Gattung. Die Ausgabe wird in Eigenschaften und Argumenten definiert. Im Gegensatz zu den funktionalen Sprachen sind damit mehrere Ergebnisse pro Prädikat/Argument Paar möglich.

Unifikation - Allgemeiner Mustervergleich. Im Laufe der Unikfikation von Prolog Termen nimmt der Interpreter die Instanzierung von noch nicht instanzierten Variablen vor, um zu einem Erfolg zu kommen. Gelingt es dem Interpreter nicht, die Muster der beiden zu unifizierenden Prologterme in Übereinstimmung zu bringen, meldet der Interpreter einen Mißerfolg. Ist der Lösungsbaum noch nicht abgearbeitet, wird mit Hilfe eines Backtracking Algorithmus nach weiteren Lösungen im Lösungsbaum gesucht. Dabei werden alle Instanzierungen von Variablen die in diesem Unifikationsversuch vorgenommen wurden zurückgenommen. Die entsprechenden Variablen werden im erneuten Unifikationsversuch neu instanziert. Die referentielle Transparenz bleibt also erhalten.

Variable - Ein Objekt, daß mittels Instanzierung an einen Wert gebunden werden kann. Ein Variablenname beginnt immer mit einem Großbuchstaben.


Aus: ST-Computer 02 / 1987, Seite 35
Links
Copyright-Bestimmungen: siehe Über diese Seite