Der Traum vom deklarativen Programmieren [abgeschlossen]

Warum wurde der Traum vom deklarativen Programmieren nicht verwirklicht? Welche konkreten Hindernisse stehen im Weg? Für ein einfaches Beispiel, warum kann ich nicht sagen

sort(A) is defined by sort(A) in perm(A) && asc(sort(A))

und automatisch einen Sortieralgorithmus daraus erhalten. permbedeutet Permutationen und ascbedeutet aufsteigend.

Es gibt einige sehr gute Antworten. Ich werde versuchen, zur Diskussion beizutragen.

Zum Thema deklarative, logische Programmierung in Prolog gibt es das großartige Buch "The Craft of Prolog" von Richard O'Keefe . Es geht darum, effiziente Programme mit einer Programmiersprache zu schreiben, mit der Sie sehr ineffiziente Programme schreiben können. In diesem Buch geht der Autor, während er die effiziente Implementierung mehrerer Algorithmen (im Kapitel "Methoden der Programmierung") diskutiert, folgendermaßen vor:

• Definieren Sie das Problem auf Englisch
• Schreiben Sie eine funktionierende Lösung, die so aussagekräftig wie möglich ist. Normalerweise bedeutet das ziemlich genau das, was Sie in Ihrer Frage haben, nur korrekter Prolog
• Ergreifen Sie von dort aus Schritte, um die Implementierung zu verfeinern und zu beschleunigen

Die (für mich) aufschlussreichste Beobachtung, die ich machen konnte, als ich mich durch diese Punkte arbeitete:

Ja, die endgültige Version der Implementierung ist viel effizienter als die "deklarative" Spezifikation, mit der der Autor begonnen hat. Es ist immer noch sehr aussagekräftig, prägnant und leicht zu verstehen. Was dazwischen passiert ist, ist, dass die endgültige Lösung Eigenschaften des Problems erfasst, auf das die ursprüngliche Lösung nicht eingegangen ist.

Mit anderen Worten, wir haben bei der Implementierung einer Lösung so viel Wissen wie möglich über das Problem verwendet. Vergleichen Sie:

Suchen Sie eine Permutation einer Liste, sodass alle Elemente in aufsteigender Reihenfolge angezeigt werden

zu:

Das Zusammenführen von zwei sortierten Listen führt zu einer sortierten Liste. Da es möglicherweise bereits sortierte Unterlisten gibt, sollten Sie diese anstelle von Unterlisten der Länge 1 als Ausgangspunkt verwenden.

Eine kleine Ausnahme: Eine Definition wie die, die Sie gegeben haben, ist attraktiv, weil sie sehr allgemein ist. Ich kann mich jedoch dem Gefühl nicht entziehen, die Tatsache, dass Permutationen ein kombinatorisches Problem sind, bewusst zu ignorieren. Das wissen wir schon ! Dies ist keine Kritik, nur eine Beobachtung.

Zur eigentlichen Frage: Wie geht es weiter? Eine Möglichkeit besteht darin, dem Computer so viel Wissen über das Problem zu vermitteln, das wir melden.

Der beste Versuch, den ich kenne, um das Problem wirklich zu lösen, wird in den von Alexander Stepanov mitverfassten Büchern "Elements of Programming" und "From Mathematics to Generic Programming" vorgestellt . Ich bin leider nicht in der Lage, alles in diesen Büchern zusammenzufassen (oder sogar vollständig zu verstehen). Der Ansatz besteht jedoch darin, effiziente (oder sogar optimale) Bibliotheksalgorithmen und Datenstrukturen zu definieren, sofern alle relevanten Eigenschaften der Eingabe im Voraus bekannt sind. Das Endergebnis ist:

• Jede wohldefinierte Transformation ist eine Verfeinerung der bereits vorhandenen Einschränkungen (der bekannten Eigenschaften).
• Wir lassen den Computer entscheiden, welche Transformation auf der Grundlage der vorhandenen Einschränkungen optimal ist.

