O que são invariantes, como eles podem ser usados e você já o usou em seu programa?

40

Estou lendo Coders at Work , e nele há muita conversa sobre invariantes. Tanto quanto eu entendi, uma invariante é uma condição que detém tanto antes como depois de uma expressão. Eles são, entre outras coisas, úteis para provar que o loop está correto, se eu me lembro corretamente do meu curso de lógica.

A minha descrição está correta ou perdi alguma coisa? Você já os usou em seu programa? E se sim, como eles se beneficiaram?

    
por gablin 30.12.2010 / 22:19
fonte

6 respostas

29

No OOP, uma invariante é um conjunto de asserções que devem sempre ser verdadeiras durante a vida de um objeto para que o programa seja válido. Ele deve permanecer verdadeiro desde o final do construtor até o início do destruidor sempre que o objeto não estiver atualmente executando um método que altere seu estado.

Um exemplo de invariante poderia ser que exatamente uma das duas variáveis de membro deveria ser nula. Ou que, se alguém tiver um determinado valor, o conjunto de valores permitidos para o outro é este ou aquele ...

Às vezes, uso uma função de membro do objeto para verificar se a invariante é válida. Se este não for o caso, uma declaração é levantada. E o método é chamado no início e na saída de cada método que altera o objeto (em C ++, isso é apenas uma linha ...)

    
por 30.12.2010 / 23:54
fonte
6

Bem, as coisas que estou vendo neste tópico são ótimas, mas eu tenho uma definição de um 'invariante' que foi tremendamente útil para mim no trabalho.

An invariant is any logical rule that must be obeyed throughout the execution of your program that can be communicated to a human, but not to your compiler.

Essa definição é útil porque separa as condições em dois grupos: a quem o compilador pode ser considerado responsável e aqueles que devem ser documentados, discutidos, comentados ou comunicados aos contribuidores para que eles interajam com a base de código sem introduzir erros.

Além disso, essa definição é útil porque permite que você use a generalização, "Invariantes são ruins".

Por exemplo, o câmbio em um carro de transmissão manual é projetado para evitar uma invariante. Se eu quisesse, poderia construir uma transmissão com uma alavanca para cada marcha. Esta alavanca pode ser para a frente ("engatado") ou para trás ("desacoplada"). Em tal sistema, criei uma "invariante", que pode ser documentada como tal:

"It is critical that the currently engaged gear be disengaged before a different gear is engaged. To engage any two gears at the same time will cause mechanical stress that will tear the transmission apart. Always disengage the currently engaged gear before engaging another."

E assim, pode-se culpar transmissões quebradas em direção desleixada. Os carros modernos, no entanto, usam um único bastão que gira entre as engrenagens. Ele foi projetado de tal forma que, em um moderno carro com alavanca, não é possível engajar duas marchas ao mesmo tempo.

Desta forma, poderíamos dizer que a transmissão foi projetada para "remover a invariante", porque ela não se permite ser mecanicamente configurada de uma maneira que viole a regra lógica.

Cada invariante desse tipo que você remove do seu código é uma melhoria, porque diminui a carga cognitiva de trabalhar com ele.

    
por 19.01.2018 / 17:42
fonte
3

Uma invariante (no senso comum) significa algumas condições que devem ser verdadeiras em algum momento ou até mesmo enquanto seu programa está sendo executado. por exemplo. Pré-condições e pós-condições podem ser usadas para confirmar algumas condições que devem ser verdadeiras quando uma função é chamada e quando é retornada. As invariantes de objeto podem ser usadas para afirmar que um objeto deve ter um estado válido durante todo o tempo em que existir. Esse é o princípio do projeto por contrato.
Eu usei invariantes informalmente usando cheques no código. Mas, mais recentemente, estou jogando com o código biblioteca de contratos para .Net que suporta diretamente invariantes.

    
por 30.12.2010 / 22:48
fonte
3

Baseado na seguinte citação de Coders At Work ...

But once you know the invariant that it's maintaining, you can see, ah, if we maintain that invariant then we'll get log lookup time.

... Eu acho que "invariante"="condição que você deseja manter para garantir um efeito desejado".

Parece que a invariante tem dois sentidos que diferem de maneira sutil:

  1. Algo que permanece o mesmo.
  2. Algo que você está tentando manter o mesmo, para atingir a meta X (como um "tempo de pesquisa de log" acima).

Então 1 é como uma afirmação; 2 é como uma ferramenta para provar correção, desempenho ou outras propriedades - eu acho. Veja o artigo da Wikipédia para um exemplo de 2 (comprovando a correção da solução para o quebra-cabeça MU).

Na verdade, um terceiro sentido de invariante é:

.3. O que o programa (ou módulo ou função) deve fazer; em outras palavras, seu propósito.

Da mesma entrevista de Coders At Work:

But what makes big software manageable is having some global invariants or big-picture statements about what it's supposed to do and what things are supposed to be true.

    
por 20.02.2014 / 23:22
fonte
1

Uma invariante é como uma regra ou uma suposição que pode ser usada para ditar a lógica do seu programa.

Por exemplo, suponha que você tenha algum aplicativo de software que controle as contas de usuários. Suponha também que o usuário possa ter várias contas, mas, por qualquer motivo, é necessário diferenciar entre a conta principal do usuário e as contas "alias".

Pode ser um registro de banco de dados ou qualquer outra coisa, mas por enquanto vamos supor que cada conta de usuário é representada por um objeto de classe.

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

}

Uma invariante pode ser a suposição de que, se pParentAccountUserName for NULL ou vazio, esse objeto será a conta pai. Você pode usar essa invariante para distinguir diferentes tipos de conta. Existem provavelmente métodos melhores para distinguir diferentes tipos de contas de usuário, portanto, lembre-se de que este é apenas um exemplo para mostrar como uma invariante pode ser usada.

    
por 30.12.2010 / 22:59
fonte
1

Vindo de uma formação em física, na física temos invariantes, que são essencialmente quantidades que não variam ao longo de todo um cálculo / simulação. Por exemplo, na física, para um sistema fechado, a energia total é conservada. Ou ainda na física, se duas partículas colidirem, os fragmentos resultantes devem conter exatamente a energia com a qual começaram, e exatamente o mesmo momento (uma quantidade vetorial). Geralmente não há invariantes suficientes para especificar totalmente o resultado. Por exemplo, na colisão de 2 partículas, temos quatro invariantes, três componentes de momentum e um componente de energia, mas o sistema tem seis graus de liberdade (seis números para descrever seu estado). Os invariantes devem ser conservados dentro do erro de arredondamento, mas sua conservação não prova que a solução está correta.

Então, normalmente, essas coisas são importantes como verificações de sanidade, mas por si só elas não podem provar correção.

    
por 30.12.2010 / 23:20
fonte

Tags