Was sind Invarianten, wie können sie verwendet werden und haben Sie sie jemals in Ihrem Programm verwendet?

48

Ich lese Coders at Work und darin wird viel über Invarianten geredet. Nach meinem Verständnis ist eine Invariante eine Bedingung, die sowohl vor als auch nach einem Ausdruck gilt. Sie sind unter anderem nützlich, um zu beweisen, dass die Schleife korrekt ist, wenn ich mich richtig an meinen Logikkurs erinnere.

Ist meine Beschreibung korrekt oder habe ich etwas verpasst? Haben Sie sie jemals in Ihrem Programm verwendet? Und wenn ja, wie haben sie davon profitiert?

gablin
quelle
@Robert Harvey: Ja, das habe ich gerade gelesen. Aber es scheint mir, dass Invarianten nur nützlich sind, wenn Sie versuchen, etwas zu beweisen. Ist das richtig (kein Wortspiel beabsichtigt)?
gablin
Das ist mein verständnis; Wenn Sie versuchen, über Ihr Programm nachzudenken, um seine Richtigkeit zu beweisen.
Robert Harvey
3
@ user9094: Eine Zusicherung ist eine Erklärung, dass zu einem bestimmten Zeitpunkt in der Laufzeit etwas wahr ist und im Code dargestellt wird. Eine Invariante ist eine Aussage (man hofft, sie ist begründet), die immer wahr ist, wenn sie zutrifft, und nicht im Code selbst dargestellt wird.
David Thornley
1
Invarianten sind in der Tat nützlich, um die Korrektheit zu beweisen, aber sie sind nicht auf diesen Fall beschränkt. Sie sind auch nützlich für die defensive Programmierung und beim Debuggen. Sie helfen nicht nur zu beweisen, dass Ihr Code korrekt ist, sondern auch, den Code zu ergründen und die Position der Fehler in der Nähe des Ursprungs zu finden.
Oddthinking

Antworten:

41

In OOP ist eine Invariante eine Reihe von Aussagen, die während der Lebensdauer eines Objekts immer wahr sein müssen, damit das Programm gültig ist. Es sollte vom Ende des Konstruktors bis zum Start des Destruktors gültig sein, wenn das Objekt gerade keine Methode ausführt, die seinen Status ändert.

Ein Beispiel für eine Invariante könnte sein, dass genau eine der beiden Mitgliedsvariablen null sein sollte. Oder dass, wenn einer einen bestimmten Wert hat, die Menge der zulässigen Werte für den anderen dieser oder jener ist ...

Manchmal benutze ich eine Member-Funktion des Objekts, um zu überprüfen, ob die Invariante gültig ist. Ist dies nicht der Fall, wird eine Behauptung aufgestellt. Und die Methode wird am Anfang und Ende jeder Methode aufgerufen, die das Objekt ändert (in C ++ ist dies nur eine Zeile ...)

Xavier Nodet
quelle
11
+1 für die Erwähnung von Invarianten muss in der Mitte einer ausgeführten Methode nicht wahr sein.
Oddthinking
1
@Oddthinking Vermeiden Sie dies jedoch, wenn möglich. Es wäre einfach, in einen Zustand zu geraten, in dem die Invarianz unterbrochen wird, und zu vergessen, vor der Rückkehr alles korrekt wiederherzustellen. Ausnahmen können ebenfalls Probleme bereiten.
Alexander
3
@Alexander: Für nicht-triviale Invarianten ist es fast unmöglich zu vermeiden. Wenn Sie mehr als eine Variable in einer Methode aktualisieren müssen, wie in der Antwort beschrieben, gibt es einen Punkt, an dem nur eine aktualisiert wurde und die Invariante falsch ist. Es gibt genug Einschränkungen, um guten Code zu schreiben, ohne neue hinzuzufügen.
Seltsame
@Oddthinking Ja, es ist oft ganz unvermeidlich. Wenn es beispielsweise eine Gruppe von Variablen gibt, die logisch zusammengehören (z. B. ein Array und den Index eines "ausgewählten" Elements im Array), ist es wahrscheinlich sinnvoll, sie in einen Typ zu extrahieren. Von dort aus können Mutationen des Arrays oder des Typs als einzelne Zuweisung einer neuen Instanz dieses Typs ausgedrückt werden
Alexander
13

Nun, die Dinge, die ich in diesem Thread sehe, sind alle großartig, aber ich habe eine Definition einer "Invariante", die für mich bei der Arbeit enorm hilfreich war.

Eine Invariante ist eine logische Regel, die während der Ausführung Ihres Programms befolgt werden muss und die einem Menschen mitgeteilt werden kann, jedoch nicht Ihrem Compiler.

Diese Definition ist hilfreich, weil sie die Bedingungen in zwei Gruppen aufteilt: Denjenigen, denen der Compiler bei der Durchsetzung vertrauen kann, und denjenigen, die dokumentiert, diskutiert, kommentiert oder auf andere Weise an die Mitwirkenden kommuniziert werden müssen, damit sie mit der Codebasis interagieren können, ohne Fehler einzuführen .

