Deklarative Programmierung

In der Informatik ist die deklarative Programmierung ein Programmierparadigma , das die Logik einer Berechnung ausdrückt , ohne deren Kontrollfluss vollständig zu beschreiben . ^{[ 1 ]}

Sprachen, die diesen Stil zulassen, ermöglichen es Entwicklern, Seiteneffekte zu minimieren oder zu eliminieren, indem sie beschreiben, was das Programm im Hinblick auf die Problemdomäne leisten soll , anstatt die Umsetzung als Folge von Programmiersprachenprimitiven detailliert zu beschreiben (die konkrete Implementierung obliegt der jeweiligen Sprachimplementierung ). Dies steht im Gegensatz zur imperativen Programmierung , die Algorithmen in expliziten Schritten implementiert . ^{[ 2 ] [ 3 ]}

Die deklarative Programmierung kann Programme als Theorien einer formalen Logik und Berechnungen als Deduktionen dieser logischen Theorie betrachten. Die deklarative Programmierung vereinfacht mitunter das Schreiben paralleler Programme . ^{[ 4 ]}

Zu den gängigen deklarativen Sprachparadigmen gehören die logische Programmierung (z. B. Prolog , Datalog , Answer Set Programming ) und algebraische Modellierungssysteme .

Deklarative Programmierung wird oft als jeder Programmierstil definiert, der nicht imperativ ist. Eine Reihe anderer gängiger Definitionen versucht, sie durch einen einfachen Gegensatz zur imperativen Programmierung zu definieren. Zum Beispiel:

• Ein übergeordnetes Programm, das beschreibt, was eine Berechnung leisten soll.
• Jede Programmiersprache, die keine Seiteneffekte hat , oder genauer gesagt, die referenzielle Transparenz aufweist .
• Eine Sprache mit einer klaren Entsprechung zur mathematischen Logik . ^{[ 5 ]}

Diese Definitionen überschneiden sich erheblich.

Deklarative Programmierung ist ein nicht-imperativer Programmierstil, bei dem Programme ihre gewünschten Ergebnisse beschreiben, ohne Befehle oder auszuführende Schritte explizit aufzulisten. Logische Programmiersprachen zeichnen sich durch einen überwiegend deklarativen Programmierstil aus. In der logischen Programmierung bestehen Programme aus Sätzen in logischer Form, und die Berechnung verwendet diese Sätze, um Probleme zu lösen, die ebenfalls in logischer Form ausgedrückt werden.

In einer rein funktionalen Sprache wie Haskell haben alle Funktionen keine Seiteneffekte , und Zustandsänderungen werden ausschließlich durch Funktionen dargestellt, die den Zustand transformieren. Dieser Zustand wird explizit als Objekt erster Klasse im Programm repräsentiert. Obwohl rein funktionale Sprachen nicht-imperativ sind, bieten sie oft die Möglichkeit, die Wirkung einer Funktion als Folge von Schritten zu beschreiben. Andere funktionale Sprachen wie Lisp , OCaml und Erlang unterstützen eine Mischung aus prozeduraler und funktionaler Programmierung.

Einige logische Programmiersprachen, wie Prolog , und Datenbankabfragesprachen, wie SQL, sind zwar im Prinzip deklarativ, unterstützen aber auch einen prozeduralen Programmierstil.

Deklarative Programmierung ist ein Oberbegriff , der eine Reihe bekannterer Programmierparadigmen umfasst .

Die Constraint-Programmierung beschreibt Beziehungen zwischen Variablen in Form von Constraints, die die Eigenschaften der Ziellösung festlegen. Die Constraints werden gelöst , indem jeder Variable ein Wert zugewiesen wird, sodass die Lösung mit der maximalen Anzahl an Constraints übereinstimmt. Die Constraint-Programmierung ergänzt häufig andere Paradigmen wie die funktionale, logische oder auch imperative Programmierung.

Makefiles beispielsweise spezifizieren Abhängigkeiten deklarativ ^{[ 6 ]} , enthalten aber auch eine imperative Liste auszuführender Aktionen. Ähnlich spezifiziert yacc eine kontextfreie Grammatik deklarativ, bindet aber Code-Snippets aus einer Hostsprache ein, die üblicherweise imperativ ist (wie z. B. C ).

Logische Programmiersprachen wie Prolog , Datalog und Answer-Set-Programmierung berechnen Ergebnisse, indem sie beweisen, dass ein Ziel eine logische Konsequenz des Programms ist, oder indem sie zeigen, dass das Ziel in einem durch das Programm definierten Modell wahr ist. Prolog berechnet Ergebnisse, indem es Ziele in Teilziele zerlegt (Top-Down-Ansatz mit Rückwärtslogik ), während die meisten Datalog-Systeme Bottom-Up-Ansatz mit Vorwärtslogik verwenden . Answer-Set-Programme nutzen typischerweise SAT-Solver, um ein Modell des Programms zu generieren.

Modelle oder mathematische Darstellungen physikalischer Systeme lassen sich in deklarativem Computercode implementieren. Dieser Code enthält Gleichungen anstelle von imperativen Zuweisungen, die die Verhaltensbeziehungen beschreiben („deklarieren“). Durch die Verwendung dieses Formalismus kann ein Computer algebraische Manipulationen durchführen, um den Lösungsalgorithmus optimal zu formulieren. Die mathematische Kausalität wird typischerweise an den Grenzen des physikalischen Systems definiert, während die Verhaltensbeschreibung des Systems selbst deklarativ oder akausal ist. Beispiele für deklarative Modellierungssprachen und -umgebungen sind Analytica , Modelica und Simile . ^{[ 7 ]}

