Deforestation (computer science)
Encyclopedia
In the theory of programming languages in computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...

, deforestation (also known as fusion) is a program transformation
Program transformation
A program transformation is any operation that takes a computer program and generates another program. In many cases the transformed program is required to be semantically equivalent to the original, relative to a particular formal semantics and in fewer cases the transformations result in programs...

 to eliminate tree structure
Tree structure
A tree structure is a way of representing the hierarchical nature of a structure in a graphical form. It is named a "tree structure" because the classic representation resembles a tree, even though the chart is generally upside down compared to an actual tree, with the "root" at the top and the...

s.

The term "deforestation" was originally coined by Philip Wadler
Philip Wadler
Philip Wadler is a computer scientist known for his contributions to programming language design and type theory. In particular, he has contributed to the theory behind functional programming and the use of monads in functional programming, the design of the purely functional language Haskell, and...

 in his paper "Deforestation: transforming programs to eliminate trees".

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, is implemented in the Glasgow Haskell Compiler
Glasgow Haskell Compiler
The Glorious Glasgow Haskell Compilation System, more commonly known as the Glasgow Haskell Compiler or GHC, is an open source native code compiler for the functional programming language Haskell. The lead developers are Simon Peyton Jones and Simon Marlow...

.
The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK