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 llamado. Al terminar la ejecución del método, el valor de retorno se apila de vuelta en la pila de operandos del nuevo esta-do y la ejecución procede normalmente. Por otro lado ya no es necesario llevar en el estado expĺıcitamente la pila de llamadas, sino sólo la infor-mación de la ejecución actual, es decir, los estado son ahora de la forma execute(S,S) :- S = st(M,PC,[_Top|_],_),bytecode(M,PC,return).execute(S,Sf) :- S = st(M,PC,_,_),bytecode(M,PC,Inst),step(Inst,S,S’),execute(S’,Sf).step(invoke(M’),S,S’) :- S = st(M,PC,OS,LV),next(M,PC,PC’),split_OS(M’,OS,Args,OSRs),main(M’,Args,RV),S’ = st(M,PC’,[RV|OSRs],LV).Figura 2.8: Fragmento del intérprete de bytecode “big-step”st(M,PC,OStack,LocalV). La pila de llamadas la mantendŕıa ahora el pro-pio Prolog por medio de las llamadas recursivas al predicado main/3.El tratamiento composicional en cuanto a las llamadas a métodos no sólo es esencial para permitir la decompilación modular (solucionando aśı L1, L2 y L3) sino que también resuelve el problema con la recur-sión de una manera simple y elegante. De hecho, la decompilación usan-do el intérprete “big-step” ya no presenta la limitación L4. Por ejemplo,la decompilación de un método recursivo m1 empezaŕıa por la llamadamain(m1, , ) y llegaŕıa entonces a main(m1, args, ) donde args represen-taŕıa a los argumentos de la llamada recursiva. Esta llamada seŕıa detectadacomo peligrosa por el control local y por tanto se paraŕıa la derivación. Adiferencia de lo que pasaba anteriormente, no es necesario una segundaevaluación pues la segunda llamada es necesariamente una instancia de laprimera, y por tanto, no habrá ninguna perdida de información asociadacon la generalización de la pila de llamadas.Nótese que la idea de utilizar una semántica “big-step” para definir elintérprete y aśı conseguir una especialización modular es igual de necesarioen el caso de la especialización de intérpretes por medio de EP offline. Másaún, esta idea es, por lo que sabemos, nueva y no hab́ıa sido propuesta antesen ningún contexto, ni en la especialización online ni offline de intérpretes.2.4.2. El Esquema de Decompilación ModularAdemás de usar un intérprete “big-step”, para poder diseñar un esque-ma de decompilación modular, es necesario: (1) proporcionar un mecanismo582.4. RETO II: DECOMPILACIÓN MODULARmain(count,[N],0) :- 0>=N.main(count,[N],I) :-0=N.execute_2(N,A,I) :-Ae0, D is B rem C,execute_1(C,D,A).execute_1(A,0,C) :- main(abs,[A],C).execute_1(A,B,F) :- B
e0,H is A rem B,execute_1(B,H,F).main(abs,[A],A) :- A>=0.main(abs,[B],A) :- B<0, A is -B.main(fact,[B],A) :- B
e0,C is B-1,main(fact,[C],D),A is B*D.main(fact,[0],1).Figura 2.9: Código decompilado usando la decompilación modularpara residualizar llamadas en el programa decompilado (es decir, no des-plegarlas y añadirlas sin cambios al código residual), y (2) definir la nociónde decompilación separada y estudiar las condiciones que aseguran su co-rrección.El Art́ıculo 6 estudia con detalle estos aspectos y define un esquema dedecompilación modular demostrando formalmente su corrección y comple-titud. También se demuestra que el esquema propuesto satisface el criteriode la método-optimalidad, que asegura que cada método es decompiladouna sola vez.La decompilación modular funciona básicamente de la siguiente mane-ra: cuando se va a decompilar una invocación a método, aparece la llama-da step(invoke(m’), , ) durante el proceso de desplegado. Utilizando elintérprete “big-step” de la Figura 2.8, se generará una llamada de la formamain(m’, , ). En este punto, habrá una anotación que indica al evaluadorparcial que no debe desplegar la llamada y que debe sin embargo dejarlaen el código residual sin modificaciones. Si m’ es interno (es decir, está de-finido en el programa de entrada) se realizará (o ya se habrá realizado) sucorrespondiente decompilación, pues el esquema de decompilación aseguraque la EP se efectúa para todos los métodos del programa.La Figura 2.9 muestra el programa decompilado que se obtiene utilizan-59do el esquema de decompilación modular sobre nuestro ejemplo motivador.Se puede observar que la estructura del programa original respecto a lasllamadas a métodos si se preserva ahora. Por ejemplo, puede verse comoen la definición de gcd hay una llamada a abs como ocurre en el programabytecode original. Mas aún, ahora si obtenemos una decompilación efectivapara el método recursivo fact donde la capa de interpretación se ha eli-minado por completo. Concluimos aśı que todas las limitaciones expuestasanteriormente en esta sección se han resuelto satisfactoriamente.2.5. Reto III: Un Esquema de Decompila-ción ÓptimaComo mencionamos en la Sección 2.2, y como podemos ver mirandoel código de la Figura 2.9, los programas decompilados obtenidos usandoel esquema modular no son aún totalmente óptimos pues contienen du-plicaciones de código. Ver por ejemplo el código de la parte derecha delas reglas que definen main(gcd,...) y execute 1/3. Estas duplicacio-nes normalmente se producen debido a que parte del código se reevalúadurante la fase de EP. Desafortunadamente, como veremos después estasduplicaciones y reevaluaciones crecen exponencialmente con el número depuntos de divergencia y convergencia respectivamente, y como veremos enla evaluación experimental, degradan mucho la eficiencia del proceso y lacalidad del código decompilado. Un aspecto fundamental de esta tesis esestudiar si se puede obtener, por medio de la decompilación interpretati-va, programas decompilados cuya calidad sea equivalente a la calidad delos programas obtenidos utilizando decompiladores dedicados (punto (c) dela Figura 2.1). Para poder obtener resultados comparables, tiene sentidoque se usen heuŕısticas similares. El hecho de que los decompiladores habi-tualmente construyan siempre un grafo del flujo de control, “control-flow-graph” (CFG), hace pensar que aplicar una noción similar para controlarla EP de