Programmi teoricamente privi di bug

Non è tanto che i programmi non possono essere privi di bug; è che è molto difficile dimostrarlo, se il programma che stai cercando di dimostrare non è banale.

Non per mancanza di tentativi, attenzione. I sistemi di tipo dovrebbero fornire una certa garanzia; Haskell ha un sistema di tipo altamente sofisticato che lo fa, in una certa misura. Ma non puoi mai rimuovere tutte le incertezze.

Considera la seguente funzione:

int add(int a, int b) { return a + b; }

Che cosa potrebbe andare storto con questa funzione? So già cosa stai pensando. Diciamo che abbiamo coperto tutte le basi, come il controllo dell'overflow, ecc. Cosa succede se un raggio cosmico colpisce il processore, causandone l'esecuzione

LaunchMissiles();

, invece?

OK, forse è un po 'forzato. Ma anche funzioni semplici come la funzione add di cui sopra devono operare in ambienti in cui il processore cambia continuamente contesti, passando tra thread multipli e core. In un ambiente come quello, può succedere di tutto. Se ne dubiti, allora considera che la RAM è affidabile, non perché sia priva di errori, ma perché ha un sistema integrato per correggere gli errori di bit che inevitabilmente si verificano.

So cosa stai pensando. "Ma sto parlando di software, non di hardware."

Ci sono molte tecniche che possono migliorare il tuo livello di confidenza che il software funziona nel modo previsto. La programmazione funzionale è una di queste. La programmazione funzionale consente di ragionare meglio sulla concorrenza. Ma la programmazione funzionale è non una dimostrazione, più di quanto non lo siano i test di unità.

Perché? Perché hai queste cose chiamate edge cases.

E una volta ottenuto solo un po 'oltre la semplicità di return a + b , diventa notevolmente difficile dimostrare la correttezza di un programma.

Ulteriori letture
Scrivono le cose giuste
Ariane 5 Explosion

Per prima cosa, stabiliamo in quale contesto desideri discutere. I programmatori Q & A allo Stack Exchange suggeriscono che probabilmente sei interessato all'esistenza del mondo reale di strumenti / lingue piuttosto che < a href="https://cstheory.stackexchange.com/"> teorico risultati e Informatica teoremi.

I have read lot of articles which state that code can't be bug-free

Spero di no, perché una tale affermazione non è corretta. Sebbene sia comunemente accettato che la maggior parte delle applicazioni su larga scala non siano prive di bug per il meglio delle mie conoscenze ed esperienze.

Più comunemente accettato è che esiste not (es. esistenza, non possibilità) uno strumento che determina perfettamente se un programma scritto in un Il linguaggio di programmazione completo di Turing è completamente privo di bug.

Una non-prova è un'estensione intuitiva del problema dell'arresto, combinata con i dati di osservazione dell'esperienza quotidiana.

Lì esiste esiste un software che può fare "prove di correttezza " che verifica che un programma soddisfi le specifiche specifiche per il programma corrispondenti.

Does this imply that every program will have at least one unintended behavior?

No. Sebbene le maggior parte delle applicazioni abbiano trovato almeno un bug o un comportamento non voluto.

Or does it mean that it's not possible to write code to verify it?

No, puoi usare le specifiche formali e gli assistenti di prova per verificare seguendo le specifiche , ma poiché l'esperienza ha dimostrato che gli errori possono ancora esistere nel sistema generale, come fattori esterni alle specifiche - il codice sorgente traduttore e amp; hardware, e gli errori più frequenti sono fatti nelle specifiche stesse.

Per ulteriori dettagli, vedi Coq è un tale strumento / lingua / sistema.

What about recursive checking?

Non lo so. Non ho familiarità con questo, e non sono sicuro che si tratti di un problema di computabilità o di un problema di ottimizzazione del compilatore.

I want to ask, does it imply that every code will get at least one unintended behaviour?

