Kann man die algorithmische Analyse automatisieren?

8

Hat jemand über die Möglichkeit einer Programmiersprache und eines Compilers nachgedacht, so dass der Compiler automatisch asymptotische Analysen im schlimmsten Fall durchführen kann? Der Anwendungsfall, an den ich denke, ist eine Programmiersprache, in der ich Code schreibe und kompiliere. Der Compiler teilt mir mit, dass mein Code beispielsweise in O (n ^ 2) ausgeführt wird. Dies geschieht, indem das getan wird, was die intelligenten Leute tun, die algorithmische Analysen durchführen, möglicherweise Schleifen zählen und so weiter.

  • Aufgrund des Anhaltens von Problemproblemen und da man Programme haben kann, die durch Verzahnung funktionieren, zum Beispiel Levins Algorithmus für SAT, der in Polynomzeit läuft, wenn P = NP, vermute ich, dass man die Programmiersprache möglicherweise so restriktiv gestalten muss, dass sie dies zulässt etwas wie das. Gibt es negative Ergebnisse, die bestimmte Arten von Programmiersprachen davon abhalten, solche Compiler zu haben?

  • Ich würde mich auch für Systeme interessieren, die keine exakte asymptotische Analyse liefern, sondern eine "interessante" Obergrenze.

  • Ich interessiere mich NICHT für Black-Box- und statistische Methoden, die aus Eingaben bestimmter Länge abtasten und herausfinden, wie lange das Programm dauert. Diese Methoden sind sehr interessant, aber sie sind nicht das, wonach ich suche. Ich interessiere mich für genaue Methoden, die ungefähre Grenzen geben können.

Ich wäre sehr dankbar, wenn mich jemand auf einige Hinweise zur Arbeit in dieser Richtung hinweisen könnte.

Manoj
quelle
5
Dies ist ein mögliches Duplikat der folgenden Frage: cstheory.stackexchange.com/questions/12585/…
cody
Die offensichtlichen Sprachen, die ausgeschlossen werden können, sind Turing vollständig, da das unentscheidbare Problem des Anhaltens in einer solchen Sprache liegt. dann führt dies zu der Frage, was ist eine begrenzte Sprache als Turing vollständig, für die dies möglich ist? aber wohl ist eine Sprache keine "Programmiersprache", es sei denn, sie ist vollständig. Daher ist ein solches Ziel im Grunde genommen theoretisch unmöglich ... es kann jedoch einige mildernde Ideen für Sprachen mit begrenzter Komplexität geben ...
vzn
n2n3
3
@Kaveh Ich bin nicht der Meinung, dass meine Frage ein Duplikat von "Sind Laufzeitgrenzen in P entscheidbar?" Ist. Ich wusste bereits, wie ich beweisen kann, dass dies unmöglich ist. Trotzdem danke, dass du mich auch auf diesen Thread aufmerksam gemacht hast! Allerdings ist es möglich , dass meine Frage ist eine doppelte Frage, wie cody hingewiesen.
Manoj
2
Als ich jung und naiv war, habe ich versucht, mit gcov einen Komplexitätsanalysator zu schreiben . Es gibt an, wie oft jede Zeile ausgeführt wurde. :) Gute Frage!
Pratik Deoghare

Antworten:

8

Die implizite Komplexität hat uns gelehrt, dass (einige) Komplexitätsklassen nach Typsystemen klassifiziert werden können, in dem Sinne, dass es Typsysteme gibt, die beispielsweise nur Polynomprogramme akzeptieren. Ein weiterer praktischer Ableger dieser Forschung ist RAML (Resource Aware ML), eine funktionale Programmiersprache mit einem Typsystem, das Ihnen genaue Informationen über die Laufzeiten ihrer Programme gibt. Es ist in der Tat präziser als die Big-O-Komplexität, da auch konstante Faktoren enthalten sind, die durch ein Kostenmodell für die Basisoperationen parametrisiert werden.

Sie denken vielleicht, dass dies Betrug ist: Sicherlich haben einige Algorithmen eine Komplexität, die sehr schwer genau zu berechnen ist. Wie könnte diese Sprache also die Komplexität ihrer Programme leicht bestimmen? Der Trick ist, dass es viele Möglichkeiten gibt, einen bestimmten Algorithmus auszudrücken, einige, die das Typsystem ablehnt (es lehnt einige gute Programme ab), und einige, die es vielleicht akzeptiert. Der Benutzer erhält die Welt also nicht kostenlos: Er muss keine Kostenschätzungen mehr berechnen, sondern muss herausfinden, wie Code auf eine vom System akzeptierte Weise ausgedrückt werden kann.

(Es ist immer der gleiche Trick wie bei Programmiersprachen, bei denen nur Berechnungen oder nachweisbare Sicherheitseigenschaften usw. beendet werden.)

Gasche
quelle
Danke, das ist eine sehr interessante Antwort. Ich werde mir RAML genauer ansehen.
Manoj
7

