Reducción de gráficos

En informática , la reducción de grafos implementa una versión eficiente de la evaluación no estricta, una estrategia de evaluación en la que los argumentos de una función no se evalúan inmediatamente. Esta forma de evaluación no estricta también se conoce como evaluación perezosa y se utiliza en lenguajes de programación funcional . La técnica fue desarrollada por primera vez por Chris Wadsworth en 1971.

A continuación se muestra un ejemplo sencillo de cómo evaluar una expresión aritmética:

${\displaystyle {\begin{aligned}&{}&&((2+2)+(2+2))+(3+3)\\&{}&=&((2+2)+(2+2))+6\\&{}&=&((2+2)+4)+6\\&{}&=&(4+4)+6\\&{}&=&8+6\\&{}&=&14\end{aligned}}}$

La secuencia de reducción anterior emplea una estrategia conocida como reducción de árbol más externo . La misma expresión se puede evaluar utilizando la reducción de árbol más interno , lo que produce la siguiente secuencia de reducción:

${\displaystyle {\begin{aligned}&{}&&((2+2)+(2+2))+(3+3)\\&{}&=&((2+2)+4)+(3+3)\\&{}&=&(4+4)+(3+3)\\&{}&=&(4+4)+6\\&{}&=&8+6\\&{}&=&14\end{aligned}}}$

Nótese que el orden de reducción se hace explícito mediante la adición de paréntesis. Esta expresión también podría haberse evaluado simplemente de derecha a izquierda, ya que la suma es una operación asociativa .

Representada como un árbol , la expresión anterior se ve así:

De aquí proviene el término reducción de árbol. Cuando se representa como un árbol, podemos pensar que la reducción interna trabaja de abajo hacia arriba, mientras que la externa trabaja de arriba hacia abajo.

La expresión también puede representarse como un grafo 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 grafos. Por lo tanto, tenemos reducción de grafos .

Ahora, la evaluación con reducción del grafo más externo puede proceder de la siguiente manera:

Observe que la evaluación ahora solo requiere cuatro pasos. La reducción del grafo más externo se denomina evaluación perezosa y la reducción del grafo más interno se denomina evaluación ansiosa .

La reducción de grafos combinatorios es una técnica de implementación fundamental para los lenguajes de programación funcional , en la que un programa se convierte en una representación combinatoria que se asigna a una estructura de datos de grafo dirigido en la memoria de la computadora, y la ejecución del programa consiste entonces en reescribir partes de este grafo ("reducirlo") para avanzar hacia resultados útiles.

El concepto de reducción de grafos que permite compartir valores evaluados fue desarrollado por primera vez por Chris Wadsworth en su tesis doctoral de 1971. ^{[ 1 ]} Esta tesis fue citada por Peter Henderson y James H. Morris Jr. en el artículo de 1976, “A lazy evaluator” ^{[ 2 ]} que introdujo la noción de evaluación perezosa. En 1976, David Turner incorporó la evaluación perezosa en SASL mediante combinadores. ^{[ 3 ]} SASL fue un lenguaje de programación funcional temprano desarrollado por primera vez por Turner en 1972.

• Máquina de reducción de gráficos
• Máquina SECD

• Bird, Richard (1998). Introducción a la programación funcional con Haskell . Prentice Hall. ISBN 0-13-484346-0.

• Peyton Jones, Simon L. (1987). La implementación de lenguajes de programación funcional . Prentice Hall. ISBN 013453333XLCCN 86020535. Consultado el 15 de abril de 2022 .