In the theory of

programming languages A programming language is a system of notation for writing computer programs. Programming languages are described in terms of their syntax (form) and semantics (meaning), usually defined by a formal language. Languages usually provide features ...

computer science Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...

, deforestation (also known as fusion) is a

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 of p ...

to eliminate intermediate lists or

tree structure A tree structure, tree diagram, or tree model 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, although the chart is gen ...

s that are created and then immediately consumed by a program. The term "deforestation" was originally coined by

Philip Wadler Philip Lee Wadler (born April 8, 1956) is a UK-based American computer scientist known for his contributions to programming language design and type theory. He holds the position of Personal Chair of theoretical computer science at the Laborato ...

in his 1990 paper "Deforestation: transforming programs to eliminate trees". Deforestation is typically applied to programs in

functional programming languages In computer science, functional programming is a programming paradigm where programs are constructed by applying and composing functions. It is a declarative programming paradigm in which function definitions are trees of expressions that map ...

, particularly non-strict programming languages such as

Haskell Haskell () is a general-purpose, statically typed, purely functional programming language with type inference and lazy evaluation. Designed for teaching, research, and industrial applications, Haskell pioneered several programming language ...

. One particular algorithm for deforestation, ''shortcut deforestation'', is implemented in the

Glasgow Haskell Compiler The Glasgow Haskell Compiler (GHC) is a native or machine code compiler for the functional programming language Haskell. It provides a cross-platform software environment for writing and testing Haskell code and supports many extensions, libra ...

. Deforestation is closely related to

escape analysis In compiler optimization, escape analysis is a method for determining the dynamic scope of pointers where in the program a pointer can be accessed. It is related to pointer analysis and shape analysis. When a variable (or an object) is allocat ...

References

Compiler optimizations Implementation of functional programming languages {{prog-lang-stub

See also

References