Das von der COSTA-Forschungsgruppe entwickelte COSTA-Tool macht genau das, was Sie wollen. Bei einem gegebenen Programm (im Java-Bytecode-Format) erstellt das Tool eine Kostengleichung basierend auf einem vom Programmierer bereitgestellten Kostenmodell. Das Kostenmodell kann Entitäten wie Laufzeit, Speichernutzung oder abrechnungsfähige Ereignisse (wie das Senden von Textnachrichten) umfassen. Die Laufzeitgleichung wird dann unter Verwendung eines speziellen Werkzeugs gelöst, um eine geschlossene Form, die Worst-Case-Obergrenze des Kostenmodells, zu erzeugen.

Natürlich funktioniert das Tool nicht in allen Fällen, indem entweder keine Laufzeitgleichung erstellt oder keine geschlossene Form gefunden wird. Das ist nicht überraschend.

Dave Clarke
quelle
2

Ich habe vor einiger Zeit über dieselbe Frage nachgedacht. Hier ist der Gedankengang, den ich hatte:

Wie Sie sagten, ist das Problem des Anhaltens ein Problem. Um dies zu vermeiden, benötigen wir eine Sprache, die nur Programme zulässt, die immer anhalten. Andererseits muss unsere Sprache ausdrucksstark genug sein, um die häufigsten Probleme zu lösen (z. B. sollte sie mindestens die gesamte Komplexitätsklasse EXP erfassen).

Schauen wir uns also die LOOP-Programme an. Ein LOOP-Programm wird immer angehalten und seine Ausdruckskraft geht weit über EXP hinaus - um eine bessere Vorstellung zu erhalten: Sie können jedes TM simulieren, für das die Laufzeitfunktion als LOOP-Programm ausgedrückt werden kann.

Jetzt können wir die Verschachtelungstiefe und die Größe der Anzahl der Wiederholungen für jede Schleife aus syntaktischer Sicht betrachten und haben einen Ausgangspunkt (wir wissen jedoch nicht, wie weit dies uns führt). Beachten Sie jedoch das folgende Problem:

f(n)

f(n)=yyny>n

p(n)nf(n)

y := n + 1
while not prime(y) 
    y++
return y

Wie machen wir das mit nur begrenzten Schleifen? Das Problem besteht nun darin, über eine Obergrenze für den Zahlenbereich nachzudenken, den wir suchen müssen.

 prime pa prime p:p<pp!+1

Meine Intuition hier ist, dass die einzige Information, die ein Compiler Ihnen geben kann, darin besteht, die Syntax, die am Ende vom Programmierer bereitgestellt wird, sorgfältig zu analysieren. Wenn der Compiler eine aussagekräftige Aussage über die zeitliche Komplexität eines Programms treffen kann, muss der Programmierer gezwungen werden, diese Informationen in das Programm aufzunehmen.

Der letzte Absatz ist jedoch subjektiv und es könnte sicherlich andere mögliche Ansätze geben, die interessante Ergebnisse liefern. Ich wollte nur eine Vorstellung davon geben, was mich auf diesem Weg nicht erwartet.

John D.
quelle
2
Die Verschachtelungstiefe von Schleifen ist hier das Hauptproblem, und die Komplexität erstreckt sich über die primitiven rekursiven Funktionen, siehe Die Komplexität von Schleifenprogrammen , Meyer & Ritchie, ACM '67 -Konferenz , dx.doi.org/10.1145/800196.806014 .
Sylvain
Vielen Dank. Ich denke, Sie machen hier einen guten Punkt. Es gibt ein Problem, wenn ich Schleifen des Typs ausführen werde, während (Prädikat = wahr) etwas tut, weil ich dann darüber streiten muss, wann das Prädikat zum ersten Mal falsch wird. Um meine Frage in dem von Ihnen festgelegten Kontext neu zu formulieren, frage ich mich, ob man eine Reihe von Grundelementen mit einer genau definierten Laufzeit entwerfen kann, die auf einfache Weise zusammengestellt werden können, um interessante Programme zu schreiben und Laufzeitgrenzen für sie zu erhalten . Vielleicht macht RAML bereits etwas davon, wie in der ersten Antwort hervorgehoben.
Manoj
1
Um mehr Hinweise dieser Art zu geben, wird Cobhams Die intrinsische Rechenschwierigkeit von Funktionen oft als eine der frühesten Arbeiten zur impliziten Komplexität angeführt: Sie charakterisiert FP mittels Rekursionsschemata. Neuere Arbeiten in dieser Richtung von Bellatoni & Cook finden Sie in Eine neue rekursionstheoretische Charakterisierung der Polytimefunktionen , Computational Complexity 1992. Siehe auch eine Umfrage von Hofmann in SIGACT News 31 (1): 31-42, 2000: dx.doi.org/10.1145/346048.346051 .
Sylvain
Danke Sylvain, ich schaue mir die Umfrage an! Ich war mir dieses Bereichs der impliziten Komplexitätstheorie bewusst, habe mich aber nie wirklich darum gekümmert, ihn zu studieren, da ich nicht weiß, was die grundlegende Frage ist, die sie zu beantworten versuchen. Jetzt habe ich mehr Motivation, diese Ideen zu verstehen!
Manoj