Possiamo mai specificare completamente, completamente qualcosa? [chiuso]

4

Questa domanda è più teorica che pratica. Immagina di avere una macchina intelligente che, se viene alimentata con una specifica completa di un oggetto, quella macchina produrrà esattamente quell'oggetto e non altro.

Ora, possiamo mai raggiungere una specifica completa di qualsiasi cosa?

Se vuoi una domanda più pratica: la "Specifica del linguaggio Java" ufficiale è completa? O in altre parole: c'è un pezzo di codice Java conforme al JLS, ma non è accettato dal compilatore corrispondente a quello JLS?

    
posta CuongHuyTo 06.04.2016 - 07:24
fonte

4 risposte

8

Sì, è possibile. La matematica e la logica formale consentono di definire calcoli che hanno esattamente le proprietà che si desidera e nient'altro. E poi la stessa logica ti permette di dimostrare che è così.

Il problema è che richiede uno sforzo enorme per farlo. Anche la scrittura di un ciclo for semplice potrebbe richiedere giorni per essere convalidata. Questo è il motivo per cui questo approccio viene usato raramente e, anche se viene utilizzato, viene applicato solo a parti critiche del sistema.

    
risposta data 06.04.2016 - 08:14
fonte
7

Ricorda che un linguaggio di programmazione è una specifica, solitamente scritta in inglese, con l'ambiguità del linguaggio naturale, in alcuni rapporti tecnici. Un linguaggio di programmazione non è la stessa della sua implementazione in alcuni software per compilatori o interpreti.

Un linguaggio di programmazione (specifica) non è solo o principalmente sulla sintassi (che potrebbe essere formalizzata con EBNF ), ma ulteriori informazioni sulla semantica . La semantica può essere in qualche modo formalizzata, ad es. con semantica denotazionale .

Non posso ragionevolmente aspettarmi dal mio compilatore C di accettare tutti programmi sintatticamente o semanticamente validi. Sono sicuro che nessun compilatore & il computer potrebbe elaborare un file C contenente alcune funzioni con un miliardo di istruzioni C, profondamente annidate e combinate in uno strano grafico di controllo. In realtà, abilito le ottimizzazioni compilando con gcc -O2 , e ho osservato empiricamente che il tempo di compilazione è proporzionale al quadrato della lunghezza della funzione più lunga. Quindi, quando genero il codice C, amo la metaprogrammazione, devo fare attenzione a evitare di generare funzioni C con più di una dozzina di migliaia di affermazioni. AFAIK lo standard o la mia documentazione del compilatore non sta affermando questa limitazione.

Purtroppo, il JLS non tenta nemmeno di formalizzare parzialmente alcuni la semantica della lingua.

Alcuni linguaggi di programmazione hanno alcune formalizzazioni parziali della loro semantica. Un buon esempio di questo è il R5RS per Scheme, ha parzialmente formalizzato alcuni degli aspetti semantici di Scheme (ma lasciare una meritata libertà agli implementatori, come l'ordine di valutazione degli argomenti nella chiamata di funzione, è difficile da formalizzare).

Ma i linguaggi di programmazione hanno anche una certa pragmatica. Leggi il libro di Scott su pragmatica del linguaggio di programmazione , è illuminante.

Un buon esempio di pragmatica è la malloc funzione standard di C11 . Lo standard n1570 (bozza) dice (in §7.22.3, in particolare §7.22.3.5):

If the space cannot be allocated, a null pointer is returned.

...

void *malloc(size_t size);

...

The malloc function allocates space for an object whose size is specified by size and whose value is indeterminate.

...

The malloc function returns either a null pointer or a pointer to the allocated space.

...

La mia comprensione dello standard C11 è che la seguente funzione è un'implementazione valida di malloc (conforme alla lettera dello standard C11 e probabilmente di uno POSIX).

 void* malloc(size_t sz) { errno = ENOMEM; return NULL; }

(certo che l'implementazione è contraria allo spirito di C; dichiaro che segue la lettera dello standard)

ma nessuno sviluppatore C sane si aspetta una tale implementazione. Un programmatore C si aspetta che malloc a di solito abbia successo. Ciò che significa esattamente non è chiaro.

Now, can we ever achieve a fully complete specification of anything ?

Credo che no. Un vero computer è diverso dall'astrazione che stiamo programmando. Prendi il mio laptop Linux per esempio. Se lo caccio dalla mia scrivania, se la batteria esplode, o se qualcuno vi lancia una pallottola, non si comporta come l'astrazione che sto programmando. E una specifica completa richiederebbe una descrizione completa dell'ambiente (cioè dell'universo fisico in cui ci troviamo), che non è possibile.

Alcuni scienziati quantistici affermano che l'universo ha un numero finito ma enorme di stati. Se ciò è "vero", nessuna descrizione completa di esso può esistere in una sottoparte, ad es. sulla Terra.

La programmazione del computer riguarda sempre le astrazioni. Leggi anche su comportamento non definito (in particolare Cataloghi del blog di Lattner a riguardo) e su comportamento non specificato . Si noti che lo standard C è volutamente (e per buoni motivi) menzionato in molti punti comportamento indefinito . Prova a evitarlo .

    
risposta data 06.04.2016 - 09:23
fonte
3

Queste sono due domande molto diverse in una.

Sicuramente puoi dare una specifica completa per un pezzo di software (immagino sia quello che intendi veramente, non "nulla") che poi potrebbe essere costruito automaticamente, se i requisiti sono abbastanza semplici. Ad esempio, si può sicuramente specificare una funzione senza parametri che restituiscono sempre 0 in modo leggibile dalla macchina. Ciò, tuttavia, non significa che l'implementazione della funzione generata sarà unica. Ad esempio, esistono trilioni di modi per implementare una funzione che restituisce sempre 0.

La tua seconda domanda è molto diversa. Se un compilatore non accetta un pezzo specifico di codice Java, forse il compilatore ha un bug o la specifica, ma ciò non significa che non possa essere risolto, almeno in linea di principio. Ma anche se hai due compilatori privi di bug al 100% (puramente ipotetici!), Entrambi conformi alle specifiche, ciò non significa che siano implementati in modo identico.

    
risposta data 06.04.2016 - 07:46
fonte
0

Quando viene sviluppato un software, dallo stesso creatore, che sa cosa dovrebbe fare il suo software, allora la specifica è completa. Il linguaggio Java è stato sviluppato dallo sviluppatore incorniciando le specifiche che sembravano complete allo sviluppatore, assicurandosi che il compilatore supportasse il design. Ma, una volta che Java divenne un linguaggio comune, si aspettava che facesse molto di più.

Ad esempio, considera gli array java. Array è una meravigliosa creazione del creatore. Ma, immagino, non avrebbe mai immaginato che la sua creazione di array sarebbe stata così grande da poter crescere fino a 2 ^ 31-1 elementi che il compilatore rifiuterà. JLS specifica questo come una limitazione.

Le specifiche complete sono possibili per qualcosa di ipotetico o ideale. In tempo reale non può esserci nulla che possa essere specificato completamente.

Per ulteriori limitazioni di JLS, fai riferimento al seguente link:
link

    
risposta data 06.04.2016 - 08:52
fonte

Leggi altre domande sui tag