Tesis:
Técnicas avanzadas de compilación para programación lógica.
- Autor: MORALES CABALLERO, José Francisco
- Título: Técnicas avanzadas de compilación para programación lógica.
- Fecha: 2010
- Materia: Sin materia definida
- Escuela: FACULTAD DE INFORMATICA
- Departamentos: LENGUAJES Y SISTEMAS INFORMATICOS E INGENIERIA DE SOFTWARE
- Acceso electrónico: http://oa.upm.es/7778/
- Director/a 1º: CARRO LIÑARES , Manuel
- Director/a 2º: HERMENEGILDO SALINAS , Manuel de
- Resumen: La programación, como esfuerzo matemático para diseñar un algoritmo que resuelva un problema especifico, junto con la tarea de codificación en un lenguaje ejecutable por un computador, puede definirse de forma precisa. Aun no sien-do una tarea fácil, determinar si un programa es correcto y adecuado para una problema dado puede realizarse mediante pruebas (formales) sobre la corrección, la complejidad en uso de memoria y tiempo y datos empíricos en una maquina particular sobre su rendimiento y tamaño de código. Cuando el objetivo es encontrar una codificación optima de un algoritmo, el lenguaje de programación adecuado puede ser cuestionable. En términos de computabilidad, la elección no permite escribir mas algoritmos de aquellos ya expresables en maquinas de Turing y tampoco permite escribir algoritmos que superen las limitaciones del hardware. Para una plataforma determinada, la mejor solución si nos centramos en el problema del rendimiento y el uso de memoria, será siempre expresable en lenguaje maquina (pues cualquier otro lenguaje es directa o indirectamente traducido a este o interpretado mediante otro programa). Sin embargo, los lenguajes maquina han pasado a ser usados solo en dominios muy concretos, viéndose desplazados por lenguajes de bajo nivel (como el lenguaje C), que surgieron principalmente como una forma de aliviar los problemas de portabilidad en diferentes arquitecturas, facilitar tareas de programación pesadas y que gracias al desarrollo de la compilación optimizante ofrecen un buen rendimiento. Este resumen de la Tesis Doctoral, presentada en lengua inglesa para su defensa ante un tribunal internacional, es preceptivo según la normativa de doctorado vigente en la Universidad Politécnica de Madrid. I Aún así, en estos lenguajes el programador tiene un control estricto sobre los recursos y las operaciones hardware. Los programas incluyen detalles muy precisos sobre el flujo de control, el tamaño y la forma de los datos, lo que hace que los programadores experimentados sean capaces de comprender que esta ocurriendo en la ejecución con gran precisión, incluso al nivel de registros maquina. El punto de vista de la programación como ingeniería es muy diferente. Los programadores, como seres humanos, están ligados a fechas de entrega, cometen errores e introducen fallos (bugs) en la programación. Por otro lado, los requisitos del software no siempre están especificados y pueden ser imprecisos, o verse modificados durante el desarrollo, requiriendo cambios en los programas. Mas aún, el proceso de desarrollo no es lineal en la practica, lo que significa que muchas partes del código de un proyecto pueden ser esbozadas como prototipos y refinadas mas adelante. Incluso si estos problemas no fueran suficientes, existen restricciones fuertes de seguridad, donde hay ciertos fallos que no son admisibles en absoluto: por ejemplo, que una aplicación externa acceda directamente a los recursos de la maquina. A esto se añaden otros factores, como el balance entre el coste humano de producir programas optimizados frente al coste de invertir en recursos hardware para aliviar ineficiencias (como usar, siempre que sea posible, mas procesadores, procesadores mas rápidos y mas memoria, en ocasiones acompañándose de un mayor consumo energético). En resumen, podemos observar una importante asimetría entre que codificación de un programa es mejor de cara a la ejecución eficiente en una maquina y cuál desde el punto de vista de los factores prácticos del desarrollo. Esta asimetría es salvable en ocasiones. Por ejemplo, el tiempo de ejecución no se dedica uniformemente al código: hay secciones que concentran la mayor parte de la ejecución. Se acepta como una buen compromiso reescribir las partes críticas de una aplicación en lenguajes de bajo nivel (atendiendo a los detalles necesarios para asegurar la eficiencia, incluso si se sacrifica la reutilización, claridad, etc.) y preservar un estilo limpio en el resto del código. Sin embargo, aunque existen técnicas de verificación de código que pueden ayudar en probar la corrección u otras propiedades del código de bajo nivel, en ocasiones se ha sacrificado las ventajas de una especificación más abstracta. Poder preservar la abstracción del problema a lo largo de todo el programa, mediante el desarrollo de lenguajes y el desarrollo de traducciones eficientes a código ejecutable, es uno de los mas temas de investigaci6n mas importantes en este área. De los Lenguajes de Bajo Nivel a la Programación Declarativa Al contrario que en los lenguajes de bajo nivel, la abstracción en lenguajes de alto nivel permiten expresar programas en un lenguaje que es más cercano al problema que se pretende resolver. Uno de estos enfoques es la programación declarativa, que intuitivamente a veces de forma no muy precisa es definida como un estilo de programación donde los programas definen que se ha de resolver, pero no cómo ha de hacerse. Una explicación mas profunda de esta frase es necesaria, como Lloyd indica en [Llo94], Usando la terminología de la ecuación de Kowalski algoritmo = lógica + control [Kow79], que define un algoritmo como la combinación de una lógica y un mecanismo de control, un lenguaje de programación declarativo sólo necesita describir la lógica del programa y no su control. Pero esta definición, que refleja la idea intuitiva del paradigma, puede ser equívoca dado que no todos los problemas que son expresables en la lógica pueden ser resueltos automáticamente. Lloyd describe que la idea principal de la programación declarativa consiste en que los programas son teorías (en una lógica adecuada) y que la computación es la deducción en esa teoría. Una lógica adecuada debe tener una teoría modelo, una teoría de prueba, teoremas de corrección (todas las respuestas computadas deben ser correctas) y preferentemente, teoremas de completitud (todas las respuestas correctas son computadas). La visión de Lloyd es suficientemente amplia para agrupar muchos paradigmas de programación bajo el ámbito de la programación declarativa: programación funcional (computación como evaluación de funciones matemáticas) programación lógica (computación basada en pruebas de teoremas y lógica matemática) y otros métodos formales. Retos de la Programación Declarativa La lógica formal detrás de la programación declarativa a menudo simplifica el razonamiento automático sobre los programas y los programas escritos en un lenguaje que esta mas cerca a la especificación son más fáciles de escribir y verificar. Esto tiene algunas implicaciones profundas: 1.- Debido a la amplia expresividad del lenguaje, los mecanismos de ejecución tienen un carácter muy general, lo que se traduce en ocasiones (especial-mente en los sistemas menos maduros) en un rendimiento pobre, comparado con aquel que ofrecen los lenguajes de bajo nivel. Por ejemplo, los lenguajes donde la aritmética es por defecto de múltiple precisión pueden ser menos eficientes que aquellos donde el usuario hace explícito el tamaño máximo de cada variable numérica, pero liberan al programador de esta tarea. 2.- Las transformaciones y los análisis de programas (como evaluación parcial e interpretaci6n abstracta) son en principio más fáciles de aplicar. 3.- No describir un problema a un nivel detallado y específico a la maquina implica que existe mas libertad por parte de los mecanismos de ejecución para encontrar soluciones. Sin cambiar el programa original, es posible adaptarlo a distintas plataformas hardware y aprovechar sus características especiales (como paralelismo, instrucciones SIMD, etc.). El Lenguaje Prolog es un lenguaje basado en la 16gica de primer orden. La historia del lenguaje ha sido descrita en detalle en la literatura [Col93]. El uso de la deducción lógica como computaci6n fue propuesta en 1960 por Cordell Green y otros, pero no fue hasta que Colmerauer y Kowalski crearon Prolog que comenzó a ser viable. Prolog nació como un proyecto dirigido al procesamiento del lenguaje natural, cuya primera versión preliminar data de finales de 1971. A lo largo de los años se convirtió en un lenguaje de propósito general. Sin embargo, Prolog también ha sido considerado como un lenguaje de bajo nivel entre el lenguaje lógico, debido a sus limitadas propiedades de terminación y su uso frecuente de efectos laterales. No obstante, desde el nacimiento de Prolog, han aparecido soluciones a la formalización de los efectos laterales en programación declarativa para su uso en aplicaciones reales, que han sido exploradas tanto en programación funcional como lógica. Prolog ha demostrado ser un lenguaje muy flexible para desarrollar nuevas ideas, como la programación con restricciones y lenguajes multiparadigmas que mezclan programación funcional, orientada a objetos e imperativa. En general, los sistemas Prolog ofrecen un largo repertorio de técnicas para conseguir buen rendimiento, como se muestra en el Capítulo 2. Importantes lenguajes que se derivan o heredan algunos aspectos de Prolog son LIFE [AKP91] (lógico, funcional, orientado a objetos), Mozart-Ox [HFOO] o Mercury [SHC96]. Objetivos de la Tesis Como ya se ha mencionado antes, uno de los objetivos mas ambiciosos de la programación declarativa es la mejora de las técnicas de compilación para reducir la diferencia de rendimiento, como lenguaje de programación general, respecto a lenguajes mas tradicionales como la programación imperativa. En esta dirección, el objetivo de esta tesis es el desarrollo de técnicas avanzadas de compilación para programación lógica, tanto a código nativo como a código de byte emulado. Los primeros trabajos existentes en compilación de Prolog a código nativo, a pesar su lentitud y grandes ejecutables, mostraron buenos resultados en comparación con código emulado. Sin embargo, estos trabajos fueron parcialmente abandonados debido a importantes mejoras en técnicas de emulación y a los problemas de portabilidad de los compiladores de código nativo. No obstante, es claro que algunos algoritmos solo pueden ser ejecutados de forma eficiente como código muy especializado, que esta fuera del ámbito de técnicas de emulación genéricas y solo disponible cuando se usa código de bajo nivel. En esta tesis, exploramos soluciones a este problema, que aunque están enfocadas a Prolog también son en principio aplicables a otros lenguajes o extensiones, como programación lógica con restricciones [JM87], Prolog con tabulación [War92] o CHR sobre Prolog [SF08]. La relevancia de estos resultados también puede ex-tenderse a otros lenguajes que comparten algunos mecanismos de ejecución (por ejemplo, lenguajes dinámicamente tipados), ya que las técnicas de optimización son similares.