En un comentario sobre rust usted dijo que: “el problema de seguridad en presencia de aliasing no es decidible -- punto”. ¿Podría ahondar un poco más en este tema?
El «aliasing» ocurre cuando una misma posición de memoria es accesible para modificación a través de más de un nombre. Eso es habitual en lenguajes imperativos donde hay pasaje de parámetros por referencias, o manipulación explícita de apuntadores. El «aliasing» puede ser local a una subrutina, puede ser inmediato entre la subrutina y su llamador, o global entre la rutina y variables globales o en alcances superiores.
Para generar código correcto y eficiente («bueno, rápido, económico», escoge dos), es necesario que el compilador aplique varios análisis estáticos sobre el código. En particular, sería deseable determinar si dos nombres particulares SIEMPRE son aliases o A VECES son aliases. Eso permitiría escribir código seguro en unos escenarios, y astuto en otros.
Sin embargo, se ha demostrado [1] que ambos problemas son «no decidibles». Un problema es «no decidible» (o «indecidible») cuando es IMPOSIBLE escribir un algoritmo que lo resuelva. Imposible hoy, imposible el año que viene, imposible con computación cuántica. No se puede. De hecho, uno de los dos problemas ni siquiera es recursivamente enumerable («simulable») lo cual es aún más bonito.
Como es (y será) IMPOSIBLE determinar si dos nombres particulares son aliases, en presencia de aliasing los compiladores para lenguajes imperativos generan el código más conservador posible, que usualmente requiere más instrucciones y más espacio. Nota que el problema ocurre por la combinación de dos cosas: apuntadores a una misma posición, Y la posibilidad de cambiar la posición.
Una solución es, obviamente, que el lenguaje NO tenga estado mutable. Que no puedas cambiar cosas explícitamente a través de las referencias. Eso es lo que hace Haskell, por eso tiene aliasing SIN mutabilidad en prácticamente todo el lenguaje.
Otra solución es, garantizar que cada posición de memoria tenga UNA y exactamente UNA forma de accederse para modificación. Esto es, está bien tener mútiples aliases sólo para lectura, UN alias para escritura y varios para lectura, pero NUNCA más de un alias para escritura. Eso es lo que hace Rust, para mantenerse imperativo. Entonces, el compilador NO está haciendo detección de aliases para modificación cuando genera código, sino impidiendo que tengas aliases para modificación cuando escribes.
Hay una infinidad (no es exageración) de problemas no decidibles, y uno cuantos tienen que ver con generar código de máquina en lenguajes imperativos. En los lenguajes funcionales puros hay otros problems, pero ese, no.
[1] http://web.cs.ucla.edu/~palsberg/course/cs232/papers/ramalingam-toplas94.pdf
Para generar código correcto y eficiente («bueno, rápido, económico», escoge dos), es necesario que el compilador aplique varios análisis estáticos sobre el código. En particular, sería deseable determinar si dos nombres particulares SIEMPRE son aliases o A VECES son aliases. Eso permitiría escribir código seguro en unos escenarios, y astuto en otros.
Sin embargo, se ha demostrado [1] que ambos problemas son «no decidibles». Un problema es «no decidible» (o «indecidible») cuando es IMPOSIBLE escribir un algoritmo que lo resuelva. Imposible hoy, imposible el año que viene, imposible con computación cuántica. No se puede. De hecho, uno de los dos problemas ni siquiera es recursivamente enumerable («simulable») lo cual es aún más bonito.
Como es (y será) IMPOSIBLE determinar si dos nombres particulares son aliases, en presencia de aliasing los compiladores para lenguajes imperativos generan el código más conservador posible, que usualmente requiere más instrucciones y más espacio. Nota que el problema ocurre por la combinación de dos cosas: apuntadores a una misma posición, Y la posibilidad de cambiar la posición.
Una solución es, obviamente, que el lenguaje NO tenga estado mutable. Que no puedas cambiar cosas explícitamente a través de las referencias. Eso es lo que hace Haskell, por eso tiene aliasing SIN mutabilidad en prácticamente todo el lenguaje.
Otra solución es, garantizar que cada posición de memoria tenga UNA y exactamente UNA forma de accederse para modificación. Esto es, está bien tener mútiples aliases sólo para lectura, UN alias para escritura y varios para lectura, pero NUNCA más de un alias para escritura. Eso es lo que hace Rust, para mantenerse imperativo. Entonces, el compilador NO está haciendo detección de aliases para modificación cuando genera código, sino impidiendo que tengas aliases para modificación cuando escribes.
Hay una infinidad (no es exageración) de problemas no decidibles, y uno cuantos tienen que ver con generar código de máquina en lenguajes imperativos. En los lenguajes funcionales puros hay otros problems, pero ese, no.
[1] http://web.cs.ucla.edu/~palsberg/course/cs232/papers/ramalingam-toplas94.pdf
