¿Por qué son importantes las invariantes en Informática?

Un algoritmo es un proceso repetible. Si es repetible, tiene que tener atributos que no cambien con la repetición. Estas son tus invariantes. Los invariantes se combinan con y / o operan en los datos (potencialmente) variables que se incorporarán a su algoritmo.

Por lo tanto, el objetivo principal de la programación es identificar lo que no varía: ese es esencialmente su programa.

En el programa orientado a objetos, hay una noción de que cada objeto debe hacer una sola cosa bien. Básicamente, esto significa que (para la POO basada en la clase) una clase define los invariantes para un solo algoritmo, junto con los marcadores de posición (variables) para cualquier variante de datos que puedan necesitar sus objetos. Idealmente, en OO, aislarías lo que varía tanto como sea posible, de modo que cada objeto sea prácticamente invariable.

La noción de invariante está fuertemente vinculada con los 'efectos secundarios'. Creo que fue promovido por el enfoque de Bertrand Meyer 'Design by Contract (DbC)' para el diseño de software.

DbC enriquece los tipos de datos abstractos (columna vertebral de las clases) con 3 nociones importantes, condiciones previas, condiciones posteriores, invariantes . Se explica fácilmente cuando se hace referencia a los procedimientos, así que intentaré explicarlo con referencia:

1. Una condición previa representa los datos de entrada de condición para que un procedimiento deba respetar para poder llamar a ese procedimiento. Esta condición previa debe ser respetada y aplicada por el cliente de ese procedimiento en particular. Sin embargo, el diseñador del procedimiento podría defenderse de los clientes que no respetan la condición previa al afirmar esa condición como primeras líneas en el procedimiento. Por ejemplo, tener un método double divide(double dividend, double divisor) una condición previa podría ser divisor != 0 .

2. Un postcondition representa una condición en los datos de salida después de que el procedimiento vuelve; Es responsabilidad del diseñador de procedimientos respetar esta condición posterior siempre que se haya respetado la condición previa; En un estilo de programación de defensa antes de regresar, se puede afirmar la condición posterior.

3. Un invariante se puede considerar como una condición previa y una condición posterior, pero con una comprensión diferente para la condición previa y la condición posterior de los conceptos anteriores. Un invariante básicamente dice que si la entrada tiene una condición particular cumplida antes de llamar al procedimiento, entonces esa condición particular es válida después de que se llame el procedimiento. Por ejemplo, un invariante válido para un procedimiento boolean search(int term, int array[]) podría decir que el estado de array antes de la llamada es el mismo que después de la llamada.

Hacer cumplir los invariantes en los procedimientos (y no solo los procedimientos) es una gran cosa, ya que reduce los efectos secundarios ; Esto es útil ya que los efectos secundarios son un gran mal en la programación. Un procedimiento en particular puede cambiar el estado de los argumentos de entrada, cambiar el estado de algunas variables globales o depender de algunas variables globales; esto podría llevar a situaciones desagradables en las que dos llamadas idénticas en el mismo procedimiento (con la misma entrada) podrían generar resultados diferentes. Esto lleva a conocer la historia de las llamadas y es muy difícil de depurar, especialmente en un contexto de multiproceso.

Un invariante es una propiedad lógica que se conserva por alguna (s) operación (es).

• Necesitas invariantes para razonar acerca de los bucles. Como no sabe de antemano cuántas iteraciones habrá (o no necesitaría un bucle), cada iteración debe conservar el invariante, de modo que al final pueda probar alguna propiedad útil sobre el bucle.

• Necesita invariantes para razonar acerca de las propiedades de los datos encapsulados. A menudo, los diversos datos dentro de un módulo u objeto necesitan satisfacer ciertas propiedades para una operación correcta (por ejemplo, una lista que representa un conjunto siempre debe estar ordenada). Desea que cada función o método que opera en los datos conserve estas propiedades, por lo que también son invariantes.

Por lo que sé, la importancia de la invariante proviene del hecho de que es el elemento fundamental para probar que un algoritmo calcula una función determinada. Por ejemplo, ha desarrollado un nuevo algoritmo de clasificación, pero ¿cómo puede estar tan seguro de que realmente clasifica con cada entrada o con cada salida correcta? El siguiente paso es construir invariantes que correspondan al flujo del algoritmo y probar que ordena usando los invariantes.

En el contexto del sistema de tipos de un lenguaje de programación, un tipo invariante es un tipo no convertible. Por ejemplo, en Java, al sobrecargar un método, todos los parámetros son invariantes, mientras que el tipo de retorno es covariante (puede ser el mismo o un subtipo).