Diese Definition ist auch hilfreich, da Sie die Verallgemeinerung "Invarianten sind schlecht" verwenden können.

Beispielsweise ist der Schalthebel in einem Schaltgetriebe so konstruiert, dass eine Invariante vermieden wird. Wenn ich wollte, könnte ich für jeden Gang ein Getriebe mit einem Hebel bauen. Dieser Hebel kann vorwärts ("eingerückt") oder rückwärts ("ausgerückt") sein. In einem solchen System habe ich eine "Invariante" erstellt, die als solche dokumentiert werden könnte:

"Es ist entscheidend, dass der aktuell eingelegte Gang vor dem Einlegen eines anderen Gangs ausgekuppelt wird. Das gleichzeitige Einlegen von zwei Gängen führt zu einer mechanischen Belastung, die das Getriebe zerreißt. Schalten Sie immer den aktuell eingelegten Gang aus, bevor Sie einen anderen einlegen."

Und so könnte man kaputte Sendungen für schlampiges Fahren verantwortlich machen. Moderne Autos verwenden jedoch einen einzelnen Steuerknüppel, der sich zwischen den Gängen dreht. Es ist so konstruiert, dass es bei einem modernen Schaltwagen nicht möglich ist, zwei Gänge gleichzeitig einzulegen.

Auf diese Weise können wir sagen, dass das Getriebe so konstruiert wurde, dass es die Invariante entfernt, da es sich nicht mechanisch so konfigurieren lässt, dass die logische Regel verletzt wird.

Jede Invariante dieser Art, die Sie aus Ihrem Code entfernen, stellt eine Verbesserung dar, da sie die kognitive Belastung der Arbeit damit verringert.

Daniel Burbank
quelle
1
Wenn eine Invariante eine logische Regel ist, die während der Ausführung Ihres Programms eingehalten werden muss, und Ihre logische Regel lautet, dass nicht zwei Gänge gleichzeitig geschaltet sein dürfen, ist dies nicht die Invariante, dass nicht zwei Gänge gleichzeitig geschaltet sein dürfen Zeit? Ohne diese Invariante könnte sich Ihr Getriebe gleichzeitig in zwei Gängen befinden und sich so selbst zerreißen. Erstens: Erzwingt ein einzelner Stick Shifter diese Invariante nicht tatsächlich? Zweitens, warum wäre eine Invariante von Natur aus gut oder schlecht?
Dustin Cleveland
1
Der Vergleich mit dem Auto ist für mich sehr klar. Vielen Dank!
Marecky
"Eine Invariante ist eine logische Regel, die während der Ausführung Ihres Programms befolgt werden muss und die einem Menschen mitgeteilt werden kann, aber nicht Ihrem Compiler." - Ich mag das sehr, prägnant und leicht zu merken.
ZeroKnight
@DustinCleveland Ich denke, dass in diesem Beispiel die Mechanismen hinter dem Stick Shift der "Compiler" sind, der die Regeln "durchsetzt", während der Treiber, der ansonsten einen Vorfall verursachen könnte, einer der vielen Clients ist, die die Informationen konsumieren und sich merken müssen, die vorhanden sind "dokumentiert, diskutiert, kommentiert oder auf andere Weise kommuniziert".
16.
Geniale Erklärung! Ich verstehe jetzt wirklich, warum es eine schlechte Praxis ist, Invarianten in Ihrem Code zu haben.
Ben C Wang
3

Eine Invariante (im gesunden Menschenverstand) bedeutet einige Bedingungen, die zu einem bestimmten Zeitpunkt oder sogar immer wahr sein müssen, während Ihr Programm ausgeführt wird. Zum Beispiel können PreConditions und PostConditions verwendet werden, um einige Bedingungen zu bestätigen, die wahr sein müssen, wenn eine Funktion aufgerufen wird und wenn sie zurückkehrt. Objektinvarianten können verwendet werden, um zu behaupten, dass ein Objekt während seiner Existenz einen gültigen Zustand haben muss. Dies ist das Design by Contract-Prinzip.
Ich habe informell Invarianten mit Checks in Code verwendet. Aber in jüngerer Zeit spiele ich mit der Codevertragsbibliothek für .NET , die Invarianten direkt unterstützt.

softveda
quelle
3

Basierend auf dem folgenden Zitat von Coders At Work ...

Aber sobald Sie die Invariante kennen, die beibehalten wird, können Sie sehen, ah, wenn wir diese Invariante beibehalten, erhalten wir die Zeit für die Protokollsuche.

... Ich denke, "invariant" = "Bedingung, die Sie beibehalten möchten, um einen gewünschten Effekt zu erzielen".

