Evaluación parcial

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Técnica para la optimización del programa

En informática, la evaluación parcial es una técnica para varios tipos diferentes de optimización de programas por especialización. La aplicación más sencilla es producir nuevos programas que se ejecuten más rápido que los originales y que se garantice que se comporten de la misma manera.

Un programa de computadora prog se ve como un mapeo de datos de entrada en datos de salida:

{displaystyle prog:I_{text{static}}times I_{text{dynamic}}to O,}

Donde ${displaystyle I_{text{static}}}$ , el Datos estáticos, es la parte de los datos de entrada conocidos en el tiempo de compilación.

El evaluador parcial transforma ${displaystyle langle prog,I_{text{static}}rangle }$ en ${displaystyle prog^{*}:I_{text{dynamic}}to O}$ precomputando toda la entrada estática en el tiempo de compilación. $prog^{*}$ se llama el "programa residual" y debe funcionar más eficientemente que el programa original. Se dice que el acto de evaluación parcial "residualiza" $prog$ a $prog^{*}$ .

Proyecciones de Futamura

Un ejemplo particularmente interesante del uso de la evaluación parcial, descrito por primera vez en la década de 1970 por Yoshihiko Futamura, es cuando prog es un intérprete de un lenguaje de programación.

Si I_estático es un código fuente diseñado para ejecutarse dentro de ese intérprete, entonces la evaluación parcial del intérprete con respecto a estos datos/programa produce 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 la fuente. En este caso, prog* es efectivamente una versión compilada de I_static.

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

Especialización de un intérprete para un código fuente dado, dando lugar a un ejecutable.
Especializando el especialista para el intérprete (como se aplica en #1), dando un compilador.
Especializar el especialista para sí mismo (como se aplica en #2), dando una herramienta que puede convertir cualquier intérprete a un compilador equivalente.

Fueron descritos por Futamura en japonés en 1971 y en inglés en 1983.

Contenido relacionado

Más resultados...