deforestation (computer science)

{{Short description|Program transformation to eliminate trees}}

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".{{cite journal

| url = http://homepages.inf.ed.ac.uk/wadler/papers/deforest/deforest.ps

| first = Philip

| last = Wadler

| title = Deforestation: transforming programs to eliminate trees

| journal = Theoretical Computer Science

| volume = 73

| pages = 231–248

| year = 1990

| doi = 10.1016/0304-3975(90)90147-A

| issue = 2| doi-access = free

| url-access = subscription

}}

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,{{cite conference

| first = Andrew

| last = Gill

| author2=John Launchbury |author3=Simon Peyton Jones

| title = A short cut to deforestation

| url = http://research.microsoft.com/en-us/um/people/simonpj/papers/deforestation-short-cut.pdf

| book-title = Proc. Conf. on Functional Programming Languages and Computer Architecture

| doi = 10.1145/165180.165214

| year = 1993

| pages = 223–232}} is implemented in the Glasgow Haskell Compiler.{{cite conference|last=Peyton Jones|first=Simon|year=2001|title=Playing by the rules: rewriting as a practical optimization technique in GHC|url=https://www.microsoft.com/en-us/research/wp-content/uploads/2001/09/rules.pdf|author2=Andrew Tolmach|author3=C.A.R. Hoare|book-title=Proc. ACM/SIGPLAN Haskell Workshop}} Deforestation is closely related to escape analysis.