Prolog (1972) steht für „PROgramming in LOGic“. Es wurde für die Beantwortung von Fragen in natürlicher Sprache entwickelt ^{[ 8 ]} und verwendet SL-Resolution ^{[ 9 ]} sowohl zum Ableiten von Antworten auf Anfragen als auch zum Parsen und Generieren von Sätzen in natürlicher Sprache.

Die Bausteine ​​eines Prolog-Programms sind Fakten und Regeln . Hier ist ein einfaches Beispiel:

Katze ( Tom ). % Tom ist eine Katze. Maus ( Jerry ). % Jerry ist eine Maus.Tier ( X ) : Katze ( X ). % Jede Katze ist ein Tier. Tier ( X ) : Maus ( X ). % Jede Maus ist ein Tier.groß ( X ) :- Katze ( X ). % Jede Katze ist groß. klein ( X ) :- Maus ( X ). % Jede Maus ist klein.eat ( X , Y ) : Maus ( X ), Käse ( Y ). % Jede Maus frisst jeden Käse. eat ( X , Y ) : Groß ( X ), Klein ( Y ). % Jedes große Wesen frisst jedes kleine Wesen.

Bei diesem Programm ist die Anfrage erfolgreich, während sie fehlschlägt. Darüber hinaus ist die Anfrage mit der Antwortsubstitution erfolgreich . eat(tom,jerry)eat(jerry,tom)eat(X,jerry)X=tom

Prolog führt Programme von oben nach unten aus und nutzt die SLD-Resolution, um rückwärts zu argumentieren und Ziele auf Teilziele zu reduzieren. In diesem Beispiel verwendet es die letzte Regel des Programms, um das Ziel, die Anfrage zu beantworten, auf die Teilziele zu reduzieren: zuerst ein X zu finden, sodass gilt, und dann zu zeigen, dass gilt. Es verwendet wiederholt Regeln, um Teilziele weiter auf andere Teilziele zu reduzieren, bis es schließlich gelingt, alle Teilziele mit Fakten im Programm zu vereinheitlichen . Diese Strategie des rückwärtsgerichteten Denkens und der Zielreduktion behandelt Regeln in Logikprogrammen als Prozeduren und macht Prolog sowohl zu einer deklarativen als auch zu einer prozeduralen Programmiersprache . ^{[ 10 ]}eat(X,jerry)big(X)small(jerry)

Die breite Palette an Prolog-Anwendungen wird im Buch „Year of Prolog“ ^{[ 11 ]} hervorgehoben, das anlässlich des 50-jährigen Jubiläums von Prolog erscheint.

Die Ursprünge von Datalog reichen bis zu den Anfängen der logischen Programmierung zurück, doch erst um 1977 wurde es als eigenständiges Gebiet etabliert . Syntaktisch und semantisch ist es eine Teilmenge von Prolog. Da es jedoch keine zusammengesetzten Terme unterstützt , ist es nicht Turing-vollständig .

Die meisten Datalog-Systeme führen Programme von unten nach oben aus, indem sie Regeln verwenden, um vorwärts zu argumentieren , neue Fakten aus bestehenden Fakten abzuleiten und zu beenden, wenn keine neuen Fakten mehr abgeleitet werden können oder wenn die abgeleiteten Fakten mit der Abfrage übereinstimmen.

Datalog wurde bereits für Probleme wie Datenintegration , Informationsextraktion , Netzwerktechnik , Sicherheit , Cloud Computing und maschinelles Lernen eingesetzt . ^{[ 12 ] [ 13 ]}

Answer Set Programming (ASP) entwickelte sich Ende der 1990er Jahre auf Basis der stabilen Modellsemantik (Antwortmengensemantik) der logischen Programmierung. Wie Datalog ist es eine Teilmenge von Prolog; und da es keine zusammengesetzten Terme unterstützt, ist es nicht Turing-vollständig.

Die meisten Implementierungen von ASP führen ein Programm aus, indem sie zunächst das Programm grundieren , alle Variablen in den Regeln auf alle möglichen Arten durch Konstanten ersetzen und dann einen propositionalen SAT-Solver wie den DPLL-Algorithmus verwenden, um ein oder mehrere Modelle des Programms zu generieren.

Seine Anwendungsgebiete zielen auf die Lösung schwieriger Suchprobleme und die Wissensrepräsentation ab . ^{[ 14 ] [ 15 ]}

• Induktive Programmierung
• Liste deklarativer Programmiersprachen

• Frans Coenen. Charakteristika deklarativer Programmiersprachen . 1999.
• Robert Harper .
  • Was, wenn überhaupt, ist eine deklarative Sprache? . 2013.
  • „ Es gibt so etwas wie eine deklarative Sprache, und sie ist die beste domänenspezifische Sprache der Welt .“ 2013.
• Olof Torgersson. Eine Anmerkung zu deklarativen Programmierparadigmen und der Zukunft der definitorischen Programmierung . 1996.