Logische Programmierung
aus Wikipedia, der freien Enzyklopädie
Logische Programmierung ist ein Programmierparadigma, das auf der mathematischen Logik beruht. Anders als bei der imperativen Programmierung besteht ein Logik-Programm nicht aus einer Folge von Befehlen, sondern aus einer Menge von Axiomen, welche hier als eine reine Ansammlung von Fakten oder Annahmen zu verstehen sind. Stellt der Benutzer eines Logik-Programms eine Anfrage, so versucht der Interpreter die Lösungsaussage allein aus den Axiomen zu berechnen.
Dazu werden eine Menge von so genannten Regeln und Anweisungen, die der Syntax gemäß aufgebaut sind, zusammen mit der Information, welche Lösungsmethode vorgesehen ist, in den Programmcode eingefügt. Regelbasierte Programmiersprachen sind zugleich auch logische und deklarative Programmiersprachen und gehören zu den grundlegenden Werkzeugen der Künstlichen Intelligenz.
In einem imperativen Programm wird genau beschrieben, wie und in welcher Reihenfolge ein Problem zu lösen ist. Im Gegensatz dazu wird in einem regelbasierten Programm idealerweise nur beschrieben, was gilt. Das "wie" ist bereits durch die Lösungsmethode vorgegeben. Die Lösung wird aus den vorhandenen Regeln hergeleitet. Meistens wird schon nur eine Menge von Regeln als "das Programm" bezeichnet, wenn klar ist, welche Lösungsmethode dazugehört: Nämlich die (einzige) in der vom regelbasierten System bereit gestellten Inferenzmaschine verwirklichte. Strenggenommen ist ein Satz von Regeln nur ein Programmtext. Diese strenge Unterscheidung ist allerdings nur selten nötig.
Die bekanntesten regelbasierten Sprachen sind Prolog und XSLT.
Inhaltsverzeichnis |
[Bearbeiten] Erläuterungen
Die Syntax gibt an, wie Regeln geschrieben werden müssen, damit der Computer sie verwenden kann. Regeln sind "Falls-dann"-Aussagen und Fakten, die das Wissen zu einem Problemkreis beschreiben. Daneben gibt es oft noch spezielle Konstrukte, um die Lösungsmethode zu beeinflussen. Am bekanntesten ist die Rückwärtsabschneidung (engl. cut) in Prolog, womit "Falls-dann-außer"-Regeln modelliert werden.
Einem regelbasierten Programm kann man Fragen stellen, indem man ein Ziel vorgibt. Das entspricht grob gesehen dem Aufruf einer Funktion oder Prozedur in anderen Programmiersprachen.
Die Lösungsmethode gibt vor, wie die Inferenzmaschine die Regeln (den Programmtext) interpretiert, um die Frage zu beantworten. In Prolog wird eine Depth-First-Suche ("Tiefe-zuerst") mit Unifikation und Backtracking (Rückverfolgung) verwendet. Jedoch sind auch andere Methoden geeignet und werden je nach Anwendungsfall auch eingesetzt.
[Bearbeiten] Besonderheiten regelbasierter Programmiersprachen
Logikorientierte Programmiersprachen haben ungewöhnliche Eigenschaften (Backtracking, Unifikationsalgorithmen), die sie für gewisse Arten von Problemen prädestiniert, die mit anderen Programmiersprachen nur sehr schwer zu lösen sind. Prolog, eine der bekanntesten logischen Programmiersprachen etwa, orientiert sich in der Beschreibung der Programme an der Prädikatenlogik.
Durch den Austausch der Lösungsmethode wird ein und derselbe Programmtext (Satz von Regeln) zu einem anderen Programm und liefert andere Ergebnisse (vergl. XSLT und Expertensystem). Die Verbesserung und Spezialisierung der Lösungsmethode ist seit den 1980'er Jahren ein "Dauerbrenner" in der Forschung auf einigen Gebieten der Künstlichen Intelligenz.
Regelbasierte Sprachen haben auch eine starke funktionale und eine prozedurale Interpretation. Mit Abstrichen und geringem Zusatzaufwand ist auch objektorientiertes Programmieren in einer typischen regelbasierten Sprache möglich.
Regelbasierte Programme sind sehr gut geeignet, auf Parallelrechnern mit entsprechender Geschwindigkeitssteigerung zu laufen. Diese Erkenntnis führte zur Entwicklung von Parlog.
Bis zu einem gewissen Grad der Komplexität lassen sich regelbasierte Programme sehr einfach durch Hinzufügen neuer Regeln erweitern und vergrößern dabei ihre Funktionalität oft überproportional. Diese Eigenschaft ist bei den "abstrakteren" regelbasierten und funktionalen Sprachen besser als bei anderen, "konkreteren" Programmiersprachen. Deshalb eignen sich regelbasierte Sprachen gut für die Entwicklung von Software-Prototypen und Rapid Prototyping.
Ist jedoch eine gewisse Komplexität erreicht, lassen sich regelbasierte Programme nur noch mit großem Aufwand erweitern: Es wird immer komplizierter, sinnvolle Regeln zu schreiben, die den schon vorhandenen Regeln nicht widersprechen. Dieser Punkt wird bei modernen objektorientierten Sprachen in der Regel später erreicht, da diese bessere Kapselungsmechanismen haben.
Denn die Regeln eines regelbasierten Programms müssen bestimmten mathematischen Anforderungen genügen, damit sie informationstechnisch verwertbar sind. Auch müssen sie frei von Widersprüchen sein. Wir unterscheiden aber in vielen Sachgebieten nicht zwischen solchen "mathematisch sauberen" und "unsauberen" Regeln. Viele der uns bekannten Zusammenhänge können wir nur in "unsauberen" Regeln in natürlicher Sprache fassen; entsprechende "mathematisch saubere" Regeln kennen wir oft gar nicht. Zwangsläufig finden sich also "unsaubere" Regeln in unseren Programmen, zumindest wenn die Domäne des Programms nicht die Mathematik ist.
Die Bemühungen der Forschung haben u.a. zu Ziel, Inferenzmaschinen zu entwerfen, die mit "unsauberen" Regeln genauso gut umgehen wie der Mensch [vergl. Fuzzy-Logik].
Seit den 1990er Jahren vermischen sich regelbasierte Sprachen mit Programmiersprachen anderer Paradigmen, um die Effizienz der Programme und Ausdruckskraft der Programmiersprache zu erhöhen.
[Bearbeiten] Beispiel
Dieses Beispiel ist in natürlicher Sprache formuliert, um das Prinzip aufzuzeigen. Die konkrete Anwendung kann man bei der Programmiersprache Prolog ersehen.
Fakten:
- Lucia ist die Mutter von Minna.
- Lucia ist die Mutter von Klaus.
- Minna ist die Mutter von Nadine.
Regel:
- Falls X ist die Mutter von Y und Y ist die Mutter von Z Dann X ist die Großmutter von Z.
Frage/Ziel:
- Wer ist die Großmutter von Nadine?
Antwort des Computers, Folgerung aus den Fakten und Regeln:
- Lucia
Dieses unspektakuläre Beispiel kann man gedanklich leicht um andere Verwandtschaftsbeziehungen erweitern.
[Bearbeiten] Einsatzgebiete
Typische Einsatzgebiete sind Simulatoren, Generatoren, sowie Systeme zur Diagnose und Prognose. Anwendungen der Logikprogrammierung finden sich beispielsweise in folgenden Bereichen:
Beispiele außerhalb der Informatik:
- Wirtschaft und Handel: Produktkonfigurator, Routenplaner, Marktsimulation (z.B. zur Preisfindung)
- Medizin: Diagnosesysteme
- Mathematik: Theorembeweiser und Theoremgeneratoren
- Naturwissenschaften: Auswerten und Abfragen geologischer und meteorologischer Datensammlungen, Simulatoren und Vorhersagesysteme für Wetter, Erdbeben und Wasserstände
- Technik: CAD, CAM
- Soziologie
- Psychologie
- Linguistik: Übersetzen natürlicher Sprache, Erkennen und Verstehen gesprochener Sprache
- und viele weitere
Auf dem Gebiet der Informatik und Computertechnik:
- Computertechnik: Design und Simulation von Prozessoren und Schaltkreisen
- Künstliche Intelligenz: Forschung, Expertensysteme, Übersetzen natürlicher Sprache, Erkennen gesprochener Sprache, Semantic Web
- Compilerbau
- Computerspiele: "intelligentes" Verhalten simulierter Mitspieler, Taktik, Strategie
- parallele Datenverarbeitung
- Dokumentenmanagement: Strukturierte Dokumente verarbeiten, Semantic Web, XSLT
- Rapid Prototyping
[Bearbeiten] Siehe auch
[Bearbeiten] Weblinks
- Antwortmengenprogrammierung (PDF) - knapper Überblick von der Entwicklung der klassischen Logik hin zur logischen Programmierung
- XSB (engl.) Logik-System und Deduktive Datenbank (Open Source)
- The Mercury Project (engl.) funktional-logische Programmiersprache
