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 n.° 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