Resumen

La evaluación parcial dirigida por narrowing (NPE:
Narrowing-driven Partial Evaluation) es una técnica potente para
la especialización de sistemas de reescritura, i.e., para el
componente de primer orden de muchos lenguajes declarativos
(lógico) funcionales como Haskell, Curry o Toy.

Los evaluadores parciales se clasifican en dos grandes categorías:
online y offline, de acuerdo al momento temporal en que se
consideran los aspectos de terminación del proceso de
especialización. Los evaluadores parciales online son usualmente
más precisos ya que tienen más información disponible. En
particular, el esquema original NPE, el cual sigue la aproximación
online, considera una variante del teorema de Kruskal (Kruskal's
Tree Theorem) llamada "subsumción homeomórfica" [Leuschel 2002],
para asegurar la terminación del proceso: si un término subsume
algún término previo en la misma computación de narrowing, se
aplica alguna forma de generalización---usualmente el operador de
generalización más específica---y la evaluación parcial se
reinicia con los términos generalizados. Sin embargo, las pruebas
para el test de subsumción, junto con las generalizaciones
asociadas, hacen que el esquema NPE online sea muy costoso (en
términos de tiempo y espacio), por lo que no se adapta
adecuadamente a problemas realistas como la especialización de
intérpretes.

Los evaluadores parciales offline proceden comúnmente en dos
etapas; la primera etapa procesa un programa (e.g., para
identificar aquellas llamadas a función que se pueden desplegar
sin riesgo de no terminación) e incluye anotaciones para guiar las
computaciones parciales;  entonces, una segunda etapa, la de
evaluación parcial propiamente dicha, sólo tiene que obedecer las
anotaciones y por tanto el especializador es mucho más rápido que
en la aproximación online.

En esta tesis se presenta un nuevo esquema de evaluación parcial
dirigido por narrowing, más eficiente y que asegura la terminación
siguiendo el estilo offline. Para ello, identificamos una
caracterización de programas cuasi-terminantes a los que llamamos
"no crecientes". En tales programas, las computaciones por
narrowing necesario presentan sólo un conjunto finito de términos
diferentes (módulo renombramiento de variables). La propiedad de
la cuasi-terminación es importante toda vez que su presencia es
regularmente una condición suficiente para la terminación del
proceso de especialización.

Sin embargo, la clase de programas cuasi-terminantes es muy
restrictiva, por lo que introducimos un algoritmo que acepta
programas inductivamente secuenciales---una clase mucho más amplia
sobre la que está definido el narrowing necesario---y anota
aquellas partes que violan la caracterización de programas no
crecientes. Para procesar de manera adecuada los nuevos términos
anotados extendemos la relación de narrowing, a la que llamamos:
narrowing necesario generalizante.

Una vez definido el esquema, desarrollamos un prototipo para la
evaluación parcial offline dirigida por narrowing. La validación
experimental arroja resultados que muestran una mejora
significativa en el tiempo de especialización offline con respecto
al esquema online.

Recientemente, se ha formulado un nuevo principio para el análisis
de terminación de los programas basado en el cambio de tamaño de
los argumentos de las llamadas a función. Con la finalidad de
mejorar la precisión de la fase  de anotación propia del nuevo
esquema, hemos adaptado los grafos de cambio de tamaño (grafos
size-change), introducidos originalmente para los lenguajes
funcionales, a los lenguajes lógico funcionales. En particular los
grafos nos son útiles para determinar una forma específica de
cuasi-terminación, que finalmente utilizamos para realizar
anotaciones al estilo de nuestra primera propuesta offline.

Los lenguajes empotrados de dominio específico (DSELs) generan
código ineficiente debido a la sobrecarga de interpretación, por
lo que [Hudak 1998, Seefried et al. 2004, Christensen 2003] entre
otros, plantean el uso de las técnicas de evaluación parcial como
un medio para remediar este inconveniente. En este punto,
seleccionamos el dominio de los routers, en particular el modelo
de routers software Click y desarrollamos un lenguaje de
especificación para routers denominado Rose, empotrado en el
lenguaje Curry.

Los DSELs aportan una vía de prueba interesante en dos aspectos:
primero, han permitido ejercitar los conceptos de la programación
lógico funcional en la generación de lenguajes de dominio
específico; y segundo, nos han proporcionado ejemplos para la
especialización de programas mediante las técnicas NPE offline
desarrolladas.