dlinear
0.0.1
Delta-complete SMT solver for linear programming
|
Represents a symbolic form of an expression. More...
#include <symbolic_expression.h>
Public Member Functions | |
Expression () | |
Default constructor. | |
Expression (const mpq_class &d) | |
Constructs a constant (rational). | |
Expression (const Variable &var) | |
Constructs an expression from var . | |
ExpressionKind | get_kind () const |
Returns expression kind. | |
size_t | get_hash () const |
Returns hash value. | |
const Variables & | GetVariables () const |
Collects variables in expression. | |
bool | EqualTo (const Expression &e) const |
Checks structural equality. | |
bool | Less (const Expression &e) const |
Provides lexicographical ordering between expressions. | |
bool | is_polynomial () const |
Checks if this symbolic expression is convertible to Polynomial. | |
bool | include_ite () const |
Returns true if this symbolic expression includes an ITE (If-Then-Else) expression. | |
mpq_class | Evaluate (const Environment &env=Environment{}) const |
Evaluates under a given environment (by default, an empty environment). | |
Expression | EvaluatePartial (const Environment &env) const |
Partially evaluates this expression using an environment env . | |
Expression | Expand () const |
Expands out products and positive integer powers in expression. | |
Expression | Substitute (const Variable &var, const Expression &e) const |
Returns a copy of this expression replacing all occurrences of var with e . | |
Expression | Substitute (const ExpressionSubstitution &expr_subst, const FormulaSubstitution &formula_subst) const |
Returns a copy of this expression replacing all occurrences of the variables in expr_subst with corresponding expressions in expr_subst and all occurrences of the variables in formula_subst with corresponding formulas in formula_subst . | |
Expression | Substitute (const ExpressionSubstitution &expr_subst) const |
Returns a copy of this expression replacing all occurrences of the variables in expr_subst with corresponding expressions in expr_subst . | |
Expression | Substitute (const FormulaSubstitution &formula_subst) const |
Returns a copy of this expression replacing all occurrences of the variables in formula_subst with corresponding formulas in formula_subst . | |
Expression | Differentiate (const Variable &x) const |
Differentiates this symbolic expression with respect to the variable var . | |
std::string | to_string () const |
Returns string representation of Expression. | |
Expression & | operator++ () |
Provides prefix increment operator (i.e. | |
Expression | operator++ (int) |
Provides postfix increment operator (i.e. | |
Expression & | operator-- () |
Provides prefix decrement operator (i.e. | |
Expression | operator-- (int) |
Provides postfix decrement operator (i.e. | |
Static Public Member Functions | |
static Expression | Zero () |
Returns zero. | |
static Expression | One () |
Returns one. | |
static Expression | Pi () |
Returns Pi, the ratio of a circle’s circumference to its diameter. | |
static Expression | E () |
Return e, the base of natural logarithms. | |
static Expression | NaN () |
Returns NaN (Not-a-Number). | |
static Expression | Infty () |
Returns positive infinity. | |
static Expression | NInfty () |
Returns negative infinity. | |
Friends | |
Expression | operator+ (const Expression &e) |
Provides unary plus operator. | |
Expression | operator- (const Expression &e) |
Provides unary minus operator. | |
Expression | log (const Expression &e) |
Creates an real-constant expression represented by [lb , ub ]. | |
Expression | if_then_else (const Formula &f_cond, const Expression &e_then, const Expression &e_else) |
Constructs if-then-else expression. | |
Expression | uninterpreted_function (const std::string &name, const Variables &vars) |
Constructs an uninterpreted-function expression with name and vars . | |
bool | is_constant (const Expression &e) |
Checks if e is a rational constant expression. | |
bool | is_variable (const Expression &e) |
Checks if e is a variable expression. | |
bool | is_addition (const Expression &e) |
Checks if e is an addition expression. | |
bool | is_multiplication (const Expression &e) |
Checks if e is a multiplication expression. | |
bool | is_division (const Expression &e) |
Checks if e is a division expression. | |
bool | is_log (const Expression &e) |
Checks if e is a log expression. | |
bool | is_abs (const Expression &e) |
Checks if e is an abs expression. | |
bool | is_exp (const Expression &e) |
Checks if e is an exp expression. | |
bool | is_sqrt (const Expression &e) |
Checks if e is a square-root expression. | |
bool | is_pow (const Expression &e) |
Checks if e is a power-function expression. | |
bool | is_sin (const Expression &e) |
Checks if e is a sine expression. | |
bool | is_cos (const Expression &e) |
Checks if e is a cosine expression. | |
bool | is_tan (const Expression &e) |
Checks if e is a tangent expression. | |
bool | is_asin (const Expression &e) |
Checks if e is an arcsine expression. | |
bool | is_acos (const Expression &e) |
Checks if e is an arccosine expression. | |
bool | is_atan (const Expression &e) |
Checks if e is an arctangent expression. | |
bool | is_atan2 (const Expression &e) |
Checks if e is an arctangent2 expression. | |
bool | is_sinh (const Expression &e) |
Checks if e is a hyperbolic-sine expression. | |
bool | is_cosh (const Expression &e) |
Checks if e is a hyperbolic-cosine expression. | |
bool | is_tanh (const Expression &e) |
Checks if e is a hyperbolic-tangent expression. | |
bool | is_min (const Expression &e) |
Checks if e is a min expression. | |
bool | is_max (const Expression &e) |
Checks if e is a max expression. | |
bool | is_if_then_else (const Expression &e) |
Checks if e is an if-then-else expression. | |
bool | is_uninterpreted_function (const Expression &e) |
Checks if e is an uninterpreted-function expression. | |
const ExpressionConstant * | to_constant (const Expression &e) |
Casts e of Expression to const ExpressionConstant*. | |
const ExpressionInfty * | to_infty (const Expression &e) |
Casts e of Expression to const ExpressionInfty*. | |
const ExpressionVar * | to_variable (const Expression &e) |
Casts e of Expression to const ExpressionVar*. | |
const UnaryExpressionCell * | to_unary (const Expression &e) |
Casts e of Expression to const UnaryExpressionCell*. | |
const BinaryExpressionCell * | to_binary (const Expression &e) |
Casts e of Expression to const BinaryExpressionCell*. | |
const ExpressionAdd * | to_addition (const Expression &e) |
Casts e of Expression to const ExpressionAdd*. | |
ExpressionAdd * | to_addition (Expression &e) |
Casts e of Expression to ExpressionAdd* . | |
const ExpressionMul * | to_multiplication (const Expression &e) |
Casts e of Expression to const ExpressionMul*. | |
ExpressionMul * | to_multiplication (Expression &e) |
Casts e of Expression to ExpressionMul* . | |
const ExpressionDiv * | to_division (const Expression &e) |
Casts e of Expression to const ExpressionDiv*. | |
const ExpressionLog * | to_log (const Expression &e) |
Casts e of Expression to const ExpressionLog*. | |
const ExpressionAbs * | to_abs (const Expression &e) |
Casts e of Expression to const ExpressionAbs*. | |
const ExpressionExp * | to_exp (const Expression &e) |
Casts e of Expression to const ExpressionExp*. | |
const ExpressionSqrt * | to_sqrt (const Expression &e) |
Casts e of Expression to const ExpressionSqrt*. | |
const ExpressionPow * | to_pow (const Expression &e) |
Casts e of Expression to const ExpressionPow*. | |
const ExpressionSin * | to_sin (const Expression &e) |
Casts e of Expression to const ExpressionSin*. | |
const ExpressionCos * | to_cos (const Expression &e) |
Casts e of Expression to const ExpressionCos*. | |
const ExpressionTan * | to_tan (const Expression &e) |
Casts e of Expression to const ExpressionTan*. | |
const ExpressionAsin * | to_asin (const Expression &e) |
Casts e of Expression to const ExpressionAsin*. | |
const ExpressionAcos * | to_acos (const Expression &e) |
Casts e of Expression to const ExpressionAcos*. | |
const ExpressionAtan * | to_atan (const Expression &e) |
Casts e of Expression to const ExpressionAtan*. | |
const ExpressionAtan2 * | to_atan2 (const Expression &e) |
Casts e of Expression to const ExpressionAtan2*. | |
const ExpressionSinh * | to_sinh (const Expression &e) |
Casts e of Expression to const ExpressionSinh*. | |
const ExpressionCosh * | to_cosh (const Expression &e) |
Casts e of Expression to const ExpressionCosh*. | |
const ExpressionTanh * | to_tanh (const Expression &e) |
Casts e of Expression to const ExpressionTanh*. | |
const ExpressionMin * | to_min (const Expression &e) |
Casts e of Expression to const ExpressionMin*. | |
const ExpressionMax * | to_max (const Expression &e) |
Casts e of Expression to const ExpressionMax*. | |
const ExpressionIfThenElse * | to_if_then_else (const Expression &e) |
Casts e of Expression to const ExpressionIfThenElse*. | |
const ExpressionUninterpretedFunction * | to_uninterpreted_function (const Expression &e) |
Casts e of Expression to const ExpressionUninterpretedFunction* . | |
Represents a symbolic form of an expression.
Its syntax tree is as follows:
E := Var | Constant(mpq_class) | 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) | if_then_else(F, E, E) | NaN | infinity | uninterpreted_function(name, {v_1, ..., v_n})
In the implementation, Expression is a simple wrapper including a pointer to ExpressionCell class which is a super-class of different kinds of symbolic expressions (i.e. ExpressionAdd, ExpressionMul, ExpressionLog, ExpressionSin).
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 symbolic_formula.h file. To check structural equality between two expressions a separate function, Expression::EqualTo, is provided.
Definition at line 162 of file symbolic_expression.h.
dlinear::drake::symbolic::Expression::Expression | ( | ) |
Default constructor.
It constructs Zero().
dlinear::drake::symbolic::Expression::Expression | ( | const Variable & | var | ) |
Constructs an expression from var
.
var
is neither a dummy nor a BOOLEAN variable. Expression dlinear::drake::symbolic::Expression::Differentiate | ( | const Variable & | x | ) | const |
Differentiates this symbolic expression with respect to the variable var
.
std::runtime_error | if it is not differentiable. |
bool dlinear::drake::symbolic::Expression::EqualTo | ( | const Expression & | e | ) | const |
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() - p2.Expand()).EqualTo(0).
mpq_class dlinear::drake::symbolic::Expression::Evaluate | ( | const Environment & | env = Environment{} | ) | const |
Evaluates under a given environment (by default, an empty environment).
std::runtime_error | if NaN is detected during evaluation. |
Expression dlinear::drake::symbolic::Expression::EvaluatePartial | ( | const Environment & | env | ) | const |
Partially evaluates this expression using an environment env
.
Internally, this method promotes env
into a substitution (Variable → Expression) and call Evaluate::Substitute with it.
std::runtime_error | if NaN is detected during evaluation. |
Expression dlinear::drake::symbolic::Expression::Expand | ( | ) | const |
Expands out products and positive integer powers in expression.
For example, (x + 1) * (x - 1)
is expanded to x^2 - 1
and (x + y)^2
is expanded to x^2 + 2xy + y^2
. Note that Expand applies recursively to sub-expressions. For instance, sin(2 * (x + y))
is expanded to sin(2x + 2y)
. It also simplifies "division by constant" cases. See "symbolic/test/symbolic_expansion_test.cc" to find the examples.
std::runtime_error | if NaN is detected during expansion. |
bool dlinear::drake::symbolic::Expression::Less | ( | const Expression & | e | ) | const |
Provides lexicographical ordering between expressions.
This function is used as a compare function in map<Expression> and set<Expression> via std::less<dlinear::drake::symbolic::Expression>.
Expression & dlinear::drake::symbolic::Expression::operator++ | ( | ) |
Provides prefix increment operator (i.e.
++x).
Expression dlinear::drake::symbolic::Expression::operator++ | ( | int | ) |
Provides postfix increment operator (i.e.
x++).
Expression & dlinear::drake::symbolic::Expression::operator-- | ( | ) |
Provides prefix decrement operator (i.e.
–x).
Expression dlinear::drake::symbolic::Expression::operator-- | ( | int | ) |
Provides postfix decrement operator (i.e.
x–).
Expression dlinear::drake::symbolic::Expression::Substitute | ( | const ExpressionSubstitution & | expr_subst | ) | const |
Returns a copy of this expression replacing all occurrences of the variables in expr_subst
with corresponding expressions in expr_subst
.
Substitute(expr_subst, {})
. std::runtime_error | if NaN is detected during substitution. |
Expression dlinear::drake::symbolic::Expression::Substitute | ( | const ExpressionSubstitution & | expr_subst, |
const FormulaSubstitution & | formula_subst ) const |
Returns a copy of this expression replacing all occurrences of the variables in expr_subst
with corresponding expressions in expr_subst
and all occurrences of the variables in formula_subst
with corresponding formulas in formula_subst
.
Note that the substitutions occur simultaneously. For example, (x / y).Substitute({{x, y}, {y, x}}, {}) gets (y / x).
std::runtime_error | if NaN is detected during substitution. |
Expression dlinear::drake::symbolic::Expression::Substitute | ( | const FormulaSubstitution & | formula_subst | ) | const |
Returns a copy of this expression replacing all occurrences of the variables in formula_subst
with corresponding formulas in formula_subst
.
Substitute({}, formula_subst)
. std::runtime_error | if NaN is detected during substitution. |
Expression dlinear::drake::symbolic::Expression::Substitute | ( | const Variable & | var, |
const Expression & | e ) const |
Returns a copy of this expression replacing all occurrences of var
with e
.
std::runtime_error | if NaN is detected during substitution. |
|
friend |
Constructs if-then-else expression.
if_then_else(cond, expr_then, expr_else)
The value returned by the above if-then-else expression is expr_then
if cond
is evaluated to true. Otherwise, it returns expr_else
.
The semantics is similar to the C++'s conditional expression constructed by its ternary operator, ?:. However, there is a key difference between the C++'s conditional expression and our
if_then_else
expression in a way the arguments are evaluated during the construction.
cond ? expr_then : expr_else
, the then expression expr_then
(respectively, the else expression expr_else
) is only evaluated when the conditional expression cond
is evaluated to true (respectively, when cond
is evaluated to false).if_then_else(cond, expr_then,
expr_else)
, however, both arguments expr_then
and expr_else
are evaluated first and then passed to the if_then_else
function. min, max, abs
math functions using if_then_else
expression, it is highly recommended to use the provided native definitions for them because it allows solvers to detect specific math functions and to have a room for special optimizations.
|
friend |
Creates an real-constant expression represented by [lb
, ub
].
use_lb_as_representative
is used to select its representative value. If it is true, lb
is used. Otherwise, ub
is used.
|
friend |
Casts e
of Expression to const
ExpressionAbs*.
*
(e.ptr_) is of ExpressionAbs
.
|
friend |
Casts e
of Expression to const
ExpressionAcos*.
*
(e.ptr_) is of ExpressionAcos
.
|
friend |
Casts e
of Expression to const
ExpressionAdd*.
*
(e.ptr_) is of ExpressionAdd
.
|
friend |
Casts e
of Expression to ExpressionAdd*
.
*
(e.ptr_) is of ExpressionAdd
.
|
friend |
Casts e
of Expression to const
ExpressionAsin*.
*
(e.ptr_) is of ExpressionAsin
.
|
friend |
Casts e
of Expression to const
ExpressionAtan*.
*
(e.ptr_) is of ExpressionAtan
.
|
friend |
Casts e
of Expression to const
ExpressionAtan2*.
*
(e.ptr_) is of ExpressionAtan2
.
|
friend |
Casts e
of Expression to const
BinaryExpressionCell*.
*
(e.ptr_) is of BinaryExpressionCell
.
|
friend |
Casts e
of Expression to const
ExpressionConstant*.
*
(e.ptr_) is of ExpressionConstant
.
|
friend |
Casts e
of Expression to const
ExpressionCos*.
*
(e.ptr_) is of ExpressionCos
.
|
friend |
Casts e
of Expression to const
ExpressionCosh*.
*
(e.ptr_) is of ExpressionCosh
.
|
friend |
Casts e
of Expression to const
ExpressionDiv*.
*
(e.ptr_) is of ExpressionDiv
.
|
friend |
Casts e
of Expression to const
ExpressionExp*.
*
(e.ptr_) is of ExpressionExp
.
|
friend |
Casts e
of Expression to const
ExpressionIfThenElse*.
*
(e.ptr_) is of ExpressionIfThenElse
.
|
friend |
Casts e
of Expression to const
ExpressionInfty*.
*
(e.ptr_) is of ExpressionInfty
.
|
friend |
Casts e
of Expression to const
ExpressionLog*.
*
(e.ptr_) is of ExpressionLog
.
|
friend |
Casts e
of Expression to const
ExpressionMax*.
*
(e.ptr_) is of ExpressionMax
.
|
friend |
Casts e
of Expression to const
ExpressionMin*.
*
(e.ptr_) is of ExpressionMin
.
|
friend |
Casts e
of Expression to const
ExpressionMul*.
*
(e.ptr_) is of ExpressionMul
.
|
friend |
Casts e
of Expression to ExpressionMul*
.
*
(e.ptr_) is of ExpressionMul
.
|
friend |
Casts e
of Expression to const
ExpressionPow*.
*
(e.ptr_) is of ExpressionPow
.
|
friend |
Casts e
of Expression to const
ExpressionSin*.
*
(e.ptr_) is of ExpressionSin
.
|
friend |
Casts e
of Expression to const
ExpressionSinh*.
*
(e.ptr_) is of ExpressionSinh
.
|
friend |
Casts e
of Expression to const
ExpressionSqrt*.
*
(e.ptr_) is of ExpressionSqrt
.
|
friend |
Casts e
of Expression to const
ExpressionTan*.
*
(e.ptr_) is of ExpressionTan
.
|
friend |
Casts e
of Expression to const
ExpressionTanh*.
*
(e.ptr_) is of ExpressionTanh
.
|
friend |
Casts e
of Expression to const
UnaryExpressionCell*.
*
(e.ptr_) is of UnaryExpressionCell
.
|
friend |
Casts e
of Expression to const ExpressionUninterpretedFunction*
.
*
(e.ptr_) is of ExpressionUninterpretedFunction
.
|
friend |
Casts e
of Expression to const
ExpressionVar*.
*
(e.ptr_) is of ExpressionVar
.
|
friend |
Constructs an uninterpreted-function expression with name
and vars
.
An uninterpreted function is an opaque function that has no other property than its name and a set of its arguments. This is useful to applications where it is good enough to provide abstract information of a function without exposing full details. Declaring sparsity of a system is a typical example.
See also FunctionalForm::Arbitrary(Variables v)
which shares the same motivation.