Represents a symbolic form of an expression.
Its syntax tree is as follows:
E := Var | Constant | E + ... + E | E * ... * E | E / E | log(E)
| abs(E) | exp(E) | sqrt(E) | pow(E, E) | sin(E) | cos(E) | tan(E)
| asin(E) | acos(E) | atan(E) | atan2(E, E) | sinh(E) | cosh(E) | tanh(E)
| min(E, E) | max(E, E) | ceil(E) | floor(E) | if_then_else(F, E, E)
| NaN | uninterpreted_function(name, {v_1, ..., v_n})
In the implementation, Expression directly stores Constant values inline, but in all other cases stores a shared pointer to a const ExpressionCell class that is a super-class of different kinds of symbolic expressions (i.e., ExpressionAdd, ExpressionMul, ExpressionLog, ExpressionSin), which makes it efficient to copy, move, and assign to an Expression.
- Note
- -E is represented as -1 * E internally.
-
A subtraction E1 - E2 is represented as E1 + (-1 * E2) internally.
The following simple simplifications are implemented:
E + 0 -> E
0 + E -> E
E - 0 -> E
E - E -> 0
E * 1 -> E
1 * E -> E
E * 0 -> 0
0 * E -> 0
E / 1 -> E
E / E -> 1
pow(E, 0) -> 1
pow(E, 1) -> E
E * E -> E^2 (= pow(E, 2))
sqrt(E * E) -> |E| (= abs(E))
sqrt(E) * sqrt(E) -> E
Constant folding is implemented:
E(c1) + E(c2) -> E(c1 + c2) // c1, c2 are constants
E(c1) - E(c2) -> E(c1 - c2)
E(c1) * E(c2) -> E(c1 * c2)
E(c1) / E(c2) -> E(c1 / c2)
f(E(c)) -> E(f(c)) // c is a constant, f is a math function
For the math functions which are only defined over a restricted domain (namely, log, sqrt, pow, asin, acos), we check the domain of argument(s), and throw std::domain_error exception if a function is not well-defined for a given argument(s).
Relational operators over expressions (==, !=, <, >, <=, >=) return symbolic::Formula instead of bool. Those operations are declared in formula.h file. To check structural equality between two expressions a separate function, Expression::EqualTo, is provided.
Regarding the arithmetic of an Expression when operating on NaNs, we have the following rules:
- NaN values are extremely rare during typical computations. Because they are difficult to handle symbolically, we will round that up to "must never
occur". We allow the user to form ExpressionNaN cells in a symbolic tree. For example, the user can initialize an Expression to NaN and then overwrite it later. However, evaluating a tree that has NaN in its evaluated sub-trees is an error (see rule (3) below).
- It's still valid for code to check
isnan
in order to fail-fast. So we provide isnan(const Expression&) for the common case of non-NaN value returning False. This way, code can fail-fast with double yet still compile with Expression.
- If there are expressions that embed separate cases (
if_then_else
), some of the sub-expressions may be not used in evaluation when they are in the not-taken case (for NaN reasons or any other reason). Bad values within those not-taken branches does not cause exceptions.
- The isnan check is different than if_then_else. In the latter, the ExpressionNaN is within a dead sub-expression branch. In the former, it appears in an evaluated trunk. That goes against rule (1) where a NaN anywhere in a computation (other than dead code) is an error.
|
class | ExpressionAddFactory |
|
class | ExpressionMulFactory |
|
template<bool > |
struct | internal::Gemm |
|
template<class HashAlgorithm > |
void | hash_append (HashAlgorithm &hasher, const Expression &item) noexcept |
| Implements the hash_append generic hashing concept. More...
|
|
Expression | operator+ (Expression lhs, const Expression &rhs) |
|
Expression & | operator+= (Expression &lhs, const Expression &rhs) |
|
Expression | operator+ (const Expression &e) |
| Provides unary plus operator. More...
|
|
Expression | operator- (Expression lhs, const Expression &rhs) |
|
Expression & | operator-= (Expression &lhs, const Expression &rhs) |
|
Expression | operator- (const Expression &e) |
| Provides unary minus operator. More...
|
|
Expression | operator * (Expression lhs, const Expression &rhs) |
|
Expression & | operator *= (Expression &lhs, const Expression &rhs) |
|
Expression | operator/ (Expression lhs, const Expression &rhs) |
|
Expression & | operator/= (Expression &lhs, const Expression &rhs) |
|
Expression | log (const Expression &e) |
|
Expression | abs (const Expression &e) |
|
Expression | exp (const Expression &e) |
|
Expression | sqrt (const Expression &e) |
|
Expression | pow (const Expression &e1, const Expression &e2) |
|
Expression | sin (const Expression &e) |
|
Expression | cos (const Expression &e) |
|
Expression | tan (const Expression &e) |
|
Expression | asin (const Expression &e) |
|
Expression | acos (const Expression &e) |
|
Expression | atan (const Expression &e) |
|
Expression | atan2 (const Expression &e1, const Expression &e2) |
|
Expression | sinh (const Expression &e) |
|
Expression | cosh (const Expression &e) |
|
Expression | tanh (const Expression &e) |
|
Expression | min (const Expression &e1, const Expression &e2) |
|
Expression | max (const Expression &e1, const Expression &e2) |
|
Expression | clamp (const Expression &v, const Expression &lo, const Expression &hi) |
|
Expression | ceil (const Expression &e) |
|
Expression | floor (const Expression &e) |
|
Expression | if_then_else (const Formula &f_cond, const Expression &e_then, const Expression &e_else) |
| Constructs if-then-else expression. More...
|
|
Expression | uninterpreted_function (std::string name, std::vector< Expression > arguments) |
| Constructs an uninterpreted-function expression with name and arguments . More...
|
|
std::ostream & | operator<< (std::ostream &os, const Expression &e) |
|
void | swap (Expression &a, Expression &b) |
|
bool | is_constant (const Expression &e) |
| Checks if e is a constant expression. More...
|
|
bool | is_constant (const Expression &e, double value) |
| Checks if e is a constant expression representing v . More...
|
|
bool | is_nan (const Expression &e) |
| Checks if e is NaN. More...
|
|
bool | is_variable (const Expression &e) |
| Checks if e is a variable expression. More...
|
|
bool | is_addition (const Expression &e) |
| Checks if e is an addition expression. More...
|
|
bool | is_multiplication (const Expression &e) |
| Checks if e is a multiplication expression. More...
|
|
bool | is_division (const Expression &e) |
| Checks if e is a division expression. More...
|
|
bool | is_log (const Expression &e) |
| Checks if e is a log expression. More...
|
|
bool | is_abs (const Expression &e) |
| Checks if e is an abs expression. More...
|
|
bool | is_exp (const Expression &e) |
| Checks if e is an exp expression. More...
|
|
bool | is_sqrt (const Expression &e) |
| Checks if e is a square-root expression. More...
|
|
bool | is_pow (const Expression &e) |
| Checks if e is a power-function expression. More...
|
|
bool | is_sin (const Expression &e) |
| Checks if e is a sine expression. More...
|
|
bool | is_cos (const Expression &e) |
| Checks if e is a cosine expression. More...
|
|
bool | is_tan (const Expression &e) |
| Checks if e is a tangent expression. More...
|
|
bool | is_asin (const Expression &e) |
| Checks if e is an arcsine expression. More...
|
|
bool | is_acos (const Expression &e) |
| Checks if e is an arccosine expression. More...
|
|
bool | is_atan (const Expression &e) |
| Checks if e is an arctangent expression. More...
|
|
bool | is_atan2 (const Expression &e) |
| Checks if e is an arctangent2 expression. More...
|
|
bool | is_sinh (const Expression &e) |
| Checks if e is a hyperbolic-sine expression. More...
|
|
bool | is_cosh (const Expression &e) |
| Checks if e is a hyperbolic-cosine expression. More...
|
|
bool | is_tanh (const Expression &e) |
| Checks if e is a hyperbolic-tangent expression. More...
|
|
bool | is_min (const Expression &e) |
| Checks if e is a min expression. More...
|
|
bool | is_max (const Expression &e) |
| Checks if e is a max expression. More...
|
|
bool | is_ceil (const Expression &e) |
| Checks if e is a ceil expression. More...
|
|
bool | is_floor (const Expression &e) |
| Checks if e is a floor expression. More...
|
|
bool | is_if_then_else (const Expression &e) |
| Checks if e is an if-then-else expression. More...
|
|
bool | is_uninterpreted_function (const Expression &e) |
| Checks if e is an uninterpreted-function expression. More...
|
|
double | get_constant_value (const Expression &e) |
| Returns the constant value of the constant expression e . More...
|
|
const ExpressionVar & | to_variable (const Expression &e) |
|
const UnaryExpressionCell & | to_unary (const Expression &e) |
|
const BinaryExpressionCell & | to_binary (const Expression &e) |
|
const ExpressionAdd & | to_addition (const Expression &e) |
|
const ExpressionMul & | to_multiplication (const Expression &e) |
|
const ExpressionDiv & | to_division (const Expression &e) |
|
const ExpressionLog & | to_log (const Expression &e) |
|
const ExpressionAbs & | to_abs (const Expression &e) |
|
const ExpressionExp & | to_exp (const Expression &e) |
|
const ExpressionSqrt & | to_sqrt (const Expression &e) |
|
const ExpressionPow & | to_pow (const Expression &e) |
|
const ExpressionSin & | to_sin (const Expression &e) |
|
const ExpressionCos & | to_cos (const Expression &e) |
|
const ExpressionTan & | to_tan (const Expression &e) |
|
const ExpressionAsin & | to_asin (const Expression &e) |
|
const ExpressionAcos & | to_acos (const Expression &e) |
|
const ExpressionAtan & | to_atan (const Expression &e) |
|
const ExpressionAtan2 & | to_atan2 (const Expression &e) |
|
const ExpressionSinh & | to_sinh (const Expression &e) |
|
const ExpressionCosh & | to_cosh (const Expression &e) |
|
const ExpressionTanh & | to_tanh (const Expression &e) |
|
const ExpressionMin & | to_min (const Expression &e) |
|
const ExpressionMax & | to_max (const Expression &e) |
|
const ExpressionCeiling & | to_ceil (const Expression &e) |
|
const ExpressionFloor & | to_floor (const Expression &e) |
|
const ExpressionIfThenElse & | to_if_then_else (const Expression &e) |
|
const ExpressionUninterpretedFunction & | to_uninterpreted_function (const Expression &e) |
|
ExpressionVar & | to_variable (Expression *e) |
|
UnaryExpressionCell & | to_unary (Expression *e) |
|
BinaryExpressionCell & | to_binary (Expression *e) |
|
ExpressionAdd & | to_addition (Expression *e) |
|
ExpressionMul & | to_multiplication (Expression *e) |
|
ExpressionDiv & | to_division (Expression *e) |
|
ExpressionLog & | to_log (Expression *e) |
|
ExpressionAbs & | to_abs (Expression *e) |
|
ExpressionExp & | to_exp (Expression *e) |
|
ExpressionSqrt & | to_sqrt (Expression *e) |
|
ExpressionPow & | to_pow (Expression *e) |
|
ExpressionSin & | to_sin (Expression *e) |
|
ExpressionCos & | to_cos (Expression *e) |
|
ExpressionTan & | to_tan (Expression *e) |
|
ExpressionAsin & | to_asin (Expression *e) |
|
ExpressionAcos & | to_acos (Expression *e) |
|
ExpressionAtan & | to_atan (Expression *e) |
|
ExpressionAtan2 & | to_atan2 (Expression *e) |
|
ExpressionSinh & | to_sinh (Expression *e) |
|
ExpressionCosh & | to_cosh (Expression *e) |
|
ExpressionTanh & | to_tanh (Expression *e) |
|
ExpressionMin & | to_min (Expression *e) |
|
ExpressionMax & | to_max (Expression *e) |
|
ExpressionCeiling & | to_ceil (Expression *e) |
|
ExpressionFloor & | to_floor (Expression *e) |
|
ExpressionIfThenElse & | to_if_then_else (Expression *e) |
|
ExpressionUninterpretedFunction & | to_uninterpreted_function (Expression *e) |
|
Checks structural equality.
Two expressions e1 and e2 are structurally equal when they have the same internal AST(abstract-syntax tree) representation. Please note that we can have two computationally (or extensionally) equivalent expressions which are not structurally equal. For example, consider:
e1 = 2 * (x + y) e2 = 2x + 2y
Obviously, we know that e1 and e2 are evaluated to the same value for all assignments to x and y. However, e1 and e2 are not structurally equal by the definition. Note that e1 is a multiplication expression (is_multiplication(e1) is true) while e2 is an addition expression (is_addition(e2) is true).
One main reason we use structural equality in EqualTo is due to Richardson's Theorem. It states that checking ∀x. E(x) = F(x) is undecidable when we allow sin, asin, log, exp in E and F. Read https://en.wikipedia.org/wiki/Richardson%27s_theorem for details.
Note that for polynomial cases, you can use Expand method and check if two polynomial expressions p1 and p2 are computationally equal. To do so, you check the following:
p1.Expand().EqualTo(p2.Expand())