realizar una ejecución simbólica del programa (ver por ejemplo [29]), donde los contenidos de las variables son expresiones en lugar de valores concretos. La ejecución simbólica produce finalmente un sistema de restricciones, las cuales definen las condiciones bajo las que se ejecutan los distintos caminos. Esto ocurre por ejemplo, en las instrucciones condicionales, como en los “if-then-else”, donde se suele requerir generar casos de prueba para las dos alternativas, y por tanto se han de acumular las condiciones de cada camino como restricciones. Para el caso de Java Bytecode, en [73] se diseñó una JVM simbólica (SJVM), la cual integraba varios resolutores de restricciones. La SJVM requiere una serie de extensiones no triviales respecto a la JVM: (1) necesita que el bytecode sea ejecutado simbólicamente como explicamos anteriormente, y (2) debe ser capaz de realizar “backtracking”, pues al no conocerse los datos de entrada, el motor de ejecución debe considerar todas las alternativas. El mecanismo de “backtracking” utilizado en [73] es de hecho esencialmente el mismo al uti-lizado en la programación lógica. Esta tesis propone un esquema novedoso de TDG de bytecode basado en técnicas de EP en CLP, el cual, a diferencia de trabajos previos, no requiere el desarrollo de una máquina simbólica virtual. La Figura 3.1 muestra un diagrama con el esquema general. Como podemos ver, el enfoque se basa en dos fases independientes de EP en CLP, que consisten básicamente en lo siguiente: 1. Decompilación del bytecode en un programa CLP. Ya hemos explica-do en el Caṕıtulo 2 que la decompilación de bytecode a LP se puede obtener automáticamente por medio de la EP de LP, o alternativa-mente utilizando un decompilador dedicado [70]. Las modificaciones en el esquema para obtener programas CLP en lugar de programas LP son prácticamente triviales. Esto se puede conseguir básicamente transformando los “builtins” aritméticos del intérprete por los corres-pondientes “builtins” CLP de la libreŕıa correspondiente. 2. Generación de casos de prueba. Ésta es una aplicación novedosa de la EP que nos permite generar generadores de casos de prueba a partir de los programas CLP decompilados. En este caso, utilizaremos un evaluador parcial CLP capaz de propagar restricciones de la misma manera que haŕıa una máquina simbólica. Los operadores de control de la EP juegan un papel esencial: (1) El control local permite cap-turar fácilmente diferentes criterios de recubrimiento. (2) El control global permite la generación de generadores de casos de prueba. Intui-tivamente, éstos son programas CLP cuya ejecución en CLP devuelve más casos de prueba bajo demanda, sin la necesidad de empezar el proceso de TDG de nuevo. Esta tesis sostiene que este enfoque de TDG de bytecode tiene varias ventajas importantes respecto a enfoques previos basados de alguna u otra manera en ejecución simbólica. Éstas incluyen: (i) Es más genérico, pues la mismas técnicas se pueden aplicar para otros lenguajes (imperativos) de entrada. En particular, una vez se la realizado la decompilación a CLP, las caracteŕısticas del lenguaje las caracteŕısticas del lenguaje quedan abs-tráıdas, siendo por tanto la fase de generación de datos de prueba total-mente independiente del lenguaje. Esto evita tener que tratar con aspectos como la recursión, las llamadas a procedimientos, la memoria dinámica, etc. (ii) Es más flexible pues es muy fácil incorporar diferentes criterios de recubrimiento simplemente proporcionando las correspondientes reglas de control local a la EP. (iii) Es más potente gracias a la caracteŕıstica de poder generar generadores de casos de prueba. (iv) Es más simple de implementar pues no requiere el desarrollo de ninguna máquina simbólica, asumiendo claro que se dispone de una evaluador parcial. Como se acaba de mencionar en la ventaja (iv), una de las ventajas de los programas decompilados CLP respecto a sus versiones bytecode es que se puede realizar una ejecución simbólica de éstos sin necesidad de escribir un mecanismo espećıfico de ejecución simbólica. Simplemente po-demos ejecutar el programa decompilado usando el mecanismo de ejecución estándar de CLP, poniendo variables en todos los argumentos del corres-pondiente predicado. Por ejemplo, para nuestro ejemplo motivador de la Figura 2.4, podŕıamos ejecutar simbólicamente el método gcd lanzando el objetivo main(gcd, [X, Y], Z) sobre el programa decompilado. Los resultados obtenidos (restricciones sobre las variables) se pueden interpretar como las condiciones que han de cumplir las variables de entrada (en este caso X e Y ) para seguir el camino de ejecución correspondiente. La solución de dichas restricciones nos daŕıa por tanto datos de entrada concretos. Sin embargo, un problema importante de la ejecución simbólica, inde-pendientemente de si se realiza en CLP o utilizando una máquina simbóli-ca, es que el árbol de ejecución a ser recorrido, es en la mayoŕıa de los casos infinito, pues los programas suelen contener construcciones iterativas y recursiones las cuales suelen inducir un número infinito de caminos de ejecución al ejecutarse sin valores concretos. Es por tanto esencial estable-cer un criterio de terminación, en este contexto criterio de recubrimiento, que garantice que el número de caminos a ser recorrido es finito, y al mis-mo tiempo que se obtiene un conjunto interesante de casos de valores de entrada. La mayoŕıa de criterios de recubrimiento están definidos sobre lenguajes de programación estructurados y de alto nivel. Un criterio basado en el flujo de control ampliamente utilizado es el loop-count(k) [53], el cual limita a una cantidad k el número de veces que se puede iterar en los bucles. No obstante, el bytecode tiene un flujo sin estructura, cuyos CFG’s pueden variar mucho en forma. Es por ello que en esta tesis hemos introducido el criterio de recubrimiento block-count(k) . Éste, en lugar de limitar el número de veces que se itera en bucles, cuenta el número de veces que se visita cada bloque durante cada computación. Básicamente, un conjunto de caminos de computación satisface el criterio block-count(k) si éste incluye todos los caminos de computación terminados en los que el número de veces que se visita cada bloque no excede la k dada. En el Art́ıculo 7 se discuten los detalles técnicos de dicho enfoque de TDG de bytecode. En particular: Se define formalmente el criterio block-count(k) . Se define una estrategia de evaluación que garantiza construir un árbol SLD de forma que se generen suficientes derivaciones para cum-plir el criterio block-count(k), asegurando al mismo tiempo la termi-nación del proceso. La fase de TDG se formaliza como una EP en CLP del programa CLP decompilado donde la regla de desplegado juega el papel del criterio de recubrimiento. Definimos además una regla de desplegado que implementa el criterio de recubrimiento block-count(k) y descri-bimos como debe el operador de abstracción tratar con restricciones para poder obtener generadores de casos de prueba efectivos. Todos estos aspectos se ilustran a través de un ejemplo que consiste en una serie de métodos que realizan diferentes cálculos aritméticos. 3.2.1. Generando Datos de Prueba para Prolog por EP Como contribución tangencial de esta tesis, hemos aplicado la idea de utilizar EP para generar automáticamente datos de prueba en el contexto de la LP. Ya mencionamos que nuestro enfoque podŕıa utilizarse en principio para hacer TDG de cualquier lenguaje imperativo. Sin embargo, al tratar de aplicarlo a un lenguaje declarativo como Prolog, encontramos problemas a la hora de generar datos de prueba que cubran ciertos flujos de control de Prolog. Básicamente, el problema es que una caracteŕıstica intŕınseca de la EP es que sólo computa derivaciones no fallidas, mientras que en la TDG de Prolog es esencial generar casos de prueba asociados a derivaciones de fallo. En el Art́ıculo 8 hemos realizado un estudio preliminar en este dirección, en el que se propone transformar el programa Prolog original en un pro-grama Prolog equivalente con fallo expĺıcito. Esto puede hacerse evaluando parcialmente un intérprete Prolog que capt