Contaminando datos

En la programación defensiva, existen varias formas de comprobar que los datos introducidos por el usuario no crean problemas de seguridad en nuestro código. La más usual es suponer que los datos están contaminados (no son fiables) hasta que se pruebe lo contrario.

Nota: A falta de mejor traducción, usaré "contaminado" por "tainted".

El funcionamiento es bien sencillo:

1. Marcamos los datos que introduce el (potencialmente maligno) usuario como contaminados.
2. Marcamos los datos que introduce el (supuestamente competente) programador como no contaminados.
3. Las funciones con las que trabaja el programa sólo deben permitir utilizar datos no contaminados.
4. El programador debe definir, adicionalmente, ciertas funciones de comprobación de la validez de los datos y quita de contaminación.

De esta manera en el único sitio donde hay que mirar por si hay problemas de seguridad es en las funciones de "descontaminación". Generalmente son muy pocas.

El caso clásico es cuando se quieren detectar desbordamientos de búfer. Hasta que no comprobemos que la cadena ofrecida por el usuario cabe en el búfer, no descontaminamos esa cadena. Este simple mecanismo, de descontaminar cuando se hace una comprobación de la longitud, puede aplicarse automáticamente al código fuente con una herramienta externa. Incluso, cuando no se estén marcando como contaminados los datos en el programa.

El resultado es que se encuentran los puntos donde se usan cadenas introducidas por el usuario sin haber comprobado antes la longitud. Algunos de estos usos inseguros pueden explotarse para introducirse maliciosamente en nuestro sistema.

En definitiva, el simple método de marcar los datos (o los tipos de los datos si hacemos el análisis estático) como contaminados o no contaminados tiene una incidencia directa en la seguridad de nuestro programa. Algunos lenguajes lo hacen así, como Ruby. Otros, no. 

La ley de Fitts

La ley de Fitts es muy simple:

Cuanto más cerca esté y más grande sea, más fácil es pulsar un botón.

Esta simple ley es la piedra angular del desarrollo de interfaces gráficas de usuario. Desafortunadamente, parece ser que no se sigue todo lo que debiera.

Adiós, Robin Milner

El 20 de marzo de 2010 murió Robin Milner. Para quién no lo conozca, era un premio Turing (el Nobel de la informática). Había desarrollado el lenguaje ML; el sistema de inferencia de tipos de Hindley/Milner, usado en lenguajes como el Haskell; el pi-cálculo que formaliza los lenguajes concurrentes; todos ellos desarrollos que han marcado la historia de la informática.

La siguiente foto está sacada de su página web de la Universidad de Cambridge.

Todo sobre la recursividad, en un zip

He descubierto un fichero zip que te explica todo lo que necesitas saber sobre la recursividad.

Está aquí.

C++0x, visto para sentencia

Los propios protagonistas han dado el aviso. Se ha votado el Final Comitee Draft (FCD) por lo que tendremos un nuevo estándar para 2012 o 2013. Al final, hubo que realizar unos recortes necesarios (aparte de los conceptos, que ya fueron quitados):

• Quitar export (por fin, nadie lo usaba y quienes lo usan lo querían quitar)
• Quitar las especificaciones de lanzamiento de excepciones (por fin) y dejar solo lanza/no lanza excepción (con la palabra clave nothrow)
• Solucionar los múltiples defectos abiertos.

Esta última parte va ha hacer que el estándar sea más sólido que los antiguos. Parece ser que ha habido muchos informes de defectos y se han solucionado. En definitiva, esperar y ver.

Polimorfismo paramétrico

El polimorfismo paramétrico aparece de forma natural en la programación. El caso más simple es la función identidad.

[$$ \lambda x.x $$]

¿Cuál es el tipo de esta función? Realmente, depende de lo que sea el tipo de su argumento. Si es un real, la función será Real->Real. Si es un natural, será Natural->Natural. Si es una cadena Cadena->Cadena.

Esto se puede agrupar con la idea de los tipos universales: Para todo tipo X el resultado es X->X. Lo que se escribe así.

[$$ \forall X.X\rightarrow X $$]

Obviamente, según el tipo que deseemos usar, especializamos. Así de 

[$$ \forall X.X\rightarrow X $$]

pasamos a

[$$ Real \rightarrow Real $$]