Was den Grund angeht, warum es noch nicht so weit ist, ist die Informatik ein sehr junges Gebiet, und wir werden immer noch damit fertig, die Neuheit des größten Teils davon wirklich zu würdigen.

PS

Um Ihnen einen Eindruck davon zu geben, was ich unter "Verfeinern der Implementierung" verstehe: Nehmen Sie zum Beispiel das einfache Problem, das letzte Element einer Liste in Prolog zu erhalten. Die kanonisch deklarative Lösung lautet:

last(List, Last) :-
    append(_, [Last], List).

Hier ist die deklarative Bedeutung von append/3:

List1AndList2ist die Verkettung von List1undList2

Da append/3wir im zweiten Argument eine Liste mit nur einem Element haben und das erste Argument ignoriert wird (der Unterstrich), erhalten wir eine Teilung der ursprünglichen Liste, die den Anfang der Liste ( List1im Kontext von append/3) verwirft und dies verlangt Das Back ( List2im Kontext von append/3) ist in der Tat eine Liste mit nur einem Element: Es ist also das letzte Element.

In der tatsächlichen Implementierung von SWI-Prolog heißt es jedoch:

last([X|Xs], Last) :-
    last_(Xs, X, Last).

last_([], Last, Last).
last_([X|Xs], _, Last) :-
    last_(Xs, X, Last).

Das ist immer noch schön aussagekräftig. Lesen Sie von oben nach unten, heißt es:

Das letzte Element einer Liste ist nur für eine Liste mit mindestens einem Element sinnvoll. Das letzte Element für ein Paar aus dem Schwanz und dem Kopf einer Liste ist dann: der Kopf, wenn der Schwanz leer ist, oder der letzte des nicht leeren Schwanzes.

Der Grund, warum diese Implementierung bereitgestellt wird, besteht darin, die praktischen Probleme im Zusammenhang mit dem Ausführungsmodell von Prolog zu umgehen. Im Idealfall sollte es keinen Unterschied machen, welche Implementierung verwendet wird. Ebenso hätten wir sagen können:

last(List, Last) :-
    reverse(List, [Last|_]).

Das letzte Element einer Liste ist das erste Element der umgekehrten Liste.

Wenn Sie eine Fülle von nicht schlüssigen Diskussionen über das Gute, das deklarative Prolog führen möchten, gehen Sie einfach einige der Fragen und Antworten im Prolog-Tag zu Stack Overflow durch .

Logische Sprachen tun dies bereits. Sie können sort ähnlich definieren, wie Sie es tun.

Das Hauptproblem ist die Leistung. Computer können zwar viele Dinge gut verarbeiten, sind aber von Natur aus dumm. Jede "kluge" Entscheidung, die ein Computer treffen könnte, wurde von einem Programmierer programmiert. Und diese Entscheidung wird in der Regel nicht dadurch beschrieben, wie das Endergebnis aussieht, sondern wie dieses Endergebnis Schritt für Schritt erreicht werden kann.

Stellen Sie sich die Geschichte eines Golems vor . Wenn Sie versuchen, ihm einen abstrakten Befehl zu erteilen, wird er ihn bestenfalls ineffizient ausführen und im schlimmsten Fall sich selbst, Sie oder jemand anderes verletzen. Wenn Sie jedoch so detailliert wie möglich beschreiben, was Sie möchten, ist sichergestellt, dass die Aufgabe effektiv und effizient ausgeführt wird.

Es ist die Aufgabe des Programmierers, zu entscheiden, welche Abstraktionsebene verwendet werden soll. Wirst du für die Anwendung, die du erstellst, hochrangig vorgehen und sie auf abstrakte Weise beschreiben und den Leistungseinbruch hinnehmen oder niedrig und schmutzig werden, 10x mehr Zeit damit verbringen, aber einen Algorithmus erhalten, der 1000x leistungsfähiger ist?

