Deforestation (computer science): Difference between revisions

Content deleted Content added

Inline

Latest revision as of 22:11, 7 June 2024

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[edit]

^ 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.

[1] Wadler, Philip (1990). "Deforestation: transforming programs to eliminate trees". Theoretical Computer Science. 73 (2): 231–248. doi:10.1016/0304-3975(90)90147-A.

[2] 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.

[3] 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.

[1]

[2]

[3]

@@ Line 1: / Line 1: @@
+{{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 [[tree structure]]s.
+In the theory of [[programming languages]] in [[computer science]], '''deforestation''' (also known as '''fusion''') is a [[program transformation]] to eliminate intermediate lists or [[tree structure]]s that are created and then immediately consumed by a program.
-The term "deforestation" was originally coined by [[Philip Wadler]] in his paper "Deforestation: transforming programs to eliminate trees"<ref>{{cite journal
+The term "deforestation" was originally coined by [[Philip Wadler]] in his 1990 paper "Deforestation: transforming programs to eliminate trees".<ref>{{cite journal
   | url = http://homepages.inf.ed.ac.uk/wadler/papers/deforest/deforest.ps
   | first = Philip
@@ Line 10: / Line 11: @@
   | pages = 231–248
   | year = 1990
-  | doi = 10.1016/0304-3975(90)90147-A}}</ref>.
+  | doi = 10.1016/0304-3975(90)90147-A
+  | issue = 2| doi-access = free
+  }}</ref>
-DefFUCKEN BITCHES<WE WANT OUR FOREST BACKorestation is typically applied to programs in [[functional programming languages]], particularly [[non-strict programming languages]] such as [[Haskell programming language|Haskell]]. One particular algorithm for deforestation, ''shortcut deforestation''<ref>{{cite conference
+Deforestation is typically applied to programs in [[functional programming languages]], particularly [[non-strict programming languages]] such as [[Haskell programming language|Haskell]]. One particular algorithm for deforestation, ''shortcut deforestation'',<ref>{{cite conference
  | first = Andrew
  | last = Gill
- | coauthors = John Launchbury, Simon Peyton Jones
+ | 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
- | booktitle = Proc. Conf. on Functional Programming Languages and Computer Architecture
+ | book-title = Proc. Conf. on Functional Programming Languages and Computer Architecture
+ | doi = 10.1145/165180.165214
  | year = 1993
- | pages = 223-232}}</ref>, is implemented in the [[Glasgow Haskell Compiler]].<ref>{{cite conference
+ | pages = 223–232}}</ref> is implemented in the [[Glasgow Haskell Compiler]].<ref>{{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}}</ref> Deforestation is closely related to [[escape analysis]].
- | first = Simon
- | last = Peyton Jones
- | coauthors = Andrew Tolmach, C.A.R. Hoare
- | title = Playing by the rules: rewriting as a practical optimization technique in GHC
- | booktitle = Proc. ACM/SIGPLAN Haskell Workshop
- | year = 2001}}</ref>
 == See also ==
@@ Line 31: / Line 30: @@
 == References ==
+{{reflist}}
-<references/>
+{{Compiler optimizations}}
-{{compu-prog-stub}}
-[[Category:Functional programming]]
+[[Category:Compiler optimizations]]
-[[Category:Programming language implementation]]
+[[Category:Implementation of functional programming languages]]
+{{prog-lang-stub}}

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 Use-define chain
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

Latest revision as of 22:11, 7 June 2024

See also[edit]

References[edit]