Redundant Computations

The objective of this code-along is to develop skills in restructuring expressions. The evaluation of an expression is performed through a sequence of computations. In some cases, such sequences contain redundant computations. When this happens variables can be declared to store the results of such computations.

The focus of this lesson is to use commutative and associative properties of operators to

1. Identify a reduntant sub-expression. In the examples below, reduntant sub-expressions are highlighted.
2. Create a let-block containing val declarations corresponding to redundant sub-expressions.
3. Rewrite: In the body of the let-block write an expression equivalent to the original expression. The expression in the let-block body should contain no redundant sub-expressions. This expression can be obtained by rewriting, whenever possible, a sub-expression to a corresponding variable that has been defined within the let-block.

Commutativity

Associativity

Idempotence

Examples

In the table below, the left column contains expressions (written in SML) which contain redundant computations. The right column contains corresponding expressions in which redundant computations are eliminated by storing results in variables.

let
    val x = 1 + 2 + 3;
in 
    x + x 
end  

let
    val x = 1 + 2;
in 
    x + x 
end    

let
    val x = 1 + 2;
in 
    x + x 
end

let
    val x1 = 1 + 1;
    val x2 = x1 + x1;
in 
    x2 + x2
end  

let
    val x1 = 1 + 2; 
    val x2 = x1 + 3;
in 
    x2 * x1 + x2 
end  

let
    val x1 = 1 + 2;
    val x2= x1 + 3;
in 
    (x2 + x2) * x1 + x2
end          

let
    val x = 1 + 2 > 2;
    val y = 3 > 4;   
in 
    (x andalso y) 
    orelse 
    (x andalso y)  
end    

let
  val x1 = 1 + 2;
  val x2= x1 + 3;
in 
  x1 > 2 andalso x2 > 4
end