SymC++: Un depurador simbólico para C++ Proyecto Sistemas Informáticos Clara Antolín García Carlos Gabriel Giraldo García Raquel Peces Muñoz Departamento de Sistemas Informáticos y Computación Facultad de Informática Universidad Complutense de Madrid 2013 / 2014 SymC++: Un depurador simbólico para C++ Proyecto de Sistemas Infórmaticos Clara Antolín García Carlos Gabriel Giraldo García Raquel Peces Muñoz Dirigido por: Miguel Gómez Zamalloa-Gil Departamento de Sistemas Informáticos y Computación Facultad de Informática Universidad Complutense de Madrid 2013 / 2014 Copyright c© Clara Antolín García, Carlos Gabriel Giraldo García y Ra- quel Peces Muñoz Autorización Clara Antolín García, Carlos Gabriel Giraldo García y Raquel Peces Mu- ñoz autores del presente documento y del proyecto �SymC++, una herra- mienta de depuración simbólica� autorizan a la Universidad Complutense de Madrid a difundir y utilizar con �nes académicos, no comerciales y mencio- nando expresamente a sus autores, tanto la propia memoria, como el código, los contenidos audiovisuales incluso si incluyen imágenes de los autores, la documentación y/o el prototipo desarrollado. Madrid, a 12 de Septiembre de 2014 Clara Antolín García Carlos Gabriel Giraldo García Raquel Peces Muñoz v Agradecimientos Este trabajo no sería posible si no hubiésemos contado con todo el apoyo de todas las personas que nos rodean. En primer lugar agradecer a nuestro tutor Miguel Gómez Zamalloa-Gil, el cual nos ha prestado todo su apoyo, interés y colaboración durante todo el desarrollo a lo largo de estos meses. En segundo lugar a todos los profesores que nos han acompañado en nuestra formación desde el primer día que pusimos un pie en la facultad, sin ellos no habríamos adquirido los conocimientos que nos han permitido desarrollar este trabajo. Por último y no menos importante, a nuestros familiares, amigos y compa- ñeros, los cuales nos han soportado y apoyado en los momentos de desánimo y crispación. A todos ellos, muchas gracias por creer en nosotros. vi Resumen En este proyecto se estudia y desarrolla una herramienta basada en de- puración simbólica que permite conocer el funcionamiento de programas in- formáticos sin ser ejecutados en base a observar todas sus posibles ramas de ejecución (hasta un cierto nivel), así como los correspondientes pares entrada- salida. Dicha herramienta está ideada con la idea de ayudar a los estudiantes de iniciación a la programación, y en general a programadores inexpertos a la hora de razonar acerca de la corrección de sus programas. El núcleo de la herramienta está basado en la ejecución simbólica, una de las técnicas más potentes para hacer estudios estáticos del comportamiento de los programas. La ejecución simbólica consiste en el análisis de un pro- grama usando valores simbólicos (o variables) en lugar de valores concretos. Esto permite comprender la ejecución del programa gracias a la observación de los comportamientos de sus diferentes caminos de ejecución, así como de- terminar las condiciones que deben ser veri�cadas por los datos de entrada para obtener un resultado particular, y la relación entre los valores ingresados y producidos en la ejecución de un programa. La herramienta desarrollada, denominada SymC++, recibe una serie de parámetros de entrada sobre la función a testear, partiendo de un código C++, obteniendo así información de las distintas ramas generadas. Dichos resultados se generan en formato XML lo cual facilita la portabilidad y es- calabilidad del proyecto ofreciendo un depurador que se puede adaptar a diferentes interfaces de usuario. Palabras clave Ejecución simbólica, ramas de ejecución, C++, XML, depuración, valor simbólico. vii Abstract This project studies and develops a tool based on symbolic debugging that allows reasoning about programs behavior statically, i.e., without being executed, by means of observing all possible branches of execution (up to a level) and their corresponding input-output behaviors. The tool is designed with the idea of helping students of introduction to programming, and, in general, inexperienced developers to reason about the correctness of their programs. The core of the tool is based on symbolic execution, one of the most powerful technologies for statically studying programs behavior. Symbolic execution consists in executing a program using symbolic values (or variables) instead of concrete values. This allows understanding the program execution by means of observing the behavior of the di�erent execution branches and to determine the conditions that must be veri�ed by the input data to obtain a particular result, and the relationship between the input and produced values in the execution of the program. The developed tool, called SymC++, receives a set of input parameters of the function to be tested (a C++ function), and obtains information about the generated execution branches. The results are output in XML format, which facilitates portability and scalability, hence providing a debugger that can be adapted to di�erent user interfaces. Key words Symbolic execution, Execution branches, C++, XML, Debugging, Sym- bolic value viii Índice Autorización v Agradecimientos vi Resumen vii Abstract viii 1. Introducción 1 1.1. Motivación de la propuesta . . . . . . . . . . . . . . . . . . . . 1 1.2. Estado del arte y trabajos relacionados . . . . . . . . . . . . . 2 1.2.1. C++ y Clang . . . . . . . . . . . . . . . . . . . . . . . 2 1.2.2. Veri�cación y Análisis . . . . . . . . . . . . . . . . . . 4 1.2.3. Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.2.4. Programación con restricciones . . . . . . . . . . . . . 8 1.2.5. Trabajos relacionados . . . . . . . . . . . . . . . . . . . 9 1.3. Objetivos, la herramienta SymC++ . . . . . . . . . . . . . . . 12 2. Herramienta de Clang 15 2.1. Historia de LLVM y CLANG . . . . . . . . . . . . . . . . . . 16 2.1.1. LLVM . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.1.2. CLANG . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.2. Uso de Clang . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.2.1. AST . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.2.2. La biblioteca LibTooling . . . . . . . . . . . . . . . . . 18 2.3. Estructura y recorrido del AST . . . . . . . . . . . . . . . . . 19 2.3.1. Funciones . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.3.2. Declaraciones e inicializaciones . . . . . . . . . . . . . . 21 2.3.3. Estructuras de control . . . . . . . . . . . . . . . . . . 23 2.3.4. Expresiones . . . . . . . . . . . . . . . . . . . . . . . . 25 ix 2.3.5. Interacción de entrada y salida . . . . . . . . . . . . . 31 2.4. Tecnología adicional . . . . . . . . . . . . . . . . . . . . . . . 32 2.5. Uso de AST2XML . . . . . . . . . . . . . . . . . . . . . . . . 33 3. Intérprete con restricciones 34 3.1. El lenguaje Prolog y la librería clpfd . . . . . . . . . . . . . . 34 3.2. Diseño e interfaz del intérprete . . . . . . . . . . . . . . . . . . 36 3.3. Ciclo de ejecución . . . . . . . . . . . . . . . . . . . . . . . . . 38 3.4. Funciones, declaración y asignación de variables. . . . . . . . . 42 3.5. Instrucciones aritméticas y condicionales. . . . . . . . . . . . . 44 3.6. Bucles y control de terminación. . . . . . . . . . . . . . . . . . 49 3.7. Instrucciones de Entrada/Salida. . . . . . . . . . . . . . . . . 52 3.8. Instrucción de retorno. . . . . . . . . . . . . . . . . . . . . . . 53 3.9. Uso del Intérprete . . . . . . . . . . . . . . . . . . . . . . . . . 54 4. Interfaz grá�ca de usuario de SymC++ 55 4.1. Java en el desarrollo de interfaces de usuario . . . . . . . . . . 55 4.2. Diseño y tecnologías utilizadas . . . . . . . . . . . . . . . . . . 56 4.3. Interfaz y sus funcionalidades . . . . . . . . . . . . . . . . . . 57 4.4. Estructura de la herramienta . . . . . . . . . . . . . . . . . . . 60 4.4.1. Comunicación entre la interfaz y ast2xml y el intérprete 60 4.4.2. Ciclo de ejecución de la herramienta . . . . . . . . . . 61 4.5. Directorio de archivos . . . . . . . . . . . . . . . . . . . . . . . 63 5. Conclusiones y trabajo futuro 65 5.1. Conclusiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 5.2. Ampliaciones potenciales y trabajo futuro . . . . . . . . . . . 66 A. Manual de usuario 68 A.1. Requisitos previos . . . . . . . . . . . . . . . . . . . . . . . . . 68 A.2. Instalación herramienta ast2xml . . . . . . . . . . . . . . . . . 69 A.3. Instalación interfaz de usuario . . . . . . . . . . . . . . . . . . 70 A.4. Tutorial de uso . . . . . . . . . . . . . . . . . . . . . . . . . . 70 Índice de �guras 1.1. Figura que muestra el ciclo de ejecución de nuestra herramien- ta. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.1. Figura que muestra la estructura del if...else. . . . . . . . . . . 48 3.2. Figura que muestra la estructura del bucle while. . . . . . . . 50 3.3. Figura que muestra la estructura del bucle for. . . . . . . . . . 51 4.1. Figura que muestra el diseño principal de la herramienta. . . . 57 4.2. Figura que muestra la sección del editor de texto. . . . . . . . 58 4.3. Figura que muestra la sección de soluciones del intérprete. . . 59 4.4. Figura que muestra la vista de un XML para su depuración por parte del usuario. . . . . . . . . . . . . . . . . . . . . . . . 59 4.5. Figura que muestra las conexiones entre todas las partes de la herramienta. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 4.6. Figura que muestra el ciclo de ejecución general de la arqui- tectura. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 4.7. Figura que muestra el diagrama de �ujo de la ejecución. . . . 64 A.1. Figura con el mensaje de aviso para seleccionar la herramienta ast2xml. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 A.2. Figura con el directorio de archivos para buscar la herramienta ast2xml. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 A.3. Figura con el directorio de archivos para buscar la herramienta ast2xml. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 A.4. Figura con una función escrita en el editor. . . . . . . . . . . . 73 A.5. Figura con la ventana para introducir los valores de entrada del intérprete. . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 A.6. Figura con la vista de la tabla de resultados. . . . . . . . . . . 74 A.7. Figura con la ventana principal de la interfaz con los resultados. 75 A.8. Figura con la vista de la traza de ejecución. . . . . . . . . . . 75 xi A.9. Figura con la ventana principal de la interfaz con los resultados y la traza resaltada. . . . . . . . . . . . . . . . . . . . . . . . . 76 A.10.Figura con la vista de las consolas de entrada y salida. . . . . 76 A.11.Figura con la vista del submenu ��le�. . . . . . . . . . . . . . . 77 A.12.Figura con la vista del submenu �edit�. . . . . . . . . . . . . . 77 A.13.Figura con la vistal submenu �run�. . . . . . . . . . . . . . . . 77 A.14.Figura con la vista del submenu �debug�. . . . . . . . . . . . . 78 A.15.Figura con la vista del XML generado. . . . . . . . . . . . . . 78 Índice de Tablas 1.1. Tabla de resultados para el código ejemplo . . . . . . . . . . . 13 3.1. Tabla con los operadores que reconoce el interprete. . . . . . . 47 xiii Índice de códigos 1.1. Código de ejemplo . . . . . . . . . . . . . . . . . . . . . . . . 12 2.1. Ejemplo del AST que emplea Clang a partir de un código especí�co. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.2. Código C++ ejemplo para un nodo function. . . . . . . . . . . 20 2.3. Código XML obtenido ejemplo de la disposición básica de un nodo function . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.4. Código C++ ejemplo para un nodo return . . . . . . . . . . . 21 2.5. Código XML obtenido ejemplo de la disposición básica de un nodo return . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.6. Código C++ ejemplo para un nodo declaration . . . . . . . . 22 2.7. Código XML obtenido ejemplo de la disposición básica de un nodo declaration . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.8. Código C++ ejemplo para un nodo If . . . . . . . . . . . . . . 23 2.9. Código XML obtenido ejemplo de la disposición básica de un nodo If . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.10. Código C++ ejemplo para un nodo While . . . . . . . . . . . 24 2.11. Código XML obtenido ejemplo de la disposición básica de un nodo While . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.12. Código C++ ejemplo para un nodo For . . . . . . . . . . . . . 24 2.13. Código XML obtenido ejemplo de la disposición básica de un nodo For . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.14. Código C++ ejemplo para un nodo de un operador binario . . 26 2.15. Código XML obtenido ejemplo de la disposición básica de un nodo con operador binario . . . . . . . . . . . . . . . . . . . . 26 2.16. Código C++ ejemplo para un nodo de un operador de asignación 27 2.17. Código XML obtenido ejemplo de la disposición básica de un nodo con operador de asignación . . . . . . . . . . . . . . . . 27 2.18. Código C++ ejemplo para un nodo con una asignación a otra variable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 xiv 2.19. Código XML obtenido ejemplo de la disposición básica de un nodo con una asignación a otra variable . . . . . . . . . . . . . 29 2.20. Código C++ ejemplo para un nodo con una asignación a un valor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.21. Código XML obtenido ejemplo de la disposición básica de un nodo con una asignación a un valor . . . . . . . . . . . . . . . 29 2.22. Código C++ ejemplo para un nodo con uun valor string . . . 30 2.23. Código XML obtenido ejemplo de la disposición básica de un nodo con un valor string . . . . . . . . . . . . . . . . . . . . . 30 2.24. Código C++ ejemplo para un nodo con la llamada a una función 30 2.25. Código XML obtenido ejemplo de la disposición básica de un nodo con la llamada a una función . . . . . . . . . . . . . . . 31 2.26. Uso de AST2XML. . . . . . . . . . . . . . . . . . . . . . . . . 33 3.1. Ejemplo de XML de entrada que recibe el intérprete . . . . . . 36 3.2. Ejemplo de XML obtenido por Clang . . . . . . . . . . . . . . 37 3.3. Ejemplo ilustrativo con función suma . . . . . . . . . . . . . . 38 3.4. árbol sintáctico de la función suma . . . . . . . . . . . . . . . 39 3.5. Elementos correspondientes a la función suma . . . . . . . . . 39 3.6. Instrucción para la de�nición de una función . . . . . . . . . . 42 3.7. Intrucción que recibe los parámetros de entrada . . . . . . . . 42 3.8. Intrucción para el cuerpo de un bloque . . . . . . . . . . . . . 42 3.9. Instrucción para la declaracion de una variable . . . . . . . . . 43 3.10. Intrucción para las declaraciones de varias variables en grupo . 43 3.11. Instrucción para la resolución de las expresiones . . . . . . . . 45 3.12. Operador unario . . . . . . . . . . . . . . . . . . . . . . . . . 45 3.13. Instrucciones para la resolución de expresiones con operadores binarios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 3.14. Asignación de una variable . . . . . . . . . . . . . . . . . . . . 46 3.15. Instrucción para la ejecución de expresiones . . . . . . . . . . 47 3.16. Instrucción para la estructura condicional if . . . . . . . . . . 47 3.17. Instrucción para la ejecución de estructuras condicionales . . . 48 3.18. Instrucción para la ejecución de la rama then . . . . . . . . . . 48 3.19. Instrucción para la ejecución de la rama else . . . . . . . . . . 49 3.20. Instrucción para la ejecución del bucle while . . . . . . . . . . 49 3.21. Instrucción para la ejecución del bucle for . . . . . . . . . . . 50 3.22. Instrucción para el caso en el que bucle �naliza por la variable maxDepth . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 3.23. Instrucción para el caso en el que llegamos al �n del bucle . . 52 3.24. Instrucción para el caso en el que ejecutamos el cuerpo del bucle 52 3.25. Instrucción para la ejecución de la consola de entrada . . . . . 52 3.26. Instrucción para la ejecución de la consola de salida . . . . . . 53 3.27. Instrucción para la ejecución de la sentencia return . . . . . . 53 Capítulo 1 Introducción If debugging is the process of removing bugs, then programming must be the process of putting them in... Edsger Dijkstra. 1.1. Motivación de la propuesta El proyecto nace de la idea y necesidad de utilizar una herramienta útil para los estudiantes de iniciación a la programación. El problema al que se en- frentan los estudiantes cuando los ejercicios a resolver crecen en complejidad, los programas también y normalmente no se comportan como deben para to- dos los casos. Escribir programas totalmente correctos requiere el uso de una serie de metodologías que en general resultan muy complejas para los estu- diantes en los primeros cursos. La mayoría de ellos siguen una mecánica de prueba-error, es decir, escriben los programas sin pararse a pensar demasiado acerca de su corrección, y luego los prueban para ver si se comportan como esperan. Estas pruebas normalmente no son lo su�cientemente exhaustivas y por lo tanto los estudiantes no son ni siquiera conscientes de las incorreccio- nes de sus programas. Desgraciadamente, los mecanismos y herramientas que ayudan en el testing y depuración de programas son en general demasiado avanzados, como para poder ser utilizados por programadores inexpertos. Dado este problema aparece nuestro proyecto, como una herramienta sen- cilla e intuitiva que pueda mostrar de un modo natural el recorrido de un programa por sus diferentes ramas y los resultados que obtendría en cada uno de ellos. Esta herramienta ofrecerá una solución a la veri�cación de pro- gramas sencillos para estudiantes de iniciación, y de este modo acercar las herramientas de testing y depuración de un modo más fácil y visual. 1 La herramienta está desarrollada para el lenguaje de C++, puesto que es el utilizado en los primeros cursos de los grados de las Facultades de Informá- tica, Estudios Estadísticos y Matemáticas, y concretamente es el utilizado en la asignatura de primer curso de Fundamentos de Programación en nuestra Facultad. 1.2. Estado del arte y trabajos relacionados En esta sección se presentan los recursos y herramientas software dispo- nibles que se han planteado como opciones a tener en cuenta a la hora de obtener apoyo en la realización de nuestro proyecto. 1.2.1. C++ y Clang C++, un lenguaje con historia C++ es un lenguaje de programación diseñado a mediados de los años 80 por Bjarne Stroustrup en los Laboratorios de Bell. [1] C++ nació como extensión del lenguaje de programación C, al mismo tiempo que proporciona un cierto número de características que engalanan dicho lenguaje. El nombre de C++ fue propuesto por Rick Mascitti en el año 1983, cuando el lenguaje fue utilizado por primera vez fuera de un laboratorio cientí�co. Hasta ese momento se había utilizado el nombre de C con clases. Se puede decir que C++ es un lenguaje que abarca tres paradigmas de programación: la programación estructurada, la programación genérica y la programación orientada a objetos. Es un lenguaje de programación interme- dio, puesto que se puede utilizar tanto para el desarrollo rápido de aplicacio- nes, como para escribir software de bajo nivel, como drivers y componentes de sistemas operativos. Actualmente existe un estándar, denominado ISO C++, al que se han adherido la mayoría de los fabricantes de compiladores más modernos. Exis- ten también algunos intérpretes, tales como ROOT. [2] Las principales características de este lenguaje son las facilidades que pro- porciona para la programación orientada a objetos y para el uso de plantillas o programación genérica. Además posee una serie de propiedades di�ciles de encontrar en otros lenguajes como es la posibilidad de rede�nir los operadores o poder crear nuevos tipos, que se comporten como tipos fundamentales. La elección de desarrollar nuestra herramienta para el lenguaje de C++ se ha basado en dos motivos, el primero ha sido su popularidad, puesto que según el ranking TIOBE, el cual recoge los lenguajes de programación más 2 usados, se encuentra en cuarta posición, y el segundo motivo ha sido el uso de este lenguaje en los primeros cursos de programación como ya hemos señalado anteriormente. [3] Clang y LLVM Clang es un front-end de compilador para los lenguajes de programación C, C++, Objective-C y Objective-C++. Usa LLVM (anteriormente conocido como Low Level Virtual Machine, o Máquina Virtual de Nivel Bajo) como su back-end y ha sido parte del ciclo de lanzamiento de LLVM desde la versión 2.6. Está diseñado para ofrecer un reemplazo de GNU Compiler Collection (GCC). Es open-source, y varias compañías de software están involucradas en su desarrollo, incluyendo a Google y Apple. Su código fuente está bajo la licencia University of Illinois/NCSA. El proyecto Clang incluye además un analizador estático de software y varias herramientas de análisis de código. [4] Por otro lado, LLVM es una infraestructura para desarrollar compiladores, escrita a su vez en el lenguaje de programación C++, que está diseñada para optimizar el tiempo de compilación, el tiempo de enlazado, el tiempo de ejecución y el tiempo ocioso en cualquier lenguaje de programación que el usuario quiera de�nir. Implementado originalmente para compilar C y C++, el diseño agnóstico de LLVM con respecto al lenguaje, y el éxito del proyecto han engendrado una amplia variedad de lenguajes, incluyendo Objective-C, Fortran, Ada, Haskell, bytecode de Java, Python, Ruby y otros. LLVM suministra las capas intermedias de un sistema de compilado com- pleto, tomando el código en formato intermedio (IF, en sus siglas en inglés) de un compilador y emitiendo un IF optimizado. Este nuevo IF puede ser convertido y enlazado en un código ensamblador dependiente de la máquina concreta para una plataforma objetivo. LLVM puede aceptar el IF generado por la cadena de herramientas GCC, permitiendo así que sea utilizado con todos los lenguages que a su vez son aceptados por GCC. LLVM también puede generar código máquina relocalizable en el momento de compilación o de enlazado, o incluso código máquina binario en el momento de ejecución. [5] 3 1.2.2. Veri�cación y Análisis Actualmente el software es uno de los productos más requeridos en el mundo. Tal demanda de software implica procesos de desarrollo más intensos, exhaustivos y menos propensos a errores. Siendo la corrección de fallos la etapa en la que más recursos se invierten y en la que hay más interés por mejorar su e�ciencia. A día de hoy en el mercado existen paquetes de herramientas capaces de ofrecer a los desarrolladores detección de errores y estudios sobre la ejecución de sus programas. Existen varias maneras de veri�car la correctitud de un programa. [6] Sistemas de tipos Asignar tipos de datos (tipi�car) da signi�cado a colecciones de bits. Los tipos de datos normalmente tienen asociaciones tanto con valores en la me- moria o con objetos como con variables. Al igual que cualquier valor consiste en un conjunto de bits de un ordenador, el hardware no hace distinción entre dirección de memoria, código de instrucción, carácteres, enteros y números en coma �otante. Los tipos de datos informan a los programas y programadores cómo deben ser tratados esos bits. Al proceso de veri�car e imponer los límites por los tipos de datos, conoci- do como comprobación o checkeo de tipi�cación. Este proceso puede ocurrir tanto en la compilación (comprobación estática) o en la ejecución (comproba- ción dinámica). La elección entre sistemas de tipi�cación dinámico y estático requiere algunas contraprestaciones: El tipado estático busca errores en los tipos de datos durante la compilación. Esto debería incrementar la �abilidad de los programas procesados. Sin embargo, los programadores, normalmente, están en desacuerdo en cómo los errores de tipos de datos más comunes ocu- rren, y en qué proporción de estos errores que se han escrito podrían haberse cazado con un tipado estático. Los defensores de los lenguajes fuertemente tipados han sugerido que casi todos los errores pueden ser considerados errores de los tipos de datos. El tipado dinámico permite a los compiladores e intérpretes ejecutar- se más rápidamente, debido a que los cambios en el código fuente en los lenguajes dinámicamente tipados puede resultar en menores comproba- ciones y menos código que revisar. Esto también reduce el ciclo editar- compilar-comprobar-depurar. El tipado dinámico típicamente hace que la metaprogramación sea más poderosa y fácil de usar. 4 Análisis estático El análisis estático de software es un tipo de análisis que se realiza sin ejecutar el programa. En la mayoría de los casos se realiza sobre el código fuente y en otros casos se realiza sobre el código objeto. Dicho término se aplica a los análisis realizados por parte de una herra- mienta automática sobre el programa sin que este se ejecute. La industria ha reconocido los métodos de análisis estático como elementos clave a la hora de mejorar la calidad de programas complejos. Un uso comercial creciente del análisis estático es la veri�cación de las propiedades de software utilizadas en sistemas informáticos críticos para la seguridad y la localización de código vulnerable, pero también se incluyen una viariedad de métodos formales que veri�can ciertas propiedades del programa. Por ejemplo, el uso de este tipo de análisis está muy extendido en los campos de la medicina, la aviación o la energía nuclear, donde no se pueden permitir errores ni riesgos. Veri�cación de modelos (Model checking) La veri�cación de modelos (o Model checking) es un método automático de veri�cación de un sistema formal, en la mayoría de las ocasiones deri- vado del hardware o del software de un sistema informático. El sistema es descrito mediante un modelo, que debe satisfacer una especi�cación formal descrita mediante una fórmula, a menudo escrita en alguna variedad de lógica temporal. El modelo suele estar expresado como un sistema de transiciones, es decir, un grafo dirigido, que consta de un conjunto de vértices y arcos. Un conjunto de proposiciones atómicas se asocia a cada nodo. Así pues, los nodos repre- sentan los estados posibles de un sistema, los arcos posibles evoluciones del mismo, mediante ejecuciones permitidas, que alteran el estado, mientras que las proposiciones representan las propiedades básicas que se satisfacen en cada punto de la ejecución. Formalmente, el problema se representa de la siguiente manera: Dada una propiedad deseada, expresada como una fórmula en lógica temporal p, y un modelo M con un estado inicial s. Los inventores del método, Edmund M. Clarke, E. Allen Emerson y Jo- seph Sifakis, recibieron el Premio Turing 2007 de la ACM, en reconocimiento de su fundamental contribución al campo de las ciencias de la computación. [7] 5 Ejecución simbólica La ejecución simbólica o evaluación simbólica es una de las técnicas más potentes para el análisis de programas. Esta técnica permite hacer razona- mientos sobre programas en base a observar los comportamientos de cada uno de sus caminos de ejecución. Un intérprete recorre el programa donde cada variable asume un valor simbólico acotado. Este recorrido dará como re- sultado expresiones en términos de dichos valores simbólicos por cada una de las ramas de ejecución. De este modo, obtendremos los resultados dependien- do del recorrido que hayan tomado las variables simbólicas, y gracias a este recorrido podremos determinar las condiciones que deben ser veri�cadas por los datos de ingreso para que un camino particular se ejecute, y la relación entre los valores ingresados y producidos en la ejecución de un programa. El proceso de generación de casos de prueba por ejecución simbólica pro- duce un conjunto de sistemas de restricciones que pueden entenderse como clases de equivalencia de entradas. Así, el conjunto posiblemente in�nito de entradas de una clase de equivalencia llevaría al programa a recorrer el mis- mo camino de ejecución. Estas clases de equivalencia se pueden entender por tanto como casos de prueba. Puesto que la ejecución simbólica razona en tér- minos de caminos de ejecución, nos permite obtener un caso de prueba para cada camino de ejecución del programa, pudiendo garantizar así un buen recubrimiento con un número reducido de casos de prueba. Este procedicimiento aplicado al hardware recibe el nombre de simulación simbólica. [8] Por otro lado, aún no se ha aplicado con éxito en el contexto de programas concurrentes. Este problema plantea sin duda nuevos retos, al tener que com- binar la complejidad inherente a la ejecución simbólica con aspectos de los programas concurrentes tales como la suspensión de tareas, la sincronización, las posibles estrategias de plani�cación de tareas, etc. 1.2.3. Testing Paralelamente a las herramientas de veri�cación y análisis nacen las prue- bas de software(o testing en inglés). Estas pruebas son investigaciones em- píricas y técnicas cuyo objetivo es proporcionar información objetiva e inde- pendiente sobre la calidad del producto a la parte interesada. Estas pruebas se diferencian de las herramientas de veri�cación y análisis en que garantizan la correctitud de los programas para esos test, pero es im- posible que dichos test abarquen todas las posibilidades o ramas de ejecución de un programa, de tal modo que el programa podría no estar correcto para todas sus posibilidades como si garantiza la veri�cación y el análisis. A conti- 6 nuación detallamos algunas de estas herramientas que ayudan a automatizar distintas fases del proceso de testing. Frameworks xUnit Durante su trabajo en los laboratorios de Xerox Park, Kent Beck desarro- llo un framework para realizar test unitarios en el lenguaje de programación Smalltalk que estaba desarrollando. Dicho framework se llamaba sUnit. sUnit Permitía agrupar los tests en suites, el lanzamiento jerárquico de éstos y realizar para cada test la comparación entre el valor obtenido y el valor esperado para determinar la corrección de la funcionalidad testeada. Este framework ha sido llevado a una gran variedad de lenguajes de programación (JUnit, XSLTUnit, PhpUnit, PyUnit/ldots). xUnit es el nombre con el que se designa genéricamente a todos estos frameworks. [9] Una de las características de los tests xUnit es la expansión y el alto grado de utilización de esta herramienta por todo el mundo. Generación de tests El objetivo de las pruebas es presentar información sobre la calidad del producto a las personas responsables, por tanto la información requerida pue- de ser de lo más variada. Esto hace que el proceso de testing sea dependiente del contexto, no existen las mejores pruebas, toda prueba puede ser ideal para una situación o completamente inutil o perjudicial para otra. A continuación detallamos algunas de los diferentes enfoques para la ge- neración de tests: [10] Pruebas de caja blanca (white-box). Estas pruebas se centran en los detalles procedimentales del software, por lo que su diseño está fuerte- mente ligado al código fuente. El testeador escoge distintos valores de entrada para examinar cada uno de los posibles �ujos de ejecución y cerciorarse de que se devuelven los valores de salida adecuados. Puesto que están basados en una implementación concreta, si esta se modi�- ca, normalmente también tendrán que rediseñarse las pruebas. A pesar de que este enfoque permite diseñar pruebas que cubran una amplia variedad de casos podría pasar por alto partes incompletas de la espe- ci�cación o requisitos faltantes. Pruebas de caja negra (black-box). Estas pruebas se centran en el estudio de las entradas y las salidas generadas, independientemente de su funcionamiento interno, es decir, nos interesa su forma de interactuar 7 entendiendo qué es lo que hace pero sin importarnos el cómo lo hace. Las pruebas basadas en este sistema serán más fáciles de entender ya que permitirán dar una visión más clara del conjunto, el sistema también será más robusto y fácil de mantener, en caso de fallo este podrá ser aislado y abordado más ágilmente. Testing aleatorio o random. Buscando ampliar el ámbito de pruebas de unidad, se han aplicado diversas técnicas que van desde la auto- matización de pasos, hasta los enfoques de generación de objetos de manera aleatoria. En este caso concreteo, la generación de tests de for- ma aleatoria es un caso particular de las pruebas de caja negra, donde las pruebas se realizan con entradas generadas de manera aleatoria e independiente. Los resultados se comparan con las especi�caciones del software en prueba para veri�car si los resultados pasan el test o no. 1.2.4. Programación con restricciones La programación con restricciones es un paradigma de la programación en informática, donde las relaciones entre las variables son expresadas en terminos de restricciones o ecuaciones. Este paradigma representa uno de los mayores desarrollos en los lenguajes de programación desde 1990 y ha sido identi�cada como una dirección estratégica en la investigación en compu- tación. Se trata de un paradigma de programación basado en la especi�cación de un conjunto de restricciones las cuales deben ser satisfechas por cualquier so- lución del problema planteado, en lugar de especi�car los pasos para obtener dicha solución. El enfoque de este tipo de programación se basa principal- mente en especi�car un estado en el cual una gran cantidad de restricciones sean satisfechas simultaneamente. Un problema se de�ne típicamente como un estado de la realidad en el cual existe un número de variables con valor desconocido. Un programa basado en restricciones busca dichos valores para todas las variables. Actualmente existen muchos frentes de desarrollo relacionados con la pro- gramación con restricciones. Entre ellos destacan: Oz: Lenguaje multiparadigma y esotérico basado en la rama concurren- te de la programación por restricciones. En el que se expresa música a partir de unas restricciones expresadas explícitamente por el progra- mador. Se utiliza en proyectos tales como Mozart y Strasheela. [11] 8 Choco: Es una librería que añade satisfacción de restricciones a Java. Está construida en una estructura basada en la propagación de eventos. Ha sido utilizada en otros proyectos de ejecución simbólica como JsyX. [12] Gecode: Es un proyecto abierto que cuenta con un conjunto de herra- mientas basado en C/C++ para el desarrollo de sistema y aplicaciones nativas que se apoyen en restricciones. [13] La programación con restricciones se relaciona mucho con la programación lógica, de hecho cualquier programa lógico puede ser traducido a un programa con restricciones y viceversa, en muchas ocasiones los programas lógicos son traducidos a programas con restricciones puesto que la solución es mucho más e�ciente. Los lenguajes de programación con restricciones son típicamente amplia- ciones de otro lenguaje. El primer lenguaje utilizado a tal efecto fue Prolog. Por esta razón este campo fue llamado inicialmente Programación Lógica con Restricciones. La programación lógica con restricciones es un caso particular de la pro- gramación con restricciones, en el cual la programación lógica se extiende para incluir conceptos de la programación con restricciones. Por tanto, un programa lógico con restricciones es un programa lógico que contiene res- tricciones en el cuerpo de sus claúsulas. Por ejemplo, la claúsula A(X,Y) :- X+Y>0, B(X), C(Y) es un ejemplo de una cláusula con restricciones donde X+Y>0 es la restriccion y B(X), C(Y) son literales al igual que en progra- mación lógica. Al igual que en la programación lógica, los programas se ejecutan bus- cando demostrar un objetivo que puede contener restricciones además de los literales. Una prueba para un objetivo se compone de claúsulas cuyos cuer- pos satisfacen las restricciones y literales que se pueden probar usando otras claúsulas. La ejecución se realiza a través de un intérprete, que empieza des- de un objetivo y recursivamente escanea el resto de claúsulas para probar el objetivo. 1.2.5. Trabajos relacionados Como hemos mencionado anteriormente, la ejecución simbólica no es algo nuevo y ha adquirido protagonismo en los últimos años. Es por esto que podemos encontrar varios proyectos orientados al testing de diversos estilos, aquí describimos algunos de ellos para contextualizar nuestro proyecto. 9 1.2.5.1. PEX PEX es una herramienta desarrollada por Microsoft para la generación automática de casos de prueba. Esta herramienta genera entradas de test para programas .NET, por tanto puede analizar cualquier programa que se ejecute en una máquina virtual .NET y soporta lenguajes como C#, Visual Basic y F#. El enfoque de PEX se caracteriza por implementar la ejecución dinámica simbólica, pero también permite el uso de ejecucución concreta de valores para simpli�car las restricciones, las cuales serían resuletas por el resolutor SMT. Por tanto, mediante un proceso iterativo, PEX realiza una ejecución concreta del método a analizar y examina la traza de ejecución buscando ramas no exploradas. Una vez ha encontrado una rama no explorada, usa la ejecu-ción simbólica y un sistema resolutor de restricciones para generar va- lores concretos que exploren dicha rama. Este proceso se repite hasta obtener el recubrimiento deseado. El hecho de combinar la ejecución simbólica con la concreta permite en muchos casos incrementar la escalabilidad y tratar con situaciones donde la ejecución no depende sólo del código sino de factores externos. Se entiende por factores externos el uso de librerías nativas, llamadas al sistema operativo o interacciones con el usuario. Ante este tipo de situaciones, la ejecución simbólica presenta grandes limitaciones y en general, no se puede aplicar. Esta herramienta se puede integrar en el entorno de desarrollo de Visual Studio facilitando su uso como un añadido (Addon). Como proyecto interesante relacionado con PEX existe el juego Code Hunt también desarrollado por Microsoft. En este juego el jugador debe es- cribir código para avanzar en el juego. La relacióncon PEX es que lo que se muestra al jugador son las entradas y salidas, y mediante ejecución simbólica se evaluará el código escrito y de este modo poder avanzar. [14] 1.2.5.2. PET PET (Partial Evaluation-based Test Case Generator for Bytecode) es una herramienta cuyo propósito es generar casos de prueba de forma automática para programas escritos en bytecode (código de bytes) de Java. PET adopta el enfoque previamente comentado, esto es, ejecuta el bytecode simbólicamente y devuelve como salida un conjunto de casos de prueba (test-cases). Cada caso de prueba está asociado a una rama del árbol y se expresa como un conjunto de restricciones sobre los valores de entrada y una descripción de los contenidos de la memoria dinámica (o heap). Las restricciones de la memoria dinámica imponen condiciones sobre la 10 forma y contenidos de las estructuras de datos del programa alojadas en esta misma. PET utiliza de un resolutor de restricciones que genera valores concretos a partir de estas restricciones, permitiendo la construcción de los tests propiamente dichos. PET puede usarse a través de una interfaz de línea de comandos o bien usando una interfaz web. Además soporta una variedad de opciones intere- santes, como la elección de criterios de recubrimiento o la generación de tests jUnit. Estas opciones se describen con más detalle en el segundo capítulo. [15] 1.2.5.3. jSYX jSYX es un proyecto desarrollado el curso pasado como trabajo de Sis- temas Informáticos. Este proyecto se basa en una máquina virtual de Java que permite la ejecución simbólica de archivos .class de Java, de este modo puede ser utilizado para el desarrollo automático de Tests. El enfoque de jSYX es el uso de del Bytecode de Java como lenguaje de ejecución. Esta herramienta permite la ejecución recibiendo como parámetros una clase y su método, y de este modo permite la ejecución simbólicamente o de manera concreta. Por otra lado se podrá obtener información sobre el bytecode del archivo .class. [16] 1.2.5.4. jPET Al igual que el detallado en la sección anterior, jPET también se trata de un proyecto de Sistemas Informáticos, en este caso desarrollado durante el curso 2010/2011. Este proyecto se basa en PET, la herramienta detallada anteriormente, y es una extensión de dicha herramienta para poder utilizarse en programas Java de alto nivel e integrarse en Eclipse, con el objetivo de poder usar los resultados obtenidos por PET durante el proceso de desarrollo de software. El enfoque de jPET es el tratamiento de la información generada por PET con el objetivo de presentarla al usuario de una manera más fácil, sencilla e intuitiva. Es por esto que incorpora un visor de casos de prueba para mostrar el contenido de memoria antes y después de la ejecución, una herramienta de depuración, para ver los resultados mostrando la secuencia de instrucciones que el caso de prueba ejecutaría, y es capaz de analizar sintácticamente precondiciones de métodos para evitar la generación de casos de prueba poco interesantes. [17] [18] 11 1.3. Objetivos, la herramienta SymC++ La elaboración de este proyecto tiene como objetivo principal el desa- rrollo de una herramienta propia de �depuración simbólica� que permite la depuración de programas informáticos sin la necesidad de ser ejecutados al mismo tiempo que permite trabajar a nivel de métodos permitiéndonos veri- �car funcionalidades sueltas. Esta herramienta pueda ser utilizada como un medio de apoyo a los estudiantes de iniciación a la programación, y en gene- ral a programadores inexpertos, a la hora de razonar acerca de la corrección de sus programas Sólo se utilizará como forma de comprobación, no como solucionador de errores tanto sintácticos como semánticos, es decir, no realiza la función de compilador; mostrará los resultados de la ejecución para ciertas posibles en- tradas y así comprobar si ésa es la solución que esperabas, de no ser así, el alumno sabrá que el código estará mal planteado. Los alumnos que están empezando a programar en C++ saben si su programa compila gracias al entorno que estén utilizando pero les es más difícil de comprobar si su progra- ma está correcto sin la ayuda de una interfaz o de algúna otra herramienta. Ahí es donde entra nuestra herramienta. La herramienta contará con una interfaz de usuario, proporcionando va- rias ventajas adicionales: el alumno podrá ver y actualizar cómodamente, en todo momento, el código que desee probar, podrá tanto escribir un código desde cero como importar un código ya creado, por otro lado, la herramienta marcará el recorrido que se ha realizado de forma que el alumno podrá corre- gir posibles errores más rápidamente, por ejemplo, al encontrar un recorrido que no era el deseado. Para ilustrar mejor el funcionamiento de nuestra herramienta detallamos aquí un pequeño ejemplo para una función cuya estructura es un pequeño decodi�cador: Código 1.1: Código de ejemplo 1 function deco(int a, int b){ 2 if (a>0) 3 if (b>0) 4 return 0; 5 else 6 return 1; 7 else 8 if (b>0) 9 return 2; 10 else 12 11 return 3; 12 } La ejecución del programa mostrado en el código anterior en nuestra herramienta generaría la tabla de resultados 1.1. n◦ Variable y valor Traza 1 a=1 b=1 return=0 1,2,3 2 a=1 b=0 return=1 1,4,5 3 a=0 b=1 return=2 6,7,8 4 a=0 b=0 return=3 6,9,10 Tabla 1.1: Tabla de resultados para el código ejemplo Esta tabla de resultados muestra en la primera columna el número co- rrespondiente a la solución, en la segunda columna se muestra el valor de las variables de la solución, las cuales hacen referencia a las variables de entrada de la función y la variable de salida o return, y en la tercera columna se muestra la traza de ejecución, o lo que es lo mismo, los números de línea que ha recorrido el programa para llegar a dicha solución. Por tanto, para el primer resultado, las entradas valen en este caso �1, 1� haciendo referencia a que son valores mayores que 0, y el valor del return es el valor de salida, por otro lado los números que indican la traza son los números de las líneas que se han recorrido del programa para esta solución, en este caso �1, 2, 3�, y así sucesivamente para lo otros tres resultados. Para llegar a esta solución, hemos desarrollado la herramienta denomina- da SymC++, el nombre surge de la relación con la ejecución simbólica y por estar desarrollada pensando en el lenguaje de programación C++. Dicha herramienta hará uso de tres componentes principales, cuyo ciclo de ejecución detallamos en la siguiente �gura: Figura 1.1: Figura que muestra el ciclo de ejecución de nuestra herramienta. 13 Por tanto, como se puede observar en la �gura anterior, la herramienta SymC++ consta de tres partes diferenciadas: Ast2xml: una herramienta desarrollada a través de Clang para obtener el arbol de sintaxis anotado con la información que nos interesa, la cual detallamos en el siguiente capítulo. Intérprete simbólico: la parte central del proyecto, es decir, el in- térprete prolog que se encarga de obtener las posibles soluciones para cada una de las ramas del programa, así como la traza de ejecución a través de sus entradas y salidas, esta parte la detallaremos en el tercer capítulo. Interfaz de usuario: funciona como enlace entre las dos partes nom- bradas anteriormente y el usuario y la detallaremos en el cuarto capítulo de esta memoria. 14 Capítulo 2 Herramienta de Clang En este capítulo analizaremos en profundidad la herramienta construida para realizar el primer paso hacia una ejecución simbólica de un programa por nuestro proyecto. Discutiremos las decisiones de diseño y los métodos empleados para organizar los datos de una manera intuitiva y cómoda de manipular en la siguiente etapa del proceso. La herramienta AST2XML conforma junto con el intérprete simbólico el cuerpo central del proyecto. Si bien esta herramienta no cumple el papel más importante, suple las necesidades básicas de obtener a partir del código fuente una representación más manejable y sencilla de visualizar. Ha sido desarrollada a partir del proyecto abierto e internacional Low Level Virtual Machine (a partir de ahora: LLVM), pero se apoya principalmente en su compilador CLANG. Al inicio del curso observamos que nos podíamos aproximar al problema de distintas formas. Si bien, de una forma similar al proyecto jSyx teniamos la posibilidad de basar nuestro proyecto en el uso de algo similar al bytecode de java pero relacionado con C++. De hecho tal aproximación hacia el aná- lisis simbólico existe en la máquina virtual simbólica Klee, el cual deriva del proyecto LLVM. Independientemente de ello, optamos por una aproximación diferente, que es separar expresamente el intérprete de la herramienta que analiza el código. Por tanto viendo las posibilidades que aporta el proyecto LLVM decidimos enfocarlo de manera similar. 15 2.1. Historia de LLVM y CLANG 2.1.1. LLVM El un principio �LLVM� eran las iniciales de �Low Level Virtual Machine� (Máquina Virtual de Bajo Nivel). LLVM nació como proyecto en el año 2000 en la Universidad de Illinois en UrbanaChampaign. En 2005, junto con Apple Inc., se empezó a adaptar el sistema para varios usos dentro del ecosistema de desarrollo de Apple. La denominación inicial del proyecto con las siglas LLVM causó una confusión ampliamente difundida, puesto que las máquinas virtuales son sólo una de sus aplicaciones posibles. Cuando la extensión del proyecto se amplió incluso más, LLVM se convirtió en un proyecto que englo- ba una gran varriedad de otros compiladores y tecnologías de bajo nivel. Por tanto el proyecto abandonó las iniciales y actualmente, LLVM es la manera de referirse a todas esas utilidades. Actualmente LLVM está integrado en las últimas herramientas de desarrollo de Apple para sus sistemas operativos. 2.1.2. CLANG El amplio interés que ha recibido LLVM ha llevado a una serie de ten- tativas para desarrollar frontends totalmente nuevos para una variedad de lenguajes. El que ha recibido la mayor atención es CLANG, un nuevo com- pilador que soporta otros lenguajes de la familia de C (ObjectiveC, C++, etc.). En un principio estaba proyectado que LLVM se apoyara en el compilador de C de GNU [19] (a partir de ahora GCC) pero los desarrolladores de Apple fueron encontrando numerosas di�cultades técnicas. Principalmente el pro- blema fue que al ser una plataforma desarrollada durante mucho tiempo GCC presentaba una estructura demasiado compleja sobre la que ir añadiendo las modi�caciones necesarias para solventar los problemas de compatibilidad. CLANG está diseñado para trabajar en una capa de abstracción por encima de LLVM. Una de los principales objetivos del diseño de CLANG es dar soporte a la compilación incremental1 con la idea de conseguir una completa integración de esta a los entornos de desarrollo con interfaz grá�ca. CLANG está construido siguiendo una estructura modular basada en la inclusión de numerosas bibliotecas con lo que intenta alejarse de otros compi- ladores de diseño monolítico. Este diseño modular se adapta a la escalabilidad que se buscaba originalmente en el proyecto. CLANG también fue diseñado para conservar mucha más información durante la compilación que GCC y mantener la forma original del código. Asimismo se ha dado importancia a 16 los informes de error que son bastante detallados. Actualmente es apoyado principalmente por Apple y se espera que CLANG sustituya al comiplador del sistema GCC. 2.2. Uso de Clang En la mayoría de los casos CLANG ejecutará el preprocesado y parseará el código formando un árbol de sintáxis abstracta (de ahora en adelante: AST). Esta estructura de árbol es más manejable que el propio código con el añadido de que cualquier subestructura mantiene referencias al código fuente. En nuestro proyecto el uso de CLANG ha sido bastante localizado dentro de las funcionalidades que ofrece. 2.2.1. AST Un AST es una representación de árbol de la estructura sintáctica abstrac- ta simpli�cada del código fuente. Esta estructura es ampliamente utilizada en los distintos compiladores del mercado. Cada nodo del árbol denota una construcción de lo que se encuenta en el código fuente. La herramienta AST2XML se apoya en la adaptación del código, por parte del AST propio de CLANG, a un formato XML. La representación del AST que emplea CLANG se diferencia de la de otros compiladores en cuanto a que mantiene la semejanza con el código escrito y con el estándar de C++. Código 2.1: Ejemplo del AST que emplea Clang a partir de un código espe- cí�co. 1 $ cat test.cc 2 int f(int x) { 3 int result = (x / 42); 4 return result; 5 } 6 7 # Clang by default is a frontend for many tools; -Xclang is used to pass 8 # options directly to the C++ frontend. 9 $ clang -Xclang -ast -dump -fsyntax -only test.cc 10 TranslationUnitDecl 0x5aea0d0 <> 11 ... cutting out internal declarations of clang ... 12 `-FunctionDecl 0x5aeab50 f 'int ( int)' 13 |-ParmVarDecl 0x5aeaa90 x 'int' 14 `-CompoundStmt 0x5aead88 17 15 |-DeclStmt 0x5aead10 16 | `-VarDecl 0x5aeac10 result 'int' 17 | `-ParenExpr 0x5aeacf0 'int' 18 | `-BinaryOperator 0x5aeacc8 'int' '/' 19 | |-ImplicitCastExpr 0x5aeacb0 'int' < LValueToRValue > 20 | | `-DeclRefExpr 0x5aeac68 'int' lvalue ParmVar 0x5aeaa90 'x' 'int' 21 | `-IntegerLiteral 0x5aeac90 'int' 42 22 `-ReturnStmt 0x5aead68 23 `-ImplicitCastExpr 0x5aead50 'int' < LValueToRValue > 24 `-DeclRefExpr 0x5aead28 'int' lvalue Var 0 x5aeac10 'result ' 'int' Como se puede apreciar en la �gura, la representación que se obtiene directamente de CLANG puede llegar a parecer abrumadoramente compleja y redundante. En momentos iniciales del proyecto tomamos la decisión de que información como la ubicación de los elementos, los tipos de las variables, o incluso el tipo de los nodos no serían necesarias en cada momento. Para ello hizo falta una implementación muy precisa de un tipo de herramienta que se puede construir para CLANG. 2.2.2. La biblioteca LibTooling La biblioteca LibTooling tiene un papel muy importante en la arqui- tectura de la herramienta. Libtooling da soporte al diseño de herramientas autónomas basadas en CLANG, proveyendo de la infraestructura necesaria para la realización de análisis sintácticos y semánticos de programas. [20] En la implementación de nuestra herramienta destacan los roles de estos elementos que nos aporta la biblioteca: CommonOptionParser: Es una utilidad que se encarga del análisis de los argumentos que recibe la llamada del ejecutable ast2xml. Aporta los mensajes por defecto de las utilidades básicas de las herramientas que se pueden implementar. ToXMLVisitor: Es el núcleo de la herramienta. Hereda de la interfaz RecursiveASTVisitor [21], que como su nombre indica, se encarga de hacer un recorrido recursivo y en profundidad de la estructura. Dentro de nuestro visitor hay que implementar los diferentes métodos especí- �cos que se amoldan a los distíntos nodos que vaya a visitar dentro del AST. 18 ToXMLASTConsumer: Es la clase que desencadena la ejecución del visitor. ToXMLFrontendAction: Es la clase que encapsula el comportamien- to de nuestra herramienta. Esta clase hereda de la clase abstracta AST- FrontendAction del paquete FrontendAction. Devuelve una instancia de nuestro consumidor en el momento de comenzar a recorrer el AST. 2.3. Estructura y recorrido del AST La estructura que emplea CLANG para representar el AST de un código se basa principalmente en la interacción de dos clases base muy �exibles a partir de las cuales se construyen todas los demás: Decl (Declarations), que engloba toda las declaraciones (funciones, variables, templates, etc ...), Stmt (Statement) que abarca las instrucciones. La mayoría de las clases que se derivan de ellas se explican por sí mismas, como por ejemplo: BinaryOperator (operador binario), FunctionDecl (declaración de función), etc ... [22] En el desarrollo de la herramienta implementada empleamos un objeto de la clase propia ToXMLVisitor que hereda de la clase RecursiveASTVisitor cuyo comportamiento está previamente de�nido dentro de las bibliotecas propias de CLANG. El recorrido que hace el RecursiveASTVisitor a lo largo del AST se realiza mediante llamadas a funciones Traverse. Estas funciones son especí�cas para cada clase que funciona como nodo del AST, aunque existen sus versiones genéricas: TraverseDecl() y TraverseStmt(). El comportamiento de ambas funciones es muy similar. En el caso de la función TraverseStmt, la instancia del RecursiceASTVisitor realiza llamadas recursivas a los nodos del AST mediante las funciones TraverseXXXStmt. Siendo XXX el nombre de la clase del nodo en cuestión. En cada llamada el RecursiceASTVisitor hace una comprobación del tipo del nodo y de si la función necesaria está declarada. En caso de no estar declarada explícita- mente en el código se prosigue con la búsqueda accediendo a los nodos más profundos. Para realizar un recorrido satisfactorio es necesario implementar en el código de la herramienta las distintas funciones Traverse de los nodos de in- terés. ésto es posible ya que las clases de las cuales los nodos son instancias particulares heredan de las super clases Decl y Stmt. Con nuestra herra- mienta transformamos cada nodo del AST en un nodo XML, manteniendo la semántica y la estructura del código. 19 2.3.1. Funciones En los �cheros de código que se espera que introduzcan los usuarios la estructura más grande a tener en cuenta es la declaración de funciones. El compilador se comporta de igual manera tanto si se trata de la declaración de una función a la que se va a invocar, como si es el caso del main del código. FunctionDecl La clase FunctionDecl se corresponde con la declaración de una función. Es un nodo del AST de CLANG que almacena información correspondiente a la situación en el código de ésta, el tipo devuelto, enlaces a sus parámetros y al cuerpo de la función. Este nodo se corresponde directamente en el XML devuelto por la herramienta con los nodos function. ParmVarDecl Un objeto ParmVarDecl almacena información referente a un parámetro necesario en la llamada de una función. Esta clase se corresponde con el nodo XML param, el cual contiene el tipo y el nombre del parámetro dentro de la función. Los nodos param sólo aparecen dentro de un nodo params. CompoundStmt Una noción que existe en el AST de CLANG es la del CompoundState- ment que representa a un bloque de código delimitado por llaves (...). Puesto que esperamos que el usuario haga uso de ellos sólo en compañia de otras estructuras (if, while, for o funciones), en el XML se representa con el nodo body. Un nodo body está compuesto por la serie de nodos correspondientes a las instrucciones que lo conforman. La disposición básica de un nodo function se puede observar en los si- guientes listados de código, 2.2 con el código C++ origen y 2.3 con el código XML con la disposición básica de un nodo function. Código 2.2: Código C++ ejemplo para un nodo function. 1 int foo(int a, int b, ...){ 2 ... 3 } 20 Código 2.3: Código XML obtenido ejemplo de la disposición básica de un nodo function 1 2 3 4 5 ... 6 7 8 ... 9 10 ReturnStmt La instrucción Return se traduce en nuestro formato a un nodod return el cual contiene su línea del código y un nodo interno que contiene la expresión que devuelve la función. La disposición básica de un nodo return se puede observar en los siguientes listados de código, 2.4 con el código C++ origen y 2.5 con el código XML con la disposición básica de un nodo return. Código 2.4: Código C++ ejemplo para un nodo return 1 return y + x; Código 2.5: Código XML obtenido ejemplo de la disposición básica de un nodo return 1 2 3 4 5 2.3.2. Declaraciones e inicializaciones C++ es un lenguaje fuertemente tipado, y requiere que cada variable esté declarada junto con su tipo antes de su primer uso. En un caso práctico, esto informa al compilador el tamaño reservar en memoria para la variable y la forma de interpretar su valor. Si se declaran varias variables del mismo tipo, se puede realizar en una sola instrucción. 21 DeclStmt Cuando se declara una variable, adquiere un valor indeterminado hasta que se le asigne alguno explícitamente. En C++ se contemplan tres maneras de inicializar el valor de una variable, aunque en nuestro proyecto, de cara a el uso de nuestra herramienta por parte de alumnos que están aprendiendo a programar, admitimos únicamente la forma más sencilla. Un nodo declarations contiene las declaraciones de las variables de un mis- mo tipo que han sido declaradas en la misma línea. Obtienen su información del nodo del AST de CLANG DeclStmt. VarDecl Los nodos declaration contienen información acerca del tipo de la variable, su nombre, la línea en la que se encuentra la declaración y la expresión cuyo valor se le va a asignar. La información surge de los nodos VarDecl que emplea el AST de CLANG. La disposición básica de un nodo declaration se puede observar en los siguientes listados de código, 2.6 con el código C++ origen y 2.7 con el código XML con la disposición básica de un nodo declaration. Código 2.6: Código C++ ejemplo para un nodo declaration 1 int w, q, l; 2 int j=0; Código 2.7: Código XML obtenido ejemplo de la disposición básica de un nodo declaration 1 2 3 4 5 6 7 8 9 10 22 2.3.3. Estructuras de control Las instrucciones que producen rami�caciones en la ejecución de un pro- grama, tales como: el if, el while o el for. Para poder realizar su ejecución correctamente mantenemos en sus respectivos nodos sus señas más caracte- rísticas. IfStmt El nodo XML if obtiene su información a partir del nodo del AST de CLANG IfStmt. Almacena el número de línea, y los nodos correspondientes a la condición que dirige su ejecución, al cuerpo del then y al cuerpo del else (en caso de estar especi�cado en el código). La disposición básica de un nodo If se puede observar en los siguientes listados de código, 2.8 con el código C++ origen y 2.9 con el código XML con la disposición básica de un nodo If. Código 2.8: Código C++ ejemplo para un nodo If 1 if(y>0){ 2 ... 3 } else{ 4 ... 5 } Código 2.9: Código XML obtenido ejemplo de la disposición básica de un nodo If 1 2 3 4 5 6 7 8 ... 9 10 11 12 13 ... 14 15 16 23 WhileStmt La instrucción while se traduce a un nodo que alberga como atributo el número de línea donde comienza la instrucción, y los nodos de la expresión de su condición y el bloque de instrucciones de su cuerpo. Toda esta información es una fracción de la que contiene el nodo del AST de clang WhileStmt. La disposición básica de un nodo While se puede observar en los siguientes listados de código, 2.10 con el código C++ origen y 2.11 con el código XML con la disposición básica de un nodo While. Código 2.10: Código C++ ejemplo para un nodo While 1 while(w>0){ 2 ... 3 } Código 2.11: Código XML obtenido ejemplo de la disposición básica de un nodo While 1 2 3 4 5 6 7 ... 8 9 ForStmt El bucle For se representa en el �chero XML con un nodo for. Este nodo obtiene su información a partir del nodo del AST de clang ForStmt. La información que contiene re�ere al número de línea en el que comienza, y a los nodos de la declaración de su variable de control, la condición de parada, la instrucción de avance y el cuerpo del bucle. Es importante recalcar que para el uso correcto de la herramienta, más especí�camente para el uso del intérprete simbólico, el bucle for introducido por el usuario en el código fuente debe contener dichas partes de forma explícita. La disposición básica de un nodo For se puede observar en los siguientes listados de código, 2.12 con el código C++ origen y 2.13 con el código XML con la disposición básica de un nodo For. 24 Código 2.12: Código C++ ejemplo para un nodo For 1 for (int i=0; i 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 ... 19 20 2.3.4. Expresiones Las expresiones escritas en C++ se traducen a nuestro formato en XML en nodos descritos por sus operadores, la variable a la que hacen referencia o la constante que representan. En caso de que estos nodos hagan referencia a un operador, contienen información acerca del tipo de este (binario, unario, asignación, etc ...) y de las expresiones que contienen. Las expresiones que se re�eren a variables almacenan el nombre de estas y deforma equivalente las que representan constantes guardan su valor. Un caso particular de expresión sería el de las llamadas a funciones. 25 ParenExpr La clase ParenExpr representa una expresión rodeada por paréntesis por ejemplo �(1)�. Esta estructura no es muy relevante en nuestra herramienta porque en el paso del análisis en el que CLANG construye el AST, ya tiene en cuenta la prioridad de los operandos. Esto convierte a la clase ParenExpr en una utilidad auxiliar que sin duda puede resultar útil en caso de querer modi�car o añadir nuevos elementos al AST en otro tipo de análisis con otra herramienta. BinaryOperator La clase BinaryOperator engloba los diversos operadores binarios de C++. Abarca las operaciones con punteros, la asignación, distintas operaciones nu- méricas, booleanas, de comparación e incluso a nivel de bit. CLANG se re�ere a los distintos operadores mediante un tipo enumerado denominado OpCo- de, pero en nuestra herramienta optamos por hacer una distinción entre la asignación y los demás operadores. De esta forma una asignación se vería traducidad a un nodo XML assignment que contiene el nombre de la varia- ble que recibe el valor, su ubicación en el código y un nodo interno para la expresión de dicho valor. De esta forma no se contempla que haya una asig- nación dentro de otra. Asimismo cualquier otra expresión aparece como un nodo binaryOperator que aparte de conservar el tipo y el operador, contiene los dos nodos internos que re�eren a las expresiones que hacen a su vez el papel de sus dos operandos. Esta distinción se hace con los estudiantes no- veles de programación en mente con la �nalidad de que, en caso de estudiar detenidamente el XML �nal de su código, tengan una visión más clara de su funcionamiento. La disposición básica de un nodo con operador binario se puede observar en los siguientes listados de código, 2.14 con el código C++ origen y 2.15 con el código XML con la disposición básica de un nodo para un operador binario. Código 2.14: Código C++ ejemplo para un nodo de un operador binario 1 a = b + c; 26 Código 2.15: Código XML obtenido ejemplo de la disposición básica de un nodo con operador binario 1 2 3 4 5 6 CompoundAssignOperator CLANG hace distinción entre los operadores binarios corrientes, y los que a su vez almacenan el valor resultante de la operación en una de las variables involucradas. Operaciones de este este tipo se resuelven mediante procesos de bajo nivel distintos a los de BinaryOperator por lo que para ello la clase CompoundAssignOperator resulta bastante útil. Un nodo Com- poundAssignOperator se traduce a un nodo assignmentoperator en el �chero XML devuelto. En este nodo damos cuenta del nombre de la variable de la que participa en la operación y posteriormente recoge el valor, el tipo de la operación, la ubicación en el código y un nodo anidado que correspondería a la expresión que pudiera aparecer en el código correspondiendo al segundo operando. La disposición básica de un nodo con operador de asignación se puede observar en los siguientes listados de código, 2.16 con el código C++ origen y 2.17 con el código XML con la disposición básica de un nodo para un operador de asignación. Código 2.16: Código C++ ejemplo para un nodo de un operador de asigna- ción 1 a *= b; Código 2.17: Código XML obtenido ejemplo de la disposición básica de un nodo con operador de asignación 1 2 3 27 UnaryOperator En C++ existen numerosos operadores unarios pero, considerando los conocimientos que hacen falta en etapas tempranas de la iniciación a la pro- gramación, nos hemos centrado en dar soporte a los operadores unarios de incremento, decremento, indicador de signo y el not lógico. Distinguimos los operadores de incremento y decremento se presentan a los programadores en un principio como parte esencial de los bucles cumpliendo la función de instrucción de avance. Estos operadores se traducen a un nodo unaryOpera- tor que indica el tipo de la operación: �+� en caso de incremento, �� en caso contrario. Por otro lado el indicador de signo cumple un papel importante a la hora de operar con valores negativos y de ayuda explícita al programador junior en caso de que quiera asegurar el valor de su variable. El nodo XML corres- pondiente es el nodo signOperator, que indica si es positivo o negativo y que contiene un subnodo correspondiente a la expresión cuyo signo se modi�ca. El not lógico no aporta más expresividad pero permite simpli�car progra- mación de expresiones booleanas. Este operador aparece en el formato XML como un nodo signOperator. Este nodo contiene el nodo de la expresión cuyo valor booleano invierte. ImplicitCastExpr Esta clase nos permite representar explícitamente las conversiones de tipo (castings) que no tienen representación en el código original. Un ejemplo en la práctica sería a la hora de determinar el tipo de una variable de la cual solo sabemos el indenti�cador de forma que case con el tipo de la operación a la que va a ser sometida. En el lenguaje C, los conversiones implícitas de tipo siempre producen valores temporales que van asociados al lado derecho de una expresión (rvalues), por ejemplo: �x = y�, la variable y es un rvalue. Aún así, en C++ una conversión implícita puede estar asociada a valores que pueden ir a la izquierda de una expresión (lvalues), por ejemplo: �x = 7�, x es un lvalue. DeclRefExprClass La clase DeclRefExprClass se corresponde con una referencia a una va- riable, función, valor de tipo enumerado, etc. que haya sido declarado con anterioridad. Un objeto de esta clase almacena numerosos detalles de como una declaración se referencia dentro de una expresión. En nuestro proyecto este nodo nos permite conocer el identi�cador de una variable cualquiera 28 que participe en una expresión. La correspondencia con el �chero XML tiene forma de nodo variable. La disposición básica de un nodo con una asignación a otra variable se puede observar en los siguientes listados de código, 2.18 con el código C++ origen y 2.19 con el código XML con la disposición básica de un nodo con una asignación a otra variable. Código 2.18: Código C++ ejemplo para un nodo con una asignación a otra variable 1 w = y; Código 2.19: Código XML obtenido ejemplo de la disposición básica de un nodo con una asignación a otra variable 1 2 3 IntegerLiteral Un nodo IntegerLiteral es utilizado por el compilador para determinar el valor y el tipo asociado al tamaño que ocupa en memoria un valor entero que aparece explícitamente en el código. En el formato XML correspondiente al código fuente que acepta nuestra herramienta se traduce en un nodo const en el que se almacena el valor de dicha constante. La disposición básica de un nodo con una asignación a un valor se puede observar en los siguientes listados de código, 2.20 con el código C++ origen y 2.21 con el código XML con la disposición básica de un nodo con una asignación a un valor. Código 2.20: Código C++ ejemplo para un nodo con una asignación a un valor 1 r = 1; Código 2.21: Código XML obtenido ejemplo de la disposición básica de un nodo con una asignación a un valor 1 2 3 29 StringLiteral La clase StringLiteral sirve para representar cualquier expresion de ti- po string (cadenas de caracteres). Es una clase muy versátil pues otorga al programador distintas utilidades para manipular strings a distintos niveles. En nuestra herramienta la presencia de strings de�nidos por el usuario está limitada a la salida por consola. Un string se traduce a un nodo string cuyo valor almacena la cadena de caracteres correspondiente La disposición básica de un nodo con un valor string se puede observar en los siguientes listados de código, 2.22 con el código C++ origen y 2.23 con el código XML con la disposición básica de un nodo con un valor string. Código 2.22: Código C++ ejemplo para un nodo con uun valor string 1 "Hola mundo" Código 2.23: Código XML obtenido ejemplo de la disposición básica de un nodo con un valor string 1 CallExpr La clase CallExpr representa la llamada a una función. En C++ las lla- madas a funciones son consideradas expresiones que devuelven un valor del tipo asociado a dicha función. Una llamada a función se traduce a un nodo callFunction que re�ere al nombre de la función y contiene varios nodos arg con las expresiones que el programador haya determinado. La disposición básica de un nodo con con la llamada a una función se puede observar en los siguientes listados de código, 2.24 con el código C++ origen y 2.25 con el código XML con la disposición básica de un nodo con con la llamada a una función. Código 2.24: Código C++ ejemplo para un nodo con la llamada a una función 1 a = foo(b); 30 Código 2.25: Código XML obtenido ejemplo de la disposición básica de un nodo con la llamada a una función 1 2 3 4 5 6 7 2.3.5. Interacción de entrada y salida En el diseño de nuestra herramienta damos mucha importancia a la uti- lidad que pueda suponer para el usuario �nal: un programador novel. Es por ello que para que una vez hecho el análisis simbólico, en caso de que el usua- rio quisiera reconstruir el �ujo de ejecución del programa, una utilidad que simule el comportamiento interactivo de una consola puede convertirse en una buena herramienta de depuración. A lo largo de la existencia de C y sus posteriores revisiones han idos surgiendo numerosas bibliotecas que se encargan de encapsular la entrada y salida para agilizar la tarea del programador. Entre estas bibliotecas destacan la biblioteca estándar de C++ y la biblioteca estándar de C. La biblioteca estándar de C (libc) [23] es una recopilación de �cheros cabe- cera y bibliotecas con rutinas, estandarizados por un comité de la Organiza- ción Internacional para la Estandarización (ISO). Estas rutinas implementan las operaciones comunes del lenguaje de forma que todos los programas im- plementados en C se basan en ella para funcionar. Dentro de los �cheros cabecera de la biblioteca el �chero stdio.h contiene las de�niciones necesarias para las operaciones de entrada y salida. La biblioteca estándar de C++ (Standard Template Lybrary, STL) [24] incluye una colección de funciones y clases de�nidas en el núcleo del lenguaje y está ideada para dar soporte a la mayoría de funcionalidades del lenguaje. Iostream (acrónimo de Input/Output Stream) es el componente responsable del control de �ujo de entrada y salida y re�ere a un conjunto de plantillas de clases que manejan las capacidades de entrada y salida de C++ por medio de �ujos (streams). Todos los objetos derivados de iostream son parte del espacio de nombres (namespace) std. Para simpli�car el acceso a las operaciones de entrada y salida teniendo en cuenta su necesaria adaptación a un formato XML y su posterior proce- sado por el intérprete simbólico hemos de�nido dos sencillas bibliotecas que 31 eliminan las diferencias entre las dos bibliotecas más generalizadas de la pro- gramación en C++ aportando la funcionalidad básica que pueda necesitar el usuario: introducción y emisión de valores enteros o strings. Las bibliotecas implementadas son BuiltinsSTD.h y BuiltinsIO.h basadas en la entrada y salida de la biblioteca estándar de C++ y C respectivamente. ConsoleIn_Int ConsoleOut_Int ConsoleOut_String 2.4. Tecnología adicional Como se ha explicado previamente en nuestra herramienta un factor clave es la producción de un �chero XML equivalente al código introducido con la �nalidad de realizar la ejecución simbólica a partir de él. Desde un principio se descartó la posibilidad de implementar una herramienta por nuestra cuenta con las capacidades requeridas, como opción �nal nos decidimos por emplear alguna de ya existente cuya utilización nos estuviera permitida, optamos por la librería TinyXML2. TinyXML2 TinyXML2 es una librería de software libre creada para la manipulación de �cheros XML. TinyXML2 está sujeta a los términos de la licencia zlib de distribución de software. Elegimos TinyXML2 como una opción viable ya que como indica su nom- bre es una herramienta de tamaño reducido y de características ajustadas a la e�ciencia que buscábamos. En el proceso de generar el �chero XML esta librería nos ofreció directivas bastante sencillas, así como una manipulación directa y ágil de los nodos XML. [25] A grandes razgos la generación del �chero que devuelve AST2XML co- mienza con la creación de un �documento en blanco� y la generación de un puntero auxiliar. El documento guarda la funcionalidad relativa a la genera- ción de nuevas estructuras XML y es el que �nalmente gestiona el volcado de información al �chero resultante. El puntero auxiliar se utiliza como almace- namiento temporal de los nodos XML una vez estos ya han sido �nalizados. 32 2.5. Uso de AST2XML Una vez compilado la herramienta, se puede ejecutar esta mediante el comando que hay en el código 2.26: Código 2.26: Uso de AST2XML. 1 /ast2xml "inputCPP_file" -- "outputXML_file" El primer y el tercer parámetro que se emplean en la llamada representan al �chero de código del que se quiere obtener una representación en XML y el �chero resultante. El segundo parámetro es una directiva de la ejecución propia de herra- mientas de LLVM que indica la inexistencia de una base de datos de compi- lación que podría ser necesaria al hacer ejecutar otra herramienta. [26] 33 Capítulo 3 Intérprete con restricciones En este capítulo hablaremos sobre la parte principal de nuestro proyecto, el Intérprete Simbólico, que recibe el árbol sintáctico generado por la herra- mienta AST2XML, y realiza una ejecución simbólica de éste devolviendo un conjunto de posibles valores de entrada con los correspondientes valores de salida generados. 3.1. El lenguaje Prolog y la librería clpfd La Programación Lógica tiene sus orígenes más cercanos en los traba- jos de prueba automática de teoremas de los años sesenta. J. A. Robinson propone en 1965 una regla de inferencia a la que llama resolución, mediante la cual la demostración de un teorema puede ser llevada a cabo de manera automática. La resolución es una regla que se aplica sobre cierto tipo de fór- mulas del Cálculo de Predicados de Primer Orden, llamadas cláusulas y la demostración de teoremas bajo esta regla de inferencia se lleva a cabo por reducción al absurdo. La realización del paradigma de la programación lógica es el lenguaje Prolog. Prolog es un lenguaje de programación ideado a principios de los años 70 en la Universidad de Aix-Marseille I (Marsella, Francia). No tiene como objetivo la traducción de un lenguaje de programación, sino la clasi�cación algorítmica de lenguajes naturales. [27] La idea es especi�car formalmente los enunciados utilizando la lógica de predicados de manera que Prolog sea capaz de interpretar e inferir soluciones a partir de esos enunciados. La lógica de predicados estudia las frases declarativas teniendo en cuenta la estructura interna de las proposiciones, es decir, un conjunto de cláusulas de la forma: �q :- p�, en la que si p es cierto entonces q es cierto. Una cláusula 34 puede ser un conjunto de hechos positivos, por ejemplo de la forma �q :- p, r, s.� ; una implicación con un único consecuente, �q :- p� ; un hecho positivo, �p.� ; instrucciones con parámetros de Entrada/Salida �p(Entrada,Salida).� ; o incluso llamadas a otras funciones. En Prolog, los predicados se contrastan en orden, la ejecución se basa en dos conceptos: la uni�cación y el backtracking. Una vez ejecutamos una función de Prolog se sigue ejecutando el programa gracias a las llamadas a predicados, si procede, hasta determinar si el objetivo es verdadero o falso. Todos los objetivos terminan su ejecución en éxito (�verdadero�), o en fracaso (�falso�). Si el resultado es falso entra en juego el backtracking, es decir, deshace todo lo ejecutado situando el programa en el mismo estado en el que estaba justo antes de llegar al punto de elección, ahí se toma el siguiente punto de elección que estaba pendiente y se repite de nuevo el proceso, de ahí la utilidad de prolog en nuestro proyecto ya que nos permite implementar un intérprete de ejecución simbólica de forma natural y prácticamente nativa. La Programación por restricciones es un paradigma de la programación en informática donde las variables están relacionadas mediante restricciones (ecuaciones). Se emplea en la descripción y resolución de problemas combina- torios, especialmente en las áreas de plani�cación y programación de tareas (calendarización). La programación con restricciones se basa principalmente en buscar un estado en el cual una gran cantidad de restricciones sean sa- tisfechas simultáneamente, expresándose un problema como un conjunto de restricciones iniciales a partir de las cuales el sistema construye las relaciones que expresan una solución. Como ya se introdujo en el estado del arte, la programación con restric- ciones proporciona una herramienta en la que las variables están expresadas en términos de restricciones o ecuaciones. Para el desarrollo de esta herra- mienta hemos necesitado hacer uso de este paradigma de programación, el cual nos facilitaba mostrar restricciones como datos de salida. La librería clpfd �Constraint Logic Programming over Finite Domains� (Programación lógica basada en restricciones sobre dominios �nitos) propor- ciona una aritmética completa para variables restringidas a valores enteros o elementos atómicos, se puede utilizar para modelar y resolver diversos pro- blemas combinatorios tales como las tareas de plani�cación, programación y asignación. [28] Para el desarrollo de nuestro intérprete, como ya indicamos anteriormente, optamos por el lenguaje de programación lógica Prolog, en gran parte debido a la familiaridad que nos supone, y al conjunto de facilidades relacionadas con el backtracking y la programación por restricciones que ya conocíamos de antemano. 35 3.2. Diseño e interfaz del intérprete Como ya hemos indicado antes, AST2XML devuelve un archivo en forma- to XML con una versión simpli�cada del árbol sintáctico que emplea Clang con el que realizaremos la ejecución simbólica. Para llevar a cabo una ejecu- ción simbólica es necesario tener un sistema capaz de establecer restricciones lógicas y matemáticas y que aparte las pueda resolver. El intérprete está dividido en módulos encapsulando los distintos aspectos del diseño: Frontend.pl, Body y Functions . Frontend.pl Por otro lado, este módulo representa el Intérprete que será llamado por la interfaz y el que devolverá la solución. Los parámetros de entrada son: �chero de entrada, �chero de salida, Inf, Sup, MaxDepth y nombre de función. Fichero de entrada Indica el nombre del �chero .xml donde está el código traducido por clang. Código 3.1: Ejemplo de XML de entrada que recibe el intérprete 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Fichero de salida Indica el nombre del �chero .xml de salida que el intérprete devolverá con las soluciones para una determinada función. 36 Código 3.2: Ejemplo de XML obtenido por Clang 1 2 3 4 5 76 77 83 6 7 8 9 Inf, Sup y MaxLoop Inf y Sup son los valores que representan el límite del dominio de los valores de entrada de la función a interpretar. MaxLoop representa el valor del número máximo de veces que puede ejecutarse una estructura de control: while y for. Nombre de la función Para indicar el nombre de la función que vamos a querer probar entre todas las funciones posibles contenidas en el �chero pasado en �Fichero de entrada�. Body Contiene los módulos auxiliares InterpreterAuxiliar.pl, Executers.pl y Ex- pressions.pl. InterpreterAuxiliar.pl Contiene el predicado que especí�camente realiza la ejecución simbólica de la función indicada por el usuario a través de frontend.pl. Executers.pl Contiene todos los predicados execute que se encargan de simular la ejecución de cada instrucción del programa. 37 Expressions.pl Contiene todos los predicados resolveExpression que se encargan de calcular el valor resultante de cada expresión del programa. Functions Contiene los módulos auxiliares:VariablesTable.pl yAuxiliaryFunctions.pl. VariablesTable.pl El intérprete irá guardando las variables y su respectivo valor en una tabla de variables representado en prolog mediante una lista, de forma que todas las posibles operaciones que se puedan aplicar sobre ella estén encapsuladas en un mismo módulo. Por ejemplo, funciones como añadir un elemento a la tabla (add), obtener el valor de una variable (getValue), modi�car el nombre de una variable (updateNames), etc. son funciones que sólo se aplican sobre la tabla de variables. AuxiliaryFunctions.pl En esta librería están presentes las distintas funciones auxiliares que ayu- dan a hacer más comprensible el código de las librerías Expressions y Exe- cuters. Destaca la implementación del estado en el que se apoyan dichas librerías. 3.3. Ciclo de ejecución Como forma explicativa del ciclo de ejecución que sigue el intérprete pon- dremos el siguiente ejemplo en el de devolvemos el resultado obtenido por los dos parámetros de entrada: Código 3.3: Ejemplo ilustrativo con función suma 1 int foo(int a, int b){ 2 int c = a + b; 3 return c; 4 } 38 Como ya sabemos, el intérprete recibirá un �chero XML como parámetro de entrada, junto con otros parámetros que explicaremos más adelante. El código de nuestro ejemplo tendrá el siguiente aspecto una vez pasado por AST2XML: Código 3.4: árbol sintáctico de la función suma 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 El primer paso es la conversión de la estructura XML en una lista de elementos mediante la función load_xml_�le(+File,-DOM) que nos aporta la librería SGML [29]. Para nuestro ejemplo, le pasaremos por el parámetro File el XML con el código anterior y nos devolverá en el parámetro de salida DOM una lista de elementos de la forma: Código 3.5: Elementos correspondientes a la función suma 1 [element(function ,[name=foo ,type=int ,line =3],[ 2 element(params ,[],[ 3 element(param ,[type=int ,name=a],[]), 4 element(param ,[type=int ,name=b],[]) 5 ]) 6 element(body ,[],[ 7 element(declarations ,[],[ 8 element(declaration ,[type=int ,name=c,line =4],[ 9 element(binaryOperator ,[type=arithmetic , operator =(+)],[ 10 element(variable ,[name=a],[]), 11 element(variable ,[name=b],[]), 39 12 ]) 13 ]) 14 ]) 15 element(return ,[line =6],[ 16 element(variable ,[name=c],[]) 17 ]) 18 ]) 19 ])] Cada element tiene tres argumentos: el nombre del nodo (nombreNodo), los atributos del nodo (atributosNodo) y el cuerpo del nodo (cuerpoNodo). // cuerpoNodo Otro parámetro que recibe el intérprete es el nombre de la función que queremos probar, tenemos que indicarlo puesto que en un mismo XML po- dremos tener más de una función. De esta forma buscaremos previamente la función que el usuario nos haya indicado e iremos pasando por cada una de las instrucciones del código de dicha función y ejecutándolas mediante las sucesivas llamadas a la función execute que se detallará más adelante. El resto de parámetros que el intérprete recibirá son: Out�le: para indicar el nombre del archivo en el que se guardará el re- sultado de la ejecución, tanto las posibles entradas como sus respectivas salidas generadas. Inf, Sup: parámetros que nos servirá para delimitar el valor posible de las salidas. MaxDepth: para poner un número máximo de vueltas que puede llegar a hacer un bucle si la condición sigue siendo cierta en el momento en el que se alcanza dicho valor. execute Es un predicado encargado de ejecutar una instrucción. Sus argumentos son: el estado previo a la ejecución de unas instrucciones, la lista que contiene las instrucciones, el estado posterior a la ejecución, y una señal indicativa de si se ha producido retorno (tanto de entrada como de salida). Este predicado se planteó de forma que pudiéramos controlar cada una de las posibles ins- trucciones que puede llegar a haber en el código. Para conseguirlo en cada 40 una de estas posibilidades expresamos explícitamente los casos de forma que la instrucción que se ejecuta en un momento dado es el primer elemento de la lista de instrucciones que recibe la función. Una vez se hayan completado los pasos que simulan el comportamiento de dicha instrucción, se hace una �llamada� recursiva a execute con el estado resultante de la ejecución, el resto de la lista de instrucciones y el estado posterior. Esta forma de realizar los pasos de cómputo se asemeja, en un aspecto más teórico, a la semántica de paso corto (semántica operacional), aunque dicha similitud no es completa puesto que al trabajar con instrucciones puntuales llevamos a cabo muchos pasos intermedios. Es importante destacar que el bactracking inherente de prolog se restrin- ge en el predicado execute. Esto se debe a que el orden de las instrucciones es siempre el mismo. En el intérprete hemos limitado el backtracking a la evaluación de condiciones puesto que éstas son las que realmente de�nen el �ujo del programa. Es por ello que, en las instrucciones de control, llegamos a necesitar la presencia de otros predicados que, además de dirigir el com- portamiento de la ejecución, permiten limitar el número de repeticiones que realiza un bucle. Iremos almacenando en cada paso el estado actual donde nos encontramos con la siguiente información: Table. Llevamos la tabla de variables correspondientes al estado en el que nos encontramos. En esta tabla contemplamos la posiblidad de estructu- rarla en ámbitos de forma que el acceso a las variables sea consistente en cada momento. Cin, Cout Listas con los valores de entrada (Cin) o salida (Cout) si procede. Trace Lista que conserva el número de las líneas de las instrucciones por las que hemos pasado para poder más tarde marcarlas en la interfaz. 41 3.4. Funciones, declaración y asignación de va- riables. De�nición de una función Una función se de�ne siguiendo el siguiente esquema: () [sentencias] Código 3.6: Instrucción para la de�nición de una función execute(Entrada ,[('function '... CuerpoFuncion)| RestoInstrucciones],Salida Ya sea el caso de la función principal o una llamada a una función esta instrucción se encargará de ejecutar el cuerpo de la función y después el resto de las instrucciones. Diferenciamos también si se trata de una función o procedimiento ya que en el caso de las funciones tiene que existir un valor de retorno, al contrario que los procedimientos. Como vemos en el esquema anterior, la función puede llegar a contener parámetros de entrada que leeremos mediante la instrucción: Código 3.7: Intrucción que recibe los parámetros de entrada execute(Entrada ,[('params '... Parametros)|RestoInstrucciones ],Salida Con esta instrucción insertaremos en la tabla de variables cada uno de los parámetros que formen parte de la variable Parametros. Una vez actualizada la tabla llamaremos a ejecutar al resto de las instrucciones para continuar con el programa. Un bloque es un mero conjunto de sentencias, que puede estar vacío, o encerradas por llaves , ese conjunto lo recogemos con la instrucción corres- pondiente: Código 3.8: Intrucción para el cuerpo de un bloque execute(Entrada ,[('body'... Body)|RestoInstrucciones],Salida ) Este es el caso en el que ejecutamos cualquier tipo de bloque, ya sea el cuerpo de una función, if, for, while, etc. Llamamos a ejecutar al cuerpo de 42 forma que creamos a su vez una nueva lista de variables para englobar las variables pertenecientes a ese ámbito. Para resolver el caso de una llamada a función el intérprete hará uso del precicado callFunction, que buscará la función a la que se está referenciando y la ejecutaremos de forma que consigamos el valor devuelto por la función como resultado de la expresión. [tipo] = () ; El tipo: [tipo] será vacío en el caso en el que la variable ya hubiese sido declarada con anterioridad. Declaración de una variable A la hora de declarar una variable primero se especi�ca el tipo y a luego una lista de variables seguidas de un punto: ; La lista de variables tiene que estar formada como mínimo por una varia- ble. Nunca podrá ser una lista vacía. El tipo será siempre int ya que es el tipo de variable que contempla nuestra herramienta. Ya que se pueden declarar una o varias variables en la misma instrucción, diferenciamos la posibilidad de guardar en la tabla de variables una sola variable: Código 3.9: Instrucción para la declaracion de una variable execute(Entrada ,[('declaration '... Nombre ... CuerpoDeclaracion)|RestoInstrucciones],Salida) y la posibilidad de guardar en la tabla de variables varias declaraciones a la vez: Código 3.10: Intrucción para las declaraciones de varias variables en grupo execute(Entrada ,[('declarations '... Body)|RestoInstrucciones ],Salida) En este último caso, internamente, se llamará a la función encargada de guardar una a una las variables con sus tipos asignados pero sin valor ya que se trata únicamente de una declaración y no de una asignación. A continuación se seguirá con la ejecución del resto de las instrucciones 43 Asignación de una variable Las sentencias de asignación responden al siguiente esquema: ; éste es el momento en el que se le da valor a una variable anteriormen- te declarada y por tanto ya añadida anteriormente a la tabla de variables. Ejecutaremos el cuerpo de la asignación para obtener el valor que tomará la variable y luego la actualizaremos. Las asignaciones pueden expresarse de dos formas distintas dependiendo de la forma en que se ponga el operador de asignación. En el caso en el que el operador de asignación sea de la forma: = ; la asignación se realizará de forma que se resuelve la expresión y luego se le asigna el valor resultante a la variable. En el caso en el que el operador de asignación sea de la forma: op= ; siendo op = +,-,*,/ éste es un caso especial en el que la asignación en este caso no es otra cosa que hacer: = op ; Se sigue la ejecución con la llamada de execute del resto de las instruc- ciones. 3.5. Instrucciones aritméticas y condicionales. Este apartado explica los predicados que se utilizarán a la hora de resolver expresiones aritméticas y sentencia de selección if / if...else. resolveExpression Este predicado servirá para resolver las distintas expresiones que existan. La estructura de llamada de este predicado es la que sigue: 44 Código 3.11: Instrucción para la resolución de las expresiones resolveExpression(Entrada ,CuerpoExpresion ,ValorRetorno , Salida), Entrada y Salida corresponden a la tabla de variables que entra y la tabla de variables actualizada después de haberse resuelto la expresión. CuerpoEx- presion es la expresión concreta que queremos resolver y ValorRetorno el valor resultante devuelto. En este apartado nos centraremos únicamente en las expresiones aritméticas Operadores aritméticos Los operadores se pueden clasi�car atendiendo al número de operandos que afectan. Según esta clasi�cación tenemos tres tipos de operadores, pueden ser unitarios, binarios o ternarios. Los primeros afectan a un solo operando, los segundos a dos y los ternarios a tres. Operadores unitarios Código 3.12: Operador unario execute(Entrada ,[('unaryOperator '... Operando ,Operador)| RestoInstrucciones],Salida) Los tipos unarios que reconoce la herramienta siguen la estructura: + Para asignar valores positivos o negativos � a los valores a los que se aplica. ++ Para incrementar o decrementar el valor � � de la variable, ambos en una unidad. Actualizamos el valor de la variable en la tabla de variables y continuamos con la ejecución del resto de las instrucciones. Operadores binarios Los operadores de tipo binario siguen el esquema: op ; siendo op los operadores: +,-,*,/ En este caso se resolverá cada expresión de forma independiente mediante la llamada recursiva: 45 Código 3.13: Instrucciones para la resolución de expresiones con operadores binarios resolveExpression(Entrada1 , Operando1 , Resultado1 , Salida1) resolveExpression(Entrada2 , Operando2 , Resultado2 , Salida2) Combinará los dos resultados únicamente cuando éstos son expresiones sencillas de forma que ya hayan llegado al caso base, que se cumple cuando se tiene que la expresión es una variable o una constante de forma que ya no se pueda más que operar mediante el predicado work detallado más adelante. Operadores lógicos Nos servirán a la hora de de�nir la condición de una instrucción de control de �ujo. Los operadores lógicos de negación siguen el esquema: ! De forma que negará el valor resultante de la expresión. Existen también otros tipos de operadores lógicos que siguen el esquema: op Siendo op los valores && o || ambos se resuelven en el predicado work detallado a continuación. Código 3.14: Asignación de una variable execute(Entrada ,[('assignmentOperator '... Name ... Operator ... Cuerpo)|RestoInstrucciones],Salida) Este es un caso especial de la asignación ya que se trata de una asignación mediante un operador binario. Esta ejecución la haremos con la llamada a resolveExpression (explicada más adelante) del cuerpo de la asignación. Co- mo en el resto de los casos pasamos a continuación a ejecutar el resto de las instrucciones para seguir con el �ujo del programa. 46 work Código 3.15: Instrucción para la ejecución de expresiones work(Operador , Resultado1 , Resultado2 ,ResultadoFinal), Cuya funcionalidad es únicamente la ejecución de la expresión expresión1 Operador expresión2 dejando la solución en ResultadoFinal. En nuestro proyecto �Operador� únicamente podrá ser: < <= > >= == != && || + - * / Tabla 3.1: Tabla con los operadores que reconoce el interprete. Instruc