Zusätzlich zu dem hervorragenden Punkt von Euphoric möchte ich hinzufügen, dass wir bereits deklarative Sprachen an vielen Stellen verwenden, an denen sie gut funktionieren, dh Zustände beschreiben, die sich wahrscheinlich nicht ändern, oder etwas anfordern, für das der Computer tatsächlich effizienten Code generieren kann allein:

• HTML deklariert den Inhalt einer Webseite.

• CSS legt fest, wie verschiedene Arten von Elementen auf einer Webseite aussehen sollen.

• Jede relationale Datenbank verfügt über eine Datendefinitionssprache, die die Struktur der Datenbank angibt.

• SQL ist eher deklarativ als imperativ, da Sie ihm sagen, was Sie sehen möchten, und der Abfrageplaner der Datenbank herausfindet, wie dies tatsächlich geschehen kann.

• Man könnte argumentieren, dass die meisten Konfigurationsdateien (.vimrc, .profile, .bashrc, .gitconfig) eine domänenspezifische Sprache verwenden, die weitgehend deklarativ ist

Abstraktionen sind undicht

Sie können ein deklaratives System implementieren, in dem Sie deklarieren, was Sie möchten, und der Compiler oder Interpretator ermittelt eine Ausführungsreihenfolge. Der theoretische Vorteil besteht darin, dass Sie nicht mehr über das 'Wie' nachdenken müssen und diese Implementierung nicht detailliert beschrieben werden muss. In der Praxis müssen Sie für das Allzweck-Computing jedoch immer noch über das 'Wie' nachdenken und alle Arten von Tricks schreiben, wobei Sie berücksichtigen müssen, wie dies implementiert wird, da der Compiler andernfalls eine Implementierung auswählen kann (und oft auch wird), die implementiert werden soll sehr, sehr, sehr langsam (zB n! Operationen, bei denen n ausreichen würde).

In Ihrem speziellen Beispiel erhalten Sie einen Sortieralgorithmus - das bedeutet nicht, dass Sie einen guten oder sogar etwas brauchbaren erhalten. Wenn Ihre angegebene Definition wörtlich (wie ein Compiler wahrscheinlich) implementiert wird, führt dies zu http://en.wikipedia.org/wiki/Bogosort, das für größere Datensätze unbrauchbar ist - es ist technisch korrekt, benötigt jedoch eine Ewigkeit, um tausend Zahlen zu sortieren .

Für einige eingeschränkte Domänen können Sie Systeme schreiben, die für die Ermittlung einer guten Implementierung fast immer von Vorteil sind, z. B. SQL. Für Allzweck-Computing, das nicht besonders gut funktioniert - Sie können Systeme beispielsweise in Prolog schreiben, aber Sie müssen visualisieren, wie genau Ihre Deklarationen am Ende in eine imperative Ausführungsreihenfolge konvertiert werden, und das verliert viel von dem erwarteten Deklarativ Programmiervorteile.

Rechenentscheidbarkeit ist der wichtigste Grund, warum deklarative Programmierung sich als nicht so einfach erwiesen hat, wie es scheint.

Viele Probleme, die relativ einfach zu benennen sind, haben sich als unentscheidbar erwiesen oder es ist eine NP-vollständige Komplexität zu lösen. Dies tritt häufig auf, wenn negative Klassen und Klassifikationen, Zählbarkeit und Rekursion berücksichtigt werden.

Ich möchte dies anhand einiger bekannter Domänen erläutern.

Die Entscheidung, welche CSS-Klasse verwendet werden soll, erfordert Kenntnisse und die Berücksichtigung aller CSS-Regeln. Das Hinzufügen neuer Regeln macht möglicherweise alle anderen Entscheidungen ungültig. Negative CSS-Klassen werden der Sprache aufgrund von NP-vollständigen Problemen absichtlich nicht hinzugefügt, aber das Fehlen negativer Klassen erschwert CSS-Entwurfsentscheidungen.