No. I programmi corretti possono essere e sono scritti. Intendiamoci, un programma può essere corretto, ma la sua esecuzione potrebbe fallire a causa, ad esempio, delle circostanze fisiche (come l'utente Robert Harvey ha scritto nella sua risposta qui ), ma questa è una questione distinta: il codice di quel programma è ancora corretto. Per essere più precisi, il errore non è causato da un errore o errore nel programma stesso, ma nel computer sottostante che lo esegue ( *).

(*) Sto prendendo in prestito le definizioni per errore , errore e errore dal campo affidabilità come, rispettivamente, un difetto statico, un stato interno errato e comportamento errato esterno osservato in base alle sue specifiche (vedere < eventuale carta da quel campo >).

Or, does it mean that I am not able to write code, which will check it?

Fai riferimento al caso generale nella dichiarazione precedente e sei corretto.

Potresti essere in grado di scrivere un programma che controlla se uno specifico programma X è corretto. Ad esempio, se definisci un programma "ciao mondo" come uno con due istruzioni in sequenza, ovvero print("hello world") e exit , puoi scrivere un programma che verifica se il suo input è un programma composto da queste due istruzioni in sequenza, riportando quindi se è corretto o meno un programma "ciao mondo".

Quello che non puoi fare usando le attuali formulazioni è scrivere un programma per controllare se un programma arbitrario si ferma, il che implica l'impossibilità di testare la correttezza nei casi generali.

L'esecuzione di due o più varianti dello stesso programma è una nota tecnica di tolleranza d'errore chiamata programmazione N-variante (o N-versione). È un riconoscimento della presenza di bug nel software.

Di solito queste varianti sono codificate da diversi team di sviluppo, utilizzando diversi compilatori e talvolta vengono eseguite su diverse CPU con diversi SO. I risultati vengono votati prima di essere inviati all'utente. Boeing e Airbus adorano questo tipo di architettura.

Restano due collegamenti deboli che portano a bug in modalità comune:

• Esiste solo una specifica.
• il sistema di votazione è unico o complesso.

Un programma ha alcune specifiche e funziona in qualche ambiente.

^{(l'esempio del raggio cosmico in altri risponde alla modifica di add in FireMissiles potrebbe essere considerato parte dell '"ambiente")}

Supponendo che tu possa specificare formalmente il comportamento previsto del programma (cioè le sue specifiche) e il suo ambiente, potresti a volte provare formalmente che il programma è ... in quel preciso senso privo di bug (quindi il suo comportamento o l'output rispetta la formalizzazione delle sue specifiche nella formalizzazione del suo ambiente).

In particolare, potresti usare analizzatori di suoni statici, come per es. Frama-C .

^{(ma lo stato attuale di tali analizzatori non consente l'analisi completa del programma e la dimostrazione di programmi su larga scala come il compilatore GCC o il browser Firefox o il kernel Linux e la mia credenza è che tali prove non accadrà nella mia vita. Sono nato nel 1959)}

Tuttavia, ciò che hai dimostrato è il comportamento corretto del programma w.r.t. alcune specifiche particolari in alcuni (classe di) ambiente (i).

In pratica, è possibile (e la NASA o l'ESA probabilmente lo vogliono) dimostrare che alcuni software di veicoli spaziali sono "senza bug" w.r.t. alcune specifiche precise e formalizzate. Ma ciò non significa che il tuo sistema si comporti sempre come vuoi.

In parole più semplici, se il tuo robot spaziale incontra alcuni E.T. e non l'hai specificato, non c'è modo di far si che il tuo robot si comporti come vuoi veramente ...

Leggi anche il blog di J.Pitrat .

BTW, il problema di Halting o il teorema di Gödel si applica probabilmente anche al cervello umano, o persino alla specie umana.

Does this imply that every program will have at least one unintended behavior?

No.

Il problema dell'arresto dice che è impossibile scrivere un programma che verifica se ogni programma si ferma in un tempo limitato. Ciò non significa che sia impossibile scrivere un programma che possa categorizzare alcuni programmi come fermanti, altri come non fermanti. Ciò che significa è che ci sono sempre dei programmi che un analizzatore non può categorizzare in un modo o nell'altro.

I teoremi di incompletezza di Gödel hanno un'area grigia simile a loro. Dato un sistema matematico di sufficiente complessità, ci saranno alcune affermazioni fatte nel contesto di quel sistema la cui veridicità non può essere valutata. Ciò non significa che i matematici debbano rinunciare all'idea di prova. La prova rimane la pietra angolare della matematica.

Alcuni programmi possono essere dimostrati come corretti. Non è facile, ma può essere fatto. Questo è l'obiettivo della dimostrazione teorica formale (una parte dei metodi formali). I teoremi di incompletezza di Gödel colpiscono qui: non tutti i programmi possono essere dimostrati corretti. Ciò non significa che sia assolutamente inutile utilizzare metodi formali perché alcuni programmi possono effettivamente essere dimostrati formalmente come corretti.

Nota: i metodi formali precludono la possibilità che un raggio cosmico colpisca il processore ed esegua launch_missiles() invece di a+b . Analizzano i programmi nel contesto di una macchina astratta piuttosto che di macchine reali che sono soggette a singoli eventi sconvolgenti come il raggio cosmico di Robert Harvey.

Ci sono molte buone risposte qui, ma sembrano gironzolare intorno al punto critico, che è questo: tutti questi teoremi hanno una struttura simile e dicono cose simili, e quello che dicono è non "è impossibile scrivere programmi corretti" (per alcuni valori specifici di "corretto" e "programma" che varia caso per caso), ma quello che fanno dice è "è impossibile impedire a qualcuno di scrivere un programma errato che non possiamo dimostrare essere errato "(ecc.)

Prendendo l'esempio specifico del problema dell'arresto, la differenza diventa più chiara: ovviamente ci sono programmi che si fermano, e altri programmi che non si fermano mai. Che ci sia una terza classe di programmi il cui comportamento non può essere determinato in un modo o nell'altro non è un problema se tutto ciò che vogliamo è scrivere un programma che stia fermando, in quanto possiamo semplicemente evitare di scrivere un programma che appartiene a quella classe. p>

Lo stesso vale per il teorema di Rice. Sì, per qualsiasi proprietà non banale di un programma possiamo scrivere un programma che non può avere quella proprietà provata vera o falsa; possiamo anche evitare di scrivere un programma del genere perché siamo in grado di determinare se un programma è dimostrabile.

La mia risposta sarà dal punto di vista degli affari del mondo reale e dalle sfide che ogni team di sviluppo dovrà affrontare. Quello che vedo in questa domanda e molte delle risposte è in realtà sul controllo dei difetti.

Il codice può essere privo di errori. Prendi uno qualsiasi dei campioni di codice "Hello World" per qualsiasi linguaggio di programmazione ed esegui quello sulla piattaforma a cui è destinato e funzionerà in modo coerente e produrrà i risultati desiderati. Finisce qualsiasi teoria sull'impossibilità che il codice sia privo di errori.

I potenziali bug arrivano mentre la logica diventa più complessa. Il semplice esempio Hello World non ha logica e fa sempre la stessa cosa statica. Non appena si aggiunge un comportamento dinamico guidato dalla logica, è ciò che introduce la complessità che porta ai bug. La logica stessa può essere imperfetta o i dati immessi nella logica possono variare in un modo che la logica non gestisce.

Una moderna applicazione dipende anche da librerie di run-time, CLR, middleware, database, ecc. che, pur risparmiando nel complesso il tempo di sviluppo, sono anche dei livelli in cui possono esistere bug all'interno di questi livelli e passare inosservati attraverso lo sviluppo e l'amp; Test UAT e in produzione.

Infine, la catena di app / sistemi che l'applicazione consuma dati che alimentano la sua logica sono tutte le fonti di potenziali bug o all'interno della loro logica, o all'interno del software impila la logica in cima oi sistemi a monte che consuma dati.

Gli sviluppatori non controllano al 100% ogni pezzo mobile che supporta la logica della loro applicazione. In realtà, non abbiamo il controllo di molto. Questo è il motivo per cui i test unitari sono importanti e la configurazione e la gestione delle modifiche sono processi importanti che non dobbiamo ignorare o essere pigri / sciatti.

Inoltre, accordi documentati tra la tua applicazione che consumano dati da un'origine al di fuori del tuo controllo, che definisce il formato e le specifiche specifici per i dati trasferiti, nonché qualsiasi limite o vincolo che il tuo sistema presume che il sistema di origine sia responsabile di garantire l'output è all'interno di questi limiti.

Nell'applicazione del mondo reale dell'ingegneria del software non sarete in grado di farlo volare spiegando al business perché teoricamente le applicazioni non possono essere prive di bug. Le discussioni di questa natura tra la tecnologia e il business non accadrà mai se non a seguito di un malfunzionamento tecnologico che ha influito sulla capacità dell'azienda di fare soldi, prevenire la perdita di denaro e / o tenere in vita le persone. La risposta a "come può accadere" non può essere "lascia che ti spieghi questa teoria così capisci".

In termini di massicci calcoli che teoricamente potrebbero richiedere sempre un tempo per eseguire il calcolo e ottenere un risultato, un'applicazione che non può terminare e restituire con un risultato - questo è un bug. Se la natura del calcolo è tale da richiedere molto tempo e molta intensità di calcolo, si accetta la richiesta e si fornisce un feedback all'utente come / quando è possibile recuperare il risultato e si avvia il thread parallelo per aggredirlo. Se questo deve accadere più rapidamente di quanto possa essere fatto su un server, e il business è abbastanza importante, allora lo ridimensiona su tutti i sistemi necessari. Questo è il motivo per cui il cloud è molto attraente e la capacità di far ruotare i nodi per lavorare e farli roteare quando è finito.

Se esiste la possibilità di ottenere una richiesta che nessuna quantità di potenza di calcolo possa essere completata, non dovrebbe rimanere bloccata all'infinito con un processo aziendale che attende la risposta a ciò che l'azienda ritiene sia un problema finito.

Non credo che il codice sia mai privo di errori al 100%, perché il codice non è mai veramente finito. Puoi sempre migliorare su ciò che scrivi.

La programmazione è un campo di scienza e matematica nel qual caso entrambi sono infiniti. Il bello di essere uno sviluppatore è che il nostro lavoro è infinito.

Ci sono mille modi per scrivere una singola riga di codice. L'idea è di scrivere la versione più ottimizzata di quella linea di codice ma potrebbe non essere priva di bug. Senza bug si riferisce all'idea che il tuo codice sia indistruttibile e che tutto il codice possa essere rotto in qualche modo o metodo.

Quindi il codice può essere efficiente? Sì.
Il codice può essere ottimizzato all'infinito? Sì.
Il codice può essere privo di errori? No, semplicemente non hai ancora trovato un modo per romperlo.
Detto questo, se ti sforzi di migliorare te stesso e le tue pratiche di scrittura del codice, il tuo codice sarà difficile da violare.