NormalExpression

java.lang.Object
- cetus.analysis.NormalExpression

All Implemented Interfaces:

java.lang.Comparable, java.util.Comparator<NormalExpression>

Deprecated.
```
@Deprecated
public class NormalExpression
extends java.lang.Object
implements java.lang.Comparable, java.util.Comparator<NormalExpression>
```
NormalExpression supports normalization and simplification of expressions. It internally transforms a given expression to a normalized form so that each operand of a commutative and associative operation is located at the same height in the tree representation; in other words, it converts a binary tree to a n-ary tree. This internal representation makes the simplification algorithm easier and the result of the simplification is converted back to the original internal representation of Cetus.
Like its predecessor Polaris, a key feature of Cetus is the ability to reason about the represented program in symbolic terms. For example, compiler analyses and optimizations at the source level often require the expressions in the program to be in a simplified form. A specific example is data dependence analysis that collects the coefficients of affine subscript expressions, which are passed to the underlying data dependence test package. Cetus has functionalities that ease the manipulation of expressions for pass writers. The following example shows how to invoke the simplifier. The simplifier returns a new copy of the original expression that was converted to a normalized form.
```
 Expression e = ...
 e = NormalExpression.simplify(e);
 
```
It is also possible for users to invoke individual simplification technique for their own purposes. The following examples show the functionality of the individual simplification technique. See the javadoc page or the source code to learn how to invoke each technique individually.
```
 1+2*a+4-a --> 5+a (folding)
 a*(b+c) --> a*b+a*c (distribution)
 (a*2)/(8*c) --> a/(4*c) (division)
 
```

Method Summary

Methods
Modifier and Type	Method and Description
`static Expression`	`add(Expression e1, Expression e2)` Deprecated. Returns addition of the two expressions with simplification.
`static Expression`	`and(Expression e1, Expression e2)` Deprecated. Returns a binary expression e1&&e2 with simplification.
`static Expression`	`binary(Expression e1, java.lang.String op, Expression e2)` Deprecated.
`static int`	`compare(Expression e1, Expression e2)` Deprecated. Compares the two expressions based on their normal forms.
`int`	`compare(NormalExpression re1, NormalExpression re2)` Deprecated. Compares tow normal expressions; `Comparator` requires this method.
`int`	`compareTo(java.lang.Object o)` Deprecated. Compares this normal expression to the specified object.
`static Expression`	`divide(Expression e1, Expression e2)` Deprecated. Returns division of two expressions with simplification.
`static Expression`	`eq(Expression e1, Expression e2)` Deprecated. Returns an equality expression e1==e2 with simplification.
`boolean`	`equals(java.lang.Object o)` Deprecated. Checks if this normal expression is equal to the specified object.
`static Expression`	`getClosedFormSum(Expression lb, Expression ub, Expression e, Identifier id)` Deprecated. Returns the closed form of the given summation parameters, sum(e) s.t.
`static Expression`	`getCoefficient(Expression e, Identifier id)` Deprecated. Returns the symbolic coefficient of the given identifier in the expression.
`static java.util.List<Expression>`	`getCoefficient(Expression e, java.util.List<Identifier> id_list)` Deprecated. Returns the list of coefficient with respect to the given set of identifiers.
`static long`	`getConstantCoefficient(Expression e)` Deprecated. Returns the constant term in the simplified expression.
`static Expression`	`getConstantCoefficient(Expression e, java.util.List<Identifier> id_list)` Deprecated. Returns the constant term with respect to the given set of variables.
`static java.util.List<Expression>`	`getPolynomialCoef(Expression e, Identifier id)` Deprecated. Returns a list of expressions which contains coefficients of n-th terms when the given id is the basis.
`static java.util.List<Identifier>`	`getVariableList(Expression e)` Deprecated. Returns the list of variables if the given expression is affine.
`static boolean`	`isAffine(Expression e, java.util.List<Identifier> id_list)` Deprecated. Checks if the given expression is an affine expression with respect to the given set of identifiers.
`static Expression`	`multiply(Expression e1, Expression e2)` Deprecated. Returns multiplication of two expressions with simplification.
`static Expression`	`negate(Expression e)` Deprecated. Returns a logically negated expression of the given expression.
`static Expression`	`or(Expression e1, Expression e2)` Deprecated. Returns a binary expression e1\|\|e2 with simplification.
`static Expression`	`power(Expression e, int p)` Deprecated. Returns the given expression's p-th power.
`static void`	`runtest(Program prog)` Deprecated.
`static Expression`	`simplify(Expression e)` Deprecated. Returns a normalized(simplified) expression of an `Expression`.
`static Expression`	`simplify(Expression e, java.lang.String opt)` Deprecated. Returns a normalized expression of an `Expression` after applying a specific option.
`static Expression`	`subtract(Expression e1, Expression e2)` Deprecated. Returns subtraction of two expressions with simplification.
`java.lang.String`	`toString()` Deprecated. Returns the string format of the normal expression (for debugging).

