Ci sono lingue del mondo reale dimostrabili? (Scala?)

StackOverflow https://stackoverflow.com/questions/4065001

Domanda

Mi è stato insegnato sui sistemi formali all'università, ma mi ha deluso come non l'hanno fatto sembrano essere usati nel mondo reale.

Mi piace l'idea di essere in grado di sapere che un certo codice (oggetto, una funzione, a prescindere) funziona, non per il test, ma da prova .

Sono sicuro che siamo tutti familiarità con i parallelismi che non esistono tra ingegneria fisica e ingegneria del software (si comporta in acciaio prevedibilmente, un software in grado di fare qualsiasi cosa -! Chi lo sa), e mi piacerebbe sapere se ci sono tutte le lingue che possono essere utilizzati nel mondo reale (chiede un framework web chiedere troppo?)

Ho sentito cose interessanti circa la verificabilità dei linguaggi funzionali come scala.

Come software ingegneri che opzioni abbiamo?

È stato utile?

Soluzione

Sì, ci sono linguaggi progettati per la scrittura di software dimostrabilmente corretto. Alcuni sono anche utilizzati nell'industria. Spark Ada è probabilmente l'esempio più evidente. Ho parlato con alcune persone a Praxis Critical Systems Limited che lo usavano per il codice in esecuzione su boing (per il monitoraggio del motore) e sembra piuttosto bella. (Qui è un grande sintesi / descrizione del linguaggio .) Questo linguaggio e sistema di prova che accompagna utilizza la seconda tecnica descritta di seguito. Non ha nemmeno supporta allocazione dinamica della memoria!

La mia impressione e l'esperienza è che ci sono due tecniche per la scrittura di software corretto:

  • Tecnica 1: scrivere il software in una lingua che a tuo agio con (C, C ++ o Java per esempio). Prendere una specifica formale di tale linguaggio, e dimostrare la vostra programma corretto.

    Se la vostra ambizione è quella di essere corretta al 100% (che è più spesso un requisito in automobile / aerospaziale) si sarebbe spesa po 'di programmazione di tempo, e più tempo di lievitazione.

  • Tecnica 2: Scrivere il software in un linguaggio un po 'più scomodo (un sottoinsieme di Ada o una versione ottimizzato di OCaml per esempio) e scrivere la dimostrazione di correttezza lungo la strada. Qui la programmazione e dimostrando va di pari passo. Programmazione in Coq loro equivale addirittura completamente! (Vedere la di Curry-Howard corrispondenza )

    In questi scenari sarai sempre finire con un programma corretto. (Un bug sarà garantita essere radicata nella specifica.) Sarete propensi a spendere più tempo sulla programmazione, ma d'altra parte si sta dimostrando che correggere lungo la strada.

Si noti che entrambi gli approcci cerniere sul fatto di avere una specifica formale a portata di mano (come altro vuoi dire che cosa è il comportamento corretto / errato), e un formalmente definiti semantica del linguaggio (in quale altro modo sarebbe in grado di dire cosa il comportamento reale del vostro programma è).

Ecco alcuni esempi di più di approcci formali. Se si tratta di "mondo reale" o no, dipende da chi si chiede: -)

Non conosco un solo "dimostrabilmente corretto" linguaggio web-application : UR . A Ur-programma che "passa attraverso il compilatore" è garantito che non:

  • soffre di una qualsiasi tipi di attacchi di code-iniezione
  • Return HTML non valido
  • Contenere morti collegamenti intra-Application
  • Ha squilibri tra moduli HTML ed i campi previsti per i loro gestori
  • Inserisci il codice lato client che rende presupposti non corretti sulla "AJAX" servizi -stile che il server Web remoti, fornisce
  • Tentativo non valido di SQL query
  • Usa marshalling improprio o unmarshalling in comunicazione con i database SQL o tra browser e server web

Altri suggerimenti

Al fine di rispondere a questa domanda, si ha realmente bisogno di definire cosa si intende per "dimostrabile". Come Ricky ha sottolineato, qualsiasi lingua con un sistema di tipo è una lingua con un sistema integrato di prova, che viene eseguito ogni volta che si compila il programma. Questi sistemi di prova sono quasi sempre tristemente impotenti - rispondere a domande come String vs Int ed evitando domande come "è la lista ordinata?" - ma sono i sistemi a prova di nessuno-la-meno

