Die Geschichte der deklarativen bzw. logikorientierten ist eine sehr kurze. Im Vergleich zu der Idee der imperativen Programmiersprachen ist die Geschichte der logikorientierten Programmiersprachen sehr kurz. Seit den frühen Anfängen der Programmierung von Maschinen stand eigentlich immer schon die kontinuierliche Abarbeitung von Befehlen im Mittelpunkt. Gerade auch wenn man moderne Computer betrachtet, muss man einfach feststellen, dass die Hardware praktisch immer darauf ausgelegt diverse Befehle auszuführen. Ein Programm kann also als eine Folge von Befehlen angesehen werden. Es ist also nicht verwunderlich, dass die imperative Programmierung in den Anfängen des Computers die unumstrittene alleinherrschende Sichtweise war. Das ist auch damit zu begründen, dass die ersten Programmiersprachen sehr hardwarenahe waren und damit auch vom imperativen Aufbau der Hardware geprägt waren.
Nicht zuletzt deshalb weil die Konzepte Programmierung und Logik erst sehr spät zur Logikprogrammierung zusammengefügt wurden, ist es wichtig zunächst einen Blick auf die Entwicklung der Logik unabhängig von der Programmierung zu werfen.
Geschichte der Logik
Logik, wie wir sie heute kennen geht in ihren ursprüngen auf das antike Griechenland zurück. Zwar hatten andere Kulturen wie etwa die Ägypter bereits eine sehr komplexe Mathematik entwickelt, die Methode des logischen Schließens von bekannten Tatsachen auf weitere, neue Tatsachen wurde erst von den alten Griechen bewußt angewandt und untersucht. Die Logik wurde von den Philosophen des antiken Griechenlands nicht einfach angewendet, sondern war selbst Gegenstand von Untersuchungen. Bereits damals versuchte man also ein umfassendes Regelwerk zum Schliessen oder Ableiten von neuen Tatsachen aus bereits vorhandenen Tatsachen aufzustellen.
Aristoteles (384 v.Chr. - 322 v.Chr.) ist hier als einer der wichtigsten griechischen Philosophen zu nennen. Er war zwar in erster Linie kein Mathematiker, leistete aber trotzdem wichtige Beiträge zur Systematisierung deduktiver Logik. Als Beispiel für die Arbeit Aristoteles sei hier nur der arestotelische Syllogissmus genannt, eine Struktur, die aus zwei Prämissen (Vorbedingungen) und einer Konklusion (Schlussfolgerung) besteht. Ein Beispiel dafür ist:
(i) Jeder Grieche ist ein Mensch.
(ii) Jeder Mensch ist sterblich.
(iii) Jeder Grieche ist sterblich.
Bereits vor Aristoteles hatte Plato die Idee eines Axiomensystems eingeführt. Aristoteles hat diese Idee Platos etwas modifiziert. Anstatt eines einzigen Axiomensystems forderte er, dass es für mehrere verschiedene Wissenschaften verschiedene Axiomensysteme geben müsse.
Wenig später wurde von Euclid (ca. 325 v.Chr. - ca. 265 v.Chr.) die Anwendung der axiomatischen Methode des logischen Schließens auf die Geometrie angewandt. Im Prinzip beruht die gesamte euklidische Geometrie auf den folgenden fünf Axiomen:
- Man kann von jedem Punkt zu jedem Punkt die Strecke ziehen.
- Man kann eine begrenzte gerade Linie zusammenhängend gerade verlängern.
- Man kann mit jedem Mittelpunkt und Abstand den Kreis ziehen.
- Alle rechten Winkel sind einander gleich.
- Wenn zwei Geraden mit einer dritten auf derselben Seite innere Winkel bilden, deren Summe kleiner als ein flacher Winkel ist, so schneiden sie sich bei hinreichender Verlängerung auf dieser Seite.
In seiner Arbeit über die Geometrie (``die Elemente''), greift Euklid ständig auf diese Axiome zurück.
Ein weiterer Philosoph, der die Entwicklung der Logik voran trieb war Leibniz (1646 - 1716). Leibniz entwickelte zeitgleich mit Newton die Differential- und Integralrechnung, aber auch eine Rechenmaschine und vieles mehr. Er formulierte als erster das Ziel einer universellen Sprache zur Formalisierung aller mathematischer Aussagen und ein Kalkül zur Herleitung aller wahren Aussagen. Folgendes Zitat von Leibniz zeigt eine enge Verbindung zwischen Logik und dem, was wir heute künstliche Intelligenz nennen:
Wenn es möglich wäre, Symbole oder Zeichen zu finden, die sich dazu eignen, alle unsere Gedanken ebenso gradlinig und stringent auszudrücken wie die Arithmetik die Zahlen oder wie die Geometrie die Figuren darstellt, dann könnten alle Dinge, soweit sie dem Schlußfolgern unterworfen sind, in der gleichen Weise behandelt werden wie es in der Arithmetik und Geometrie getan wird.
Gottlob Frege (1848 - 1925) war ebenfalls ein Wegbereiter der modernen Logik. Er führte um 1879 eine mathematische Formalisierung der Prädikatenlogik mittels grafischer Notation ein.
Einer der bedeutendsten Mathematiker des 19. und 20. Jahrhunderts war David Hilbert (1862 - 1943). Er formulierte als erster zwei grundlegende Ziele der Logik:
- Beweis der Widerspruchsfreiheit der Arithmetik (wobei Arithmetik als Logik plus Natürliche Zahlen aufgefasst wird) innerhalb der Arithmetik selbst.
- Entwicklung einer Methode zur Berechnung aller wahren mathematischen Aussagen.
Kurt Gödel (1906 - 1978) war der bedeutendste Logiker des 20 Jahrhunderts. Er leitete eine Krise der Logik ein, indem er zeigte, dass die Widerspruchsfreiheit der Arithmetik innerhalb der Arithmetik nicht nachgewiesen werden kann (1931). Dies macht das erste Ziel Hilberts zunichte.
Alonzo Church zeigte später, dass es keinen Algorithmus gibt, der für jede mathematische Aussage entscheidet, ob sie wahr oder falsch ist (1936). Dies macht auch das zweite von Hilbert formulierte Ziel der Logik zunichte.
Als letzte wichtige Entdeckung auf dem Gebiet der Logik soll das von Alan Robinson erfundene Resolutions-Kalkül genannt werden. Diese Methode, die 1965 entstanden ist, ist die erste effektive Methode des automatischen Beweisen in der Prädikatenlogik.
Logik-Programmierung und AI
Wie erwähnt ist die Geschichte der Logik-Programmierung im Vergleich zu der Geschichte der Logik selbst sehr kurz. Erst in der zweiten Hälfte des 20. Jahrhunderts wurde versucht, die Logik selbst als Programmiersprache zu verwenden. In den späten 1960ern bzw. in den frühen 1970ern entstand als erste logikorientierte Programmiersprache Prolog an der Universität von Aix-Marseille.
Wer das letzte Kapitel aufmerksam gelesen hat, der stellt fest, dass man mit Hilfe der Logik bereits in der Antike versucht hat, das Denken auf eine gewisse Art zu mechanisieren. Genau dieses mechanisieren von Denkvorgängen ist ja eigentlich der zentrale Punkt in der ganzen Forschung der Künstlichen Intelligenz. Es ist also nich verwunderlich, dass Wissensrepräsentation in Computersystemen sehr oft mittels Formalismen durchgeführt wird, die sehr stark an die herkömmlichen Notationen in der Logik anknüpfen.
Prolog - "Programmieren in Logik"
Prolog ("Programming in Logic" oder "Programmation en Logique"), die erste und wohl auch bekannteste und am weitesten verbreitete Sprache der Familie der logikorientierten Prorammiersprachen, wurde in den frühen 70er Jahren des vorigen Jahrhunderts an der Universität von Marseille-Aix entwickelt. Als Hauptpersonen bei der Entwicklung sind Alain Colmerauer, Phillip Roussel und Robert Kowalski zu nennen. Colmerauer kann man dabei als Initiator der Idee hatte ansehen, wobei man allerdings die Arbeiten von Roussel und Kowalski nicht vernachlässigen sollte. Manche Autoren (z.B. Jaques Cohen)verweisen allerdings darauf, dass es nur wenige Sprachen gab, die in ähnlichem Ausmass von einer einzigen Person geprägt wurden. Ursprünglich wurde Prolog in ALGOL-W implementiert und war zur Verarbeitung von natürlicher Sprache entworfen worden, es wurde dann aber zur am meisten verwendeten Sprache im Bereiche der künstlichen Intelligenz.
Eine zentrale Betrachtungsweise der Entwicklung Prologs ist die der Compilerbauer, da Alain Colmerauer, der sozusagen als Motor der Prologentwicklung bezeichnet werde kann, dieses Fach gelernt hatte.
Erste Wurzeln Prologs aus einer Sicht der Compilerbauer finden sich bereits in den späten 50er und frühen 60er Jahren, und sie sind eng verbunden mit der Förderung einer nationalen französischen Informatik. Frankreich ist zentralistisch aufgebaut, die Metropole Paris hat sich im Laufe der Geschichte zum eigentlichen Zentrum des Landes entwickelt; gegen Ende der 50er gab es in Frankreich jedoch von politischer Seite Bestrebungen zur Dezentralisierung, und so wurde unter anderem die Forschung in den Provinzen stark gefördert. Da gleichzeitig in einem großangelegten Vorhaben eine nationale Computerindustrie entwickelt werden sollte, waren die materiellen Möglichkeiten in Grenoble überaus günstig. Am dortigen Institut für angewandte Mathematik befaßte man sich unter der Leitung von Louis Bolliet mit Compilerbau und war insbesondere mit der Entwicklung eines französischen Algol 60-Compiler für die IBM 7044 befaßt.
In diesem Umfeld erlernte Alain Colmerauer sein Handwerk. Nach seinem Studium am Polytechnischen Institut in Grenoble arbeitete er an der dortigen Universität in der Compilerbau-Gruppe, wo er sich auf Syntaxanalyse und Programmierung spezialisierte und in diesen Bereichen auch seine Doktorarbeit schrieb.
Grossen Einfluß auf Alain Colmerauer und seine weitere Entwicklung hatte dabei die Entwicklung der Programmiersprache Algol. Beim Entwurf von Algol 60 spielten die Arbeiten des Linguisten Noam Chomsky eine wichtige Rolle. Dieser hatte in den 50er Jahren eine Systematik formaler Grammatiken entworfen, die sich als ein mächtiges Hilfmittel beim Bau von Compilern herausstellten. Chomsky unterscheidet hierbei Grammatikregeln vom Typ 0 bis 3, die auch als allgemeine, kontextsensitive, kontextfreie und reguläre Regeln bezeichnet werden. Für die Genese von Prolog waren dabei die kontextfreien Regeln wichtig, doch spielten auch andere Regeln im Vorfeld der Entwicklung zu Prolog als auch danach eine Rolle.
Grammatikregeln sind für Linguisten Regeln, um eine natürliche Sprache zu beschreiben, sind also rekonstruktiv. Für Informatiker hingegen sind Grammatikregeln sowohl Ersetzungsregeln, die eine formale Sprache erzeugen als auch Regeln, um eine formale Sprache zu analysieren. Für die Informatik spielt damit der konstruktive und analytische Charakter der Regeln die vorherrschende Rolle.
Ein erstes Forschungsprojekt Colmerauers war die Entwicklung eines Scanners für Syntaxfehler für die Programmiersprache Cobol. Danach arbeitete Colmerauer in der Algol-Gruppe weiter, die unter J. C. Boussard den französischen Algol-Compiler entwickeln sollte. Hier führte Colmerauer seine Arbeit fort und schrieb ein Programm zur Syntaxanalyse und Fehlerkorrektur für Algol 60.
In dieser Zeit nahm Colmerauer auch an mehreren der Treffen teil, in denen Algol entworfen wurde. Hier lernte er unter anderem die Wissenschaftler Aard van Wijngaarden und Robert Floyd kennen, die den jungen Forscher stark beeindruckten. Zu letzterem unterhielt er auch private Kontakte. "He visited me when I was still a student in Grenoble and I was very impressed by him."
Der persönliche Kontakt fokussierte den Blick Colmerauers besonders auf die Theorien von Robert Floyd, und er machte sich diese für sich nutzbar. Auch die Arbeiten von Aard van Wijngaarden als Koryphäe der Algol-Entwicklung gewinnen für Colmerauer eine größere Bedeutung. Insbesondere die Theorien von Floyd sind es, die Colmerauer aus der Algol-Zeit hinüberrettet und die er in die Programmiersprache Prolog einbringt.
Als zentrale Texte für Colmerauer geben sowohl er selber als auch Cohen die beiden Arbeiten "Syntactic analysis and operator precedence" (1963) und "Nondeterministic algorithms" (1967) von Robert Floyd an. Diese Texte sind recht kurz mit 8 bzw. 17 Seiten und kommen damit dem Problem Colmerauers mit der englischen Sprache durchaus entgegen. "Alain avoided reading many technical papers because at the time he had some difficulties with English. I am sure that when he located a key paper he read it with great care." (Cohen).
Beachtenswert sind jedoch auch die privaten Kontakte zwischen den beiden. Sie waren schon früh persönlich bekannt, zu Zeiten, als Colmerauer noch in Grenoble arbeitete. Colmerauer war dabei so fasziniert von Robert Floyd und dessen Arbeiten, daß er seine Dissertation darauf aufbaute. Ein weiteres Indiz für das gute Verhältnis zwischen beiden ist, daß Colmerauer der Text über die nichtdeterministischen Algorithmen bereits vor dessen eigentlicher Veröffentlichung zur Verfügung stand. Als schließlich im November 1972 Colmerauer zusammen mit seinen Kollegen Philippe Roussel und Robert Pasero eine Reise durch die Forschungslabors der USA machte, verbrachte er Thanksgiving bei Robert Floyd zu hause.
Durch seine frühen Arbeiten wurde Robert Floyd zu einer der Größen der jungen Disziplin Informatik. Im Jahr 1978 erhielt er für seine Erfolge den jährlich vergebenen Turing-Award der ACM und steht damit in einer Reihe mit Allan Perlis (1966), Marvin Minsky (1969), John McCarthy (1971), E.W. Dijkstra (1972), Donald E. Knuth (1974), Allen Newell und Herbert A. Simon (1975) sowie John Backus (1977), um nur einige der bekanntesten Namen aus jener Zeit hervorzuheben. Es ist also nicht verwunderlich, wenn auch Colmerauer von Floyd und dessen Arbeiten beeindruckt ist. Syntaxanalyse und nichtdeterministische Algorithmen
Die erste von Colmerauer angegebene Publikation von Robert Floyd befaßte sich mit Syntaxanalyse und Operatorenpräzedenz und wurde bereits 1963 publiziert. Auf dieser Arbeit baute Colmerauer seine Doktorarbeit auf, und die Festlegung von Präzedenzen bei der Definition von Operatoren wird später zu den Besonderheiten und Stärken von Prolog gehören. Über die Syntaxanalyse formaler Sprachen wagte Colmerauer den Versuch der Analyse natürlicher Sprache, bewaffnet mit den Floydschen Algorithmen und damals wohl auch in dem Bewußtsein einer engen Verwandtschaft formaler und natürlicher Sprache.
Die zweite Arbeit aus dem Jahre 1967 beschreibt am Beispiel des "Eight Queens"-Problems die Verwendung nichtdeterministischer Algorithmen, wobei Floyd hiermit jedoch keine Zufallsalgorithmen meint.
"Because the word 'nondeterministic' has a double meaning, it is perhaps desirable to make clear that nondeterministic algorithms are not probabilistic, random or Monte Carlo algorithms. Rather, they are convenient representations of systematic search procedures" . In diesem Sinne ist also Prolog eine nichtdeterministische Programmiersprache, und ein Teil ihrer Grundlagen wurde bereits in diesem Artikel von Robert Floyd gelegt. So lesen wir bei Robert Floyd: "All points of termination are labeled as successes or failures." Dort finden wir also bereits das TRUE und FALSE, das jedes terminierende Prolog-Programm als Ergebnis ausgibt.
Obwohl wir auch beim Theorembeweisen die Berechnungen mit einem TRUE oder FALSE abschließen, scheint es bei Floyd und dessen Arbeit keine expliziten Beziehung zum Theorembeweisen zu geben - weder das Literaturverzeichnis noch der Text selber unterstützen eine derartige Annahme; es scheint vielmehr, daß an dieser Stelle Theorembeweiser und Compilerbauer noch aneinander vorbei arbeiteten.
In diesem Zusammenhang muß auf die Relevanz des Nichtdeterminismus für den Übersetzerbau eingegangen werden. Wir können eine Programmiersprache mit einer formalen Grammatik beschreiben und damit arbeiten. Eine Grammatik ist vom Standpunkt der Theorie aus nichtdeterministisch. Wir unterscheiden üblicherweise nicht zwischen deterministischen und nichtdeterministischen Grammatiken, wohl aber zwischen dazu äquivalenten deterministischen und nichtdeterministischen Automaten. In der Praxis des Übersetzerbau beschränkt man sich aus Gründen der Effizienz und Eindeutigkeit gerne auf deterministisch analysierbare kontextfreie Grammatiken, doch auch die Arbeit mit nichtdeterministisch analysierbaren kontextfreien Grammatiken ist von Interesse. Die solcherart durch eine Grammatik beschriebene Sprache kann möglicherweise nicht mehr deterministisch durch einen Kellerautomaten erkannt werden, wohl aber durch eine Turingmaschine oder, was dieser äquivalent ist, durch eine Kellermaschine mit zwei Kellern. Wenn Colmerauer in seiner Dissertation mit zwei Stacks arbeitet, bewegt er sich genau in diesem Feld. Und die Lösung, die Prolog zum Problem des Nichtdeterminismus von Regeln anzubieten hat, ist noch faszinierender: indem der Nichtdeterminismus akzeptiert wird, wird er zu einem zentralen Bestandteil der Programmiersprache.
Es bleibt festzuhalten, daß vieles, was Colmerauer im Umfeld der Algol-Entwicklung erlernte, später auf die eine oder andere Art in den Entwurf der Programmiersprache Prolog einfließt. Einzig in diesem Sinne können wir eine Verwandtschaft zwischen Algol und Prolog festmachen.
Andere logikorientierte Programmiersprachen
ALF
ALF (Algebraic Logic Funktional language) ist eine Sprache, die funktionale und logische Programmiertechniken miteinander vereint. Die Grundlage für ALF sind einerseits Horn-Klauseln für Logik-Programmierung und andererseits auch Funktionen und Gleichungen für funktionales Programmieren. Jeder Funktionale Ausdruck kann auch in einem Goal oder einem Literal vorkommen. Genau so kann auch ein Prädikat in einer Bedingung oder Gleichung auftreten.
Ähnlich wie Prolog verwendet ALF eine Backtracking-Strategie gemeinsam mit einer Tiefensuche im Abgeleiteten Suchbaum. ALF Programme werden in Instruktionen einer abstrakten Maschine kompiliert. Diese abstrakte Maschine basiert auf der Warren Abstract Machine (WAM), umfasst aber dieser gegenüber diverse Erweiterungen um auch funktionale Elemente der Sprache effizient verarbeiten zu können.
Die Syntax von ALF ist ähnlich der von Prolog, allerdings umfasst ALF diverse zusätzliche Sprachelemente und spezielle Eigenschaften. Wie erwähnt sind das die Teile der Sprache die die funktionalen Teil von ALF bilden. Weiters gibt es in ALF ein strenges Typensystem. Für jede Funktion müssen beispielsweise die Typen für Eingabeparameter und Rückgabewert definiert werden. Ein weiteres interessantes Konzept, das ALF umfasst ist Modularisierung. Ein Modul kann von einem anderen Modul mittels einer use-Deklaration importiert werden. In diesem Fall werden alle exportierten Objekte des importierten Moduls sichtbar im importierenden Modul.
Gödel
Gödel ist eine deklarative, logische Programmiersprache, die allgemein einsetzbar ist. Die Sprache ist streng typisiert und unterstützt auch1 Modularisierung. Gödel unterstützt unter anderem auch Integers und Gleitkommazahlen. Gödel kann auch Bedingungen (constraints) über endlichen Bereichen ganzer Zahlen lösen und auch linear rationale Bedingungen. Weiters unterstützt Gödel die Verarbeitung von endlichen Mengen.
Beispielprogramm in Gödel
Folgendes Beispiel soll vermitteln, wie die Programmiersprache Gödel aufgebaut ist. Das Beispielprogramm berechnet den größten gemeinsamen Teiler:
MODULE GCD.
IMPORT Integers.
PREDICATE Gcd : Integer * Integer * Integer.
Gcd(i,j,d) <-
CommonDivisor(i,j,d)
SOME [e] (CommonDivisor(i,j,e) & e > d).
PREDICATE CommonDivisor : Integer * Integer * Integer.
CommonDivisor(i,j,d) <-
IF (i = 0 \/ j = 0)
THEN d = Max(Abs(i),Abs(j))
ELSE
1 =< d =< Min(Abs(i),Abs(j)) &
i Mod d = 0 &
j Mod d = 0.
Sampletalk
Sampletalk ist eine Sprache, die sich sehr stark an die menschliche Sprache anlehnt. Ganz bewußt wurde Sampletalk so konzipiert, dass es extrem wenig an Syntax vorschreibt. Das einzige, was die Sprache definiert ist ":-'' zwischen Köpfen und Rümpfen von Klauseln. Sampletalk hat viele Aspekte und vereint mehrere interessante Wissensgebiete: künstliche Intelligenz, Logik-Programmierung, Verarbeitung natürlicher Sprache, Wissensrepräsentation etc. Folgendes Beispiel zeigt ein mögliches Sampletalk Programm:
where is new york? % Goal (Anfrage)
where is X? in Y :- X is situated in Y. % Inferenz Regeln
who is X? Y :- X is Y.
new york is situated in america. % Fakten in natürlicher Sprache
st. petersburg is situated in russia.
a book is situated on a table.
joe is son of maria and peter.
julia is daughter of maria and peter.
peter 2 is son of maria and peter 1.
jack 2 is son of julia and jack 1.
Auf den ersten Blick fällt auf, dass dieses Programm eher einem Text in natürlicher Sprache ähnlich ist, als einem "normalen'' C++, LISP oder Prolog Programm. Zu beachten ist, dass Wörter wie "where", "is", "situated" und "who" keine Schlüsselwörter sind, sondern ihre Bedeutung wird durch ihren Gebrauch festgelegt. Als Ergebnis auf das Goal "Where is new york?" liefert obiges Programm die Antwort "in america".
Folgende Goals würden folgende Antworten liefern:
Goal Antwort
who is julia? daughter of maria and peter
X is son of maria and Y X wird zunächst zu "joe" und dann
zu "peter 2" evaluiert
Jack N is Y of Z Y wird zu "son" und
Z zu "julia and jack 1"
|