Die Entwickler von Expertensystemen und entsprechenden Software-Tools greifen zunehmend auf die Sprache "Prolog" zurück. Bislang stand das bereits 30 Jahre alte "Lisp" in der Gunst der. Programmierschmieden ganz oben. Gerhard Barth* vergleicht vier verschiedene Sprachkonzepte vor allem hinsichtlich ihrer Eignung für die Implementierung wissensbasierter Systeme (Teil 2).

Der Programmiersprache "Prolog" liegt das Modell der wissensorientierten Programmierung zugrunde. Der Entwickler sieht sich mit den beiden Aufgaben konfrontiert, eine Wissensbasis aufzubauen und Probleme als Anfragen an diese Wissensbasis zu formulieren. Ganz entscheidend ist, daß der Entwickler nicht verantwortlich für die Abwicklung seiner Anfragen ist. Diese übernimmt ein fest eingebauter Interpretationsmechanismus, der von dem in der Wissenbasis codierten Problembereich unabhängig ist.

Prolog" kommt der Vorstellung, die man im allgemeinen mit dem Begriff "nichtprozedurale Programmierung" verbindet, näher als alle anderen in diesem Beitrag skizzierten Sprachen. Der Programmierer ist in erster Linie damit befaßt, Wissen über einen bestimmten Problembereich zu formulieren. Er ist weitestgehend davon befreit, die Herleitung neuen Wissens operational beschreiben zu müssen.

Der Name "Prolog" steht für PRO-gramming in LOGic. Dahinter verbirgt sich die Tatsache, daß sowohl der Inhalt der Wissensbasis als auch die daran gerichteten Anfragen als logische Formeln zu erfassen sind. Grundbausteine sind die sogenannten Horn-Klauseln, die eine für die Zwecke der Programmierung geeignete Variante der Prädikatenlogik (erster Stufe) bilden. Sie sind in der Lage, einfache und strukturierte Objekte sowie Aussagen über solche Objekte zu beschreiben. Für die Erstellung einer "Prolog"-Wissensbasis können unbedingt richtige Aussagen ("Fakten, Tatsachen") und bedingt richtige Aussagen ("Regeln") verwandt werden.

Um beispielsweise das Autobahnnetz (in vereinfachter Weise) als "Prolog"-Wissensbasis zu erfassen, könnten Tatsachen wie:

autobahn_stück (stuttgart, ulm).

autobahn_stück (ulm, augsburg).

autobahn_stück (augsburg, münchen). etc. verwandt werden. Sie enthalten Wissen darüber, daß es zwischen Stuttgart und Ulm, zwischen Ulm und Augsburg sowie zwischen Augsburg und München Autobahnabschnitte gibt.

Durch die Hinzunahme von Regeln wie:

autobahn (START, ZIEL) :-autobahn_stück (START, ZIEL).

autobahn (START, ZIEL) :-autobahn_stück (START, ORT), autobahn (ORT, ZIEL).

wird zum Ausdruck gebracht, daß es eine Autobahnverbindung zwischen einem Start- und einem Zielpunkt gibt - falls entweder ein die beiden Punkte direkt verbindendes Autobahnstück oder eine direkte Verbindung vom Startpunkt zu irgendeinem Ort existiert, von dem aus der Zielpunkt auf einer Autobahn erreichbar ist.

Auf die Anfrage

?-autobahn (stuttgart, münchen).

an diese Wissensbasis würde der "Prolog"-Interpreter mit "ja" antworten. In der Anfrage

?-autobahn (stuttgart, WOHIN). kommt die Variable WOHIN vor; die Antworten des Prolog"-Interpreters wären daraufhin von der Form:

WOHIN = ulm;

WOHIN = augsburg;

WOHIN = münchen; etc.

Für die Herleitung von Antworten auf Anfragen verwendet "Prolog" das sogenannte Resolutionsverfahren. Es beruht auf der Betrachtung der Wissensbasis als einer logischen Formel "WB" und der Anfrage als einer logischen Formel "A". Durch systematische Anwendung von Resolutionsschritten versucht der Interpreter, die Formel "A" aus der Formel "WB" zu folgern. Zu diesem Zweck wird die Wissensbasis sequentiell nach einer passenden Horn-Klausel durchsucht. Das ist entweder eine Regel der Form "A:-B,C,D, ..." oder eine Tatsache "A".

Im zweiten Fall ist die Richtigkeit der logischen Formel Am unmittelbar gesichert. Im ersten Fall hat sich die ursprüngliche Anfrage "?- A" -in mehrere Teilanfragen aufgespalten: "?- B" ,"?- C" ,"?- D ... " Deren positive Beantwortung beweist erst die Richtigkeit von "A" bezüglich der Wissensbasis "WB". Diese Teilanfragen werden der Reihe nach entsprechend der Antwort auf die ursprüngliche Anfrage in Angriff genommen.

