entonces probablemente se producirán demasiadas generalizaciones resultando en una especialización muy pobre; mientras que si éstos son demasiado grandes, entonces la especialización tenderá a ser demasiado agresiva, produciendo posiblemente versiones innecesarias. Veremos después que ésta puede mejorarse gramas reales, pues entre otras cosas, y como veremos, la composicio-nalidad del programa original respecto a las llamadas a métodos se pierde en la decompilación. 2Veremos después que ésta puede mejorarse 53 gramas reales, pues entre otras cosas, y como veremos, la composicio-nalidad del programa original respecto a las llamadas a métodos se pierde en la decompilación. 54 2.4. RETO II: DECOMPILACIÓN MODULAR Consideremos de nuevo nuestro ejemplo de la Figura 2.4. El código de-compilado que obtenemos usando el evaluador parcial mejorado se muestra en la Figura 2.7. Se puede observar que éste es básicamente el mismo de la Figura 2.5 excepto para el método count, para el que se obtiene ahora el código que mostramos en la parte baja de la Figura 2.6. Es importante hacer notar que este ejemplo no es suficientemente complejo como para poner en evidencia el problema de la polivarianza que el nuevo operador de abstracción del Art́ıculo 2 resuelve. El lector interesado puede consultar el Art́ıculo 2 donde se presenta un ejemplo representativo en este sentido. A la vista del ejemplo, identificamos las siguientes cuatro limitaciones del esquema actual de decompilación (a partir de ahora llamado decom-pilación no-modular) denotadas como (L1). . . (L4). Nótese que dichas li-mitaciones, aśı como la forma de resolverlas que explicamos más adelante, son también relevantes para el caso de la decompilación por medio de EP puramente offline. (L1) Los métodos aparecen “inlined” en los diferentes contextos en los que son llamados, lo que hace que se pierda la estructura original del código. Por ejemplo, la invocación a abs desde gcd (ĺınea 12 de gcd) no aparece en el código decompilado. Como resultado, el código decompilado para gcd tiene dos casos base en los que aparecen “inlined” los correspondientes “builtins” de abs, es decir, A>=0, B<0 y A is -B. Esto ocurre porque las llamadas a métodos se tratan de forma “small-step” en el intérprete, es decir, el código de los métodos invocados se despliega como se estuviese incluido dentro el método que lo invoca. (L2) Como consecuencia, el proceso de decompilación es muy ineficien-te cuando aparecen muchas llamadas a métodos. Por ejemplo, si se tienen n llamadas a un mismo método, éste será decompilado n veces. Incluso aún peor, si aparece una invocación a método dentro de un bucle, el código será decompilado en el caso mejor 2 veces, al tenerse que realizar la corres-pondiente generalización en el control global antes de llegar al punto fijo en la EP. Esto podŕıa incluso ser peor en el caso de bucles anidados. (L3) El esquema no-modular no trabaja de forma incremental, en el sentido de que no permite la decompilación separada de métodos sino que redecompila todas las llamadas. Por tanto, decompilar un lenguaje real es totalmente inviable, pues han de considerarse las libreŕıas, cuyo códi-go podŕıa incluso no estar disponible. La limitación L2 junto con la L3 55 CAPÍTULO 2. DECOMPILACIÓN INTERPRETATIVA DE BYTECODE A LP responden negativamente al punto (a) de la Figura 2.1. (L4) El programa decompilado contendrá básicamente el intérprete completo cuando aparezcan métodos recursivos. Esta es la razón por la que en el programa decompilado de la Figura 2.7 no aparece el códi-go correspondiente al método recursivo fact. El problema con la recur-sión es el siguiente. Asumamos que queremos decompilar el método re-cursivo m1 cuyo código es de la siguiente forma 〈pc0 : bc0, . . . , pcj : invoke(m1), . . . , pcn : return〉. Hay una primera decompilación para Ak = execute(st(fr(m1, pcj, os, lv), []), Sf) en la que la pila de llama-das es vaćıa. Al decompilarla, aparece una llamada de la forma Al = execute(st(fr(m1, pcj, os ′, lv′), [fr(m1, pcj, os, lv)]), Sf), con la pila de llamadas conteniendo la anterior llamada, al llegar a la llamada re-cursiva. En este punto, la derivación debe pararse pues AkET Al. Pa-ra asegurar terminación, el control global generaliza estas llamadas a execute(st(fr(m1, pcj, , ), ), Sf), donde denota una variable libre, sien-do por tanto la pila de llamadas desconocida. Como consecuencia, al evaluar la instrucción return, la continuación obtenida de la pila de llamadas es desconocida produciéndose la llamada execute(st(fr( , , , ), ), Sf), que habrá de decompilada. El hecho de que el método y el contador de pro-grama sean desconocidos provoca que sea imposible eliminar la capa de interpretación, y de hecho, el código decompilado contendrá potencialmen-te el intérprete al completo. Esta situación se da al decompilar el método fact. Las limitaciones L1 y L4 responden negativamente al punto (b) (ver Figura 2.1). A continuación identificamos los ingredientes necesarios para definir un esquema de decompilación modular. Entendemos por decompilación modu-lar, una decompilación en la que la unidad de procesamiento es el méto-do, es decir, se decompila un método cada vez. Mostraremos como dicho esquema resuelve las cuatro limitaciones descritas de la decompilación no-modular y responde afirmativamente a los puntos (a) y (b) de la Figu-ra 2.1. Básicamente necesitaremos: (i) Dar un tratamiento composicional a las invocaciones a método. Veremos que esto se puede conseguir consi-derando un intérprete implementado utilizando una semántica “big-step”. (ii) Proporcionar un mecanismo para residualizar las llamadas del progra-ma decompilado (es decir, no desplegarlas y añadirlas sin modificaciones al código residual). Generaremos automáticamente anotaciones en la EP 56 2.4. RETO II: DECOMPILACIÓN MODULAR para este propósito. (iii) Estudiaremos las condiciones que aseguran que la decompilación separada de métodos es correcta. 2.4.1. Intérprete con Semántica “Big-step” para ha-bilitar la Modularidad Tradicionalmente, se han considerado dos enfoques distintos a la hora de definir la semántica de un lenguaje, la semántica “big-step” (o natural) y la “small-step” (o operacional-estructural), ver por ejemplo [59]). Bási-camente, en una semántica “big-step” las transiciones relacionan los estas inicial y final para cada instrucción, mientras que en una “small-step” las transiciones definen el siguiente paso de ejecución para cada sentencia. En el contexto de los intérpretes de bytecode, ocurre que la mayoŕıa de las instrucciones se ejecutan en un solo paso, haciendo que ambos enfoques sean prácticamente equivalentes. Este es el caso de nuestro intérprete de bytecode de la Figura 2.3 para todas las instrucciones excepto para invoke. La transición para invoke en la semántica “small-step” define el siguien-te paso de la computación, es decir, el “frame” actual se apila en la pila de llamadas y se inicializa un nuevo “frame” para la ejecución del méto-do invocado. Nótese que después de dar este paso, no es posible distinguir ya entre el código del método anterior y el llamado. Esto provoca que no podamos obtener modularidad en la decompilación. En el contexto de la decompilación interpretativa de lenguajes impera-tivos, tradicionalmente se han utilizado intérpretes con semántica “small-step” (ver por ejemplo [77, 48]). En esta tesis sostenemos que el uso de intérprete con una semántica “big-step” es necesario para poder definir un esquema modular y poder aśı escalar al considerar lenguajes y progra-mas reales. En la Figura 2.8, mostramos la parte relevante de la versión “big-step” del intérprete de bytecode de la Figura 2.3. Podemos observar que ahora, la instrucción invoke, una vez extráıdos los parámetros de lla-mada de la pila de operandos, llama recursivamente al predicado main/3 para ejecutar el método llam