Warum ist es unmöglich zu bauen, einen compiler, der bestimmen kann, ob eine C++ - Funktion, ändert sich der Wert einer bestimmten Variablen?

Lese ich diese Zeile in einem Buch:

Es ist nachweislich unmöglich, zu bauen, einen compiler, der kann eigentlich
bestimmen, ob oder ob nicht eine C++ - Funktion, ändert sich der Wert eines
bestimmte variable.

Wurde der Absatz darum, warum der compiler ist konservativ, wenn die Prüfung für const-ness.

Warum ist es unmöglich, den Bau eines solchen compiler?

Kann der compiler überprüfen Sie immer, ob eine variable zugewiesen wird, eine nicht-const-Funktion aufgerufen wird, oder wenn es weitergegeben wird in eine nicht-const-parameter...

  • Erste Sache, die kommt meiner Meinung dynamic link libraries. Wenn ich kompilieren von code auf meinem Rechner, und kompilieren Sie code auf Ihrem Rechner, und wir verknüpfen zur Laufzeit, wie könnte dein compiler wissen, ob ich die modifizierten Variablen oder nicht?
  • Wenn ich bitten Sie für die Eingabe in mein Programm und basiert auf, dass ich entweder ändern oder nicht ändern, eine bestimmte variable. Dann kann nie vorausgesagt werden zur compile-Zeit, ob ich den Wert der variable nicht. Es könnte, aber Sie kann nicht sicher sagen, es "wird".
  • Genau dieses. Mehr breit, die der compiler nicht kompilieren der Funktion einzeln, aber kompiliert es als Teil eines umfassenderen Bildes, die möglicherweise nicht alle innerhalb der compiler-Bereich.
  • aber ich bin nicht immer, warum jemand wollen, um zu wissen, dass die Funktion ändern sich einige Werte während der Ausführung,da gibt es einige andere Möglichkeiten, um die Spur der Zustand der Variablen oder den Wert.
  • MooingDuck Hat code-Objekt markieren, wenn eine bestimmte Funktion ist const? Auch in Ihrem header-Datei, wenn Sie markiert eine oder mehrere Ihrer Funktionen als const oder einen der Parameter const, der compiler kann dann bestimmen, wenn der code ändert Variablen oder nicht. Richtig? Wenn ja, dann auch wenn Sie kompiliert deinen code an Ihre Maschine, und Sie gab mir Ihre Kopf, mein compiler kann ermitteln, ob die variable geändert wird oder nicht. Richtig?
  • "unmöglich" ist vielleicht eine übertreibung - "rechnerisch unmöglich" (wie im NP-hart) eine bessere Charakterisierung, ist aber ein wenig schwieriger für die Schüler zu fassen. Stellen Sie sich eine Link-Liste oder andere abstrakte Datenstruktur. Wenn ich eine Funktion aufzurufen, die änderungen, die man Knoten in der Liste/Baum/was auch immer, wie kann ein compiler jemals hoffen, um zu beweisen genau, welche Knoten geändert habe (und was vielleicht noch wichtiger ist, welche nicht), ohne im wesentlichen vollständig zu simulieren, das Programm mit den erwarteten Eingang, alle zwar nicht unter 3 Tagen zu kompilieren eine source-Datei...
  • Unmöglich ist keine übertreibung, das Halteproblem gilt hier mehrere Antworten erklären. Es ist einfach nicht möglich, algorithmisch vollständig analysieren zu einem Allgemeinen Programm.
  • Wie vereinbart, für die ganz Allgemeine/willkürliche Fall. Jedoch, viele gut ausgebaute Programme ordnungsgemäße überprüfung der Eingabe nicht zu tun haben mit "beliebige Eingabe", und so kann nicht von Instanzen der vollständige Halteproblem, aber einige reduzierte Teilmenge, die möglicherweise sehr gut nachweisbar, wenn auch nicht unbedingt effizient...
  • Compiler, die nur kompilieren eine Teilmenge der gültigen Programme sind nicht sehr nützlich.
  • Ich Stimme zu, es ist definitiv eine subsprache, wo das Halteproblem nicht gelten. Aber von Turing ' s Beweis wir können folgern, dass solche subsprache ist nicht mehr turing-vollständig, also wirklich nicht so interessant.
  • Wenn der Compiler könnte diese Art von Analyse darüber, wie sich ein Programm verhält, würden wir nicht brauchen, um ausführen unserer Programme. (Ich bin mir sicher, dass ist ein grober overgeneralization.)
  • Ich denke, das ist eine Variante der so genannten "Halteproblem". Gegeben ein beliebiges Programm in einem genügend reiche Programmier-Sprache ist es unmöglich zu bestimmen, ob die Kontrolle überhaupt fließt durch einen bestimmten Punkt. Beachten Sie, dass dies nicht einfach "schwierig", es ist wirklich unmöglich.
  • Sie scheinen zu vergessen, dass dies keine reinen Mathe-problem - "Das problem ist, zu bestimmen, da ein Programm und einen input an das Programm, ob das Programm irgendwann stoppen, wenn mit diesem Eingang." Wenn einer sagt: "Während die Entscheidung, ob diese Programme (wie "Hallo Welt") die Einstellung ist einfach, komplexere Programme als problematisch erweisen." - dies bedeutet, dass Sie gehen in das Gebiet der mathematischen Logik.
  • Während eine "richtige" compiler sollte in der Lage sein zu kompilieren jede gültige Programm, die Teilmenge der gültigen Programme, die wirklich nützlich sind, ist sehr klein (aber immer noch unendlich, und keine mögliche Art und Weise zu charakterisieren, den Satz), so ist auch eine "gebrochene" compiler beherrscht nur "nützliche" Programme (was auch immer das bedeutet) ist noch... die Meisten Compiler bemühen, "richtig" ist, aber aufgrund von bugs und anderen Unzulänglichkeiten nie ganz komplett, dieses Ziel zu erreichen...
  • void UserChange() { int* p; scanf("%p", &p); (*p)++; } unmöglich zu sagen, was hier geändert werden zur Laufzeit.
  • Das Buch ist text, ist unklar, welche verschleiert das Problem. Es ist der Versuch zu sagen, "Holen wir uns eine unendliche Anzahl von Affen, die schreiben jeden erdenklichen C++ - Funktion, die jemals geschrieben werden. Es wird Fälle geben, wo, wenn wir wählen eine variable, die (einige bestimmte Funktion, die Affen geschrieben) verwendet, können wir nicht herausfinden, ob die Funktion ändern, die variable." Natürlich für einige (sogar viele) Funktionen in einer bestimmten Anwendung, diese kann bestimmt werden, indem der compiler, und sehr leicht. Aber nicht für alle (oder unbedingt die meisten).
  • Aus demselben Grund kann man nicht erkennen, Endlosschleife, (können Sie feststellen, es gibt eine Pause-Taste auf der Tastatur, die Sie drücken müssen, selbst wenn man glaubt, dass Sie Ihren code in Endlosschleife)
  • Kann jemand erklären warum der Letzte Satz meiner Frage falsch ist? Warum ist diese Prüfung nicht genug? Hier ist die Letzte Frage: Der compiler kann immer überprüfen, ob seine zugewiesen wird, eine nicht-const-Funktion aufgerufen wird, oder wenn es weitergegeben wird in eine nicht-const-parameter. Warum ist diese Prüfung nicht ausreichend, um zu bestimmen, const-ness?