Cuando especializamos X a un real. Pero, ¿podemos especializar X a lo que queramos? ¿Incluso al propio tipo universal? La respuesta es que sí. Es un caso de impredicación en el cual cuantificamos la propia sentencia en la que está el cuantificador. Es decir, que podríamos pasar a especializar

[$$ \forall X.X\rightarrow X $$]
[$$ (\forall X.X\rightarrow X)\rightarrow (\forall X.X\rightarrow X) $$]
[$$ (((\forall X.X\rightarrow X)\rightarrow (\forall X.X\rightarrow X))\rightarrow

((\forall X.X\rightarrow X)\rightarrow (\forall X.X\rightarrow X)))\rightarrow
(((\forall X.X\rightarrow X)\rightarrow (\forall X.X\rightarrow X))\rightarrow
((\forall X.X\rightarrow X)\rightarrow (\forall X.X\rightarrow X))) $$]

Y así, infinitamente.

Las estructuras infinitas no son malas de por sí. A menos que quieras recorrerlas enteras. En ese caso vas a tardar un tiempo infinito. Esto es la indecibilidad. Una forma de evitarlo es dividir los tipos en dos. Los esquemas con los para todos y los tipos monomórficos sobre los que se predica.

Esta separación de los tipos en dos niveles es lo que hacen los sistemas de tipos al estilo ML o  de polimorfismo let. Aunque esa será historia para otro post.

El alto modo mimético

Traduzco el primer párrafo de aquí para iniciar un nuevo tag en el blog: narrativa, que se unirá al de lenguaje natural.

Roger Zelazny, hablando de por qué le gustaba escribir ciencia ficción, alludía a la teoría de modos de Northrop Frye. Zelazny interpretaba que Frye describía los personajes de ficción de cuatro modos:

• El modo mítico de historias sobre dioses.
• El alto modo mimético de historias sobre héroes (personas mejores que meros humanos)
• El bajo modo mimético de histrorias sobre personas normales.
• El modo irónico de historias sobre personas peores que las normales (criminales, bufones)

[...] Zelazny decía que le gustaba la ciencia ficción porque le permitía escribir en modo mítico o alto mimético.

Estas reflexiones me han llevado a rememorar los distintos tipos de historias en función a su trama que leí hace tiempo aquí:

• Arquitrama: El protagonista se enfrenta a dificultades y obtiene una recompensa al vencerlas. Nota bene: Todo lo que quieras saber de la arquitrama está en El camino del escritor y en El camino del héroe.
• Antitrama: O no hay protagonista, o no hay dificultades, o no hay trama. Más información aquí.
• Minitrama: Muchas pequeñas historias encadenadas.

Y a modo de mecanismo de serialización, dejo aquí una entrada de blog para su persistencia.

El "yo" tópico

Hasta que no estudias algunos idiomas orientales no te das cuenta de que existen otras maneras de hablar. Muchos de estos idiomas no están orientados a sujeto, están orientados a tópico. ¿Y qué es eso del tópico?

Cuando nosotros decimos "el niño corre" dejamos claro quién está haciendo algo (el niño) y qué es lo que está haciendo (corre). El castellano es un idioma orientado a sujeto. En un idioma orientado a tópico diríamos de qué vamos a hablar: del niño; y añadiríamos una acción: correr. La frase sería algo como...

"Hablando del niño, corre"

Obviamente estos idiomas tienen una forma abreviada de decir "hablando de..." por lo que la frase final suele ser más corta que en los idiomas con sujeto.

Lo más sorprendente es que en castellano se usa algunas veces el tópico. No está marcado gramaticalmente, ni es habla culta, pero se usa. Ocurre cuando nos preguntan nuestra opinión y empezamos diciendo "Yo..." Luego, cambiamos y decimos la opinión.

"¿Y tú que opinas de la gatita?"

"Yo... La gatita es buena"

Podríamos decir que ese uso del "Yo" es como tópico ya que vamos a hablar de nosotros (nuestra opinión) aunque el resto de la frase no esté relacionada gramaticalmente con ese "yo".

Predicativo e impredicativo

Veamos esta fórmula de la lógica de primer orden

[$$ \forall y.y \lt x $$]

Podríamos verla como un predicado

[$$ P(x) \equiv \forall y.y \lt x $$]

Ahora veamos esta fórmula de la lógica de segundo orden

[$$ \forall Q.Q(x) $$]

