Deforestation (computer science)

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.

References

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

This programming-language-related article is a stub. You can help Wikipedia by expanding it.

v t e Compiler optimizations
Basic block	Peephole optimization Local value numbering
Loop	Automatic parallelization Automatic vectorization Induction variable Loop fusion Loop-invariant code motion Loop inversion Loop interchange Loop nest optimization Loop splitting Loop unrolling Loop unswitching Software pipelining Strength reduction
Data-flow analysis	Available expression Common subexpression elimination Constant folding Dead store elimination Induction variable recognition and elimination Live-variable analysis Upwards exposed uses Use-define chain Reaching definitions
SSA-based	Global value numbering Sparse conditional constant propagation
Code generation	Instruction scheduling Instruction selection Register allocation Rematerialization
Functional	Deforestation Tail-call elimination
Global	Interprocedural optimization
Other	Bounds-checking elimination Compile-time function execution Dead-code elimination Expression templates Inline expansion Jump threading Partial evaluation Profile-guided optimization
Static analysis	Alias analysis Array-access analysis Control-flow analysis Data-flow analysis Dependence analysis Escape analysis Pointer analysis Shape analysis Value range analysis