Es scheint, dass die Invariante zwei Sinne hat, die sich auf subtile Weise unterscheiden:

  1. Etwas, das gleich bleibt.
  2. Etwas, das Sie beibehalten möchten, um Ziel X zu erreichen (z. B. die oben angegebene "Protokollsuchzeit").

Also ist 1 wie eine Behauptung; 2 ist wie ein Werkzeug zum Nachweis von Korrektheit, Leistung oder anderen Eigenschaften - denke ich. Im Wikipedia-Artikel finden Sie ein Beispiel für 2 (Beweis für die Richtigkeit der Lösung des MU-Puzzles).

Tatsächlich ist ein dritter Sinn der Invariante:

.3. Was soll das Programm (oder Modul oder Funktion) tun? Mit anderen Worten, sein Zweck.

Aus demselben Interview mit Coders At Work:

Aber was große Software handhabbar macht, ist, einige globale Invarianten oder Gesamtaussagen darüber zu haben, was sie tun soll und welche Dinge wahr sein sollen.

Jonathan Aquino
quelle
1

Eine Invariante ist wie eine Regel oder eine Annahme, die verwendet werden kann, um die Logik Ihres Programms zu diktieren.

Angenommen, Sie haben eine Softwareanwendung, die Benutzerkonten verwaltet. Angenommen, der Benutzer kann mehrere Konten haben, aber aus welchem ​​Grund auch immer müssen Sie zwischen dem Hauptkonto eines Benutzers und den "Alias" -Konten unterscheiden.

Dies könnte ein DB-Datensatz oder etwas anderes sein, aber nehmen wir vorerst an, dass jedes Benutzerkonto durch ein Klassenobjekt dargestellt wird.

Klasse userAccount {private char * pUserName; private char * pParentAccountUserName;

...}

Eine Invariante könnte die Annahme sein, dass dieses Objekt das übergeordnete Konto ist, wenn pParentAccountUserName NULL oder leer ist. Mit dieser Invariante können Sie verschiedene Kontotypen unterscheiden. Es gibt wahrscheinlich bessere Methoden, um verschiedene Arten von Benutzerkonten zu unterscheiden. Denken Sie also daran, dass dies nur ein Beispiel ist, um zu zeigen, wie eine Invariante verwendet werden kann.

Pemdas
quelle
Invarianten überprüfen den Status eines Programms. Sie sind keine Designentscheidungen.
Xavier Nodet
3
Invarianten überprüfen nichts. Sie können den Status des Programms überprüfen, um festzustellen, ob eine Invariante WAHR oder FALSCH ist, aber die Invarianten selbst "tun" nichts.
Pemdas
2
In C ++ wird normalerweise eine Art Klasseninvarianz angezeigt, z. B. Member x muss kleiner als 25 und größer als 0 sein. Das ist die Invariante. Alle Überprüfungen gegen diese Invariante sind Behauptungen. In dem obigen Beispiel lautet meine Invariante: Wenn pParentAccountUserName NULL oder leer ist, handelt es sich um ein übergeordnetes Konto. Invarianten sind gestaltete Entscheidungen.
Pemdas
Wie können Sie überprüfen, ob dieses Objekt das übergeordnete Konto ist, wenn pParentAccountUserName NULL oder leer ist? Ihre Anweisung definiert nur, was ein Null- / Leerwert darstellen soll. Die Invariante ist, dass das System dem entspricht, dh, dass pParentAccountUserName nur null oder leer sein kann, wenn es sich um ein übergeordnetes Konto handelt. Es ist eine subtile Unterscheidung.
Cameron
1

Aus der Physik kommend gibt es in der Physik Invarianten, also Größen, die nicht über die gesamte Berechnung / Simulation variieren. Beispielsweise wird in der Physik für ein geschlossenes System Gesamtenergie eingespart. Oder wieder in der Physik: Wenn zwei Teilchen kollidieren, müssen die resultierenden Fragmente genau die Energie enthalten, mit der sie begonnen haben, und genau den gleichen Impuls (eine Vektorgröße). Normalerweise gibt es nicht genügend Invarianten, um das Ergebnis vollständig zu spezifizieren. Zum Beispiel haben wir bei der 2-Teilchen-Kollision vier Invarianten, drei Impulskomponenten und eine Energiekomponente, aber das System hat sechs Freiheitsgrade (sechs Zahlen, um seinen Zustand zu beschreiben). Die Invarianten sollten auf einen Rundungsfehler konserviert werden, aber ihre Konservierung beweist nicht, dass die Lösung korrekt ist.

Daher sind diese Dinge in der Regel wichtig für die Überprüfung der geistigen Gesundheit, können jedoch selbst keine Korrektheit nachweisen.

Omega Centauri
quelle
1
-1 Invarianten in der Physik sind unterschiedlich. Das Berechnen einer Lösung ist nicht das Gleiche wie der Nachweis, dass ein Algorithmus korrekt ist. Für letztere können Invarianten die Richtigkeit nachweisen.
Aaronasterling