Deforestation (computer science)

In the theory of programming languages in computer science, deforestation (also known as fusion) is a program transformation to eliminate tree structures.

The term "deforestation" was originally coined by Philip Wadler in his 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]

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". Proc. ACM/SIGPLAN Haskell Workshop.

Compiler optimizations

Basic block	Peephole optimization

Loop optimization	Induction variable Strength reduction Loop fusion Loop inversion Loop interchange Loop-invariant code motion Loop nest optimization Loop unrolling Loop splitting Loop unswitching Software pipelining Automatic parallelization

Data-flow analysis	Common subexpression elimination Constant folding Induction variable recognition and elimination Dead store elimination Use-define chain Live variable analysis Available expression

SSA-based	Global value numbering Sparse conditional constant propagation

Code generation	Register allocation Instruction selection Instruction scheduling Rematerialization

Functional	Tail call elimination Deforestation

Global	Interprocedural optimization

Other	Bounds-checking elimination Dead code elimination Inline expansion Jump threading

Static analysis	Alias analysis Pointer analysis Shape analysis Escape analysis Array access analysis Dependence analysis Control flow analysis Data flow analysis

This article is issued from Wikipedia - version of the 7/3/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.