Non è esattamente chiaro cosa stai chiedendo.
Puoi sempre provare un programma corretto, se vuoi. Questo è indipendente dalla lingua.
La domanda è: puoi chiedere al computer di fare la prova per te o almeno controllare una prova da te fornita? E la risposta è: Sì!
In effetti, il Curry-Howard-Isomorphism afferma che esiste un isomorfismo tra logica e programmazione, tra prove e programmi, tra teoremi e tipi. Ogni tipo è un teorema (e viceversa), ogni programma è una prova (e viceversa). Quindi, in un certo senso, ogni linguaggio tipizzato staticamente lo fa; ogni type checker è un dimostratore di teoremi!
Tuttavia, c'è un limite a ciò che puoi esprimere in un tipo. Haskell ti consente di esprimere più di, per esempio, Java, ma ce n'è ancora di più. In un linguaggio tipizzato, i tipi statici possono dipendere dai valori di runtime. Ad esempio, potrebbe esserci un tipo List<n>
che è una lista con n
elementi, dove n
è un valore determinato solo in fase di esecuzione.
Ora, per digitare type-check un programma di questo tipo, il type checker deve essere in grado di dimostrare staticamente le proprietà sui valori di runtime, ma sappiamo tutti che questo ci consente di eseguire rapidamente il problema di interruzione. Bene, i linguaggi tipizzati in modo dipendente hanno una soluzione semplice: non consentono la non-terminazione, sono totali , cioè essi sempre terminano, quindi il problema di interruzione non applicare.
Ovviamente, questo significa che non sono completi di Turing, ma suona più spaventoso di quanto non sia in realtà. In primo luogo, ci sono molte lingue che non sono complete di Turing, ma comunque utili: regex, SQL (prima del 2003), HTML + CSS (prima di HTML5 + CSS3) e molti altri. Infatti, poiché la specifica C richiede che io possa prendere l'indirizzo di qualsiasi oggetto e la dimensione di qualsiasi oggetto, ed entrambi devono inserirsi in un numero intero finito, C non è tecnicamente completo di Turing, perché non lo fa avere una memoria infinita Allo stesso modo, i nostri computer non sono completi di Turing, infatti, è fisicamente impossibile costruire una macchina di calcolo completa di Turing.
Ma questo è un taglio di capelli, ci sono molte più considerazioni pratiche. Ad esempio, si potrebbe pensare che un sistema operativo, un server Web o qualsiasi cosa con un ciclo di eventi non possa essere costruito con una lingua che non è completa con Turing. Ma si scopre che invece di modellare, per esempio, un sistema operativo come un loop infinito (o piuttosto una ricorsione infinita) sui dati, possiamo anche modellarlo usando la ricorsione congiunta finita su co-dati! E infatti, ci sono molti modelli di questo tipo per problemi che a prima vista potrebbero richiedere un ciclo infinito o una ricorsione non terminante.
Le lingue tipizzate in modo discendente rientrano in tre campi principali:
- Assistenti per la prova (interattivi): si tratta di programmi progettati principalmente per prove computerizzate. Il fatto che si possa anche programmare in essi è piuttosto incidentale.
- Lingue tipizzate in modo dipendente: queste sono principalmente intese come linguaggi di programmazione, il linguaggio stesso di solito non offre strumenti per semplificare la parte "prova".
- Approcci integrati, in cui l'IDE per la lingua contiene un assistente di prova interattivo che ti aiuta a costruire le prove mentre stai costruendo il programma, in modo simile a come un IDE moderno con debugging visivo interattivo, profiling, ecc. ti aiuta con la costruzione di programmi.
Alcune di queste lingue / sistemi di prova sono (in nessun ordine particolare):
Di questi, Coq è il più maturo. Tuttavia, non era chiaramente progettato per la programmazione. Quando viene visto come un linguaggio di programmazione, in realtà non è molto bello.
OTOH, Idris è in qualche modo nuovo, ma è chiaramente concepito come linguaggio di programmazione. È molto simile a Haskell. Potresti pensarlo come Haskell-with-dependent-types.
ATS è diverso dagli altri. Non è una lingua completamente dipendente / assistente di prova. Piuttosto è stato progettato come un linguaggio di programmazione dei sistemi, come sostituto di C, C ++, D, Java, C # e linguaggi simili con prestazioni paragonabili a C, e "abbastanza tipizzazione dipendente da dimostrare alcune proprietà interessanti". ATS non è orientato a provare tutto, ma piuttosto a specifiche proprietà di sicurezza di sistemi software come sistemi operativi, compilatori, server, ecc.