Che cosa significa per un linguaggio per essere digitato in modo statico?

Question

La mia comprensione è che significa che uno può potenzialmente scrivere un programma per formalmente dimostrare che un programma scritto in un linguaggio a tipizzazione statica sarà libero di un certo (piccolo) sottoinsieme di difetti.

Il mio problema è il seguente:

Si supponga che abbiamo due lingue Turing completi, A e B. A si presume essere 'SICURO tipo' e 'B' si presume di non essere. Supponiamo che io sono dato un programma di L per verificare la correttezza di qualsiasi programma scritto in A. Che cosa è per impedirmi di tradurre qualsiasi programma scritto in B ad A, l'applicazione di L. Se P traduce da A a B, allora perché non è un PL tipo valido checker per qualsiasi programma scritto in B?

io sono addestrato in Algebra e sto appena iniziando a studiare CS quindi ci potrebbe essere qualche ragione evidente che questo non funziona, ma mi piacerebbe molto sapere. Tutta questa faccenda 'la sicurezza di tipo' è odore di pesce a me per un po '.

Answer 1

Sia ALLA lingua Turing-complete che dovrebbe essere a tipizzazione statica e lasciare che un' essere la lingua che si ottiene da A quando si rimuove il controllo dei tipi (ma non le annotazioni di tipo perché servono anche altri scopi). I programmi accettati di A saranno un sottoinsieme dei programmi accettati di A'. Così, in particolare, A' sarà anche Turing-completo.

Dato il tuo traduttore P da B ad A (e viceversa). Che cosa è dovuto fare? Si potrebbe fare una delle due cose:

1. In primo luogo, si potrebbe tradurre ogni programma y di B a un programma di A. In questo caso, sarebbe sempre LPY return true come i programmi di A sono, per definizione, digitato correttamente.

2. In secondo luogo, P potrebbe tradurre ogni programma y di B ad un programma di A'. In questo caso, LPY sarebbe ritornato True se Py sembra essere un programma di A e False se no.

Mentre il primo caso non produce nulla di interessante, cerchiamo di attenerci al secondo caso, che è probabilmente quello che vuoi dire. Ha la funzione LP definita su programmi di B ci dice qualcosa di interessante sui programmi di B? Io non dico, perché non è invariante sotto un cambiamento di P. Poiché A è Turing-complete, anche nel secondo caso P potrebbe essere scelto in modo che la sua immagine succede trovano in A. Poi LP sarebbe sempre vero. D'altra parte, P potrebbe essere scelta in modo che alcuni programmi sono mappati al complemento di A in A'. In questo caso LP avrebbe sputato fuori False per alcuni (forse tutti) i programmi di B. Come si può vedere, non si ottiene tutto ciò che dipende solo da y.

Posso anche messo più matematicamente nel modo seguente: C'è una categoria C di linguaggi di programmazione i cui oggetti sono i linguaggi di programmazione e le cui morfismi sono traduttori da un linguaggio di programmazione ad un altro. In particolare, se esiste un morfismo P: X -> Y, Y è almeno espressivo come X. Tra ogni coppia di Turing-completo lingue ci sono morfismi in entrambe le direzioni. Per ogni oggetto X di C (vale a dire per ogni linguaggio di programmazione) abbiamo un insieme associato, ad esempio {X} (mala notazione, so) di tali funzioni parzialmente definiti che possono essere calcolate da programmi di X. Ogni morfismo P: X - > Y induce quindi un'inclusione {X} -> {Y} di insiemi. Vediamo formalmente invertito tutti coloro morfismi P: X -> Y che inducono l'identità {X} -> {Y}. Chiamerò la categoria risultante (che è, in termini matematici, una localizzazione di C) C'. Ora l'inclusione A -> A 'è un morfismo in C'. Tuttavia, non si conserva sotto automorfismi di A 'che è il morfismo A -> A' non è un invariante di A 'in C'. In altre parole: da questo punto di vista astratto l'attributo "staticamente tipizzato" non è definibile e può essere arbitrariamente fissato a un linguaggio

.

Per rendere più chiaro il mio punto si può anche pensare a C' la categoria di, diciamo, forme geometriche nello spazio tridimensionale insieme ai movimenti euclidee come morfismi. A 'e B sono quindi due forme geometriche e P e Q sono movimenti euclidee portando B ad A' e viceversa. Ad esempio, A' e B potrebbero essere due sfere. Ora fissiamo un punto A 'che deve stare in piedi per il sottoinsieme A di A'. Chiamiamo questo punto "staticamente tipizzato". Vogliamo sapere se un punto di B è staticamente tipizzato. Quindi prendiamo come punto di y, la mappa via P ad A 'e di prova, se è il nostro punto marcato sulla A'. Come si può facilmente notare, questo dipende dalla carta P scelto o, per mettere in altre parole: Un punto su una sfera contrassegnato non viene mantenuto da automorfismi (pari moti euclidee che mappano la sfera su se stesso) di quella sfera