.

Purtroppo, il più sofisticato i vostri obiettivi di prova, più difficile è quello di lavorare con un sistema in grado di controllare le vostre prove. Questo intensifica abbastanza rapidamente in indecidibilità se si considera la vastità della classe di problemi che sono indecidibile su macchine di Turing. Certo, in teoria si possono fare cose di base come attestano l'esattezza della vostra algoritmo di ordinamento, ma niente di più di quello che sta per essere calpestando sul ghiaccio molto sottile.

Anche per dimostrare qualcosa di semplice come la correttezza di un algoritmo di ordinamento richiede un sistema a prova relativamente sofisticato. (Nota: dal momento che abbiamo già stabilito che i sistemi di tipo sono un sistema a prova costruita nella lingua, ho intenzione di parlare di cose in termini di teoria dei tipi, piuttosto che agitando le mani ancora più vigorosamente) Sono abbastanza certo che un piena prova di correttezza nella lista di ordinamento richiederebbe una qualche forma di tipi dipendenti, altrimenti non si ha modo referenziare valori relativi al livello tipo. Questo inizia immediatamente la rottura nei regni della teoria dei tipi che hanno dimostrato di essere indecidibile. Così, mentre si può essere in grado di dimostrare la correttezza sulla vostra lista algoritmo di ordinamento, l'unico modo per farlo sarebbe quello di utilizzare un sistema che vi permetterà anche di esprimere prove che non si può verificare. Personalmente, trovo questo molto sconcertante.

C'è anche l'aspetto facilità d'uso che ho accennato in precedenza. Il più sofisticato sistema tipo, il meno piacevole è quello di utilizzare. Questa non è una regola dura e veloce, ma penso che vale per la maggior parte. E come in ogni sistema formale, si trovano spesso che esprimere la prova è più lavoro (e più soggetto a errori) che creare l'attuazione, in primo luogo.

Con tutto quello che fuori del modo, vale la pena di notare che il sistema di tipi di Scala (come Haskell di) è Turing completo, che significa che è possibile teoricamente usarlo per dimostrare tutta la proprietà decidibile sul codice, a condizione che avete scritto il codice in tal modo un che sia suscettibile di tali prove. Haskell è quasi certamente un linguaggio migliore per questo che Java (dal programmazione tipo di livello in Haskell è simile a Prolog, mentre la programmazione tipo di livello in Scala è più simile a SML). Io non consiglio di utilizzare i sistemi di tipi di Scala o Haskell di in questo modo (prove formali di algoritmico correttezza), ma l'opzione è teoricamente disponibile.

Nel complesso, credo che il motivo non avete visto i sistemi formali nel "mondo reale" deriva dal fatto che i sistemi dimostrazione formale hanno ceduto alla tirannia spietata del pragmatismo. Come ho già detto, c'è così tanto sforzo coinvolti nella realizzazione di vostre prove di correttezza che è quasi mai utile. L'industria ha deciso molto tempo fa che era più facile per creare test ad hoc di quanto non fosse a passare attraverso qualsiasi tipo di ragionamento analitico formale.

lingue digitati dimostrano l'assenza di alcune categorie di colpa. Il più avanzato sistema tipo, più difetti che possono dimostrare l'assenza di.

Per la prova che un intero programma funziona, sì, si sta intensificando di fuori dei confini dei linguaggi ordinari, in cui la matematica e si incontrano di programmazione l'altro, si stringono la mano e poi procedere a parlare usando simboli greci su come i programmatori non possono gestire greca simboli. Si tratta di circa il Σ di esso comunque.

Si sta facendo una domanda che molti di noi hanno chiesto nel corso degli anni. Non so che ho una buona risposta, ma qui ci sono alcuni pezzi:

  • Ci sono lingue ben compreso con la possibilità di essere dimostrata oggi in uso; Lisp tramite ACL2 è uno, e, naturalmente, Scheme ha un ben inteso definizione formale pure.

  • una serie di sistemi hanno cercato di utilizzare linguaggi puri funzionali, o quelli quasi puri, come Haskell. C'è un bel po 'di lavoro metodi formali in Haskell.

  • Tornando 20 anni, c'è stata una cosa di breve durata per l'utilizzo di mano la prova di un linguaggio formale che è stato poi rigorosamente tradotto in un linguaggio compilato. Alcuni esempi erano di IBM Software camere bianche, ACL, Zingaro, e Rose di Logica Computazionale, John McHugh e il mio lavoro su affidabile compilazione di C, e il mio lavoro a portata di mano a prova per i sistemi di programmazione C. Questi tutti ottenuto una certa attenzione, ma nessuno di loro ha reso molto in pratica.

