Peter Bothner und Wolf-Michael Kihler Programmieren in PROLOG ___ Programmierung ____________- --..... EinftIhnmg in die Progruuniersprache Pascal von G. Lamprecht EinftIhnmg in die Programmiersprache Modula-2 von H. Pudlatz ParaUele Programmierung mit Modula-2 von E. A. Heinz Ada vonM.Nagl Programmieren in PL/I vonE.Sturm Programmieren in PROLOG von P. Bothner und W.-M. Kahler Einflihrung in die Programmiersprache APL von P. Bothner und W.-M. Kahler Einfiihrung in die Programmiersprache COBOL von W.-M. Kahler Einfiihrung in die Methode des Jackson Structured Programming (JSP) von K. Kilberth PEARL, Process and Experiment Automation Realtime Language von W. Werum und H. Wmdauer Eint1ihnmg in die Programmiersprache SIMULA von G. Lamprecht LISP - FaUstudien mit Anwendungen in der KtlnstIichen Intelligenz von R. Esser und E. Feldmar ____ \r.eweg ________________________________ Peter Bothner und Wolf-Michael Kahler Programmieren in PROLOG Eine umfassende und praxisgerechte Einfdhrung Das in diesem Buch enthaltene Programm-Material ist mit keiner Verpflichtung oder Garantie irgend einer Art verbunden. Die Autoren und der Verlag iibemehmen infolgedessen keine Verantwortung und werden keine daraus folgende oder sonstige Haftung iibernehmen, die auf irgendeine Art aus der Benutzung dieses Programm-Materials oder Teilen davon entsteht. Der Verlag Vieweg ist ein Unternehmen der Verlagsgruppe Bertelsmann International. AIle Rechte vorbehalten © Friedr. Vieweg & Sohn Verlagsgesellschaft mbH, Braunschweig 1991 Das Werk einschlieBlich a1ler seinerTeile ist urheberrechtlich geschiitzt. Jede Verwertung auBerhalb der engen Grenzen des Urheberrechtsgesetzes ist ohne Zustimmung des Verlags unzuliissig und stratbar. Das gilt insbesondere fur VervieIfliltigungen, Ubersetzungen, Mikroverfilmungen und die Einspei cherung und Verarbeitung in elektronischen Systemen. Umschlaggestaltung: Schrimpf und Partner, Wiesbaden ISBN-13: 978-3-528-05158-7 e-ISBN-13: 978-3-322-87223-4 DOl: 10.1007/978-3-322-87223-4 Vorwori In der traditionellen Datenverarbeitung werden klassische Programmierspra chen wie z.B. FORTRAN, COBOL und PASCAL eingesetzt, um LOsungen von Problemstellungen zu beschreiben. Bei den LOsungsplinen mu6 an gegeben werden, welche LOsungsschritte jeweils im einzelnen auszufiihren sind. Dieses Vorgehen kennzeichnet die prozedurale LOsungsbeschreibung. Deshalb werden die klassischen Programmiersprachen FORTRAN, COBOL und PASCAL prozedurale Sprachen genannt. Seit Beginn der siebziger Jahre wurden Programmiersprachen (der 5. Ge neration) entwickelt, mit denen sich Informationen bearbeiten lassen, die in einem logischen Zusammenhang zueinander stehen. Die zwischen Infor mationen bestehenden "logischen" Abhingigkeiten werden durch geeignete Regeln beschrieben, die auf den Prinzipien des "logischen Schlie6ens" beru hen. Deshalb werden diese (nicht-prozeduralen) Programmiersprachen logik basierte Sprachen genannt, und die Entwicklung einer LOsungsbeschreibung wird als "logik-basierte Programmierung" bezeichnet. Als bedeutsamer Anwendungsbereich von logik-basierten Sprachen ist die Entwicklung von wissensbasierten Systemen wie z.B. Expertensystemen zu nennen. Diese Systeme sollen das Wissenund die Erfahrungen von Experten auf ihren Wissensgebieten so zuganglich machen, daB Informationen in ein facher Weise abgefragt werden konnen. Dazu verfiigen diese Systeme iiber eine Wissensbank, in der die Kenntnisse iiber bestimmte Sachverhalte als abrufbare Informationen in geeigneter Form gespeichert sind. Bei der Entwicklung von wissensbasierten Systemen hat die logik-basierte Programmiersprache PROLOG (PROgramming in LOGic) eine zentrale Be deutung erlangt. Diese zu Beginn der siebziger Jahre von Alain Colmerauer an der Universitat von Marseilles entwickelte Sprache ist Gegenstand die ser Einfiihrungsschrift. Wir geben eine anwendungs-orientierte Darstellung und erlautem die Sprachelemente von PROLOG an einem durchgangigen Beispiel. 1m Kapitell stellen wir einfiihrend dar, aus welchen Komponenten ein wis sensbasiertes System aufgebaut ist. Anschlie6end beschreiben wir im Kapi tel 2, wie sich eine Wissensbasis - im Hinblick auf einen im Rahmen einer Aufgabenstellung vorliegenden Sachverhalt - als PROLOG-Programm for mulieren la.6t. Dieses PROLOG-Programm mu6 dem PROLOG-System als Wissensbasis bereitgestellt werden, damit dieses wissensbasierte System An fragen im Hinblick auf die vorgegebene Aufgabenstellung bearbeiten kann. Zur Uberpriifung, ob sich die innerhalb einer Anfrage enthaltene(n) Aus- vi sage(n) aus der Wissensbasis ableiten lassen, setzt das PROLOG-System einen Inferenz-Algorithmus ein. Die Kenntnis liber dessen Arbeitsweise ist von grundlegender Bedeutung fUr die logik-basierte Programmierung mit PROLOG. Deswegen erliutern wir die einzelnen Schritte dieses Algorith mus in aller Ausfiihrlichkeit. Dabei lemen wir die Begiffe "Instanzierung", "Unifizierung" und "Backtracking" kennen, die von zentraler Bedeutung fiir das Verstindnis des Inferenz-Algorithmus sind. 1m Kapitel 3 wird beschrieben, wie rekursive Regeln vereinbart und bei der Ableitungs-Priifung bearbeitet werden. Hieran schlie8t sich die Diskus sion der Probleme an, die beim Einsatz rekursiver Regeln auftreten konnen: mogliche Programmzyklen und Anderungen der deklarativen bzw. prozedu ralen Bedeutung eines PROLOG-Programms. Um Dialog-, Erklarungs- und Wissenserwerbskomponenten programmieren zu konnen, steilt PROLOG eine Vielzahl von Standard-Pradikaten zur Verfiigung. 1m Kapitel 4 werden ausgewihlte Pradikate zur Bearbeitung und zur Sicherung der Wissensbasis vorgestellt. 1m Kapitel 5 beschreiben wir, wie das Backtracking durch die Pradikate "fail" und "cut" beeinfluBt werden kann, so daB sich einerseits mehrere LOsungen ableiten lassen und andererseits ein mogliches Backtracking ge- zielt unterbunden werden kann. . Die Beschreibung wie sich Werte direkt bzw. erst nach einer Zwischenspei cherung in der Wissensbasis verarbeiten lassen, ist Gegenstand von Kapi tel 6. Es folgt die Darstellung der Operatoren, die in einem PROLOG Programm eingesetzt werden konnen. Daran anschlieBend geben wir an, wie Operatoren ausgewertet werden und wie sich neue Operatoren vereinbaren lassen. 1m Kapitel1 erlautem wir, wie Werte in Form von Listen zusammengefaBt werden konnen. Da das Verstindnis der Listen-Verarbeitung erfahrungsge mi.8 zu den schwierigsten Problemen bei der PROLOG-Programmierung zihlt, wird in aller Ausfiihrlichkeit gezeigt, wie sich Listen aufbauen und bearbeiten lassen. AuBer in Listen konnen Werte in Form von Strukturen zusammenfaBt wer den. 1m Kapitel 8 wird der Umgang mit Strukturen erliutert, und es wird beschrieben, in welchem Verhiltnis die Sprachelemente "Pradikat", "Liste" und "Struktur" zueinander stehen. Die Ausfiihrung von PROLOG-Programmen erlautem wir fUr das PROLOG System "IF/Prolog" der Firma InterFace GmbH. Dieses System stellt den Industrie-Standard dar und ist 8Owohl unter MS-DOS als auch unter UNIX einsetzbar. Um auch der Tatsache Rechnung zu tragen, daB das PDC-Prolog der Firma Prolog Development Center - ehemals als "Turbo Prolog" von vii der Firma Borland International vertrieben - unter MS-DOS und OS/2 weit verbreitet ist, haben wir immer dort, wo Abweichungen zwischen beiden Sy stemen vorliegen, erginzende Hinweise gegeben. Dariiberhinaus haben wir aIle Beispielprogramme, die wir zunichst in einer unter "IF/Prolog" unmit telbar ausfuhrbaren Form vorstellen, im Anhang in der unter PDC-Prolog ausfiihrbaren Form zusa.mmengestellt. Um den spontanen Einsatz dieser beiden Systeme zu erleichtern, sind im Anhang geeignete Hinweise angege ben. Insbesondere erschien es uns wichtig, die Mogllchkeiten der Trace- und Debug-Module zur Uberpriifung der Ableitbarkeits-Priifungen zu erllutern. Die Darstellung ist so gehalten, daB zum Verstlndnis keine Vorkenntnisse aus dem Bereich der elektronischen Datenverarbeitung vorhanden sein miissen. Das Buch eignet sich zum Selbststudium und als Begleitlektiire fiir Veran staltungen, in denen eine Einfuhrung in die Programmiersprache PROLOG gegeben wird. Zur Lernkontrolle sind Aufgaben gestellt, deren Losungen im Anhang in einem gesonderten Losungsteil angegeben sind. Das diesem Buch zugrundeliegende Manuskript wurde in Lehrveranstaltun gen eingesetzt, die am Rechenzentrum der Universitlt Bremen durchgefiihrt wurden. Wir danken Herm Dr. R. Weibezahn fUr seine Hinweise im Zusammenhang mit der ~TEX-Formatierung des Manuskripts. Dem Vieweg Verlag mOchten wir fur die gewohnt gute Zusammenarbeit und der Firma InterFace GmbH fiir ihre freundliche Unterstiitzung danken. Bremen/Ritterhude Peter P. Bothner und Wolf-Michael Klhler im November 1990 Inhaltsverzeichnis 1 Arbeitsweise eines wissensbasierien Systems 1 1.1 Aussagen und Pridikate . . . . . . ..... 1 1.2 Wissensbasis und Regeln ......... . 3 1.3 Anfragen an die Wissensbasis . . . . . . . 7 1.4 Struktur von wissensbasierten Systemen 10 2 Arbeiten mit dem PROLOG-System 12 2.1 Programme als Wiba des PROLOG-Systems 12 2.2 Fakten ........................ . 13 2.3 Start des PROLOG-Systems und Laden der Wiba 16 2.4 Anfragen ....................... . 18 2.5 Regeln ......................... . 20 2.6 Die Arbeitsweise der PROLOG-Inferenzkomponente 24 2.6.1 Instanzierung und Unifizierung ....... . 24 2.6.2 Das Backtracking. . . . . . . . . . . . . . . . 30 2.7 Beschreibung der Ableitbarkeits-Priifung durch Ableitungs- biume ................... . 32 2.8 Ableitbarkeits-Priifung bei zwei Regeln .. 36 2.9 Aufgaben . . . . . . . . . . . . . . . . . . 42 3 Rekursive Regeln 45 3.1 Vereinbarung und Bearbeitung von rekursiven Regeln 45 3.2 Anderungen der Reihenfolge . . . . . . . . . . . . . . . . . 53 3.3 Programmzyklen 57 3.4 Aufgaben . . . . 61 4 Standard-Pridikate 62 4.1 Standard-Pridikate und Dialogkomponente 62 4.2 Standard-Pridikate und Erkli.rungskomponente ... 68 4.3 Standard-Pridikate und Wissenserwerbskomponente 74 4.4 Aufgaben . . . . . . . . . . . . . . . . . . . . . . . . 83 INHALTSVERZEICHNIS ix 5 EinfluBnahme auf das Backtracking 84 5.1 Erschopfendes Backtracking mit dem Pradikat "fail" 84 5.2 Erschopfendes Backtracking durch ein externes Goal 89 5.3 Einsatz des Pradikats "cut" . . . . . . . . . . . . . . 91 5.3.1 Unterbinden des Backtrackings mit dem Pradikat "cut" 91 5.3.2 Unterbinden des Backtrackings mit den Pradikaten "cut" und "fail" ("Cut-fail"-Kombination) . 97 5.3.3 Rote und griine Cuts . 99 5.4 Aufgaben . . . . . . . . . . . 104 6 Sicherung und Verarbeitung von Werten 110 6.1 Sicherung und Zugriff auf Werte 110 6.2 Verarbeitung von Werten .... 124 6.2.1 Verarbeitung nach Zwischenspeicherung 124 6.2.2 Unmittelbare Verarbeitung 130 6.3 Operatoren ... . . . . . . . . . . 133 6.3.1 Zuweisungs-Operatoren "is" und "=" 134 6.3.2 Arithmetische Operatoren und mathematische Funk- tionen . . . . . . . . . . . . . . . . . . . . . . . . .. 135 6.3.3 Operatoren zum Vergleich arithmetischer Ausdriicke 138 6.3.4 Operatoren zum Vergleich von Ausdriicken 139 6.3.5 Operatoren zum Test auf Uni:fizierbarkeit . 140 6.3.6 Auswertung und Vereinbarung von Operatoren i41 6.4 Aufgaben .... . . . . . . . . . . . . . . . . . . . . . 149 x INHALTSVERZEICHNIS 1 Verarbeitung von Listen 153 7.1 Listen als geordnete Zusammenfassung von Werten . 153 7.2 Unifizierung von Komponenten einer Liste . . . . . . 156 7.3 Ausgabe von Listenelementen . . . . . . . . . . . . . 158 7.4 Aufbau von Listen . . . . . . . . . . . . . . . . . . . 162 7.5 Anwendung des Prinzips zum Aufbau von Listen . . 168 7.6 Pridikate zur Verarbeitung von Listen . . . . . 172 7.6.1 Anfiigen von Listen ..... 173 7.6.2 Invertierung von Listen ... 177 7.7 Uberpriifung von Listenelementen. . 183 7.8 Vermeiden von Programmzyklen ..... 184 7.9 Reduktion von Listen .............. 188 7.10 Anfragen nach richtungslosen IC-Verbindungen 191 7.11 Anfragen nach der kiirzesten IC-Verbindung . . 194 7.12 Flie6muster . . . . . . . . . . . . . . . . . . . . 204 7.13 LOsung eines krypto-arithmetischen Problems. 211 7.14 Aufgaben .... . . . . . . . . . . . . . . . . . . . . 218 8 Verarbeitung von Strukturen 220 8.1 Strukturen als geordnete Zusammenfassung von Werten 220 8.2 Unifizierung von Strukturen . . . . . . . . . . . . . 221 8.3 Bestimmung der zeitlich kiirzesten IC-Verbindung . 225 8.4 Listen, Strukturen und Pridikate . . . . . 241 8.4.1 Der Univ-Operator "= .. " ..... 241 8.4.2 Das Standard-Pridikat "call" . . . 244 8.4.3 Das Standard-Pridikat "find all" . 246 8.5 LOsung einer klassischen Problemstellung 247 8.6 Aufgaben . . . . . . . . . . . . . . . 257 Anhang 261 A.1 Arbeiten unter dem System "Turbo Prolog" 261 A.2 Testhilfen . . . . . . . . . . . 264 A.3 Das System "Turbo Prolog" 282 A.4 "Turbo Prolog"-Programme 290