¿Qué significa para un idioma que se escribe de forma estática?

Question

Mi entendimiento es que significa que uno potencialmente puede escribir un programa para demostrar formalmente que un programa escrito en un lenguaje de tipos estáticos estará libre de una cierta (pequeña) subconjunto de defectos.

Mi problema con esto es la siguiente:

Supongamos que tenemos dos lenguas Turing completos, A y B. A se presume que es 'un tipo seguro' y 'B' se presumirá que no se. Supongamos que yo soy dado un programa L para comprobar la corrección de cualquier programa escrito en A. ¿Qué es para que dejara de traducir cualquier programa escrito en B a A, aplicando L. Si P se traduce de A a B, entonces por qué no es un PL comprobador de tipos válidos para cualquier programa escrito en B?

Estoy entrenado en Álgebra y estoy empezando a hacer estudiar CS por lo que podría haber alguna razón obvia de que esto no funciona, pero me gustaría mucho saber. Todo este asunto de 'seguridad tipo' ha olido a pescado a mí por un tiempo.

Answer 1

Sea A su idioma Turing completo que se supone debe ser estático de tipos y sea A' será el idioma que se obtiene de A cuando se quita la comprobación de tipos (pero no las anotaciones de tipos, ya que también sirven para otros fines). Los programas aceptados de A será un subconjunto de los programas aceptados de A'. Así, en particular, A' también será Turing completo.

Dada su traductor P de B a A (y viceversa). ¿Qué se supone que haga? Se podría hacer una de dos cosas:

1. En primer lugar, se podría traducir cada programa y de B a un programa de A. En este caso, sería LPY siempre devuelven verdadero como los programas de A son, por definición, escrito correctamente.

2. En segundo lugar, P podría traducir cada programa y de B a un programa de A'. En este caso, LPY volvería True si Py pasa a ser un programa de A y falso en caso contrario.

Como el primer caso no produce nada interesante, atengámonos al segundo caso, que es probablemente lo que quiere decir. ¿El LP función definida en los programas de B nos dicen nada interesante acerca de los programas de B? Digo que no, porque no es invariante ante un cambio de P. Como A es Turing completo, incluso en el segundo caso P podría ser elegido de modo que su imagen pasa a mentira en A. Entonces LP sería constante verdadera. Por otro lado, P podría ser elegido de modo que algunos programas se asignan al complemento de A en A'. En este caso LP escupía falso para algunos (posiblemente todos) los programas de B. Como se puede ver, no se consigue nada, que sólo depende de y.

También puedo decirlo más matemáticamente de la siguiente manera: Hay una categoría C de lenguajes de programación cuyos objetos son los lenguajes de programación y cuyos morfismos son traductores de un lenguaje de programación a otro. En particular, si hay un morfismo P: X -> Y, Y es al menos tan expresivo como X. Entre cada par de lenguas Turing completo hay morfismos en ambas direcciones. Para cada objeto X de C (es decir, para cada lenguaje de programación) que tenemos un conjunto asociado, por ejemplo {X} (mala notación, lo sé) de esas funciones parcialmente definidos que se pueden calcular mediante programas de X. Cada morfismo P: X - > Y a continuación, induce una inclusión {X} -> {Y} de conjuntos. Veamos formalmente invertido todos los morfismos P: X -> Y que inducen la identidad {X} -> {Y}. Voy a llamar a la categoría resultante (que es, en términos matemáticos, una localización de C) por C'. Ahora la inclusión A -> A 'es un morfismo en C'. Sin embargo, no se conserva bajo automorfismos de A 'que es el morfismo A -> A' no es un invariante de A 'en C'. En otras palabras: desde este punto de vista abstracto el atributo "tipos estáticos" no es definible y se puede fijar arbitrariamente a una lengua

.

Para hacer más claro mi punto también se puede pensar en C' como la categoría de, por ejemplo, formas geométricas en el espacio de tres dimensiones junto con los movimientos euclidianas como morfismos. A 'y B son entonces dos formas geométricas y P y Q son movimientos euclidianas trayendo B a A', y viceversa. Por ejemplo, A' y B podría ser de dos esferas. Ahora vamos a fijar un punto en A 'la cual estará puesta por el subconjunto A de A'. Llamemos a este punto "tipos estáticos". Queremos saber si un punto de B es de tipo estático. Así que tomamos como un punto Y, asignarla a través de P a A 'y prueba, si es nuestro punto marcado en A'. Como se puede ver fácilmente, esto depende en el mapa P elegido o, para decirlo en otras palabras: un punto en una esfera marcada no se conserva por automorfismos (que son movimientos euclidianas que mapean la esfera sobre sí misma) de esa esfera

