Misura di potenza diversa dalla completezza di Turing

18

Inizialmente ho provato a chiedermelo su StackOverflow, ma era troppo soggettivo Triste Sono interessato ai metodi per definire il potere dei linguaggi di programmazione. La completezza di Turing è una, ma è quasi universalmente soddisfatta. per definire una misura del potere che discrimina tra i linguaggi di programmazione effettivamente utilizzati.Per esempio, qualcuno può proporre un metodo non soggettivo che possa discriminare tra assembly e Java?

Completezza di Turing significa che un linguaggio è massimamente potente in ciò che può produrre (il che significa praticamente che può fare qualsiasi cosa che non sia basata nel tempo nel mondo reale). Quindi, se vogliamo definire una misura di potere più strong, dobbiamo adottare un altro approccio. La questione è stata suggerita nella domanda originale, ma non è affatto facile definirla. Qualcuno ha altri suggerimenti?

    
posta Casebash 04.09.2010 - 02:21
fonte

4 risposte

24

La nozione che stai cercando si chiama espressiveness e Matthias Felleisen ha una definizione matematicamente rigorosa:

"On the Expressive Power of Programming Languages"

www.ccs.neu.edu/scheme/pubs/scp91-felleisen.ps.gz (Postscript version)

L'intuizione dietro l'idea è che se hai due programmi equivalenti in due lingue diverse, ad esempio, programma A nella lingua X e programma B nella lingua Y-- e se apporti una modifica locale ad A che richiede un globale cambia in B, quindi X è più espressivo di Y.

Un esempio di Felleisen è l'assegnazione: nei linguaggi di programmazione Scheme è possibile rimuovere l'operatore di assegnazione e avere ancora una lingua completa di Turing. Tuttavia, in un linguaggio così limitato, l'aggiunta di una funzionalità che sarebbe stata localizzata se l'assegnazione fosse consentita richiederebbe una modifica globale del programma senza assegnazione.

La mia discussione ha semplificato alcuni dettagli e dovresti leggere il documento stesso per l'intero account.

Per rispondere alla tua altra domanda: puoi dire che Java è più espressivo dell'assemblaggio perché puoi aggiungere una nuova classe al tuo programma Java, e poi ottenere i benefici del polimorfismo facendo in modo che altre parti del tuo programma chiamino i suoi metodi senza global modifica. La gestione delle eccezioni è un altro esempio in cui Java è più espressivo dell'assembly: è sufficiente scrivere una singola istruzione throw per trasferire il controllo sullo stack. Ad un livello più elementare, puoi anche aggiungere una nuova istruzione case all'inizio di una switch e non dovrai preoccuparti di ricalcolare manualmente eventuali scarti di salto.

    
risposta data 29.10.2010 - 02:57
fonte
6

Se comprendo correttamente la tua domanda, stai comunque cercando qualcosa che sia relativamente misurabile e non solo una chiamata soggettiva. In tal caso, personalmente preferirei la quantità di tempo impiegato per risolvere ogni particolare problema (media su tutti i problemi e tutti i programmatori). In questa misura, potrebbe essere necessario considerare non solo il linguaggio stesso, ma anche il framework / API utilizzato con esso. La sintassi sintetica è un fattore molto piccolo: molto più importante è che la funzionalità più richiesta è facilmente accessibile.

Se stai cercando qualcosa di più soggettivo, direi quanto è divertente . I programmatori tendono ad essere persone che vogliono risolvere i problemi, quindi un linguaggio di programmazione che sia divertente da usare per i programmatori sarà inevitabilmente quello che risolverà la maggior parte dei problemi. Questa misura tiene conto del fatto che persone diverse hanno preferenze diverse su come usare le cose, quindi il linguaggio di programmazione "migliore" sarà quello più attraente per la più ampia gamma di programmatori. Tuttavia, potrebbe essere necessario prendere in considerazione non solo il linguaggio di programmazione e le API qui, ma anche l'ambiente (IDE), che è ovviamente ciò con cui il programmatore interagisce realmente.

    
risposta data 04.09.2010 - 21:38
fonte
1

Definire quanto sia potente una lingua per quanto produttiva puoi essere con essa. Molte persone tendono a parlare rapidamente di produttività in termini di scrittura del codice, ma poiché la maggior parte del ciclo di vita di un programma è la manutenzione, non lo sviluppo, una misura migliore è la facilità con cui puoi leggere e eseguire il debug del codice, specialmente quando è scritto da qualcuno altro. Le lingue più potenti sono quelle che sono più facili da leggere e gestire.

    
risposta data 10.09.2010 - 15:56
fonte
1

Devi definire meglio la terminologia.

La completezza di Turing non riguarda il "potere" nel senso che probabilmente intendi. Piuttosto riguarda la computabilità; cioè se una determinata lingua può esprimere qualsiasi programma che può essere implementato usando una macchina di Turing. Si scopre che praticamente ogni linguaggio di programmazione è completo di Turing.

Quello che probabilmente stai dopo è una misura di ciò che viene definito "espressività" del linguaggio di programmazione. Non sono sicuro che esista una misura del genere, o se lo fa, se è utile. Fondamentalmente, i diversi linguaggi di programmazione sono più adatti a esprimere soluzioni a diversi tipi di problemi.

Modifica

Solo per sillabare, i linguaggi di programmazione non hanno una proprietà conosciuta come "potere". Esiste un concetto comunemente noto come "espressività" o "potenza espressiva" di un linguaggio di programmazione. L'espressività riguarda in parte la facilità con cui si scrivono programmi concisi per affrontare problemi particolari. Ma c'è anche una misura considerevole di quanto sia facile leggere e scrivere i programmi. È una specie di "bellezza". Lo saprò quando lo vedrò, ma non chiedermi di definirlo.

Il semplice confronto dei conteggi dei caratteri non ti dà una misura adeguata di espressività. Altrimenti potresti rendere un linguaggio più espressivo comprimendo il codice sorgente ... e questo è assurdo. In effetti, non conosco alcuna misura oggettiva di espressività, e sospetto strongmente che non esista. Ciò rende efficacemente la caratteristica inutile e piuttosto poco interessante.

    
risposta data 05.09.2010 - 13:51
fonte

Leggi altre domande sui tag