Evaluación parcial

Técnica para la optimización de programas

En informática , la evaluación parcial es una técnica para distintos tipos 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 comportarán de la misma manera.

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

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

donde , los datos estáticos , son la parte de los datos de entrada conocidos en el momento de la compilación. ${\displaystyle I_{\text{static}}}$

El evaluador parcial transforma en mediante el cálculo previo de 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. El acto de evaluación parcial se denomina "residualizar" a . ${\displaystyle \langle prog,I_{\text{static}}\rangle }$ ${\displaystyle prog^{*}:I_{\text{dynamic}}\to O}$ ${\displaystyle prog^{*}}$ ${\displaystyle prog}$ ${\displaystyle prog^{*}}$

Proyecciones de Futamura

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 prog es un intérprete de un lenguaje de programación .

Si I _static 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 el código fuente. En este caso, prog * es efectivamente una versión compilada de I _static .

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

1. Especializar un intérprete para un código fuente determinado, produciendo un ejecutable.
2. Especializar el especializador para el intérprete (como se aplica en el punto n.° 1), dando como resultado un compilador.
3. Especializar el especializador para sí mismo (como se aplica en el punto n.° 2), produciendo 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]

Véase también

• Ejecución de funciones en tiempo de compilación
• Memorización
• Solicitud parcial
• Especialización de algoritmos en tiempo de ejecución
• teorema _de smn
• Reducción de fuerza
• Metaprogramación de plantillas

Referencias

1. Sitio web de Yoshihiko Futamura.
2. "Evaluación parcial del proceso computacional --- Un enfoque hacia un compilador-compilador", Transactions of the Institute of Electronics and Communications Engineers of Japan , 54-C : 721–728, 1971
3. Futamura, Y. (1983). "Computación parcial de programas". Simposios RIMS sobre ciencia e ingeniería del software . Apuntes de clase sobre informática. Vol. 147. Springer. págs. 1–35. doi :10.1007/3-540-11980-9_13. hdl :2433/103401. ISBN. 3-540-11980-9.

Referencias generales

• Futamura, Y. (1999). "Evaluación parcial del proceso computacional: un enfoque hacia un compilador-compilador". Computación simbólica y de orden superior . 12 (4): 381–391. CiteSeerX  10.1.1.10.2747 . doi :10.1023/A:1010095604496. S2CID  12673078.
• Consel, Charles; Danvy, Olivier (1993). "Notas tutoriales sobre evaluación parcial". POPL '93: Actas del 20.º Simposio ACM SIGPLAN-SIGACT sobre principios de lenguajes de programación . Association for Computing Machinery. págs. 493–501. CiteSeerX  10.1.1.114.7330 . doi :10.1145/158511.158707. ISBN . 0897915607.S2CID 698339  .

Enlaces externos

• Jones, Neil D.; Gomard, Carsten K.; Sestoft, Peter (1993). Evaluación parcial y generación automática de programas. Prentice Hall. ISBN 9780130202499.
• Danvy, O., ed. (1999). "Evaluación parcial y manipulación de programas basada en semántica PEPM'99" (PDF) . CiteSeerX  10.1.1.164.2284 .
• Veldhuizen, Todd L. (1999). "Plantillas C++ como evaluación parcial". PEPM'99 . págs. 15–. arXiv : cs/9810010 .
• Aplicación de la evaluación parcial dinámica a lenguajes de programación dinámicos y reflexivos