Por que os invariantes são importantes em Ciência da Computação?

14

Eu entendo 'invariante' em seu sentido literal. Também os reconheço quando digito código. Mas não acho que entendi a importância desse termo no contexto da ciência da computação.

Sempre que leio white papers de conversas sobre design de linguagem de programadores famosos \ cientistas de computação, o termo 'invariante' continua aparecendo como um jargão; e essa é a parte que não entendo. O que há de tão especial nisso?

    
por Antony Thomas 22.09.2012 / 19:55
fonte

5 respostas

7

Um algoritmo é um processo repetitivo. Se for repetitivo, ele deve ter atributos que não mudam com a repetição. Estas são suas invariantes. Os invariantes são combinados com e / ou operam nos dados (potencialmente) variáveis que serão inseridos em seu algoritmo.

Assim, o objetivo da programação é identificar o que não varia - isso é essencialmente o seu programa.

No programa orientado a objetos, há uma noção de que cada objeto deve fazer uma única coisa bem. Isso essencialmente significa que (para OOP baseada em classe) uma classe define as invariantes para um único algoritmo, juntamente com os place-holders (variáveis) para quaisquer dados variantes que seus objetos possam precisar. Idealmente, em OO, você isolaria o que varia tanto quanto possível, de modo que cada objeto é praticamente invariável.

    
por 22.09.2012 / 21:19
fonte
25

A noção de invariante está strongmente ligada aos "efeitos colaterais". Acredito que foi promovido pela abordagem “Design by Contract (DbC)” de Bertrand Meyer para design de software.

O DbC enriquece os Tipos de dados abstratos (backbone de classes) com três noções importantes, pré-condições, pós-condições, invariantes. É facilmente explicado quando se refere a procedimentos, então tentarei explicar em referência a ele:

  1. Uma pré-condição representa os dados de entrada da condição para que um procedimento deva respeitar para chamar esse procedimento. Esta pré-condição deve ser respeitada e aplicada pelo cliente desse procedimento específico. O designer de procedimentos pode, no entanto, defender de clientes que não respeitam a pré-condição, afirmando que as condições são as primeiras linhas do procedimento. Por exemplo, ter um método double divide(double dividend, double divisor) uma pré-condição pode ser divisor != 0 .

  2. Uma póscondição representa a condição nos dados de saída após o procedimento retornar; é inteiramente tarefa do projetista de procedimentos respeitar essa condição pós-condição desde que a condição prévia seja respeitada; em um estilo de programação de defesa antes de retornar, a pós-condição pode ser afirmada.

  3. Um invariante pode ser considerado como uma precondição e uma pós-condição, mas com diferentes entendimentos para pré-condição e pós-condição a partir dos conceitos acima. Uma invariante basicamente diz que, se a entrada tiver uma condição específica satisfeita antes de o procedimento ser chamado, essa condição específica é válida após o procedimento ser chamado. Por exemplo, uma invariante válida para um procedimento boolean search(int term, int array[]) pode dizer que o estado de array antes da chamada é o mesmo que é depois da chamada.

Impor invariantes em procedimentos (e não apenas em procedimentos) é ótimo, pois reduz os efeitos colaterais ; isso é útil, já que os efeitos colaterais são um grande mal na programação. Um determinado procedimento pode alterar o estado dos argumentos de entrada ou alterar o estado de algumas variáveis globais ou depender de algumas variáveis globais; isso pode levar a situações desagradáveis em que duas chamadas idênticas no mesmo procedimento (com a mesma entrada) podem produzir saídas diferentes. Isso leva a conhecer o histórico das chamadas e é muito difícil de depurar, especialmente em um contexto de multithreading.

    
por 22.09.2012 / 20:44
fonte
2

Uma invariante é uma propriedade lógica preservada por algumas operações.

  • Você precisa de invariantes para raciocinar sobre loops. Como você não sabe de antemão quantas iterações haverá (ou você não precisaria de um loop), cada iteração deve preservar a invariante, de modo que no final você possa provar alguma propriedade útil sobre o loop.

  • Você precisa de invariantes para raciocinar sobre propriedades de dados encapsulados. Geralmente, os vários dados dentro de um módulo ou objeto precisam satisfazer certas propriedades para uma operação correta (por exemplo, uma lista representando um conjunto deve sempre ser classificada). Você quer que cada função ou método operando nos dados preserve essas propriedades, então elas também são invariantes.

por 22.09.2012 / 20:55
fonte
0

Pelo que eu sei, a importância da invariante vem do fato de que é o bloco de construção para provar que um algoritmo calcula uma certa função. Por exemplo, você desenvolveu um novo algoritmo de ordenação, mas como pode ter tanta certeza de que ele realmente ordena a cada entrada ou a cada saída correta. O próximo passo é construir invariantes que correspondam ao fluxo do algoritmo e provar que ele ordena usando os invariantes.

    
por 23.09.2012 / 06:45
fonte
0

No contexto de um sistema de tipos de linguagem de programação, um tipo invariável é um tipo não conversível. Por exemplo, em java, ao sobrecarregar um método, todos os parâmetros são invariantes, enquanto o tipo de retorno é covariante (pode ser o mesmo ou um subtipo).

    
por 23.09.2012 / 20:12
fonte