Déforestation (informatique)

Dans la théorie des langages de programmation en informatique, la déforestation (aussi connue sous le nom de fusion) est une transformation de programmes qui permet d'éliminer les structures d'arbre.

Le terme de "déforestation" a été inventé par Philip Wadler , dans son article "La déforestation : la transformation des programmes afin d'éliminer les arbres"^[1].

La déforestation est généralement appliquée aux langages de programmation fonctionnelle, en particulier les langages non-stricts (en) tels que Haskell. Un des algorithmes de déforestation, la déforestation par raccourcis^[2] est mis en œuvre dans le Glasgow Haskell Compiler^[3].

Voir aussi[modifier | modifier le code]

Hylomorphism (informatique)

Références[modifier | modifier le code]

↑ (en) Philip Wadler, « Deforestation: transforming programs to eliminate trees », Theoretical Computer Science, vol. 73, n^o 2,‎ 1990, p. 231–248 (DOI 10.1016/0304-3975(90)90147-A, lire en ligne)
↑ Andrew Gill « A short cut to deforestation » (1993) (DOI 10.1145/165180.165214, lire en ligne)
— « (ibid.) », dans Proc. Conf. on Functional Programming Languages and Computer Architecture, p. 223–232
↑ Simon Peyton Jones « Playing by the rules: rewriting as a practical optimization technique in GHC » (2001)
— « (ibid.) », dans Proc. ACM/SIGPLAN Haskell Workshop

Portail de l’informatique

[1] (en) Philip Wadler, « Deforestation: transforming programs to eliminate trees », Theoretical Computer Science, vol. 73, n^o 2,‎ 1990, p. 231–248 (DOI 10.1016/0304-3975(90)90147-A, lire en ligne)

[2] Andrew Gill « A short cut to deforestation » (1993) (DOI 10.1145/165180.165214, lire en ligne)
— « (ibid.) », dans Proc. Conf. on Functional Programming Languages and Computer Architecture, p. 223–232

[3] Simon Peyton Jones « Playing by the rules: rewriting as a practical optimization technique in GHC » (2001)
— « (ibid.) », dans Proc. ACM/SIGPLAN Haskell Workshop

[1]

[2]

[3]