Innerhalb eines (SQL-) Abfrageoptimierers gibt es das lästige Problem, zu entscheiden, in welcher Reihenfolge verbunden werden soll, welche Indizes verwendet werden sollen und welcher Speicher welchen temporären Ergebnissen zugeordnet werden soll. Dies ist ein bekanntes NP-vollständiges Problem und erschwert das Datenbankdesign und die Abfrageformulierung. Um es anders zu formulieren: Beim Entwerfen einer Datenbank oder einer Abfrage muss der Designer die Aktionen und die Reihenfolge der Aktionen kennen, die der Abfrageoptimierer wahrscheinlich ausführen wird. Ein erfahrener Ingenieur benötigt Kenntnisse über die Heuristiken, die von großen Datenbankanbietern verwendet werden.

Konfigurationsdateien sind deklarativ, aber bestimmte Konfigurationen sind schwer zu deklarieren. Um beispielsweise Funktionen ordnungsgemäß zu konfigurieren, müssen Versionierung, Bereitstellung (und Bereitstellungsverlauf), mögliche manuelle Überschreibungen und mögliche Konflikte mit anderen Einstellungen berücksichtigt werden. Die ordnungsgemäße Überprüfung einer Konfiguration kann zu einem NP-vollständigen Problem werden.

Das Ergebnis ist, dass diese Komplikationen Anfänger überraschen, die Schönheit der deklarativen Programmierung sprengen und einige Ingenieure dazu bringen, nach anderen Lösungen zu suchen. Die Migration unerfahrener Ingenieure von SQL zu NoSQL wurde möglicherweise durch die zugrunde liegende Komplexität relationaler Datenbanken ausgelöst.

Wir haben einen Unterschied in der Deklarativität von Programmiersprachen, der für die Verifikation der digitalen Logik von Nutzen ist.

Normalerweise wird die digitale Logik auf der Registertransferebene (RTL) beschrieben, auf der der Logikpegel der Signale zwischen den Registern definiert ist. Um zu überprüfen, dass wir zunehmend Eigenschaften hinzufügen, die abstrakter und deklarativer definiert sind.

Eine der deklarativeren Sprachen / Sprachuntergruppen heißt PSL für Property Specification Language. Beim Testen eines RTL-Modells eines Multiplikators, in dem beispielsweise alle logischen Verknüpfungen von Verschieben und Addieren über mehrere Taktzyklen spezifiziert werden müssen; Sie können eine Eigenschaft in der Art von schreiben assert that when enable is high, this output will equal the multiplication of these two inputs after no more than 8 clock cycles. Die PSL-Beschreibung kann dann zusammen mit der RTL in einer Simulation überprüft werden, oder es kann formal nachgewiesen werden, dass die PSL für die RTL-Beschreibung gilt.

Das deklarativere PSL-Modell zwingt dazu, dasselbe Verhalten wie die RTL-Beschreibung zu beschreiben, jedoch auf eine ausreichend unterschiedliche Weise, die automatisch anhand der RTL überprüft werden kann, um festzustellen, ob sie übereinstimmt.

Meistens liegt das Problem darin, wie Sie die Daten modellieren. und deklaratives Programmieren hilft hier nicht. In imperativen Sprachen haben Sie bereits Tonnen von Bibliotheken, die viele Dinge für Sie erledigen, sodass Sie nur wissen müssen, wie Sie sie anrufen sollen. In gewisser Weise könnte man diese deklarative Programmierung in Betracht ziehen (das wahrscheinlich beste Beispiel dafür ist die Stream-API in Java 8 ). Damit ist die Abstraktion bereits aufgelöst und eine deklarative Programmierung ist nicht erforderlich.

Wie bereits gesagt, machen Logik-Programmiersprachen genau das, was Sie wollen. Man könnte sagen, das Problem ist die Leistung, aber mit der heutigen Hardware und Forschung auf diesem Gebiet können die Dinge verbessert werden, um für den produktiven Einsatz bereit zu sein. Eigentlich wird Prolog für KI-Sachen verwendet, aber ich glaube nur von Akademikern.

