gray kangaroo

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

x + y = y + x x * y = y * x x < y = y > x

x > y = y < x

x <= y = y >= x

x >= y = y <= x

Associativity

(x + y) + z = x + (y + z) (x * y) * z = x * (y * z)

Idempotence

x and x = x
x or x = x

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.

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