Digitare il sistema per le prestazioni

11

Esistono sistemi di tipo statico che tentano di formalizzare le caratteristiche di prestazione dei programmi? Non riesco a trovare sembrano trovare tali tentativi.

Poiché i sistemi di tipo sono (uno dei) strumenti più potenti nell'arsenale del programmatore per fare affermazioni sui programmi, e dal momento che ci sono molti casi in cui le prestazioni sono critiche, non sembra inverosimile immaginare tentativi fatti è stato intrapreso per creare un sistema di tipi che tenta di fare almeno alcune affermazioni sulle caratteristiche di memorizzazione e di runtime dei programmi.

    
posta Klaas van Schelven 06.07.2015 - 12:04
fonte

2 risposte

6

Potresti immaginare un sistema di tipi abbastanza sofisticato da essere correlato a WCET o complexity del programma. Quindi, il problema è di creare un analizzatore di suoni (o controllore) - ovvero le regole di digitazione - per renderlo possibile e implementarlo in modo sufficientemente efficiente da renderlo ragionevolmente utile.

La maggior parte dei sistemi di tipi sono abbastanza semplici da essere veloci da calcolare nella pratica (almeno per il ragionevole insieme di programmi che uno sviluppatore umano potrebbe scrivere manualmente).

Alcuni linguaggi di programmazione accademici (ad es. AGDA ) hanno sistemi di tipi molto sofisticati che sono completi di Turing, quindi il loro compilatore può richiedere una grande (forse infinita) quantità di tempo.

(Se capisco bene, il lavoro di dottorato di Jérémie Salvucci in corso al LIP6 di Parigi è abbastanza legato alla tua domanda: gli ho mandato un'email a riguardo, potresti cercare regioni e tipi ...).

Sii comunque consapevole del teorema di Rice & il problema di interruzione . I sistemi di tipo potrebbero non essere sempre il proiettile d'argento che potresti desiderare di essere (vedi il vecchio nessun proiettile d'argento libro).

    
risposta data 06.07.2015 - 12:36
fonte
3

Sembra eminentemente possibile creare un sistema di tipi che categorizzi le caratteristiche delle prestazioni di tipi (ad esempio "veloce / lento per accesso seriale", veloce / lento per accesso casuale "," efficiente memoria / inefficiente Tali tratti potrebbero essere tipi astratti inseriti nella gerarchia in modo tale che i tipi più concreti vengano ereditati da essi. Tuttavia, le prestazioni di qualsiasi programma che utilizza tali tipi dipenderebbero dal modo in cui vengono effettivamente utilizzati / utilizzati. digitare il sistema per fare affermazioni sul programma stesso, l'uso di (accesso a) quei tipi dovrebbero essere rappresentati come tipi.Questo significherebbe rinunciare all'uso di strutture di controllo integrate (ad esempio per / while loop) e invece usare tipi Quindi, la gerarchia potrebbe avere un tipo di accesso seriale e un elenco discendente di tipo seriale-accesso, tipi di accesso seriale-albero e così via. L'efficienza di utilizzo potrebbe quindi essere almeno in parte espressa dalla combinazione e applicazione di questi tipi a ciascuno altro.

In un linguaggio funzionale come Haskell - che comunque non ha quasi nessuna struttura di controllo - questo mi sembra abbastanza pratico e applicabile. In Java, tuttavia, un tale sistema sembra molto meno realizzabile (non so molto dall'implementazione a partire dall'applicabilità / attendibilità del risultato).

Haskell ci consente già di stabilire in modo definitivo quanta parte di un programma è pura e fornisce modi per limitare particolari attività all'interno di scatole sigillate. Dal momento che parallelismo / concorrenza in Haskell è implementato attraverso il sistema dei tipi , si potrebbe sostenere che è già parte del modo in cui ciò che vuoi). Al contrario, i linguaggi imperativi (anche quelli tipizzati staticamente come Java) offrono al programmatore molti, molti modi per sovvertire qualsiasi tentativo.

    
risposta data 06.07.2015 - 13:42
fonte

Leggi altre domande sui tag