Editing Graph reduction (section)

== 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]].