Methods inherited from class java.lang.Object
getClass, hashCode, notify, notifyAll, wait, wait, wait

- Method Detail
  - simplify
```
public static Expression simplify(Expression e)
```
    Deprecated.
    
    Returns a normalized(simplified) expression of an Expression. It is important to notice that this method returns a normalized form and this transformation may or may not result in reduced complexity in the expression. Normalized expressions can be useful in analysis passes by imposing a certain orders in the expression. Pass writers may be able to customize the normalization process with simplify(Expression,String).
    
    Parameters:
    e - the Expression object to be normalized.
    
    Returns:
    the normalized form of the expression e.
    See Also:
    simplify(Expression, String)
  - simplify
```
public static Expression simplify(Expression e,
                  java.lang.String opt)
```
    Deprecated.
    Returns a normalized expression of an Expression after applying a specific option. These options include:
    - "FOLD" , expression folding, e.g. 1-2+a+2*a -> -1+3*a
    - "DIST" , expression distribution, e.g. 2*(a+b) -> 2*a+2*b
    - "DIV" , expression division/mod, e.g. a*b/a -> b
    - "LOGIC", logical expression simplification
    Parameters:
    e - the Expression object to be normalized.
    opt - the normalization option.
    
    Returns:
    the normalized form of the expression e.
  - compare
```
public static int compare(Expression e1,
          Expression e2)
```
    Deprecated.
    
    Compares the two expressions based on their normal forms.
    
    Parameters:
    e1 - the first expression.
    e2 - the second expression.
    
    Returns:
    0 if they are equal, -1 if e1 contains less symbolic variables, 1 otherwise.
  - binary
```
public static Expression binary(Expression e1,
                java.lang.String op,
                Expression e2)
```
    Deprecated.
  - add
```
public static Expression add(Expression e1,
             Expression e2)
```
    Deprecated.
    
    Returns addition of the two expressions with simplification.
    
    Parameters:
    e1 - the first operand of addition.
    e2 - the second operand of addition.
    
    Returns:
    the result of addition.
  - subtract
```
public static Expression subtract(Expression e1,
                  Expression e2)
```
    Deprecated.
    
    Returns subtraction of two expressions with simplification.
    
    Parameters:
    e1 - the first operand of subtraction.
    e2 - the second operand of subtraction.
    
    Returns:
    the result of subtraction.
  - multiply
```
public static Expression multiply(Expression e1,
                  Expression e2)
```
    Deprecated.
    
    Returns multiplication of two expressions with simplification.
    
    Parameters:
    e1 - the first operand of multiplication.
    e2 - the second operand of multiplication.
    
    Returns:
    the result of multiplication.
  - divide
```
public static Expression divide(Expression e1,
                Expression e2)
```
    Deprecated.
    
    Returns division of two expressions with simplification.
    
    Parameters:
    e1 - the first operand of division.
    e2 - the second operand of division.
    
    Returns:
    the result of division.
  - power
```
public static Expression power(Expression e,
               int p)
```
    Deprecated.
    
    Returns the given expression's p-th power.
  - negate
```
public static Expression negate(Expression e)
```
    Deprecated.
    
    Returns a logically negated expression of the given expression.
    
    Parameters:
    e - the input expression.
    
    Returns:
    the negated expression.
  - eq
```
public static Expression eq(Expression e1,
            Expression e2)
```
    Deprecated.
    
    Returns an equality expression e1==e2 with simplification.
    
    Parameters:
    e1 - the first expression.
    e2 - the second expression.
    
    Returns:
    the resulting expression.
  - and
```
public static Expression and(Expression e1,
             Expression e2)
```
    Deprecated.
    
    Returns a binary expression e1&&e2 with simplification.
    
    Parameters:
    e1 - the first expression.
    e2 - the second expression.
    
    Returns:
    the resulting expression.
  - or
```
public static Expression or(Expression e1,
            Expression e2)
```
    Deprecated.
    
    Returns a binary expression e1||e2 with simplification.
    
    Parameters:
    e1 - the first expression
    e2 - the second expression
    
    Returns:
    the resulting expression
  - toString
