Graph reduction

From Wikipedia, the free encyclopedia

In computing, graph reduction avoids duplicated computation of equivalent sub-expressions of an expression. When evaluating the expression of a formula given in syntactic notation of some formal system (or "calculus"), it becomes necessary to consider the order and strategy for reducing the expression to its simplest form (or "value", hence "evaluation").

A simple example of evaluating an arithmetic expression follows:

 ((2+2)+(2+2))+(3+3)
=((2+2)+(2+2))+(6) 
=((2+2)+ 4)+6
=(4+4)+6
=8+6
=14

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:

 ((2+2)+(2+2))+(3+3)
=((2+2)+4)+(3+3)
=(4+4)+(3+3)
=(4+4)+6
=8+6
=14

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, the expression above looks like this:

          +
       /     \
      +       +
    /   \    / \
   +     +  3   3
  / \   / \
 2   2 2   2

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 graph, allowing sub-expressions to be shared:

          +
       /     \
      +       +
    _/ \_    / \
     \ /    3   3
      +    
     / \
    2   2

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:

 (_ + _)+(3+3)
   \ /
  (2+2)
      
=(_ + _)+6
   \ /
  (2+2)
      
=(_ + _)+6       
   \ /
    4 
=8+6
=14

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.

[edit] References

• Bird, Richard (1998). Introduction to Functional Programming using Haskell. Prentice Hall. ISBN 0-13-484346-0.