Desforestació (informàtica)
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 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]- 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]- ↑ 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.
- ↑ Gill, Andrew; John Launchbury, Simon Peyton Jones (1993). "A short cut to deforestation". Proc. Conf. on Functional Programming Languages and Computer Architecture: 223–232
- ↑ 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
- ↑ From lists to streams to nothing at all (presentació) Document(anglès)
- ↑ Stream fusion a MLton
- ↑ Stream-fusion(anglès)
- ↑ Biblioteca Stream-fusion al Hackage(anglès)
- ↑ Loop fusion (anglès)
- ↑ Stream fusion for Haskell Arrays (anglès)