Reducció de grafos

En informàtica, la reducció de grafos implementa una versió eficient d'evaluació no estricta, una estratègia d'evaluació a on els arguments per a una funció no s'evaluen immediatament. Esta forma d'evaluació no estricta també es coneix com evaluació pereosa i s'usa en llenguages de programació funcionals. La tècnica va ser desenrollada per primera volta per Chris Wadsworth en 1971.

Motivació

Un eixemple simple d'evaluació d'una expressió aritmètica:

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

La seqüència de reducció anterior ampra una estratègia coneguda com a reducció d'arbres més externa. La mateixa expressió es pot evaluar usant la reducció d'arbre més interna, produint la seqüència de reducció:

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

Observe que l'orde de reducció es fa explícit per mig de l'adició de paréntesis. Esta expressió també podria haver-se evaluat simplement de dreta a esquerra, perque l'adició és una operació associativa.

Representat com un arbre, l'expressió anterior es veu aixina:

• Archiu:Expression Tree.svg

D'ací ve el terme reducció d'arbres. Quan li'l representa com un arbre, podem pensar que la reducció interna funciona des d'avall cap a dalt, mentres que la més externa funciona de dalt cap a avall.

L'expressió també es pot representar com un grafo acíclic dirigit, lo que permet compartir sub-expressions:

• Archiu:Expression Graph.svg

Sobre els arbres, la reducció més externa i interna també s'aplica als grafos. Per lo tant, tenim reducció de grafo.

Ara l'evaluació en reducció de grafo més externa pot procedir de la següent manera:

• Archiu:Expression Graph Reduction.svg

Tinga en conte que l'evaluació ara solament requerix quatre passos. La reducció de grafo més externa es coneix com evaluació pereosa i la reducció de grafo més interna es coneix com evaluació ansiosa.

Reducció del grafo combinador

La reducció del grafo combinador és una tècnica d'implementació fonamental para llenguages de programació funcionals, en la que un programa es convertix en una representació combinatòria assignada a una estructura de senyes de grafos dirigits en la memòria de la computadora i l'eixecució del programa consistix en reescriure parts d'este grafo per a alvançar cap a resultats útils.

Notes

L'evaluació pereosa pot proporcionar una forma per a que els llenguages de programació d'us general s'eixecuten en computadores quàntiques, com l'ona d.

El qpu podria reduir el gràfic lo més possible, i una CPU podria completar la reducció.

Referències

Bird, Richard (1998). Introduction to Functional Programming using Haskell, Prentice Hall. ISBN 0-13-484346-0.