Deforestation (computer science) explained

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 originally coined by Philip Wadler in his 1990 paper "Deforestation: transforming programs to eliminate trees".[1]

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

See also

Notes and References

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

This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article "Deforestation (computer science)".

Except where otherwise indicated, Everything.Explained.Today is © Copyright 2009-2024, A B Cryer, All Rights Reserved. Cookie policy.