Es ist zu beachten, dass es für allgemeine Programmiersprachen gilt. Für domänenspezifische Sprachen sind deklarative Sprachen viel besser. SQL ist wahrscheinlich das beste Beispiel.

Es würde ungefähr so ​​aussehen .. {(was auch immer => eine Datei lesen und eine URL aufrufen) | eine URL aufrufen und eine Datei lesen} Dies sind jedoch auszuführende Aktionen, und der Status des Systems ändert sich infolgedessen, was jedoch aus der Quelle nicht ersichtlich ist.

Deklarative können eine endliche Zustandsmaschine und ihre Übergänge beschreiben. Das FSM ist wie das Gegenteil von Deklarativen ohne Aktionen, auch wenn die einzige Aktion darin besteht, den Status in den nächsten Status zu ändern.

Der Vorteil dieser Methode besteht darin, dass Übergänge und Aktionen durch Prädikate angegeben werden können, die sich auf mehrere Übergänge und nicht nur auf einen beziehen.

Ich weiß, das klingt ein bisschen seltsam, aber 2008 habe ich einen Programmgenerator geschrieben, der diese Methode verwendet, und das generierte C ++ ist zwei- bis fünfzehnmal so groß wie der Quellcode. Ich habe jetzt über 75.000 Zeilen C ++ aus 20.000 Eingabezeilen. Dazu gehören zwei Dinge: Konsistenz und Vollständigkeit.

Konsistenz: Keine zwei Prädikate, die gleichzeitig wahr sein können, können inkonsistente Aktionen implizieren, wie sowohl x = 8 als auch x = 9, und auch keine unterschiedlichen nächsten Zustände.

Vollständigkeit: Die Logik für jeden Zustandsübergang wird angegeben. Es mag schwierig sein, diese auf Systeme mit N Unterzuständen mit> 2 ** N Zuständen zu überprüfen, aber es gibt interessante kombinatorische Methoden, die alles verifizieren können. 1962 schrieb ich Phase 1 einer Systemsorte für die 7070-Maschinen, wobei ich diese Art der bedingten Codegenerierung und des kombinatorischen Debugs verwendete. Von den 8.000 Zeilen dieser Art war die Anzahl der Fehler seit dem ersten Release für immer gleich Null!

Die zweite Phase, 12.000 Zeilen, wies in den ersten beiden Monaten über 60 Fehler auf. Dazu gibt es noch viel mehr zu sagen, aber es funktioniert. Wenn die Autohersteller diese Methode zur Überprüfung der Firmware verwenden würden, würden wir die Fehler, die wir jetzt sehen, nicht sehen.

Nicht alles kann deklarativ dargestellt werden.

Häufig möchten Sie den Ausführungsfluss explizit steuern

Zum Beispiel folgender Pseudocode: if whatever read a file call an URL else call an URL write a file Wie würden Sie ihn deklarativ darstellen?

Sicher, es gibt wahrscheinlich einige exotische Möglichkeiten, dies zu tun. Wie Monaden . Diese sind jedoch in der Regel umständlicher, komplizierter und weitaus weniger intuitiv als ihr prozeduraler Teil.

Alles läuft darauf hinaus, dass die "Interaktion" mit Ihrer Umgebung / Ihrem System nicht deklarativ ist. Alles, was mit I / O zu tun hat, ist im Wesentlichen prozedural. Sie müssen genau angeben, wann und was in welcher Reihenfolge geschehen soll.

Deklarativ ist großartig für alles, was sich nur auf die Berechnung bezieht. Wie bei einer Riesenfunktion setzt du X ein und erhältst Y. Das ist großartig. Ein Beispiel dafür ist HTML, die Eingabe ist Text, die Ausgabe ist das, was Sie in Ihrem Browser sehen.