Evaluación parcial

En informática , la evaluación parcial es una técnica para optimizar programas mediante especialización . Su aplicación más directa consiste en crear programas nuevos que se ejecuten más rápido que los originales, manteniendo al mismo tiempo el mismo comportamiento.

Un programa informático${\displaystyle {\texttt {prog}}}$se considera como una asignación de datos de entrada a datos de salida:

$${\displaystyle {\texttt {prog}}:I_{\text{estático}}\times I_{\text{dinámico}}\to O,}$$

dónde${\displaystyle I_{\text{estático}}}$Los datos estáticos son la parte de los datos de entrada que se conoce en tiempo de compilación.

El evaluador parcial transforma${\displaystyle \langle {\texttt {prog}},I_{\text{static}}\rangle }$en${\displaystyle {\texttt {prog}}^{*}:I_{\text{dynamic}}\to O}$precalculando todos los datos de entrada estáticos en tiempo de compilación.${\displaystyle {\texttt {prog}}^{*}}$Se denomina "programa residual" y debería ejecutarse de forma más eficiente que el programa original. El acto de evaluación parcial se denomina "residualización".${\displaystyle {\texttt {prog}}}$a${\displaystyle {\texttt {prog}}^{*}}$.

Un ejemplo particularmente interesante del uso de la evaluación parcial, descrita por primera vez en la década de 1970 por Yoshihiko Futamura, ^{[ 1 ]} es cuando${\displaystyle {\texttt {prog}}}$es un intérprete para un lenguaje de programación .

Si${\displaystyle I_{\text{estático}}}$es código fuente diseñado para ejecutarse dentro de ese intérprete, luego la evaluación parcial del intérprete con respecto a estos datos/programa produce${\displaystyle {\texttt {prog}}^{*}}$, una versión del intérprete que solo ejecuta ese código fuente, está escrita en el lenguaje de implementación del intérprete, no requiere que se vuelva a suministrar el código fuente y se ejecuta más rápido que la combinación original del intérprete y el código fuente. En este caso${\displaystyle {\texttt {prog}}^{*}}$es efectivamente una versión compilada de${\displaystyle I_{\text{estático}}}$.

Esta técnica se conoce como la primera proyección de Futamura, de la cual existen tres:

1. Especializar un intérprete para un código fuente dado, generando un archivo ejecutable.
2. Especializar el especializador para el intérprete (como se aplicó en el #1), lo que produce un compilador.
3. Especializar el especializador para sí mismo (como se aplica en el punto 2), lo que da como resultado una herramienta que puede convertir cualquier intérprete en un compilador equivalente.

Fueron descritos por Futamura en japonés en 1971 ^{[ 2 ]} y en inglés en 1983. ^{[ 3 ]}

RPython de PyPy y el framework Truffle de GraalVM son ejemplos de compiladores JIT del mundo real que implementan la primera proyección de Futamura.

• Ejecución de funciones en tiempo de compilación
• Memorización
• Meta-rastreo
• Aplicación parcial
• Especialización de algoritmos en tiempo de ejecución
• teorema smn
• Reducción de fuerza
• Metaprogramación de plantillas