Quali sono le invarianti, come possono essere utilizzate e che hai mai usato nel tuo programma?

40

Sto leggendo Coders at Work e in esso si parla molto di invarianti. Per quanto ho capito, un invariante è una condizione che contiene sia prima che dopo un'espressione. Sono, tra le altre cose, utili a dimostrare che il ciclo è corretto, se ricordo bene il mio corso di logica.

La mia descrizione è corretta o mi sono perso qualcosa? Li hai mai usati nel tuo programma? E se sì, come hanno beneficiato?

    
posta gablin 30.12.2010 - 22:19
fonte

6 risposte

29

In OOP, un invariante è un insieme di asserzioni che devono essere sempre valide durante la vita di un oggetto affinché il programma sia valido. Dovrebbe rimanere vero dalla fine del costruttore all'inizio del distruttore ogni volta che l'oggetto non sta attualmente eseguendo un metodo che cambia il suo stato.

Un esempio di invariante potrebbe essere che esattamente una delle due variabili membro dovrebbe essere nullo. O che se uno ha un valore dato, allora l'insieme dei valori consentiti per l'altro è questo o quello ...

A volte uso una funzione membro dell'oggetto per verificare che l'invariante regga. Se questo non è il caso, viene sollevata un'asserzione. E il metodo viene chiamato all'inizio e all'uscita di ogni metodo che modifica l'oggetto (in C ++, questa è solo una riga ...)

    
risposta data 30.12.2010 - 23:54
fonte
7

Bene, le cose che vedo in questo thread sono tutte fantastiche, ma ho una definizione di "invariante" che è stata estremamente utile per me al lavoro.

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.

Questa definizione è utile perché elimina le condizioni in due gruppi: quelle del compilatore possono essere attendibili con l'imposizione e quelle che devono essere documentate, discusse, commentate o altrimenti comunicate ai contributori affinché possano interagire con il codebase senza introdurre bug.

Inoltre, questa definizione è utile perché ti permette di usare la generalizzazione, "Gli invarianti sono cattivi".

Ad esempio, il cambio in una macchina di trasmissione manuale è progettato per evitare un'invarianza. Se volessi, potrei costruire una trasmissione con una leva per ogni marcia. Questa leva potrebbe essere in avanti ("impegnata") o indietro ("disinnestata"). In tale sistema, ho creato un "invariante", che potrebbe essere documentato come tale:

"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 così, si potrebbero incolpare le trasmissioni rotte durante la guida in stato di abbandono. Le auto moderne, tuttavia, usano un solo bastone che ruota intorno agli ingranaggi. È progettato in modo tale che, su una moderna auto stick-shift, non è possibile impegnare due marce contemporaneamente.

In questo modo, potremmo dire che la trasmissione è stata progettata per "rimuovere l'invariante", perché non consente a se stessa di essere configurata meccanicamente in un modo che viola la regola logica.

Ogni invariante di questo tipo che rimuovi dal tuo codice è un miglioramento, perché riduce il carico cognitivo del lavoro con esso.

    
risposta data 19.01.2018 - 17:42
fonte
3

Un invariante (nel senso comune) indica alcune condizioni che devono essere vere in un determinato momento o anche durante l'esecuzione del programma. per esempio. Le pre-condizioni e le post-condizioni possono essere utilizzate per asserire alcune condizioni che devono essere vere quando viene chiamata una funzione e quando ritorna. Gli invarianti di oggetti possono essere usati per affermare che un oggetto deve avere uno stato valido per tutto il tempo in cui esiste. Questo è il principio del design per contratto.
Ho usato invarianti in modo informale usando i controlli nel codice. Ma più recentemente sto giocando con la biblioteca dei contratti per .Net che supporta direttamente gli invarianti.

    
risposta data 30.12.2010 - 22:48
fonte
3

Basato sulla seguente citazione da 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.

... Immagino "invariante"="condizione che vuoi mantenere per garantire l'effetto desiderato".

Sembra che l'invariante abbia due sensi che differiscono in modo sottile:

  1. Qualcosa che rimane uguale.
  2. Qualcosa che stai cercando di mantenere invariato, al fine di raggiungere l'obiettivo X (ad esempio un "tempo di ricerca del registro" sopra).

Quindi 1 è come un'asserzione; 2 è come uno strumento per dimostrare correttezza, prestazioni o altre proprietà - penso. Vedere l' articolo di Wikipedia per un esempio di 2 (che dimostra la correttezza della soluzione del puzzle MU).

In realtà un terzo senso di invariante è:

0,3. Cosa dovrebbe fare il programma (o modulo o funzione); in altre parole, il suo scopo.

Dallo stesso intervista di 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.

    
risposta data 20.02.2014 - 23:22
fonte
1

Un invariante è come una regola o un'ipotesi che può essere usata per dettare la logica del tuo programma.

Ad esempio, supponiamo di avere qualche applicazione software che tenga traccia degli account utente. Supponiamo anche che l'utente possa avere più account, ma per qualsiasi motivo è necessario distinguere tra account principale di un utente e account "alias".

Potrebbe trattarsi di un record DB o qualcos'altro, ma per ora lascia che ogni account utente sia rappresentato da un oggetto di classe.

classAccount utente {   private char * pUserName;   char privato * pParentAccountUserName;

... }

Un invariante potrebbe essere l'assunto che se pParentAccountUserName è NULL o vuoto, questo oggetto è l'account genitore. È possibile utilizzare questo invariante per distinguere diversi tipi di account. Probabilmente esistono metodi migliori per distinguere diversi tipi di account utente, quindi tieni presente che questo è solo un esempio per mostrare come potrebbe essere utilizzata un'invarianza.

    
risposta data 30.12.2010 - 22:59
fonte
1

Venendo da un contesto di fisica, in fisica abbiamo invarianti, che sono essenzialmente quantità che non variano nel corso di un intero calcolo / simulazione. Per esempio, in fisica, per un sistema chiuso l'energia totale è conservata. O ancora in fisica, se due particelle si scontrano, i frammenti risultanti devono contenere esattamente l'energia con cui hanno iniziato, e esattamente la stessa quantità di moto (una quantità di vettore). Di solito non ci sono abbastanza invarianti per specificare completamente il risultato. Per esempio nella collisione con le 2 parti, abbiamo quattro invarianti, tre componenti di quantità di moto e una componente di energia, ma il sistema ha sei gradi di libertà (sei numeri per descrivere il suo stato). Gli invarianti devono essere conservati entro un errore di arrotondamento, ma la loro conservazione non dimostra che la soluzione sia corretta.

In genere, queste cose sono importanti come controlli di integrità, ma da sole non possono dimostrare la correttezza.

    
risposta data 30.12.2010 - 23:20
fonte

Leggi altre domande sui tag