Desforestació (informàtica)

De Viquipèdia
Dreceres ràpides: navegació, cerca

Desforestació en informàtica, anomenada també fusió de bucles, és una transformació de programes per eliminar estructures intermèdies temporals. S'aplica en el context d'una composició de funcions sobre estructures, obtenint la fusió dels bucles que les recorren. El terme “desforestació” va ésser emprat per primera vegada per Philip Wadler en el seu estudi "Deforestation: transforming programs to eliminate trees".[1]

La desforestació té aplicació en llenguatges de programació funcional, en especial els llenguatges estrictes com ara el OCaml i Scala.

En els llenguatges d'avaluació tardana com ara Haskell en una composició els elements els elements es forneixen sota comanda d'un en un (crida per necessitat), evitant la generació completa d'estructures intermèdies dels llenguatges estrictes. Queda llavors l'optimització possible de fusió dels bucles.

Tipus[modifica | modifica el codi]

Fusió de bucles en curt-circuit (ang
Shortcut fusion)[2] implementat en el compilador GHC (Glasgow Haskell Compiler).[3]
Transformació en corrents de dades (ang
Stream-fusion):

El corrent incorpora la possibilitat de tenir elements sense dades, com a conseqüència d'operacions de filtratge.[4]

Implementat inicialment al compilador MLton de llenguatge ML Estàndard.[5][6]

Implementat al compilador GHC (Glasgow Haskell Compiler) gràcies a la pragma RULES. Vegeu biblioteca Stream-fusion al Hackage[7]

Les funcions com ara els filtres d'aquesta biblio. s'implementen en Haskell com una composició, començant per l'operació de conversió stream sobre l'estructura i acabant per la inversa unstream. En la composició de funcions, l'aparició juxtaposada de les conversions unstream al final d'una funció amb la inversa stream de l'inici de la següent és eliminada pel compilador.[8][9]

Referències[modifica | modifica el codi]

  1. Wadler, Philip. «Deforestation: transforming programs to eliminate trees». Theoretical Computer Science, vol. 73, 1990, pàg. 231–248. DOI: 10.1016/0304-3975(90)90147-A.
  2. Gill, Andrew; John Launchbury, Simon Peyton Jones (1993). "A short cut to deforestation". Proc. Conf. on Functional Programming Languages and Computer Architecture: 223–232.  
  3. Peyton Jones, Simon; Andrew Tolmach, C.A.R. Hoare (2001). "Playing by the rules: rewriting as a practical optimization technique in GHC". Proc. ACM/SIGPLAN Haskell Workshop.  
  4. From lists to streams to nothing at all (presentació) Document(anglès)
  5. Stream fusion a MLton
  6. Stream-fusion(anglès)
  7. Biblioteca Stream-fusion al Hackage(anglès)
  8. Loop fusion (anglès)
  9. Stream fusion for Haskell Arrays (anglès)