PrologEdit
Die Programmiersprache Prolog wurde 1972 von Alain Colmerauer entwickelt. Es entstand aus einer Zusammenarbeit zwischen Colmerauer in Marseille und Robert Kowalski in Edinburgh. Colmerauer arbeitete am Verständnis natürlicher Sprache, mit Logik zur Darstellung der Semantik und mit Auflösung zur Beantwortung von Fragen. Im Sommer 1971 entdeckten Colmerauer und Kowalski, dass die klausale Form der Logik zur Darstellung formaler Grammatiken verwendet werden kann und dass Auflösungssatzprüfer zum Parsen verwendet werden können. Sie beobachteten, dass sich einige Theorembeweiser wie Hyper-Resolution als Bottom-up-Parser und andere wie SL-resolution (1971) als Top-Down-Parser verhalten.
Im folgenden Sommer 1972 entwickelte Kowalski in Zusammenarbeit mit Colmerauer die prozedurale Interpretation von Implikationen. Diese duale deklarative /prozedurale Interpretation wurde später in der Prolog-Notation formalisiert
H :- B1, …, Bn.
, das sowohl deklarativ als auch prozedural gelesen (und verwendet) werden kann. Es wurde auch klar, dass solche Klauseln auf bestimmte Klauseln oder Hornklauseln beschränkt werden könnten, wo H, B1, …, Bn sind alle atomare Prädikatenlogikformeln, und diese SL-Auflösung könnte auf L oder SLD-Auflösung beschränkt (und verallgemeinert) werden. Kowalskis Verfahrensinterpretation und VERFAHREN wurden 1973 in einem Memo beschrieben, das 1974 veröffentlicht wurde.
Colmerauer verwendete zusammen mit Philippe Roussel diese doppelte Interpretation von Klauseln als Grundlage für Prolog, das im Sommer und Herbst 1972 implementiert wurde. Das erste Prolog-Programm, ebenfalls 1972 geschrieben und in Marseille implementiert, war ein französisches Frage-Antwort-System. Die Verwendung von Prolog als praktische Programmiersprache wurde 1977 durch die Entwicklung eines Compilers durch David Warren in Edinburgh stark vorangetrieben. Experimente zeigten, dass der Prolog mit der Verarbeitungsgeschwindigkeit anderer symbolischer Programmiersprachen wie Lisp konkurrieren konnte. Edinburgh Prolog wurde zum De-facto-Standard und beeinflusste stark die Definition des ISO-Standards Prolog.
Abduktive Logikprogrammierung
Die abduktive Logikprogrammierung ist eine Erweiterung der normalen Logikprogrammierung, die es ermöglicht, dass einige Prädikate, die als abduzierbare Prädikate deklariert sind, „offen“ oder undefiniert sind. Eine Klausel in einem abduktiven Logikprogramm hat die Form:
H :- B1, …, Bn, A1, …, An . wobei H eine Atomformel ist, die nicht abduzierbar ist, sind alle Bi Literale, deren Prädikate nicht abduzierbar sind, und die Ai sind Atomformeln, deren Prädikate abduzierbar sind. Die abduzierbaren Prädikate können durch Integritätsbedingungen eingeschränkt werden, die die Form haben können: false :- L1, …, Ln .
wobei die Li beliebige Literale sind (definiert oder teilbar und atomar oder negiert). Beispiel:
canfly(X) :- bird(X), normal(X).false :- normal(X), wounded(X).bird(john).bird(mary).wounded(john).
wobei das Prädikat normal teilbar ist.
Problemlösung wird erreicht, indem Hypothesen abgeleitet werden, die in Bezug auf die abduzierbaren Prädikate als Lösungen für zu lösende Probleme ausgedrückt werden. Diese Probleme können entweder Beobachtungen sein, die erklärt werden müssen (wie im klassischen abduktiven Denken) oder Ziele, die gelöst werden müssen (wie in der normalen logischen Programmierung). Zum Beispiel erklärt die Hypothese normal(Mary) die Beobachtung canfly(Mary). Darüber hinaus beinhaltet dieselbe Hypothese die einzige Lösung X = 1 des Ziels, etwas zu finden, das fliegen kann:
:- canfly(X).
Die abduktive Logikprogrammierung wurde für die Fehlerdiagnose, Planung, Verarbeitung natürlicher Sprache und maschinelles Lernen verwendet. Es wurde auch verwendet, um Negation als Versagen als eine Form des abduktiven Denkens zu interpretieren.
Metalogic programmingEdit
Da die mathematische Logik eine lange Tradition hat, zwischen Objektsprache und Metasprache zu unterscheiden, ermöglicht die Logikprogrammierung auch die Metallevel-Programmierung. Das einfachste Metalogic-Programm ist der sogenannte „Vanille“ -Meta-Interpreter:
solve(true). solve((A,B)):- solve(A),solve(B). solve(A):- clause(A,B),solve(B).
wobei true eine leere Konjunktion darstellt, und Klausel(A, B) bedeutet, dass es eine Klausel auf Objektebene der Form gibt : – B.
Die Metalogic-Programmierung ermöglicht die Kombination von Objekt- und Metallevel-Darstellungen wie in natürlicher Sprache. Es kann auch verwendet werden, um jede Logik zu implementieren, die als Inferenzregeln angegeben ist. Metalogic wird in der Logikprogrammierung verwendet, um Metaprogramme zu implementieren, die andere Programme, Datenbanken, Wissensdatenbanken oder axiomatische Theorien als Daten manipulieren.
Beschränkungslogikprogrammierungbearbeiten
Die Beschränkungslogikprogrammierung kombiniert die Blockklausellogikprogrammierung mit dem Lösen von Einschränkungen. Es erweitert Horn-Klauseln, indem es einigen Prädikaten, die als Einschränkungsprädikate deklariert sind, erlaubt, als Literale im Hauptteil von Klauseln aufzutreten. Ein Constraint-Logikprogramm ist ein Satz von Klauseln der Form:
H :- C1, …, Cn , B1, …, Bn.
wobei H und alle Bi Atomformeln sind und die Ci Einschränkungen sind. Deklarativ werden solche Klauseln als gewöhnliche logische Implikationen gelesen:
H wenn C1 und … und Cn und B1 und … und Bn. Während jedoch die Prädikate in den Klauselköpfen durch das Constraint-Logikprogramm definiert werden, sind die Prädikate in den Constraints durch eine domänenspezifische modelltheoretische Struktur oder Theorie vordefiniert.
Prozedural werden Unterziele, deren Prädikate vom Programm definiert werden, durch Zielreduktion gelöst, wie in der gewöhnlichen Logikprogrammierung, aber Einschränkungen werden von einem domänenspezifischen Constraint-Solver auf Erfüllbarkeit überprüft, der die Semantik der Constraint-Prädikate implementiert. Ein anfängliches Problem wird gelöst, indem es auf eine erfüllbare Verbindung von Einschränkungen reduziert wird.
Das folgende Beschränkungslogikprogramm stellt eine vollständige zeitliche Datenbank von Johns Geschichte als Lehrer dar:
teaches(john, hardware, T) :- 1990 ≤ T, T < 1999.teaches(john, software, T) :- 1999 ≤ T, T < 2005.teaches(john, logic, T) :- 2005 ≤ T, T ≤ 2012.rank(john, instructor, T) :- 1990 ≤ T, T < 2010.rank(john, professor, T) :- 2010 ≤ T, T < 2014.
Hier ≤ und < sind Einschränkungsprädikate mit ihrer üblichen beabsichtigten Semantik. Die folgende goal-Klausel fragt die Datenbank ab, um herauszufinden, wann john sowohl Logik lehrte als auch Professor war:
:- teaches(john, logic, T), rank(john, professor, T) .
Die Lösung ist 2010 ≤ T, T ≤ 2012.Constraint Logic Programming wurde verwendet, um Probleme in Bereichen wie Bauingenieurwesen, Maschinenbau, digitale Schaltungsüberprüfung, automatisierte Fahrpläne, Flugsicherung und Finanzen zu lösen. Es ist eng mit der abduktiven Logikprogrammierung verwandt.
Concurrent logic programmingbearbeiten
Concurrent logic programming integriert Konzepte der Logikprogrammierung mit Concurrent programming. Seine Entwicklung wurde in den 1980er Jahren durch die Wahl für die Systemprogrammiersprache des japanischen Projekts der fünften Generation (FGCS) stark vorangetrieben.
Ein Concurrent-Logic-Programm ist ein Satz bewachter Klauseln der Form: H :- G1, …, Gn / B1, …, Bn.
Die Konjunktion G1, … , Gn wird der Wächter der Klausel genannt, und / ist der Verpflichtungsoperator. Deklarativ werden bewachte Hornklauseln als gewöhnliche logische Implikationen gelesen:
H wenn G1 und … und Gn und B1 und … und Bn.
Wenn jedoch mehrere Klauseln vorhanden sind, deren Köpfe H einem bestimmten Ziel entsprechen, werden alle Klauseln parallel ausgeführt, wobei überprüft wird, ob ihre Wachen G1, … , Gn halten. Wenn die Wächter von mehr als einer Klausel halten, dann wird eine festgeschriebene Wahl für eine der Klauseln getroffen, und die Ausführung wird mit den Unterzielen B1 fortgesetzt, …, Bn der gewählten Klausel. Diese Unterziele können auch parallel ausgeführt werden. Somit implementiert die gleichzeitige Logikprogrammierung eine Form von „kümmert sich nicht um Nichtdeterminismus“, anstatt „weiß nicht, Nichtdeterminismus“.
Das folgende gleichzeitige Logikprogramm definiert beispielsweise ein Prädikat Shuffle(Left, Right, Merge), mit dem zwei Listen nach links und rechts gemischt und zu einer einzigen Listenzusammenführung kombiniert werden können, die die Reihenfolge der beiden Listen Links und rechts beibehält:
shuffle(, , ).shuffle(Left, Right, Merge) :- Left = | Merge = , shuffle(Rest, Right, ShortMerge).shuffle(Left, Right, Merge) :- Right = | Merge = , shuffle(Left, Rest, ShortMerge).
Stellt hier die leere Liste dar und repräsentiert eine Liste mit dem ersten Element Head gefolgt von list Tail , wie in Prolog. (Beachten Sie, dass das erste Vorkommen von | in der zweiten und dritten Klausel der Listenkonstruktor ist, während das zweite Vorkommen von | der Commitment-Operator ist.) Das Programm kann beispielsweise verwendet werden, um die Listen zu mischen und die goal-Klausel aufzurufen:
shuffle(, , Merge).
Das Programm generiert nicht deterministisch eine einzelne Lösung, z. B. Merge = .Wohl basiert die gleichzeitige Logikprogrammierung auf der Nachrichtenübermittlung und unterliegt daher derselben Unbestimmtheit wie andere gleichzeitige Nachrichtenübermittlungssysteme, z. B. Akteure (siehe Unbestimmtheit in der gleichzeitigen Berechnung). Carl Hewitt hat argumentiert, dass die gleichzeitige logische Programmierung nicht auf Logik in seinem Sinne basiert, dass Rechenschritte nicht logisch abgeleitet werden können. Bei der gleichzeitigen logischen Programmierung ist jedoch jedes Ergebnis einer beendenden Berechnung eine logische Konsequenz des Programms, und jedes Teilergebnis einer Teilberechnung ist eine logische Konsequenz des Programms und des Restziels (Prozessnetzwerks). Die Unbestimmtheit von Berechnungen impliziert also, dass nicht alle logischen Konsequenzen des Programms abgeleitet werden können.
Concurrent constraint logic programmingbearbeiten
Concurrent Constraint logic programming kombiniert Concurrent Logic Programming und Constraint Logic Programming und verwendet Constraints zur Steuerung der Parallelität. Eine Klausel kann einen Guard enthalten, d. H. eine Reihe von Einschränkungen, die die Anwendbarkeit der Klausel blockieren können. Wenn die Guards mehrerer Klauseln erfüllt sind, trifft die Programmierung der Concurrent Constraint Logic eine feste Entscheidung, nur eine zu verwenden.
Induktive Logikprogrammierungbearbeiten
Die induktive Logikprogrammierung beschäftigt sich mit der Verallgemeinerung von positiven und negativen Beispielen im Kontext von Hintergrundwissen: maschinelles Lernen von Logikprogrammen. Jüngste Arbeiten in diesem Bereich, die logische Programmierung, Lernen und Wahrscheinlichkeit kombinieren, haben das neue Gebiet des statistischen relationalen Lernens und der probabilistischen induktiven Logikprogrammierung hervorgebracht.
Logikprogrammierung höherer Ordnungbearbeiten
Mehrere Forscher haben die Logikprogrammierung um Programmierfunktionen höherer Ordnung erweitert, die von Logik höherer Ordnung abgeleitet sind, z. B. Prädikatvariablen. Zu diesen Sprachen gehören die Prolog-Erweiterungen HiLog und proprolog.
Lineare Logikprogrammierungbearbeiten
Die logische Programmierung innerhalb der linearen Logik hat dazu geführt, dass logische Programmiersprachen entworfen wurden, die wesentlich expressiver sind als solche, die auf klassischer Logik basieren. Horn-Klausel-Programme können Zustandsänderungen nur durch die Änderung von Argumenten in Prädikate darstellen. In der linearen Logikprogrammierung kann man die umgebende lineare Logik verwenden, um Zustandsänderungen zu unterstützen. Einige frühe Entwürfe von Logikprogrammiersprachen, die auf linearer Logik basieren, umfassen LO , Lolli, ACL und Forum . Forum bietet eine zielgerichtete Interpretation der gesamten linearen Logik.
Objektorientierte Logikprogrammierungbearbeiten
F-logic erweitert die Logikprogrammierung um Objekte und die Frame-Syntax.
Logtalk erweitert die Programmiersprache Prolog um die Unterstützung von Objekten, Protokollen und anderen OOP-Konzepten. Es unterstützt die meisten standardkonformen Prolog-Systeme als Backend-Compiler.
Transaktionslogikprogrammierungbearbeiten
Die Transaktionslogik ist eine Erweiterung der Logikprogrammierung mit einer logischen Theorie zustandsmodifizierender Aktualisierungen. Es hat sowohl eine modelltheoretische als auch eine prozedurale Semantik. Eine Implementierung einer Teilmenge der Transaktionslogik ist im Flora-2-System verfügbar. Andere Prototypen sind ebenfalls erhältlich.