Saranno prove di correttezza di codice mai andare mainstream? [chiuso]

Question

Tutti i programmi, ma la maggior parte banali sono pieni di bug e quindi tutto ciò che promette di rimuovere loro è estremamente allettante. Al momento, le prove di correttezza sono codice sono estremamente esoteriche, soprattutto a causa della difficilmente di imparare questo e lo sforzo supplementare necessario per dimostrare un programma corretto. Pensi che il codice proving potrà mai decollare?

Answer 1

Non proprio in quel senso, ma la programmazione funzionale pura è buono in questo dominio. Se si utilizza Haskell, è probabile che il vostro programma è corretta se i compila codice. Tranne da IO, un sistema di tipo bene è un buon aiuto.

la programmazione anche per contratto può essere utile. Vedere Contratti Microsoft Codice

Answer 2

Tutti i programmi, ma la maggior parte banali

non può essere pienamente provato di essere corretto con uno sforzo ragionevole. Per ogni prova formale della correttezza, è necessario almeno una specifica formale e che spec deve essere completa e corretta. Questo è in genere nulla è possibile creare facilmente per la maggior parte dei programmi del mondo reale. Ad esempio, prova a scrivere un tale specifica per qualcosa come l'interfaccia utente di questo sito discussione, e sai cosa voglio dire.

Qui ho trovato un bel articolo sul tema:

http://www.encyclopedia.com/doc/1O11-programcorrectnessproof.html

Answer 3

Il problema con le prove formali è che si muove solo il problema indietro di un passo.

Dire che un programma è corretta equivale a dire che un programma fa quello che dovrebbe fare. Come si fa a definire ciò che il programma dovrebbe fare? Si specifica di esso. E come si fa a definire ciò che il programma dovrebbe fare in casi limite che le specifiche non copre? Bene, allora dovete rendere le specifiche più dettagliate.

Quindi diciamo che il tuo spec finalmente diventa abbastanza dettagliata per descrivere il comportamento corretto di ogni aspetto di tutto il programma. Ora è necessario un modo per rendere i vostri strumenti di prova lo capiscono. In modo da avere a tradurre la specifica in una sorta di linguaggio formale che lo strumento prova può capire ... ehi, aspetta un attimo!

Answer 4

La verifica formale ha percorso una lunga strada, ma di solito l'industria / strumenti largamente utilizzati in ritardo le ultime ricerche. Ecco alcuni recenti sforzi in questa direzione:

http://research.microsoft.com/en-us/projects/specsharp/ Si tratta di un'estensione di C # che supporta i contratti di codice (pre / post condizioni e invarianti) e può utilizzare questi contratti a fare vari tipi di analisi statica.

progetti simili a questo esiste per altri linguaggi, come JML per Java, e Eiffel ha questo praticamente built-in.

Andando ancora oltre, progetti come sbattere e blast può essere utilizzato per verificare alcune proprietà comportamentali con il minimo programmatore annotazioni / intervento, ma ancora non può trattare con la piena generalità delle lingue moderne ( cose come integer overflow / aritmetica dei puntatori non sono modellate).

Credo che vedremo molto di più di queste tecniche utilizzate nella pratica in futuro. La barriera principale è che invarianti di programma sono difficili da dedurre, senza annotazioni manuali, ei programmatori sono di solito non vogliono fornire queste annotazioni perché così facendo è / ora troppo noioso consumando.

Answer 5

No, a meno di un metodo di provare automaticamente il codice senza un ampio lavoro di sviluppo si pone.

Answer 6

metodi formali strumenti (come ad esempio Frama-C critica software embedded C) può essere visto come (in ordine-of) che fornisce, o almeno controllare, un (correttezza) la prova di un dato software. (Controllo Frama-C che un programma obbediscono alla sua specifica formalizzata, in un certo senso, e rispettare invarianti esplicitamente annotati nel programma).

In alcuni settori, tali metodi formali sono possibili, per esempio come DO-178C per il software critico aerei civili. Quindi, in alcuni casi, tali approcci sono possibili e disponibili.

Naturalmente, lo sviluppo di software meno buggy è molto costoso. Ma l'approccio metodo formale senso per qualche tipo di software. Se siete pessimisti, si potrebbe pensare che il bug vengono spostati dal codice alla sua specifica formale (che può avere alcuni "bug", perché formalizzare il comportamento previsto di un software è difficile e soggetto a errori).

Answer 7

mi sono imbattuto su questa questione, e penso che questo legame potrebbe essere interessante:

applicazioni industriali di Astrée

Dimostrando l'assenza di RTE in un sistema utilizzato da Airbus con più di 130K righe di codice nel 2003 non sembra essere cattivo, e mi chiedo ci sarà qualcuno dire che questo non è il mondo reale.

Answer 8

No. Il proverbio comuni per questo è: "In teoria, teoria e pratica sono gli stessi. In pratica, non è".

Un esempio molto semplice:. Typos

In realtà l'esecuzione del codice tramite test unità rileva queste cose quasi subito, e un insieme coerente di test sarà negare la necessità di eventuali prove formali. Tutti i casi d'uso - buono, cattivo, di errore, e casi limite -. Devono essere enumerati nei test di unità, che finiscono come prova migliore è il codice è corretto di qualsiasi prova che è separato dal codice

Soprattutto se i requisiti cambiano, o l'algoritmo viene aggiornato per correggere un bug - la prova formale è più probabilità di finire fuori moda, uguale a commenti del codice ottenere spesso

.

Answer 9

Credo che i limiti imposti prove di correttezza a causa della arresto problema potrebbe essere il più grande barriera per le prove di correttezza diventando mainstream.

Answer 10

E 'gia' utilizzato da tutti. Ogni volta che si utilizza il controllo dei tipi del linguaggio di programmazione, si sta fondamentalmente facendo una prova di matematica della correttezza del programma. Questo funziona già molto bene - che richiede solo di scegliere i tipi corretti per ogni struttura e la funzione dei dati che si usa. Il più preciso il tipo, il meglio controllando che si vuole ottenere. I tipi esistenti disponibili in linguaggi di programmazione hanno già strumenti abbastanza potenti per descrivere quasi ogni comportamento possibile. Questo funziona in tutte le lingue disponibili. C ++ ed i linguaggi statici sono solo facendo i controlli in fase di compilazione, mentre le lingue più dinamici come Python stanno facendo quando il programma viene eseguito. Il controllo esiste ancora in tutte queste lingue. (Ad esempio, C ++ supporta già il controllo di effetti collaterali allo stesso modo Haskell fa, ma non vi resta che scegliere di usarlo.)