Deforestation (computer science)

Last updated

In the theory of programming languages in computer science, deforestation (also known as fusion) is a program transformation to eliminate intermediate lists or tree structures that are created and then immediately consumed by a program.

The term "deforestation" was created by Philip Wadler, originally in his 1990 paper "Deforestation: transforming programs to eliminate trees". [1]

Deforestation is typically applied to programs in functional programming languages, more so non-strict programming languages such as Haskell. One algorithm for deforestation, named shortcut deforestation, [2] is implemented in the Glasgow Haskell Compiler. [3] Deforestation is closely related to escape analysis.

See also

References

  1. ↑ Wadler, Philip (1990). "Deforestation: transforming programs to eliminate trees" . Theoretical Computer Science. 73 (2): 231–248. doi: 10.1016/0304-3975(90)90147-A .
  2. ↑ Gill, Andrew; Launchbury, John; Peyton Jones, Simon (1993). "A short cut to deforestation" (PDF). Proceedings Conference on Functional Programming Languages and Computer Architecture. pp. 223–232. doi:10.1145/165180.165214.
  3. ↑ Peyton Jones, Simon; Tolmach, Andrew; Hoare, C.A.R. (2001). "Playing by the rules: rewriting as a practical optimization technique in GHC" (PDF). Proceedings ACM/SIGPLAN Haskell Workshop.


This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.