```
public java.lang.String toString()
```
    Deprecated.
    
    Returns the string format of the normal expression (for debugging).
    
    Overrides:
    
    toString in class java.lang.Object
    
    Returns:
    the string format of the normal expression.
  - compareTo
```
public int compareTo(java.lang.Object o)
```
    Deprecated.
    
    Compares this normal expression to the specified object.
    
    Specified by:
    
    compareTo in interface java.lang.Comparable
    
    Parameters:
    o - the object compared to.
    
    Returns:
    the integer result of the comparison.
  - equals
```
public boolean equals(java.lang.Object o)
```
    Deprecated.
    
    Checks if this normal expression is equal to the specified object.
    
    Specified by:
    
    equals in interface java.util.Comparator<NormalExpression>
    
    Overrides:
    
    equals in class java.lang.Object
    
    Parameters:
    o - the object compared to.
    
    Returns:
    true if they are normalized to the same expression, false otherwise.
  - compare
```
public int compare(NormalExpression re1,
          NormalExpression re2)
```
    Deprecated.
    
    Compares tow normal expressions; Comparator requires this method.
    
    Specified by:
    
    compare in interface java.util.Comparator<NormalExpression>
    
    Parameters:
    re1 - the first normal expression.
    re2 - the second normal expression.
    
    Returns:
    the integer result of the comparison.
  - getConstantCoefficient
```
public static long getConstantCoefficient(Expression e)
```
    Deprecated.
    
    Returns the constant term in the simplified expression.
    
    Parameters:
    e - the expression to be examined.
    
    Returns:
    the constant term in "long" type.
  - getConstantCoefficient
```
public static Expression getConstantCoefficient(Expression e,
                                java.util.List<Identifier> id_list)
```
    Deprecated.
    
    Returns the constant term with respect to the given set of variables.
    
    Parameters:
    e - the expression to be examined.
    id_list - the list of variables (identifiers).
    
    Returns:
    the symbolic constant term.
  - getCoefficient
```
public static Expression getCoefficient(Expression e,
                        Identifier id)
```
    Deprecated.
    
    Returns the symbolic coefficient of the given identifier in the expression.
    
    Parameters:
    e - the expression to be examined.
    id - the identifier.
    
    Returns:
    the symbolic coefficient of the identifier, null if the expression is too complicated.
  - getCoefficient
```
public static java.util.List<Expression> getCoefficient(Expression e,
                                        java.util.List<Identifier> id_list)
```
    Deprecated.
    
    Returns the list of coefficient with respect to the given set of identifiers. The last element of the returned list is symbolic constant coefficient.
    
    Parameters:
    e - the expression to be examined.
    id_list - the list of identifiers.
    
    Returns:
    the list of coefficients.
  - getVariableList
```
public static java.util.List<Identifier> getVariableList(Expression e)
```
    Deprecated.
    
    Returns the list of variables if the given expression is affine.
    
    Parameters:
    e - the expression to be examined.
    
    Returns:
    the list of variables if e is affine, null otherwise.
  - isAffine
```
public static boolean isAffine(Expression e,
               java.util.List<Identifier> id_list)
```
    Deprecated.
    
    Checks if the given expression is an affine expression with respect to the given set of identifiers.
    
    Parameters:
    e - the expression to be examined.
    id_list - the list of identifiers.
    
    Returns:
    true if it is affine, false otherwise.
  - getClosedFormSum
```
public static Expression getClosedFormSum(Expression lb,
                          Expression ub,
                          Expression e,
                          Identifier id)
```
    Deprecated.
    
    Returns the closed form of the given summation parameters, sum(e) s.t. 0<lb<=id<=ub. Computation is based on Bernoulli numbers. For now, assume the given constraints holds when this method is called. We can use range information to assure this assumption in the future.
  - getPolynomialCoef
```
public static java.util.List<Expression> getPolynomialCoef(Expression e,
                                           Identifier id)
```
    Deprecated.
    
    Returns a list of expressions which contains coefficients of n-th terms when the given id is the basis. e.g.) (2*i*i+1-i,i) returns [1, -1, 2].
    
    Parameters:
    e - the input expression.
    id - the basis variable.
    
    Returns:
    the list of coefficients.
  - runtest
```
public static void runtest(Program prog)
```
    Deprecated.

Class NormalExpression

Method Summary

Methods inherited from class java.lang.Object

Method Detail

simplify

simplify

compare

binary

add

subtract

multiply

divide

power

negate

eq

and

or

toString

compareTo

equals

compare

getConstantCoefficient

getConstantCoefficient

getCoefficient

getCoefficient

getVariableList

isAffine

getClosedFormSum

getPolynomialCoef

runtest