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 ejecutan más rápido que los originales y se garantiza que se comportarán de la misma manera.
Un programa de ordenador prog es visto como un mapeo de datos de entrada en datos de salida:
dónde , los datos estáticos , es la parte de los datos de entrada conocidos en el momento de la compilación.
El evaluador parcial se transforma dentro precalculando toda la entrada estática en tiempo de compilación. se denomina "programa residual" y debería ejecutarse de manera más eficiente que el programa original. Se dice que el acto de evaluación parcial "residualiza" a .
Proyecciones 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, [1] es cuando prog es un intérprete de un lenguaje de programación.
Si I static es el 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á escrito 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 las cuales hay tres:
- Especializando un intérprete para un código fuente dado, produciendo un ejecutable.
- Especialización del especialista para el intérprete (como se aplicó en el n. ° 1), obteniendo un compilador.
- Especializando al especialista por sí mismo (como se aplicó en el n. ° 2), produciendo una herramienta que puede convertir cualquier intérprete en un compilador equivalente.
Además, la aplicación de la herramienta en el n. ° 3 a sí misma produce la herramienta en sí, por lo que es un Quine .
Fueron descritos por primera vez por Futamura en 1983. [2]
Ver también
Referencias
- ^ Sitio web de Yoshihiko Futamura .
- ^ Cálculo parcial de programas , Yoshihiko Futamura, marzo de 1983.
Referencias generales
- Yoshihiko Futamura, https://web.archive.org/web/20110629171734/http://www.brics.dk/~hosc/local/HOSC-12-4-pp381-391.pdf Evaluación parcial del proceso de cálculo - Una Enfoque de un compilador-compilador
- Charles Consel y Olivier Danvy (1993). "Notas del tutorial sobre evaluación parcial". Actas del vigésimo simposio anual de ACM sobre principios de lenguajes de programación : 493–501.
enlaces externos
- Neil D. Jones, Carsten K. Gomard y Peter Sestoft: Evaluación parcial y generación automática de programas (1993) Libro, texto completo disponible en línea.
- 1999 Taller ACM SIGPLAN sobre evaluación parcial y manipulación de programas basada en semántica (PEPM'99)
- Plantillas C ++ como evaluación parcial, 1999 ACM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation (PEPM'99)
- Plantillas C ++ como evaluación parcial una versión diferente que incluye Catat (pdf)
- Aplicación de la evaluación parcial dinámica a lenguajes de programación dinámicos y reflexivos