Reducción de grafos
En informática, la reducción de grafos implementa una versión eficiente de evaluación no estricta, una estrategia de evaluación donde los argumentos para 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 usa en lenguajes de programación funcionales. La técnica fue desarrollada por primera vez por Chris Wadsworth en 1971.
Motivación
editarUn ejemplo simple de evaluación de una expresión aritmética:
La secuencia de reducción anterior emplea una estrategia conocida como reducción de árboles más externa. La misma expresión se puede evaluar usando la reducción de árbol más interna, produciendo la secuencia de reducción:
Observe 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, porque la adición es una operación asociativa.
Representado como un árbol, la expresión anterior se ve así:
De aquí viene el término reducción de árboles. Cuando se lo representa como un árbol, podemos pensar que la reducción interna funciona desde abajo hacia arriba, mientras que la más externa funciona de arriba hacia abajo.
La expresión también se puede representar como un grafo acíclico dirigido, lo que permite compartir sub-expresiones:
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 grafo.
Ahora la evaluación con reducción de grafo más externa puede proceder de la siguiente manera:
Tenga en cuenta que la evaluación ahora solo requiere cuatro pasos. La reducción de grafo más externa se conoce como evaluación perezosa y la reducción de grafo más interna se conoce como evaluación ansiosa.
Reducción del grafo combinador
editarLa reducción del grafo combinador es una técnica de implementación fundamental para lenguajes de programación funcionales, en la que un programa se convierte en una representación combinatoria asignada a una estructura de datos de grafos dirigidos en la memoria de la computadora y la ejecución del programa consiste en reescribir partes de este grafo para avanzar hacia resultados útiles.
Historia
editarEl concepto de una reducción de grafos que permite compartir valores evaluados fue desarrollado por primera vez por Chris Wadsworth en su Ph.D. disertación. Esta disertación fue citada por Peter Henderson y James H. Morris Jr. en el documento de 1976, "Un evaluador perezoso" que introdujo la noción de evaluación perezosa. En 1976, David Turner incorporó la evaluación perezosa en SASL utilizando combinadores. SASL fue un lenguaje de programación funcional desarrollado por primera vez por Turner en 1972.
Notas
editarLa evaluación perezosa puede proporcionar una forma para que los lenguajes de programación de uso general se ejecuten en computadoras cuánticas, como la onda d.
El qpu podría reducir el gráfico lo más posible, y una CPU podría completar la reducción.
Referencias
editarBird, Richard (1998). Introduction to Functional Programming using Haskell. Prentice Hall. ISBN 0-13-484346-0.
Otras lecturas
editarSimon Peyton Jones, The Implementation of Functional Programming Languages, Prentice Hall, 1987. Full text online
Datos: Q5597097