InformationsquelleAutor Cricketer | 2013-07-01
  1. 139

    Warum ist es unmöglich, den Bau eines solchen compiler?

    Aus dem gleichen Grund kann man nicht ein Programm schreiben, dass wird bestimmen, ob ein bestimmtes Programm beendet wird. Dies ist bekannt als die Halteproblem, und es ist eines jener Dinge, die nicht berechenbar sind.

    Klar zu sein, Sie können schreiben Sie einen compiler, der bestimmen kann, dass eine Funktion ändert die variable in einigen Fällen, aber Sie können nicht schreiben, eine, die zuverlässig sagt Ihnen, dass das funktionieren wird oder nicht, ändern Sie die variable (oder halt), für alle möglichen Funktionen.

    Hier ist ein einfaches Beispiel:

    void foo() {
    if (bar() == 0) this->a = 1;
}

    Wie kann ein compiler bestimmen, nur aus der Betrachtung, dass der code, ob foo jemals ändern wird a? Ob es tut oder nicht, hängt von den Bedingungen der externen auf die Funktion, nämlich die Umsetzung der bar. Es ist mehr als das, um den Beweis, dass das Halteproblem nicht berechenbar ist, aber es ist schon schön erklärt in dem verlinkten Wikipedia-Artikel (und in jedem Berechnungs-Theorie-lehrbuch), also werde ich nicht versuchen zu erklären, es richtig hier.

    • +1 Du triffst den Nagel auf dieses Ding !
    • Würde diese änderung mit der richtigen quantum computing algorithmen? Es klingt wie eine perfekte Anwendung für Quantencomputer.
    • Quanten-Computer sind "nur" exponentiell schneller für manche Probleme können Sie nicht lösen unentscheidbaren Probleme.
    • Diese exponentiell komplizierter algorithmen (wie factoring) ist perfekt für Quantencomputer, aber Halteproblem ist ein logisches dilemma, es ist nicht berechenbar, egal, welche Art von "computer", die Sie haben.
    • nur ein Klugscheißer, ja, es würde sich ändern. Leider, es bedeutet, dass der Algorithmus terminiert und läuft immer noch, leider, man kann nicht sagen, welche, ohne direkt zu beobachten, durch die Sie Einfluss auf den tatsächlichen Zustand.
    • Können Sie erklären, warum ist das ein problem, dasselbe wie das Halteproblem?
    • Um zu entscheiden, wenn eine Funktion zurückgeben einen Wert, Sie haben zu bestimmen, wenn die Funktion beenden kann. In dem gegebenen Beispiel, ist es notwendig zu wissen, ob es existiert ein Szenario, in dem bar() 0 zurück. Dies erfordert die Lösung der Halteproblem.
    • Ich glaube nicht, dass du berufen das Halteproblem erklären diese Einschränkung. Ist es nicht ausreichend, nur zu sagen, dass eine Funktion ändern könnte, eine variable oder nicht-je nach Laufzeit-Bedingungen, die zur Kompilierzeit nicht bekannt? E. g. foo(int x) { if (x < 1) a = 3;
    • Als die höchste stimmten die Antworten ich denke, dies sollte auch darüber reden, aliasing...
    • "... Sie können nicht schreiben, ein Programm, das ermitteln, ob ein bestimmtes Programm wird beendet" - ohne tatsächlich ausführen das Programm ist.
    • O. K., also, angenommen, ich bin ein Programm ausführt. Wie genau kann ich ermitteln, ob Sie kündigen?
    • Aber wenn Sie tatsächlich führen Sie das Programm, und es nicht beenden (z.B. eine Endlosschleife), wird man nie herausfinden, dass es nicht beenden... Sie nur immer auf die Ausführung noch einen Schritt weiter, denn es könnte der Letzte sein...
    • Gute Antwort, @Caleb. Es kann sein, erwähnenswert, jedoch, dass, während es ist unmöglich zu schreiben, einen compiler, der kann bestimmen, ob oder nicht eine Funktion ändert die variable für alle mögliche Funktionen, ist es möglich, einen compiler erstellen kann bestimmen, dass gewissen Funktionen ändern wird eine varaible, oder Sie werden es nie ändern, eine variable.
    • Grundsätzlich ist die Aussage in der ursprünglichen Frage ist nicht bedeutet, dass ein compiler, bei der Frage "Funktioniert das ändern von X?" kann immer nur Antworten "ich weiß es nicht." Aber, was es nicht bedeutet ist, dass der Compiler die Funktionen in "ja", "Nein" und "ich weiß nicht" Kategorien, aber für die Menge aller möglichen funtion "ich weiß nicht" - Kategorie kann niemals leer sein; es wird immer etwas Funktionen, für die kann es nicht sagen.
    • Danke, @DaveL. Ich habe versucht, so zu schreiben, als viel-ich betont in einigen Fällen. Siehe auch meine Antwort auf twalberg Kommentar auf die Frage.
    • nicht der Punkt. Sie können bestimmen, FALLS es wird beendet, ohne laufen, bis es beendet wird.
    • Sie können auch nicht bestimmen, FALLS wird beendet durch ausgeführt, bis es beendet wird, weil-was, wenn es nicht? In anderen Worten-man kann nicht ein Programm schreiben, dass untersucht einige andere Programm und wird garantiert zu drucken "Halte," wenn es halte und "nicht halt", wenn nicht.
    • Ich bin damit einverstanden, denn selbst wenn Sie nachweisen können, dass eine Funktion unterbrochen, können Sie immer noch nicht in der Lage sein zu beweisen, dass Sie nicht ändern, eine variable.
    • Die Anbindung an das Halteproblem ist nicht, dass Sie nicht entscheiden kann, dass die Funktion angehalten wird oder nicht (obwohl es das auch), ist es, dass Sie sich nicht entscheiden können für alle gültigen Funktionen, ob eine gegebene Funktion bedeutet beliebiger spezifische Sache. Das gleiche argument (wirklich nicht die, die ich oben), der beweist, dass Sie sich nicht entscheiden können über anhalten kann auch verwendet werden, um zu zeigen, dass Sie sich nicht entscheiden können, ob Sie die Funktion ruft eine Funktion, eine variable ändert, etc. nightcracker Antwort verdeutlicht dies sehr schön.
    • Aliasing erhöht die Komplexität, aber das problem bleibt, auch wenn Sie entfernen von aliasing. Ich konzentriere auf die Tatsache, dass der compiler nicht genügend Informationen, weil es leicht zu verstehen, und auf das Halteproblem, da es Dichtungen der deal. Aber eine andere Antwort Abdeckung aliasing wäre sicherlich hilfreich.
    • Es scheint einige Verwirrung zwischen dem Halteproblem - was bedeutet, dass es gibt einige Dinge, die uncomputable Fragen und Schwierigkeiten (z.B. NP-schwere Probleme), die unpraktisch zu berechnen. Das Halteproblem ergibt sich aus einer fundamentalen Eigenschaft der informatik (und in der Tat Mathematik, die computing ist eine Teilmenge - siehe en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorem) - dies ist eine Funktion des Programms, und den Eingang - auch das wissen Sie beide nicht, ob das Programm angehalten wird.
    • M - Sie können sagen, dass "Hallo Welt" - Programm wird halt sehr schnell. Dies ist eine grundlegende Eigenschaft des computing.
    • Wenn Sie "Hello world" warten auf externes Ereignis zu kündigen, dem wird es unmöglich sein, um vorherzusagen, ob es wird jemals aufhören, weil externe Ereignisse können nicht passieren.

    InformationsquelleAutor Caleb
  2. 124

    Vorstellen, wie compiler existiert. Lassen Sie uns auch davon ausgehen, dass für die Bequemlichkeit es bietet eine Bibliothek-Funktion, die 1 zurückgibt, wenn die übergebene Funktion ändert eine gegebene variable ist und 0, wenn die Funktion nicht. Was soll dann mit diesem Programm drucken?

    int variable = 0;

void f() {
    if (modifies_variable(f, variable)) {
        /* do nothing */
    } else {
        /* modify variable */
        variable = 1;
    }
}

int main(int argc, char **argv) {
    if (modifies_variable(f, variable)) {
        printf("Modifies variable\n");
    } else {
        printf("Does not modify variable\n");
    }

    return 0;
}
    • Schön! ich bin ein Lügner-Paradoxon wie geschrieben von einem Programmierer.
    • Es ist eigentlich nur eine nette adaption des berühmten Beweis für die nicht-entscheidbarkeit des Halteproblem.
    • In diesem konkreten Fall "modifies_variable" sollte true zurückgeben: gibt Es mindestens einen Ausführungspfad, in denen die variable ist in der Tat geändert. Und, dass die Ausführung Pfades erreicht ist, nachdem ein Anruf zu einem externen, nicht-deterministische Funktion - also die ganze Funktion ist nicht-deterministisch. Für diese 2 Gründe, der compiler sollte die pessimistisch ansehen und entscheiden, dass es ändern Sie die variable. Wenn der Pfad geändert wird, die variable wird nach erreichen einer deterministischen Vergleich (nachprüfbar durch den compiler) ergibt false (d.h. "1==1") dann compiler könnte sicher sagen solche Funktion nie ändert, die variable
    • Wie ist, dass die pessimistische Sicht? Wenn es war, sagen wir, aktuelle Mikrosekunde statt einer beliebigen Ganzzahl, wäre das nicht das "pessimistische" Sicht "es ist immer noch das selbe"? Sie scheinen die modifies_variable() viel mehr wissen, als es tatsächlich ist...
    • Die Frage ist, ob f ändert sich die variable nicht, ob Sie es ändern könnte, die variable. Diese Antwort ist richtig.
    • was ist, wenn modifies_variable funktioniert für alle Funktionen außer sich selbst.
    • Nicht ändern würde, ist die Antwort. Es heißt auf f hier, nachdem alle. Und Nein, man kann nicht einfach so beheben, dass durch das Verbot der indirekten Aufrufe so gut.
    • genau. Dieses problem ist mindestens so schwierig wie das Halteproblem, da der compiler muss in der Lage sein zu entscheiden, ob oder nicht ein Programm wird angehalten, bevor eine variable geändert wird, um zu sehen, ob die variable wirklich geändert.
    • Erstens ist dies nicht ganz das problem, sollte modifies_variable(f, Variablen). Zweitens nehmen wir an, dass modifies_variable() ist durchaus plausibel, wenn man betrachtet eine Funktion von außen. Auch in diesem (unmöglichen) Fall würde der compiler eine endlos-Schleife. Ich denke, das verschleiert eher, als Höhepunkte das problem durch die Einführung der Rekursion enthält der test. Ein einfacheres Beispiel wäre einfach eine Funktion, die bestimmt, dessen Ausführungspfad durch die Funktion " rand() oder eine andere externe nicht-statisch auswertbaren Faktor, das ist, was das ursprüngliche Buch wurde versucht zu vermitteln und zu scheitern.
    • Sie den ersten Punkt über modifies_variable(f, variable) ist wahr, aber ich hielt die "API -" so einfach wie möglich für Klarheit. Ihr zweiter Punkt, den ich nicht akzeptiere. Beachten Sie, dass das Buch sagte, es ist nachweislich unmöglich. Für mich ist es klar, dass das Buch versucht zu vermitteln, den mathematischen Aspekt und der Bezug zum Halteproblem/ähnliche Probleme. Und während Sie mit einem nicht-statisch auswertbaren Faktor - wie ein geiger-Zähler angeschlossen an den PC - das wäre eine einfachere und leichter verständliche Aspekt des Problems nicht in der grundsätzlichen Unmöglichkeit dieses problem.
    • In Bezug auf den mathematischen Aspekt, es ist theoretisch möglich zu "lösen" das Halteproblem gegeben sei ein (völlig deterministischen) Turing-Maschine und einem deterministischen Programm mit Zugriff auf eine beschränkte (als im endlichen) Menge von Speicher. Argumente gegen diese nach unten kommen, um Zeit und Maßstab eher als mathematischen Beweis (ironisch). Die am besten zugänglichen (und verkehrsgünstig, zentral) - Elemente, dieses problem für die Programmierer, bleiben die Aspekte der nicht-deterministische Programme.
    • große Reduzierung von "modify variable", um das Halteproblem. Sehr konkreter Ansatz!
    • die Antwort auf die Frage "hat f ändern Sie die variable" wir müssen wissen, was "modifies_variable" selbst. Der compiler weiß nicht seinen code, oder, wenn es deterministisch ist, und kann nicht ausgeführt werden es bei der Kompilierung zu wissen, was es würde nachgeben. Stell dir vor "modifies_variable" war wirklich eine Funktion, die Anfragen der Benutzer zu beantworten "y/n" und gibt eine 1 oder 0, die Grundlage. Die Funktion f ändern Sie die variable oder nicht, basierend auf einem externen, code-undurchsichtig, nicht deterministische Funktion. So ein anständiger compiler sollte im Herbst auf der sicheren Seite und nehme an, es bedeutet, gelegentlich ändern.
    • Nein, eher das Gegenteil: ich mache, der compiler wirklich unwissend auf was modifies_variable ist über die Absicht, zu markieren mein Punkt: die Entscheidung, ob eine variable kann modifiziert oder nicht hängt wirklich davon ab, die Funktion (und die Funktionen, die es nennen kann) wird deterministisch ist oder nicht. Wenn alle möglichen Ausführungspfade deterministisch sind dann für eine Konstante Eingangs-compiler ausführen könnte zur compile-Zeit und wissen sicher, wenn die variable geändert wird oder nicht. Wenn Sie eine nicht-det. Funktionsaufruf in der Mitte (oder Ihre Eingabe hängt von einer externen Quelle) alles, was Sie wissen, ist Sie nichts wissen.
    • nichts hält mich davon ab, mit kopieren/einfügen den code von modifies_variable aus dem compiler-source, völlig zunichte Ihrem argument. (vorausgesetzt, open-source, aber der Punkt sollte klar sein)
    • sobald Sie das tun, dann haben wir die haltungproblem in der Verkleidung, und die original-Antwort nicht gelten, aber auch nicht vor 🙂
    • +1 dafür, dass es mir -1 - I feel großzügige#
    • Wie kommt es, Gödel die Unvollständigkeit Theorem hat noch nicht einmal erwähnt worden noch? 🙁

    InformationsquelleAutor orlp
  3. 60

    Nicht zu verwechseln "werden oder nicht, ändern einer variable gegeben, diese Eingänge" für "hat einen Ausführungspfad, ändert eine variable."

    Ersteres nennt Opak-Prädikat-Bestimmung, und ist trivial unmöglich zu entscheiden - abgesehen von der Reduktion vom Halteproblem, Sie konnte nur darauf aus, die Eingänge stammen möglicherweise aus einer unbekannten Quelle (zB. die Benutzer). Dies gilt für alle Sprachen, nicht nur C++.

    Letztere Aussage, jedoch kann bestimmt werden, indem man den parse-Baum, die ist etwas, das alle optimizing Compiler tun. Der Grund, warum Sie tun, ist, dass Reine Funktionen (und referentiell transparent Funktionen, für einige definition referentiell transparent) haben alle möglichen schönen Optimierungen angewendet werden können, wie leicht inlinable oder mit Ihren ermittelten Werte zur compile-Zeit, aber zu wissen, ob eine Funktion rein, die wir brauchen, um zu wissen, ob es kann jemals ändern einer variable.

    So, was zu sein scheint eine überraschende Aussage über C++ ist eigentlich eine triviale Aussage über alle Sprachen.

    • Dies ist die beste Antwort, meiner Meinung nach, ist es wichtig, diese Unterscheidung zu treffen.
    • +1, gute Antwort.
    • "trivial unmöglich" ?
    • unmöglich zu entscheiden", bedeutet wahrscheinlich "unmöglich zu entscheiden, und der Beweis ist trivial".
    InformationsquelleAutor BlueRaja - Danny Pflughoeft
  4. 28

    Glaube ich das Stichwort in "ob oder ob nicht eine C++ - Funktion, ändert sich der Wert einer bestimmten variable" ist "wird". Es ist sicherlich möglich, erstellen Sie einen compiler, der prüft, ob oder ob nicht eine C++ - Funktion darf ändern Sie den Wert einer bestimmten variable, Sie kann nicht mit Sicherheit sagen, dass die Veränderung geschehen wird:

    void maybe(int& val) {
    cout << "Should I change value? [Y/N] >";
    string reply;
    cin >> reply;
    if (reply == "Y") {
        val = 42;
    }
}
    • "Es ist sicherlich möglich, erstellen Sie einen compiler, der prüft, ob oder ob nicht eine C++ - Funktion kann den Wert einer bestimmten variable" Nein, ist es nicht. Siehe Caleb ' s Antwort. Für einen compiler wissen, ob foo() ändern kann, wäre es schon zu wissen, ob es möglich ist für bar() auf 0 zurück. Und es gibt keine berechenbare Funktion, die einem sagen, alle möglichen Rückgabewerte von jeder berechenbaren Funktion. So gibt es code-Pfade, so dass der compiler nicht in der Lage zu sagen, ob Sie je erreicht werden. Wenn eine variable geändert wird nur die code-Pfad, der nicht erreicht werden kann es nicht ändern, aber ein compiler nicht erkennen, es
    • Von "können" meine ich "ändern darf", nicht "kann sich möglicherweise ändern". Ich glaube, dass dies ist, was der OP im Sinn hatte, wenn die Rede von const-ness überprüft.
    • Würde ich Zustimmen, dass ich glaube, der OP meinte wohl die erste, "ist erlaubt o ändern", oder "kann oder kann nicht ändern" vs. "wird definitiv nicht wechseln". Natürlich kann ich nicht denken Sie an ein Szenario, wo das ein Problem sein. Sie könnte sogar ändern Sie den compiler an, beantworten Sie einfach "ändern können" auf eine beliebige Funktion, die entweder die Kennung oder ein Aufruf einer Funktion, die ein "sich ändern" Antwort-Attribut. Das heißt, C und C++ sind schrecklich Sprachen, zu versuchen, diese mit, da Sie so eine lockere definition der Dinge. Ich denke, das ist der Grund, warum const-ness wäre ein Problem in C++ überhaupt.
    • es gibt keine berechenbare Funktion, die einem sagen, alle möglichen Rückgabewerte der jede berechenbare Funktion". Ich denke, dass die überprüfung "aller möglichen Rückgabewerte" ist der falsche Ansatz. Es gibt mathematische Systeme (maxima, mathlab), die Gleichungssysteme lösen können, das heißt, es würde Sinn machen, gelten der Ansatz ähnlich zu Funktionen. I. e. behandeln Sie es wie eine Gleichung mit mehreren unbekannten. Die Probleme sind Durchfluss-Steuerung + Nebenwirkungen => unlösbare Situationen. IMO, ohne diese (funktionale Sprache, keine-Zuordnung/Nebenwirkungen), wäre es schon möglich, vorherzusagen, welchen Weg das Programm
    • Lesen sollte if (reply == "Y") { statt if (reply == Y) {...
    InformationsquelleAutor dasblinkenlight
  5. 15

    Ich glaube nicht, dass es notwendig ist, rufen Sie das Halteproblem zu erklären, dass Sie nicht algorithmisch wissen zur compile-Zeit, ob eine gegebene Funktion zu ändern, eine bestimmte variable oder nicht.

    Stattdessen ist es ausreichend zu zeigen, dass eine Funktion das Verhalten hängt oft von Laufzeit-Bedingungen, die der compiler kann nicht wissen, über Sie im Voraus. E. g.

    int y;

int main(int argc, char *argv[]) {
   if (argc > 2) y++;
}

    Wie könnte man den compiler mit Sicherheit voraussagen, ob y geändert werden?

    InformationsquelleAutor LarsH
  6. 7

    Es getan werden kann und Compiler sind tun es die ganze Zeit für einige Funktionen, das ist zum Beispiel eine triviale Optimierung für einfache inline-Accessoren oder viele Reine Funktionen.

    , Was unmöglich ist zu wissen, dass es im Allgemeinen Fall.

    Immer, wenn es ein system Anruf oder einen Aufruf der Funktion aus einem anderen Modul, oder ein Anruf zu einem potenziell überschreiben-Methode, alles, was passieren könnte, enthalten die feindliche übernahme von einigen hacker verwenden eines stack-überlauf zu ändern, dass eine unabhängige variable.

    Allerdings sollten Sie verwenden, const, vermeiden globals, lieber Referenzen auf Zeiger, vermeiden, wiederverwenden Variablen voneinander unabhängigen Aufgaben, etc. das macht der compiler das Leben leichter, wenn die Durchführung aggressive Optimierungen.

    • Endlich und ja.
    • Wenn ich mich erinnere richtig, das ist der springende Punkt, der die funktionale Programmierung, richtig? Durch die Verwendung von nur rein deterministisch, keine Nebenwirkungen-Funktionen, Compiler sind frei zu tun, aggressiven Optimierungen, vor der Ausführung, post-Ausführung memoization und auch die Ausführung zur compile-Zeit. Der Punkt, dass ich denke, dass viele die Antwort ignorieren (oder verwirrt) ist, dass es wird tatsächlich für ein gut erzogener Teilmenge aller Programme. Und Nein, dieser Teil ist nicht trivial oder uninteressant, eigentlich ist es sehr nützlich. Aber es ist in der Tat unmöglich für den absoluten Allgemeinen Fall.
    • Überlastung ist eine compile-time-Konzept. Sie meinte wahrscheinlich "überschriebenen Methode".
    • ja, ich meine überschrieben. Überlastung ist zwar eine compile-time-Konzept. Vielen Dank für Flecken es (natürlich wenn die Umsetzung kommt aus einer anderen compilation unit, kann der compiler immer noch Probleme haben, analysieren Sie es, aber das war nicht das, was ich meinte). Ich werde fix die Antwort.
    InformationsquelleAutor kriss
  7. 6

    Gibt es mehrere Möglichkeiten, zu erklären, diese, von denen die Halteproblem:

    In der berechenbarkeitstheorie, das Halteproblem kann wie folgt angesetzt werden: "eine Beschreibung von einem beliebigen computer-Programm, entscheiden, ob das Programm beendet oder weiter ausgeführt wird, für immer". Dies ist äquivalent zu dem problem zu entscheiden, da ein Programm und einen input, ob das Programm irgendwann stoppen, wenn run mit, dass die Eingabe, oder laufen ewig.

    Alan Turing bewies 1936, dass ein allgemeiner Algorithmus, um das zu lösen Halteproblem für alle möglichen Programm-input-Paare nicht existieren kann.

    Wenn ich ein Programm schreiben, das wie folgt aussieht:

    do tons of complex stuff
if (condition on result of complex stuff)
{
    change value of x
}
else
{
    do not change value of x
}

    Nicht den Wert von x ändern? Um dies zu ermitteln, Sie müsste zunächst, um zu bestimmen, ob die do tons of complex stuff Teil bewirkt, dass die Bedingung zur Feuer - oder sogar mehr-basic, ob es hält. Das ist etwas, was der compiler kann das nicht tun.

    InformationsquelleAutor Timothy Shields
  8. 6

    Wirklich überrascht, dass es nicht eine Antwort, die über das Halteproblem direkt! Es ist eine sehr einfache Reduktion von dieses problem das Halteproblem.

    Vorstellen, dass der compiler könnte erkennen, ob oder nicht eine Funktion verändert den Wert einer Variablen. Dann wäre es sicherlich in der Lage sein zu sagen, ob die folgende Funktion ändert den Wert von y oder nicht, vorausgesetzt, dass der Wert von x sein kann, verfolgt alle Anrufe in den rest des Programms:

    foo(int x){
   if(x)
       y=1;
}

    Nun für jedes Programm, die wir mögen, wir umschreiben es so:

    int y;
main(){
    int x;
    ...
    run the program normally
    ...
    foo(x);
}

    Beachten Sie, dass, wenn, und nur wenn unser Programm ändert sich der Wert von y ist, tut es dann beenden - von foo() ist das Letzte, was er tut, vor dem beenden. Dies bedeutet, dass wir gelöst haben das Halteproblem!

    Was die obige Reduktion zeigt uns, dass das problem der Bestimmung, ob eine variable den Wert ändert, ist mindestens so hart wie das Halteproblem. Das Halteproblem ist bekannt, incomputable, also das muss man auch sein.

    • Ich bin mir nicht sicher, ich Folge Ihrer Argumentation, warum alles über unser Programm beendet iff-es ändert sich der Wert der y. Sieht für mich wie foo() gibt schnell, und dann main() beendet. (Sie können auch anrufen foo() ohne ein argument... das ist ein Teil meiner Verwirrung.)
    • Iff-das veränderte Programm beendet, wird die Letzte Funktion, die es genannt wurde,. f. Wenn y geändert wurde, f genannt wurde (die anderen Aussagen kann man nicht ändern, y, denn es wurde erst eingeführt durch die änderung). Daher, wenn y geändert wurde, wird das Programm beendet.
    InformationsquelleAutor John Doucette
  9. 4

    Sobald eine Funktion ruft eine andere Funktion, die der compiler nicht "sehen", die Quelle, die es entweder davon ausgehen muss, dass die variable verändert wird, oder die Sachen können auch schief gehen, weiter unten. Zum Beispiel, sagen wir, wir haben diese in "foo.cpp":

     void foo(int& x)
 {
    ifstream f("f.dat", ifstream::binary);
    f.read((char *)&x, sizeof(x));
 }

    und wir haben diese in "bar.cpp":

    void bar(int& x)
{
  foo(x);
}

    Wie kann der compiler "weiß", dass x ist nicht zu ändern (oder ändern, in geeigneter Weise) in bar?

    Ich bin sicher, wir können kommen mit etwas komplexer, wenn das noch nicht Komplex genug.

    • Der compiler wissen kann, dass x nicht ändern, in bar, wenn bar x übergeben wird, wie pass-by-reference-to-const, richtig?
    • Ja, aber wenn ich einen const_cast foo, wäre es immer noch machen x ändern - ich würde in Verletzung des Vertrages, die besagt, dass Sie nicht zu ändern const Variablen, aber da kann man konvertieren, alles zu "mehr const", und const_cast vorhanden ist, der Designer der Sprache sicherlich hatte die Idee im Hinterkopf, dass es manchmal gute Gründe zu glauben, dass const Werte können geändert werden.
    • Ich glaube, wenn man const_cast, Sie zu halten alle die Stücke, die brechen, denn der compiler kann, muss aber nicht kompensieren.
    • Ja, ich bin sicher, das ist richtig. Aber zur gleichen Zeit, den cast nicht existiert, was bedeutet, dass jemand wer die Sprache hat eine Art von Idee, dass "möglicherweise müssen wir das irgendwann" - was bedeutet, es ist nicht dazu gedacht, um nicht alles sinnvoll, bei allen.
    InformationsquelleAutor Mats Petersson
  10. 1

    Ist es unmöglich, im Allgemeinen für den compiler, um festzustellen, ob die variable wird geändert werden, wie schon betont wurde.

    Beim Check-const-ness, die Frage von Interesse zu sein scheint, wenn die variable kann geändert werden, indem eine Funktion. Auch dies ist schwer in Sprachen, die Unterstützung von Zeigern. Sie können nicht kontrollieren, was andere code wird mit einem Zeiger, es könnte sogar sein, Lesen aus einer externen Quelle (obwohl unwahrscheinlich). In Sprachen, die den Zugang zu Speicher, sind diese Arten von Garantien möglich sein kann, und mehr aggressive Optimierung als C++ tut.

    • Eine Sache, die ich wünschte, unterstützt wurde, in Sprachen wäre eine Unterscheidung zwischen ephemeren, Mehrweg-und persistente Referenzen (oder Zeiger). Ephemere Referenzen dürfen nur kopiert werden, um andere Ephemere Referenzen, Mehrweg-diejenigen, die können kopiert werden Ephemere oder Mehrweg lieben, und die beständige diejenigen, die kopiert werden können, welche die Art und Weise. Der Rückgabewert einer Funktion wird eingeschränkt durch die am meisten einschränkende Argumente, die übergeben werden, die als "Mehrweg" - Parameter. Ich halte es für bedauerlich, dass in vielen Sprachen, wenn man übergibt eine Referenz-es gibt nichts, um anzuzeigen, wie lange kann es verwendet werden.
    • Das wäre sicherlich nützlich sein. Natürlich gibt es Muster für dieses, aber in C++ (und vielen anderen Sprachen) ist es immer möglich, zu "betrügen".
    • Eine große Weise, in der .NET überlegen ist, Java ist, dass es ein Konzept des ephemeren Referenz, aber leider gibt es keine Möglichkeit für Objekte setzen Eigenschaften als vergänglich Referenzen (was ich wirklich gerne sehen, wäre ein Mittel, mit dem code mit einer Eigenschaft bestehen würde, einen temporären Verweis auf einen code (zusammen mit temporären Variablen), die verwendet werden soll zum Bearbeiten des Objekts.
    InformationsquelleAutor Krumelur
  11. 1

    Um die Frage spezifischer, schlage ich die folgende Reihe von Einschränkungen können zu dem geworden, was der Autor des Buches mag im Sinn gehabt haben:

    1. Übernimmt der compiler prüft das Verhalten einer bestimmten Funktion mit const-ness, die von einer Variablen. Für Richtigkeit, ein compiler würde davon ausgehen (wegen aliasing wie unten erklärt wird), wenn die Funktion aufgerufen, eine weitere Funktion die variable verändert wird, also Annahme #1 gilt nur für code-Fragmente, die nicht mit Funktionsaufrufen.
    2. Übernehmen die variable nicht geändert durch eine asynchrone oder gleichzeitige Aktivitäten.
    3. Übernimmt der compiler ist nur die Bestimmung, wenn die variable geändert werden kann, nicht ob es geändert werden wird. In anderen Worten ist der compiler nur statische Analyse.
    4. Übernimmt der compiler ist nur in ordnungsgemäß funktionierenden code (nicht in Betracht, array-überläufe/Unterläufe, ungültige Zeiger, etc.)

    Im Kontext der compiler-design, ich denke Annahmen 1,3,4 durchaus Sinn machen, in der Ansicht von einem compiler Schriftsteller im Kontext der code-gen Richtigkeit und/oder code-Optimierung. Annahme 2 macht Sinn in der Abwesenheit des volatile-Schlüsselwort. Und diese Annahmen konzentrieren sich auch die Frage genug, um die Beurteilung einer vorgeschlagenen Antwort viel mehr endgültiger 🙂

    Gegeben diese Annahmen, ist ein wesentlicher Grund, warum const-ness nicht angenommen werden kann, ist aufgrund der variable aliasing. Der compiler kann nicht wissen, ob eine andere variable Punkte in der const variable. Aliasing könnte durch eine andere Funktion in der selben compilation unit, in dem Fall der compiler könnte auch der Blick über die Funktionen und Nutzung einer call-Baum statisch zu bestimmen, die aliasing auftreten könnten. Aber wenn das aliasing ist durch eine Bibliothek oder andere ausländische code und der compiler hat keine Möglichkeit zu wissen, die auf Funktion Eintrag, ob Variablen Aliasing.

    Könnte man argumentieren, dass wenn eine variable/argument ist const markiert dann sollte es nicht geändert werden, die über aliasing, aber für einen compiler schreibt, der ist ziemlich riskant. Es kann sogar riskant sein, für einen menschlichen Programmierer, um eine variable zu deklarieren const als Teil von, sagen wir, ein großes Projekt, wo er nicht weiß, wie das Verhalten des ganzen Systems, oder das OS, oder eine Bibliothek, um wirklich zu wissen, eine variable nicht zu ändern.

    InformationsquelleAutor Χpẘ
  12. 0

    Selbst wenn eine variable deklariert wird const sind, bedeutet nicht, schlecht geschriebenen code kann überschrieben werden.

    //  g++ -o foo foo.cc

#include <iostream>
void const_func(const int&a, int* b)
{
   b[0] = 2;
   b[1] = 2;
}

int main() {
   int a = 1;
   int b = 3;

   std::cout << a << std::endl;
   const_func(a,&b);
   std::cout << a << std::endl;
}

    Ausgabe:

    1
2
    • Dies geschieht, weil a und b sind stack-Variablen, und b[1] nur zufällig die gleiche Speicherposition wie a.
    • -1. Undefiniertes Verhalten entfernt alle Beschränkungen für die ein compiler-Verhalten.
    • Unsicher über die unten abstimmen. Dies ist nur ein Beispiel, das geht an die OP ' s ursprüngliche Frage, warum kann ein compiler herausfinden, ob etwas wirklich const wenn alles gekennzeichnet ist const. Es ist, weil Undefiniertes Verhalten ist ein Teil von C/C++. Ich war auf der Suche nach einer anderen Antwort auf seine Frage anstatt zu erwähnen das Halteproblem oder externe menschlichen input.
    InformationsquelleAutor Mark Lakata
  13. 0

    Erweitern auf meine Kommentare, das Buch ist text, ist unklar, welche verschleiert das Problem.

    Als ich kommentierte, dass das Buch versucht zu sagen, "Holen wir uns eine unendliche Anzahl von Affen, die schreiben jeden erdenklichen C++ - Funktion, die jemals geschrieben werden. Es wird Fälle geben, wo, wenn wir wählen eine variable, die (einige bestimmte Funktion, die Affen geschrieben) verwendet, können wir nicht herausfinden, ob die Funktion ändern, die variable."

    Natürlich für einige (sogar viele) Funktionen in einer bestimmten Anwendung, diese kann bestimmt werden, indem der compiler, und sehr leicht. Aber nicht für alle (oder unbedingt die meisten).

    Diese Funktion kann so leicht analysiert:

    static int global;

void foo()
{
}

    "foo" klar, ändert sich nicht "global". Es nicht ändern, überhaupt nichts, und ein compiler kann diese Arbeit sehr leicht.

    Dieser Funktion können Sie nicht so analysiert:

    static int global;

int foo()
{
    if ((rand() % 100) > 50)
    {
        global = 1;
    }
    return 1;

    Da "foo"'s Aktionen hängt davon ab einen Wert ändern können zur Laufzeit, es offensichtlich nicht bestimmt werden kann zur compile-Zeit ob es sich ändern wird "global".

    Dieses ganze Konzept ist weit einfacher zu verstehen als Informatiker machen es aus zu sein. Wenn die Funktion etwas anderes machen, basierend auf Dinge, die sich zur Laufzeit ändern kann, dann kann man nicht herausfinden, was es tun werde, bis es läuft, und jedes mal, wenn es läuft, kann es etwas anders machen. Ob es nachweislich unmöglich oder nicht, es ist offensichtlich unmöglich.

    InformationsquelleAutor El Zorko
Schreibe einen Kommentar