Editing Graph reduction

{{Short description|Efficient version of non-strict evaluation}}
{{About|the computer science term|the graph theory use|transitive reduction}}
In [[computer science]], '''graph reduction''' implements an efficient version of non-strict evaluation, an [[evaluation strategy]] where the arguments to a function are not immediately evaluated. This form of non-strict evaluation is also known as [[lazy evaluation]] and used in [[functional programming|functional programming languages]]. The technique was first developed by [[Chris Wadsworth]] in 1971.

== Motivation ==
A simple example of evaluating an arithmetic expression follows:

:<math>
\begin{align}
& {} & &((2+2)+(2+2))+(3+3) \\
& {} &=&((2+2)+(2+2))+ 6 \\
& {} &=&((2+2)+ 4)+6 \\
& {} &=&(4+4)+6 \\
& {} &=&8+6 \\
& {} &=&14
\end{align}
</math>

The above reduction sequence employs a strategy known as [[outermost tree reduction]]. The same expression can be evaluated using [[innermost tree reduction]], yielding the reduction sequence:

:<math>
\begin{align}
& {} &  &((2+2)+(2+2))+(3+3) \\
& {} &= &((2+2)+4)+(3+3) \\
& {} &= &(4+4)+(3+3) \\
& {} &= &(4+4)+6 \\
& {} &= &8+6 \\
& {} &= &14
\end{align}
</math>

Notice that the reduction order is made explicit by the addition of parentheses. This expression could also have been simply evaluated right to left, because addition is an [[associative]] operation.

Represented as a [[Tree data structure|tree]], the expression above looks like this:

[[Image:Expression Tree.svg|300px]]

This is where the term tree reduction comes from.  When represented as a tree, we can think of innermost reduction as working from the bottom up, while outermost works from the top down.

The expression can also be represented as a [[directed acyclic graph]], allowing sub-expressions to be shared:

[[Image:Expression Graph.svg|300px]]

As for trees, outermost and innermost reduction also applies to graphs.  Hence we have '''graph reduction'''.

Now evaluation with outermost graph reduction can proceed as follows:

[[Image:Expression Graph Reduction.svg|200px]]

Notice that evaluation now only requires four steps. Outermost graph reduction is referred to as [[lazy evaluation]] and innermost graph reduction is referred to as [[eager evaluation]].

== Combinator graph reduction ==
'''Combinator graph reduction''' is a fundamental implementation technique for [[functional programming]] languages, in which a program is converted into a [[combinator]] representation which is mapped to a [[directed graph]] [[data structure]] in computer memory, and program execution then consists of rewriting parts of this graph ("reducing" it) so as to move towards useful results.

== History ==
The concept of a graph reduction that allows evaluated values to be shared was first developed by [[Chris Wadsworth]] in his 1971 Ph.D. dissertation.<ref>{{Cite journal |last=Hudak |first=Paul |author-link=Paul Hudak |date=September 1989 |title=Conception, evolution, and application of functional programming languages |journal=ACM Computing Surveys |volume=21 |issue=3 |pages=359–411 |citeseerx=10.1.1.83.6505 |doi=10.1145/72551.72554}}</ref> This dissertation was cited by Peter Henderson and James H. Morris Jr. in 1976 paper, “A lazy evaluator”<ref>{{Cite conference |last=Henderson |first=Peter |last2=Morris |first2=James H. |author2-link=James H. Morris|date=1976 |title=A lazy evaluator |conference=POPL '76: Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages |language=en |publisher=ACM Press |pages=95–103 |doi=10.1145/800168.811543}}</ref> that introduced the notion of lazy evaluation. In 1976 [[David Turner (computer scientist)|David Turner]] incorporated lazy evaluation into [[SASL programming language|SASL]] using combinators.<ref>{{Cite conference |last=Hudak |first=Paul |author-link=Paul Hudak |last2=Hughes |first2=John |author-link2=John Hughes (computer scientist) |last3=Peyton Jones |first3=Simon |author-link3=Simon Peyton Jones |last4=Wadler |first4=Philip |author-link4=Philip Wadler |title=A History of Haskell: Being Lazy with Class |url=http://haskell.org/haskellwiki/History_of_Haskell |book-title=History of Programming Languages Conference 2007}}</ref>
SASL was an early functional programming language first developed by Turner in 1972.

==See also==
*[[Graph reduction machine]]
*[[SECD machine]]

==Notes==

<references/>

==References==
*{{cite book
 |title=Introduction to Functional Programming using Haskell
 |last=Bird|first=Richard
 |publisher=Prentice Hall
 |year=1998
 |isbn=0-13-484346-0
 }}

==Further reading==
*{{cite book |last=Peyton Jones |first=Simon L. |author-link=Simon Peyton Jones |date=1987 |title=The Implementation of Functional Programming Languages |publisher=Prentice Hall |isbn=013453333X |lccn=86020535 |url=https://www.microsoft.com/en-us/research/publication/the-implementation-of-functional-programming-languages/ |access-date=2022-04-15}}

[[Category:Implementation of functional programming languages]]
[[Category:Graph algorithms]]
[[Category:Graph rewriting]]