Warum sind Invarianten in der Informatik wichtig?

Ich verstehe "invariant" im wahrsten Sinne des Wortes. Ich erkenne sie auch, wenn ich Code eingebe. Aber ich glaube nicht, dass ich die Bedeutung dieses Begriffs im Kontext der Informatik verstehe.

Wann immer ich Konversationen \ Whitepapers über Sprachdesign von berühmten Programmierern \ Informatikern lese, taucht der Begriff "Invariant" immer wieder als Jargon auf. und das ist der Teil, den ich nicht verstehe. Was ist das Besondere daran?

Ein Algorithmus ist ein wiederholbarer Prozess. Wenn es wiederholbar ist, muss es Attribute haben, die sich bei Wiederholung nicht ändern. Das sind deine Invarianten. Die Invarianten werden mit den (potenziell) unterschiedlichen Daten kombiniert und / oder arbeiten mit diesen, die in Ihren Algorithmus eingespeist werden.

Der springende Punkt bei der Programmierung ist also, zu identifizieren, was nicht variiert - das ist im Wesentlichen Ihr Programm.

In objektorientierten Programmen gibt es die Vorstellung, dass jedes Objekt eine einzelne Sache gut machen sollte. Dies bedeutet im Wesentlichen, dass (für klassenbasiertes OOP) eine Klasse die Invarianten für einen einzelnen Algorithmus zusammen mit Platzhaltern (Variablen) für alle Variantendaten definiert, die ihre Objekte möglicherweise benötigen. Idealerweise würden Sie in OO so viele Variationen wie möglich isolieren, sodass jedes Objekt größtenteils invariant ist.

Der Begriff der Invariante ist stark mit „Nebenwirkungen“ verbunden. Ich glaube, es wurde von Bertrand Meyer 'Design by Contract (DbC)' Ansatz für Software-Design gefördert.

DbC bereichert abstrakte Datentypen (Rückgrat von Klassen) mit 3 wichtigen Begriffen, Vorbedingungen, Nachbedingungen, Invarianten . Wenn ich mich auf Prozeduren beziehe, ist dies leicht zu erklären, daher werde ich versuchen, dies in Bezug darauf zu erklären:

1. Eine Vorbedingung stellt die Bedingung dar, die Eingabedaten für eine Prozedur berücksichtigen müssen, um diese Prozedur aufzurufen. Diese Vorbedingung muss vom Kunden des jeweiligen Verfahrens eingehalten und durchgesetzt werden. Der Prozedurdesigner kann sich jedoch gegen Clients verteidigen, die die Vorbedingung nicht erfüllen, indem er diese Bedingung als erste Zeile in der Prozedur geltend macht. Zum Beispiel double divide(double dividend, double divisor)könnte eine Methode eine Vorbedingung sein divisor != 0.

2. Eine Nachbedingung stellt die a-Bedingung für die Ausgabedaten dar, nachdem die Prozedur zurückgegeben wurde. Es ist ganz und gar Aufgabe des Verfahrensentwicklers, diese Nachbedingung zu beachten, vorausgesetzt, die Vorbedingung wurde eingehalten. in einem Verteidigungsprogrammierstil vor der Rückkehr kann die Nachbedingung geltend gemacht werden.

3. Eine Invariante kann sowohl als Vorbedingung als auch als Nachbedingung betrachtet werden, jedoch mit einem anderen Verständnis für Vorbedingung und Nachbedingung als die obigen Konzepte. Eine Invariante sagt im Grunde, dass, wenn die Eingabe eine bestimmte Bedingung erfüllt hat, bevor die Prozedur aufgerufen wurde, diese bestimmte Bedingung gültig ist, nachdem die Prozedur aufgerufen wurde. Beispielsweise könnte eine gültige Invariante für eine Prozedur boolean search(int term, int array[])besagen, dass der Status arrayvor dem Aufruf derselbe ist wie nach dem Aufruf.

Das Erzwingen von Invarianten für Prozeduren (und nicht nur für Prozeduren) ist eine großartige Sache, da es die Nebenwirkungen verringert . Dies ist nützlich, da Nebenwirkungen beim Programmieren ein großes Übel sind. Eine bestimmte Prozedur kann den Status der Eingabeargumente oder den Status einiger globaler Variablen ändern oder von einigen globalen Variablen abhängen. Dies kann zu unangenehmen Situationen führen, in denen zwei identische Aufrufe derselben Prozedur (mit derselben Eingabe) unterschiedliche Ausgaben ergeben können. Dies führt dazu, dass der Verlauf der Aufrufe bekannt ist, und ist insbesondere in einem Multithreading-Kontext sehr schwer zu debuggen.

Eine Invariante ist eine logische Eigenschaft, die von einigen Operationen beibehalten wird.

• Sie brauchen Invarianten, um über Schleifen zu argumentieren. Da Sie vorher nicht wissen, wie viele Iterationen es geben wird (oder Sie keine Schleife benötigen), muss jede Iteration die Invariante beibehalten, damit Sie am Ende eine nützliche Eigenschaft der Schleife nachweisen können.

• Sie benötigen Invarianten, um über Eigenschaften gekapselter Daten zu urteilen. Häufig müssen die verschiedenen Daten in einem Modul oder Objekt bestimmte Eigenschaften erfüllen, damit sie ordnungsgemäß funktionieren (z. B. muss eine Liste, die einen Satz darstellt, immer sortiert sein). Sie möchten, dass jede Funktion oder Methode, die mit den Daten arbeitet, diese Eigenschaften beibehält, damit sie auch invariant sind.

Soweit ich weiß, beruht die Bedeutung der Invariante auf der Tatsache, dass sie der Baustein für den Nachweis ist, dass ein Algorithmus eine bestimmte Funktion berechnet. Sie haben beispielsweise einen neuen Sortieralgorithmus entwickelt, aber wie können Sie sicher sein, dass er wirklich bei jeder Eingabe oder bei jeder korrekten Ausgabe sortiert. Der nächste Schritt besteht darin, Invarianten zu konstruieren, die dem Ablauf des Algorithmus entsprechen, und zu beweisen, dass er unter Verwendung der Invarianten sortiert.

Im Kontext des Typsystems einer Programmiersprache ist ein invarianter Typ ein nicht konvertierbarer Typ. Beispielsweise sind in Java beim Überladen einer Methode alle Parameter invariant, während der Rückgabetyp kovariant ist (kann derselbe oder ein Subtyp sein).