Una domanda interessante per chiedere, credo, è ciò che sarebbe condizioni sufficienti quella di ottenere approcci formali in pratica? Mi piacerebbe sentire alcuni suggerimenti.

È possibile esaminare puramente linguaggi funzionali come Haskell, che vengono utilizzati quando uno dei vostri requisiti è dimostrabilità .

Questa è una lettura divertente, se siete interessati circa linguaggi di programmazione funzionale e pura linguaggi di programmazione funzionale.

usi del mondo reale di tali lingue dimostrabili sarebbe incredibilmente difficile da scrivere e capire dopo Woods. il mondo delle imprese ha bisogno di software di lavoro, veloce.

"dimostrabili" lingue appena scala Dont per la scrittura / lettura di codice di base di un ampio progetto e sembrano solo di lavoro nelle piccole e isolati casi d'uso.

sono coinvolto in due lingue dimostrabili. La prima è la lingua supportata da Perfect Developer, un sistema per specificare sotfware, raffinazione e generazione di codice. E 'stato utilizzato per alcuni grandi sistemi, tra cui PD stesso, ed è insegnato in diverse università. La seconda lingua dimostrabile che sono coinvolto con è un sottoinsieme dimostrabile di MISRA-C, vedi C / C ++ di verifica Blog di più.

Omega .

introduzione contiene un'implementazione relativamente indolore di alberi AVL con incluso prova di correttezza.

Scala è destinata ad essere "mondo reale", in modo che nessuno sforzo è stato fatto per rendere più dimostrabile. Cosa si può fare a Scala è quello di produrre codice funzionale. codice funzionale è molto più facile da testare, che è secondo me un buon compromesso tra "mondo reale" e dimostrabilità.

EDIT ===== Rimosso mie idee errate su ML essere "dimostrabile".

Il mio (controversa) definizione di "mondo reale" nel contesto del codice dimostrabilmente-corretto è:

  • Si deve comportare un certo grado di automazione , altrimenti si sta andando a spendere troppo tempo di lievitazione e si occupano di piccoli dettagli disordinati, e sta andando ad essere del tutto impraticabile (tranne forse per il controllo del veicolo spaziale software e questo genere di cose, per i quali si potrebbe effettivamente desiderare di trascorrere megabucks sui controlli meticolosi).
  • Deve sostenere un certo grado di programmazione funzionale , che consente di scrivere codice che è molto modulare, riutilizzabile e facile da ragionare su. Ovviamente la programmazione funzionale non è necessaria per la scrittura o provare Ciao Mondo, o una varietà di programmi semplici, ma ad un certo punto, la programmazione funzionale non diventare molto utile.
  • Anche se non devono necessariamente essere in grado di scrivere il codice in un linguaggio di programmazione tradizionale, in alternativa, si dovrebbe almeno essere in grado di macchina tradurre il vostro codice in codice ragionevolmente efficiente scritto in un linguaggio di programmazione mainstream, in modo affidabile.

È possibile che questo sono requisiti relativamente più universali. Altri, come la possibilità di modellare il codice imperativo, ovvero la possibilità di dimostrare di ordine superiore funzioni corretto, può essere importante o essenziale per alcuni compiti, ma non tutti.

In considerazione di questi punti, molti degli strumenti elencati in questo post del blog di mine può essere utile - anche se sono quasi tutti o nuova e sperimentale, o sconosciuti alla stragrande maggioranza dei programmatori del settore. Ci sono alcuni strumenti molto maturo coperti però.

Come su Idris e Agda ? Reale abbastanza mondo?

Come un buon esempio di vita reale, c'è un progetto che mira a fornire un verificata libreria HTTP REST scritta in Agda, chiamato Lemmachine: https://github.com/larrytheliquid/Lemmachine

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top