Answer 2

si usted puede traducir todos B '(un programa escrito en B) en una Un equivalente' (que es correcta si B' es), entonces el lenguaje B disfruta apenas tanto "tipo de seguridad", como lengua a (en un sentido teórico, por supuesto ;-) - básicamente esto significaría que B es tal que se puede hacer inferencia tipo perfecto. Pero eso es muy limitado para un lenguaje dinámico - por ejemplo, tener en cuenta:

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

donde thefun (Asumamos) es typesafe de argumento int, pero no para el argumento str. Ahora - ¿Cómo se traduce esto a A idioma en el primer lugar ...

Answer 3

Otra forma de hacer el mismo punto que se ha hecho es que su pregunta constituye una prueba por la contradicción que, o bien:

• A no puede ser asignada a B
• Tipo de seguridad no es una propiedad léxica de una lengua

o ambos. Mi intuición dice que este último es probablemente el punto de estancamiento:.-Ese tipo de seguridad es una propiedad metalingüística

Answer 4

No hay nada "sospechoso" al respecto. ;)

El conjunto de idiomas Turing completo que son de tipo seguro con respecto a cualquier no trivial [ 1 ] sistema de tipo T es un estricta subconjunto de los idiomas de Turing-completos. Como tal, en el caso general, no traductor P ^-1 de B a A existe; por lo tanto, tampoco lo hace cualquier translator- cum de tipo ortográfico LP ^-1 .

Una instintiva reacción a este tipo de reclamo podría ser: Tonterías! Tanto y B son Turing completo, por lo que puedo expresar cualquier función computable en o bien idioma! Y, de hecho, esto es correcto - que puede expresar cualquier función computable en ambos idiomas; Sin embargo, muy a menudo, también se puede expresar un poco más . En particular, se puede construir expresiones cuya semántica denotacional no están bien definidos, tales como las que podían felizmente tratar de tomar la suma aritmética de las cadenas de caracteres "foo" y "bar" (esta es la esencia de Chubsdad Alex Martelli 's respuesta). Este tipo de expresiones pueden ser "en" lenguaje B , pero puede simplemente no ser expresable en el idioma , porque la semántica denotativa no están definidos, por lo tanto no hay sensata manera de traducirlos.

Esta es una de las grandes fortalezas de tipos estáticos: Si su sistema de tipo no puede probar, en tiempo de compilación, que la función antes mencionada recibirá ningún parámetro, pero aquellos para los que el resultado del operador de suma aritmética está bien definido , puede ser rechazado como un enfermo-mecanografiada.

Tenga en cuenta que mientras que el anterior es el tipo habitual de ejemplo dado para explicar los méritos de un sistema de tipo estático, es tal vez demasiado modesto. En general, un sistema de tipo estático necesidad no se limita a la mera aplicación de tipo correcto de parámetros, pero de hecho puede expresar cualquier propiedad deseada de un programa que puede ser probada en tiempo de compilación. Por ejemplo, es posible construir sistemas de tipo que hacen cumplir la restricción de que uno liberar un identificador de sistema de archivos ( por ejemplo a una base de datos, archivo, socket de red, etc. ) dentro de la mismo alcance en el que se adquirió. Obviamente, esto es un valor muy importante en ámbitos tales como los sistemas de soporte de vida, entre otros, donde demostrable corrección de todos los parámetros del sistema como sea posible es absolutamente esencial. Si usted cumple con el sistema de tipo estático, puede obtener este tipo de pruebas de forma gratuita.

[ 1 ] Por no trivial, es decir de tal manera que no todas las expresiones posibles son bien mecanografiados a.

Answer 5

Mi entendimiento es que esto tiene que ver con el tiempo de compilación vs. tiempo de ejecución. En un lenguaje de tipos estáticos la mayoría de comprobación de tipos se realiza durante el tiempo de compilación. En un lenguaje de tipos dinámicos, la mayoría de su comprobación de tipos se realiza en tiempo de ejecución.

Answer 6

Permítanme responder a esto al revés:

Hay dos tipos diferentes de programación "dinámica".

Uno es "tipos dinámicos", lo que significa que tiene una especie de concha donde se puede programar mediante las definiciones de escritura en esa cáscara, piense en ello como cáscara de IDLE de Python.

El otro tipo de programación dinámica, es uno más teórico. Un programa dinámico, es uno que puede cambiar su propia fuente. Se necesita un cierto nivel de introyección, y con frecuencia se utiliza para cambiar la memoria del programa en microcontroladores. A veces la generación de búsqueda de tablas de cálculo de números se llama programación dinámica.