Answer 2

se è possibile tradurre tutti B '(un programma scritto in B) in una Un equivalente' (che è corretto se B' è), allora il linguaggio B gode altrettanto "tipo-sicurezza" come lingua a (in senso teorico, naturalmente ;-) - in pratica questo significherebbe che B è tale che si può fare inferenze tipo perfetto. Ma questo è estremamente limitata per un linguaggio dinamico - per esempio, prendere in considerazione:

if userinput() = 'bah':
    thefun(23)
else:
    thefun('gotcha')

dove thefun (supponiamo) è typesafe per int argomento, ma non per argomento str. Ora - come si fa a tradurre questo per A lingua in primo luogo ...

Answer 3

Un altro modo per fare lo stesso punto come è stato fatto è che la tua domanda costituisce una dimostrazione per assurdo che:

• A non può essere mappato B
• sicurezza di tipo non è una proprietà lessicale di una lingua

o entrambi. Il mio intuito dice che quest'ultimo è probabilmente il punto critico:. Che tipo di sicurezza è una struttura meta-linguistica

Answer 4

Non c'è niente di "pesce" su di esso. ;)

L'insieme di Turing-completo lingue che sono type-safe rispetto a qualsiasi banale [ 1 ] sistema di tipo T è una rigoroso sottoinsieme delle lingue Turing-complete. Come tale, nel caso generale, nessun traduttore P ^-1 da B A esiste; pertanto, non fa alcun traduttore- cum tipo verificatore LP ^-1 .

Una reazione istintiva a questo tipo di affermazione potrebbe essere: Sciocchezze! Entrambi e B sono Turing-complete, in modo da poter esprimere qualsiasi funzione calcolabile in o lingua! E, in effetti, questo è corretto - si possono esprimere qualsiasi funzione calcolabile in entrambe le lingue; Tuttavia, molto spesso, è anche possibile esprimere la un po 'più . In particolare è possibile costruire espressioni la cui semantica denotazionale non sono ben definiti, come quelli che potrebbero felicemente cercare di prendere la somma aritmetica delle stringhe di caratteri "foo" e "bar" (questo è il succo del Chubsdad Alex Martelli 's risposta). Questi tipi di espressioni possono essere "in" lingua B , ma potrebbe semplicemente non essere esprimibili nella lingua A , perché la semantica denotazionale non sono definiti, in tal modo non v'è alcuna ragionevole modo di tradurli.

Questo è uno dei punti di forza di tipizzazione statica: Se il sistema tipo è in grado di dimostrare, in fase di compilazione, che la funzione suddetta riceverà alcun parametro ma quelli per cui il risultato della operatore di addizione aritmetica è ben definita , può essere respinto in quanto mal digitato.

Si noti che mentre il sopra è il solito tipo di esempio dato per spiegare i meriti di un sistema di tipo statico, è forse troppo modesto. In generale, non una necessità del sistema di tipo statico essere limitata a solo far rispettare tipo correttezza dei parametri, ma anzi può esprimere qualsiasi proprietà desiderata di un programma che può essere provato al momento della compilazione. Ad esempio, è possibile costruire sistemi di tipo che attuano il vincolo che si rilasciare un handle file system ( es ad un database, un file, presa di rete, etc. ) all'interno stessa portata in cui è stato acquisito. Ovviamente, questo è estremamente prezioso in tali domini come sistemi di supporto vitale, tra gli altri, dove dimostrabile correttezza dei tutti i parametri del sistema possibile è assolutamente essenziale. Se si soddisfano il sistema di tipo statico, è possibile ottenere questo tipo di prove gratuitamente.

[ 1 ] Per non banale, voglio dire in modo tale che non tutte le possibili espressioni sono ben digitati-.

Answer 5

La mia comprensione è che questo ha a che fare con il tempo di compilazione vs. run-time. In un linguaggio a tipizzazione statica viene eseguita la maggior parte di controllo di tipo durante la fase di compilazione. In un linguaggio tipizzato in modo dinamico, la maggior parte del suo tipo di controllo viene effettuata in fase di esecuzione.

Answer 6

Lasciatemi rispondere a questa il contrario:

Ci sono due diversi tipi di programmazione "dinamico".

Una è "dinamico digitato", che significa che hanno una sorta di un guscio in cui è possibile programmare da definizioni di battitura a macchina in quel guscio, pensare ad esso come le coperture IDLE di Python.

L'altro tipo di programmazione dinamica, è una più teorica. Un programma dinamico, è uno che può cambiare la propria fonte. Ha bisogno di un certo livello di introiezione, ed è spesso usato per modificare la memoria di programma su microcontrollori. A volte la generazione di ricerca tabelle per macinare numeri si chiama programmazione dinamica.