Tesis:
Análisis de Terminación Modular y Sensible a los Campos de Código de Byte Java.
- Autor: RAMIREZ DEANTES, Diana Vanessa
- Título: Análisis de Terminación Modular y Sensible a los Campos de Código de Byte Java.
- Fecha: 2011
- Materia: Sin materia definida
- Escuela: FACULTAD DE INFORMATICA
- Departamentos: LENGUAJES Y SISTEMAS INFORMATICOS E INGENIERIA DE SOFTWARE
- Acceso electrónico: http://oa.upm.es/6094/
- Director/a 1º: PUEBLA SANCHEZ, Alvaro Germán
- Resumen: En las últimas dos décadas, una variedad de sofisticadas herramientas de análisis de terminación se han desarrollado. Estos incluyen los analizadores para sistemas de reescritura de terminos [GSKT06], lógicos y los de lenguajes funcionales [LS97]. El análisis de terminación [CT99, LJBA01] puede considerarse como otro tipo de análisis de uso de recursos, y también se ha estudiado en el contexto de varios lenguajes de programación. Tradicionalmente, en el contexto de la programación declarativa y, recientemente, para lenguajes imperativos y orientados a objetos (OO). De hecho, existen analizadores de terminación para OO que son capaces de probar terminación de aplicaciones de tamaño medio a través de un análisis global, en el sentido de que se debe demostrar terminación para todo el código usado por esas aplicaciones. Sin embargo, el análisis global tiene desventajas importantes, tales como, su alto consumo de memoria y su falta de eficiencia. Ya que a menudo algunas partes del código tienen que ser analizadas una y otra vez, las librerias son un ejemplo primordial de ello. El análisis modular se ha estudiado en diferentes paradigmas desde la programación lógica [ea04, CPHB06, CDG93] a la programación orientada a objetos [Pro02, BJ03, Log04]. La mayoría de los trabajos existentes que se centran en el análisis modular se aplican a los análisis específicos con propiedades particulares o dominios abstractos. Las herramientas de análisis de terminación se esfuerzan por encontrar pruebas de terminación para la mas amplia clase de programas (que terminen) como sea posible. Aunque existen varias herramientas que son capaces de probar terminación de programas no triviales, cuando se trata de aplicarlos a programas realistas, todavía hay una serie de problemas abiertos. En [AAGP08b] se identifican una serie de dificultades para resolverse con el fin de tratar los campos numéricos en la terminación y se proponer algunas ideas para un análisis ligero que es capaz de probar terminación de programas Java-like secuenciales en presencia de campos numéricos. Técnicas automatizadas para demostrar terminación se basan normalmente en los análisis que mantienen un registro del tamaño de la información, tales como el valor de los datos numéricos o el tamaño de las estructuras de datos. En particular, los análisis deben hacer un seguimiento de cómo (el tamaño de) los datos involucrados en el bucle cambian a través de sus iteraciones. Esta informaci ón se utiliza para especificar una ranking function para el bucle [PR04a], que es una función que disminuye estrictamente en cada iteración del bucle, lo que garantiza que el bucle se ejecutará un número finito de veces. Algunos análisis sensible a los campos se han desarrollado en los últimos años ([Min06, AAGP09]). Para asignar estructuras de datos en el heap, el pathlength [SHP06b] es un dominio abstracto que proporciona una aproximación segura de la longitud de la referencia más larga alcanzable desde las variables de interés. Esto permite probar terminación de los bucles que recorren las estructuras de datos acíclicos tales como listas enlazadas, árboles, etc. Sin embargo, las técnicas propuestas en [AAGP09] para los campos numéricos no son efectivos para los campos de referencia. Porque para el seguimiento de los campos de referencia, replicar los accesos de campo por las variables locales, presenta problemas de aliasing no deseado entre los campos y variables locales. Por otro lado, el enfoque sensible al contexto que se presenta en [AAG+10] es capaz de manejar los campos mediante una transformación polivariante.