Galois y la Interpretación Abstracta

Es bien sabido que lo ”intangible” de la informática está fuertemente influenciado por ciertas ramas de las matemáticas. Esta estrecha relación tiene múltiples ejemplos, pero en esta pequeña reseña me gustaría reconocer las contribuciones de tres investigadores franceses Evariste Galois (1811-1832) y Radhia (1947 –2014) y Patrick Cousot (1947- ) que, aunque lejanos en el tiempo, representan la importancia que tienen en la investigación la inteligencia natural de los individuos, por un lado, y el estudio profundo de los antecedentes, por otro.

Evariste Galois fue un matemático de principios del siglo XIX de muy corta vida. Evariste no entendía las estructuras matemáticas como el resto de sus coetáneos. Él definió el nuevo concepto de grupo que, en su momento, le sirvió para probar la no existencia de soluciones mediante radicales para ecuaciones de más de 4 grados. Posteriormente, los grupos han sido útiles en muchos otros campos, como la cristalografía, pero Galois no vivió para ver estas aplicaciones. De entre los múltiples legados que dejó para la posteridad en su corta vida, está la noción de “conexiones de Galois” que es la que nos interesa en este artículo. Intuitivamente, una conexión de Galois se da entre dos mundos si se parecen suficientemente. A uno de estos mundos se le llama concreto, y al otro abstracto. Por ejemplo, supongamos que tenemos una película en color, y decidimos pasarla a blanco y negro. Está claro que ambas películas la original (concreta) y la que está en blanco y negro (abstracta) se parecen mucho. Los personajes se mueven igual, los diálogos son los mismos, las secuencias entre planos también se mantienen. Sólo ha cambiado el color. Está también claro que de una película en color siempre podemos pasar a una en blanco y negro. Pero lo contrario no es tan fácil, ya que habría muchas películas en color cuyas versiones en blanco y negro coinciden. Pues esto es, a grandes rasgos, lo que propuso Galois, las condiciones necesarias y suficientes para que haya una relación de ida y vuelta, como la descrita, entre los mundos concretos y abstractos.

En 1977, Radhia y Patrick Cousot publicaron un artículo de referencia para todos los que nos dedicamos al análisis del software en el que utilizaban el concepto de conexión de Galois para relacionar dos mundos muy lejanos inimaginables seguramente para Galois. Los investigadores franceses tomaron como mundo concreto un programa y como abstracto el mismo programa en el que ciertas partes habían sido simplificadas (como el color en la analogía del cine) y describieron la forma automática para trasformar un programa concreto en uno abstracto utilizando la noción de conexiones de Galois. Llamaron a este nuevo campo “Interpretación abstracta”. ¿Y esto para qué sirve? Pues la aplicación más importante está en detectar propiedades (y errores) del programa original pero analizando el abstracto, que es mucho más pequeño. Por ejemplo, siguiendo con la metáfora del cine. Supongamos que tenemos una secuencia de viñetas de unos dibujos animados en la que sólo son perceptibles los trazos de los personajes. En esta versión reducida, sería más fácil averiguar si hay dos secuencias que son exactamente iguales, o si alguno de los personajes aparece sólo una vez. En el caso de los programas podría detectarse si hay cierto código del programa que no se ejecuta nunca, si hay un punto del programa a partir del cual no puede avanzar, o si, en algún momento, se divide por cero. Los tipos análisis que se pueden hacer sobre el programa abstracto son muy diversos y, en general, dependen de la aplicación que se está analizando. Lo importante es que respetando las reglas dadas por los Radhia y Patrick cualquier propiedad del programa abstracto es una propiedad del programa concreto.

Esta historia muestra los caprichosos caminos que a veces utiliza la ciencia y que hay que ser pacientes a la hora de juzgar la utilidad de la investigación básica. En algunas ocasiones, las soluciones a nuestros problemas hace tiempo que se estudiaron, pero hace falta que investigadores de la talla e inteligencia de Radhia y Patrick Cousot estudien los trabajos de Galois con otra mirada, desde otra perspectiva, para que se haga la luz y se vean todas las tonalidades del problema.

María del Mar Gallardo Melgarejo es catedrática del área de Lenguajes y Sistemas Informáticos de la Universidad de Málaga

Crónicas del Intangible es un espacio de divulgación sobre las ciencias de la computación, coordinado por la sociedad académica SISTEDES (Sociedad de Ingeniería de Software y de Tecnologías de Desarrollo de Software). El intangible es la parte no material de los sistemas informáticos (es decir, elsoftware), y aquí se relatan su historia y su devenir. Los autores son profesores de las universidades españolas, coordinados por Ricardo Peña Marí (catedrático de la Universidad Complutense de Madrid) y Macario Polo Usaola (profesor titular de la Universidad de Castilla-La Mancha).