También podríamos verla como un predicado

[$$ R(x) \equiv \forall Q.Q(x) $$]

Pero R(x) dice que todos los predicados Q cumplen Q(x) ¡incluido R(x)!

Así que factorizamos ese término para que se vea bien.

[$$ R(x) \equiv R(x) \wedge \forall Q.Q(x) $$]

Esto no pasaba con la lógica de primer orden porque la y en

[$$ \forall y.y<x $$]

sólo puede ser un elemento del dominio. Cuando ocurre esto, se dice que es un sistema predicativo. Cuando ocurre lo de la lógica de segundo orden, el sistema es impredicativo (habla de sí mismo).

Los sistemas impredicativos son una puerta a los problemas. Si hubiéramos definido por ejemplo

[$$ R(x) \equiv \forall Q.\neg Q(x) $$]

Podríamos especializar en

[$$ R(x) \equiv \neg R(x) \wedge \forall Q.\neg Q(x) $$]

Así que R(x) es cierta cuando R(x) es falsa... Mal rollo, ¿no?

Haciendo un intérprete de LISP (XX)

Esta es la última entrada sobre cómo hacer un intérprete LISP. Son las conclusiones.

Conclusiones

Empezamos describiendo los valores con los que íbamos a trabajar y dijimos que los guardaríamos en celdas. La idea de los valores elegidos era la homoiconicidad de forma que las propias expresiones del lenguaje fueran valores.

A continuación vimos cómo representar expresiones con celdas. También dijimos que la idea de la evaluación era convertir esas expresiones en otros valores.

Debido a que necesitábamos manipular las celdas empezamos a introducir operaciones sobre celdas.

Como también hacía falta inicializar y crear nuevas celdas, nos dedicamos a definir las operaciones correspondientes en el montículo.

Finalmente, en la quinta parte, nos dedicamos a definir la evaluación. La evaluación se apoyaba en la aplicación de las que teníamos dos variantes.

La primera era la predefinida. Estos eran los valores que llamábamos nativos y de los que dábamos la suma como ejemplo. También introdujimos el REPL como medio de comprobar que realmente la suma funcionaba.

La segunda forma de aplicación era usando una llamada compuesta. Es decir, definida por el usuario. Para eso teníamos las funciones lambda que guardábamos en objetos Lambda.

Para aplicar el objeto lambda realizábamos varios pasos: Creábamos un nuevo entorno local, vinculábamos los argumentos, comprobábamos la aridad y, finalmente, evaluábamos el cuerpo de la función lambda.

Hasta este punto habíamos hablado de entornos, pero no los habíamos definido. En la novena parte los definíamos.

Una vez que teníamos claro cómo usar los objetos lambda, lo único que nos faltaba era crearlos. Para eso introducíamos una nueva nativa.

Aunque mencionamos el REPL anteriormente, no lo habíamos especificado. En la undécima parte lo hacíamos.

En nuestra definición de celdas y entornos habíamos hablado repetidamente de los nombres. En la duodécima parte explicamos cómo usarlos y modificar su contenido. Además, introducimos la nativa que nos saca del REPL y otra que detiene la evaluación.

Cuando todo parecía terminado con las funciones lambda, nos damos cuenta que hace falta un pequeño detalle en nuestra implementación de los entornos. Debemos tener la capacidad de modificar nuestros entornos padre para poder realizar la clausura léxica correctamente.

La décimo cuarta parte es una colección de funciones nativas que posiblemente sean interesantes tener: operaciones con listas, formas especiales, formas especiales con booleanos y operaciones de inspección del estado del intérprete.

En la décimo quinta parte damos por concluida la realización del intérprete añadiendo las rutinas de lectura de expresiones y escritura de valores.

Las últimas cuatro partes (descontando ésta) las dedicamos a pensar en extensiones posibles.

Primero hablamos de mejoras básicas y casi siempre realizadas por un intérprete real: la recolección de basura y cache de celdas.

Luego, de otras extensiones menos básicas como las macros o carga de ficheros en tiempo de ejecución.

También exploramos la posibilidad de modificar la estructura del lenguaje. Vemos cómo podríamos llegar a Lua, Self o Smalltalk.

Finalmente, en vez de modificar el lenguaje, podríamos estandarizarlo. Hablábamos de los dos dialectos principales del lisp: Common Lisp y Scheme.