Sollte der "Prolog"-Interpreter bei der Beantwortung einer Teilanfrage in eine Sackgasse geraten, versucht er, durch schrittweises Zurücksetzen ("backtracking") entlang des bisher verfolgten Pfades andere für die Beantwortung der Anfrage in Betracht kommende Horn-Klauseln zu finden. Um Zyklen zu vermeiden, werden diejenigen Einträge in der Wissensbasis markiert, mittels derer Teilanfragen positiv beantwortet werden konnten. Sollten bei Rücksetzung Teilanfragen erneut zur Bearbeitung anstehen, wird nur noch der bei der entsprechenden Marke beginnende Ausschnitt der Wissensbasis berücksichtigt.

Variable in "Prolog"-Programmen erhalten ihren Wert durch Unifikation. Das bedeutet, daß sie beim Ver. gleich zweier Horn-Klauseln innerhalb einer dieser Klauseln an einer Position auftauchen, bei der in der anderen Klausel der entsprechende Wert steht.

Die Anfrage "?- autobahn (stuttgart, WOHIN)." führt zum Vergleich mit der Klausel autobahn (START, ZIEL) :- autobahn_stück (START, ZIEL)." Dadurch werden die Gleichsetzungen: START = Stuttgart und ZIEL = WOHIN vorgenommen, so daß die neu entstandene Anfrage die Form "?- autobahn_stück (stuttgart, WOHIN)" annimmt. Diese wiederum paßt auf die Tatsache: autobahn_stück (stuttgart, ulm), wodurch die Gleichsetzung WOHIN = Ulm entsteht, die eine erste positive Anwort auf die ursprüngliche Frage darstellt.

Durch Rücksetzungen innerhalb des Resolutionsprozesses werden zuvor erfolgte Bindungen von Variablen an Werte wieder rückgängig gemacht. Erst dadurch eröffnen sich eventuell neue Möglichkeiten für die Beantwortung von Teilanfragen.

Aufbau der Wissensbasis muß bekannt sein

"Prolog" erspart es dem Anwender, die Abfolge der Resolutionsschritte mitsamt den dabei notwendigen Unifikationen und Rücksetzungen explizit zu beschreiben. Trotzdem müssen ihm beim Aufbau der Wissensbasis die später durch seine Anfragen ausgelösten Vorgänge bekannt sein. "Prolog" bietet Möglichkeiten für steuernde Eingriffe in den Resolutionsprozeß, wobei zum Beispiel der Suchraum beschnitten, Schleifen erzwungen, eine Ein-Ausgabe durchgeführt oder die Wissensbasis dynamisch verändert werden kann.

Von seiner Konzeption her ist "Prolog' auf die Erstellung wissensbasierter Softwaresysteme ausgerichtet. So sind zwar Ausdrucksmittel für die Durchführung numerischer Berechnungen vorhanden; sie werden jedoch zumeist lediglich für einfache Hilfsdienste verwandt. Die wichtigste Datenstruktur sind Listen, die wie in "Lisp" geschachtelt werden dürfen. Allerdings hat der Programmierer weitergehende Möglichkeiten ("Funktoren) zum Aufbau strukturierter Datentypen.

In Abbildung 4 ist der typische Aufbau eines Expertensystems dargestellt. Im Blickpunkt des Interesses stehen der Erwerb (die Akquisition"), die Darstellung ("Repräsentation") und die Nutzung ("Deduktion") von Wissensstrukturen.

Wissen zu einem bestimmten Problembereich zerfällt in deskriptives und prozedurales Wissen. Deskriptives Wissen setzt sich in der Regel aus Attributen und deren Werten zusammen; es dient vor allem der Beschreibung von statischen Aspekten eines Gegenstandes. Beispielsweise umfaßt deskriptives Wissen über ein Automobil die Attribute. Marke, Typ, Baujahr, Kilometerstand, Hubraum und Zylinderzahl. Prozedurales Wissen hingegen enthält die Operationen, in die der Betrachtungsgegenstand einzubeziehen ist. Für ein Auto gehören dazu etwa: Lenken, Bremsen, Beschleunigen, Schalten, Parken und Waschen.

Bei der Wissensdarstellung in Expertensystemen finden heutzutage hauptsächlich die folgenden vier Methoden Anwendung: semantische Netze, Rahmen ("frames"), Produktionsregeln und Prädikatenlogik. Die Herleitung neuen Wissens ist jeweils auf die Eigenarten dieser Methoden zugeschnitten.

Die beiden erstgenannten Verfahren sind sehr eng miteinander verwandt; bei ihnen ergibt sich Wissen hauptsächlich durch Vererbung entlang einer netzartigen Hierarchie von Wissensmodulen. Produktionsregeln liefern aufgrund von verketteten Anwendungen neues Wissen. Bei der prädikatenlogischen Darstellung von Wissen finden Beweisverfahren für die Richtigkeit von Aussagen statt.

Dr. Gerhard Barth ist Professor am Institut für Informatik der Universität Stuttgart.

Der Beitrag basiert auf einem Vortrag, der im Rahmen des CW-CSE-Seminars "Objektorientierte Sprachen für Software-Technologie" in München gehalten wurde.