En informática , la reducción de gráficos implementa una versión eficiente de evaluación no estricta, una estrategia de evaluación en la que los argumentos de una función no se evalúan de inmediato. Esta forma de evaluación no estricta también se conoce como evaluación perezosa y se usa en lenguajes de programación funcionales . La técnica fue desarrollada por primera vez por Chris Wadsworth en 1971.
Motivación
A continuación, se muestra un ejemplo sencillo de evaluación de una expresión aritmética:
La secuencia de reducción anterior emplea una estrategia conocida como reducción del árbol más externo . La misma expresión se puede evaluar utilizando la reducción del árbol más interno , dando como resultado la secuencia de reducción:
Observe que la orden de reducción se hace explícita al agregar paréntesis. Esta expresión también podría haberse evaluado simplemente de derecha a izquierda, porque la suma es una operación asociativa .
Representada como un árbol , la expresión anterior se ve así:
De aquí es de donde proviene el término reducción de árboles. Cuando se representa como un árbol, podemos pensar que la reducción más interna funciona de abajo hacia arriba, mientras que la más externa funciona de arriba hacia abajo.
La expresión también se puede representar como un gráfico acíclico dirigido , lo que permite compartir subexpresiones:
En cuanto a los árboles, la reducción más externa e interna también se aplica a los gráficos. Por lo tanto, tenemos reducción gráfica .
Ahora la evaluación con la reducción del gráfico más externo puede proceder de la siguiente manera:
Tenga en cuenta que la evaluación ahora solo requiere cuatro pasos. La reducción del gráfico más externo se conoce como evaluación perezosa y la reducción del gráfico más interno se conoce como evaluación ansiosa .
Reducción del gráfico combinador
La reducción del gráfico combinador es una técnica de implementación fundamental para los lenguajes de programación funcionales , en la que un programa se convierte en una representación del combinador que se asigna a una estructura de datos de gráfico dirigido en la memoria de la computadora, y la ejecución del programa luego consiste en reescribir partes de este gráfico ("reducir "it) para avanzar hacia resultados útiles.
Historia
El concepto de reducción gráfica que permite compartir los valores evaluados fue desarrollado por primera vez por Chris Wadsworth en su Ph.D. de 1971. disertación. [1] Esta tesis fue citada por Peter Henderson y James H. Morris Jr. en el artículo de 1976, "Un evaluador perezoso" [2] que introdujo la noción de evaluación perezosa. En 1976, David Turner incorporó la evaluación perezosa en SASL utilizando combinadores. [3] SASL fue un lenguaje de programación funcional temprano desarrollado por Turner en 1972.
Ver también
Notas
- ^ Hudak, Paul (septiembre de 1989). "Concepción, evolución y aplicación de lenguajes de programación funcional". Encuestas de computación ACM . 21 (3): 359–411. CiteSeerX 10.1.1.83.6505 . doi : 10.1145 / 72551.72554 .
- ^ Un evaluador perezoso
- ^ Hudak, Paul; Hughes, John; Peyton Jones, Simon; Wadler, Philip. "Una historia de Haskell: ser vago con la clase" . Conferencia de Historia de los Lenguajes de Programación 2007 .
Referencias
- Bird, Richard (1998). Introducción a la programación funcional con Haskell . Prentice Hall. ISBN 0-13-484346-0.
Otras lecturas
- Simon Peyton Jones , La implementación de lenguajes de programación funcionales , Prentice Hall, 1987. Texto completo en línea. [1]