fmatvec  0.0.0
Fast Matrix/Vector Library
ast.h
1 #ifndef _FMATVEC_AST_H_
2 #define _FMATVEC_AST_H_
3 
4 #include <vector>
5 #include <map>
6 #include <memory>
7 #include <boost/uuid/uuid.hpp>
8 
9 // the following two lines are a workaround for a bug in boost 1.69
10 #define BOOST_PENDING_INTEGER_LOG2_HPP
11 #include <boost/integer/integer_log2.hpp>
12 
13 #include <boost/uuid/uuid_generators.hpp>
14 #include <boost/math/special_functions/sign.hpp>
15 #include <fmatvec/types.h>
16 #include <fmatvec/stream.h>
17 
18 namespace fmatvec {
19 
20 // forward declarations
21 
22 class IndependentVariable;
23 
24 namespace AST {
25  class Vertex;
26  class Symbol;
27  class Operation;
28  template<class T> class Constant;
29 }
30 
36 class FMATVEC_EXPORT SymbolicExpression : public std::shared_ptr<const AST::Vertex> {
37  friend class AST::Operation;
38  friend class AST::Constant<int>;
39  friend class AST::Constant<double>;
40  friend FMATVEC_EXPORT SymbolicExpression parDer(const SymbolicExpression &dep, const IndependentVariable &indep);
41  friend FMATVEC_EXPORT double eval(const SymbolicExpression &x);
42  friend FMATVEC_EXPORT SymbolicExpression subst(const SymbolicExpression &se, const IndependentVariable& a, const SymbolicExpression &b);
43  protected:
44  template<class T> SymbolicExpression(const shared_ptr<T> &x);
45 #ifndef SWIG
46  static const struct ConstructSymbol{} constructSymbol; // just used for tag dispatching
47 #endif
48  SymbolicExpression(ConstructSymbol);
49 
50  // do not allow to call these functions inherited from std::shared_ptr
51  using std::shared_ptr<const AST::Vertex>::get;
52  using std::shared_ptr<const AST::Vertex>::operator*;
53  using std::shared_ptr<const AST::Vertex>::operator->;
54  public:
58  SymbolicExpression(const std::string &str);
60  SymbolicExpression(int x);
62  SymbolicExpression(double x);
63 
67  static void garbageCollect();
68 
69  // default ctors and assignment operators
70  SymbolicExpression(const SymbolicExpression& x) = default;
72  SymbolicExpression& operator=(const SymbolicExpression& x) = default;
73  SymbolicExpression& operator=(SymbolicExpression&& x) = default;
74  ~SymbolicExpression() = default;
75 
76  // operators
77 #ifndef SWIG
78  SymbolicExpression operator+(const SymbolicExpression &b) const;
79  SymbolicExpression operator-(const SymbolicExpression &b) const;
80  SymbolicExpression operator*(const SymbolicExpression &b) const;
81  SymbolicExpression operator/(const SymbolicExpression &b) const;
82 #endif
83  SymbolicExpression operator-() const;
84  SymbolicExpression& operator+=(const SymbolicExpression &b);
85  SymbolicExpression& operator-=(const SymbolicExpression &b);
86  SymbolicExpression& operator*=(const SymbolicExpression &b);
87  SymbolicExpression& operator/=(const SymbolicExpression &b);
88 
89  // We implement operator<<= to be able to use SymbolicExpression fully equivalent to the vector/matrix classes
90  // which have a assign method which redimension before assigning. Redimensioning is not required for a scalar
91  // type like assign
92  SymbolicExpression& operator<<=(const SymbolicExpression &src);
93 
94 #if !defined(NDEBUG) && !defined(SWIG)
95  static unsigned long evalOperationsCount;
96 #endif
97 };
98 
102 class FMATVEC_EXPORT IndependentVariable : public SymbolicExpression {
103  friend class AST::Symbol;
104  friend FMATVEC_EXPORT std::istream& operator>>(std::istream& s, IndependentVariable &v);
105  public:
109  IndependentVariable(const std::string &str);
110 
111 #ifndef SWIG
112  inline IndependentVariable& operator^=(double x);
114 #endif
115 
116  private:
117  IndependentVariable(const shared_ptr<const AST::Symbol> &x);
118 };
119 
120 // define the operator results of SymbolicExpression and IndependentVariable with other AT types.
121 FMATVEC_OPERATORRESULT1(SymbolicExpression, SymbolicExpression)
122 
123 FMATVEC_OPERATORRESULT2(SymbolicExpression, int, SymbolicExpression)
124 FMATVEC_OPERATORRESULT2(SymbolicExpression, double, SymbolicExpression)
125 
126 FMATVEC_OPERATORRESULT1(IndependentVariable, SymbolicExpression)
127 
128 FMATVEC_OPERATORRESULT2(IndependentVariable, int, SymbolicExpression)
129 FMATVEC_OPERATORRESULT2(IndependentVariable, double, SymbolicExpression)
131 
132 // Some member function definition of SymbolicExpression/IndependentVariable are moved to the end of this file
133 // since they need the defintion of the other class defined in this file.
134 
135 FMATVEC_EXPORT SymbolicExpression operator+(double a, const SymbolicExpression &b);
136 FMATVEC_EXPORT SymbolicExpression operator-(double a, const SymbolicExpression &b);
137 FMATVEC_EXPORT SymbolicExpression operator*(double a, const SymbolicExpression &b);
138 FMATVEC_EXPORT SymbolicExpression operator/(double a, const SymbolicExpression &b);
139 FMATVEC_EXPORT SymbolicExpression operator+(int a, const SymbolicExpression &b);
140 FMATVEC_EXPORT SymbolicExpression operator-(int a, const SymbolicExpression &b);
141 FMATVEC_EXPORT SymbolicExpression operator*(int a, const SymbolicExpression &b);
142 FMATVEC_EXPORT SymbolicExpression operator/(int a, const SymbolicExpression &b);
143 
146 FMATVEC_EXPORT SymbolicExpression parDer(const SymbolicExpression &dep, const IndependentVariable &indep);
147 
152 inline double eval(const SymbolicExpression &x);
153 
155 FMATVEC_EXPORT std::ostream& operator<<(std::ostream& s, const SymbolicExpression& se);
157 FMATVEC_EXPORT std::istream& operator>>(std::istream& s, SymbolicExpression &se);
159 FMATVEC_EXPORT std::istream& operator>>(std::istream& s, IndependentVariable &v);
161 FMATVEC_EXPORT SymbolicExpression subst(const SymbolicExpression &se, const IndependentVariable& a, const SymbolicExpression &b);
162 
163 // function operations overloaded for SymbolicExpression
164 FMATVEC_EXPORT SymbolicExpression pow(const SymbolicExpression &a, const SymbolicExpression &b);
165 FMATVEC_EXPORT SymbolicExpression log(const SymbolicExpression &a);
166 FMATVEC_EXPORT SymbolicExpression sqrt(const SymbolicExpression &a);
167 FMATVEC_EXPORT SymbolicExpression sin(const SymbolicExpression &a);
168 FMATVEC_EXPORT SymbolicExpression cos(const SymbolicExpression &a);
169 FMATVEC_EXPORT SymbolicExpression tan(const SymbolicExpression &a);
170 FMATVEC_EXPORT SymbolicExpression sinh(const SymbolicExpression &a);
171 FMATVEC_EXPORT SymbolicExpression cosh(const SymbolicExpression &a);
172 FMATVEC_EXPORT SymbolicExpression tanh(const SymbolicExpression &a);
173 FMATVEC_EXPORT SymbolicExpression asin(const SymbolicExpression &a);
174 FMATVEC_EXPORT SymbolicExpression acos(const SymbolicExpression &a);
175 FMATVEC_EXPORT SymbolicExpression atan(const SymbolicExpression &a);
176 FMATVEC_EXPORT SymbolicExpression asinh(const SymbolicExpression &a);
177 FMATVEC_EXPORT SymbolicExpression acosh(const SymbolicExpression &a);
178 FMATVEC_EXPORT SymbolicExpression atanh(const SymbolicExpression &a);
179 FMATVEC_EXPORT SymbolicExpression exp(const SymbolicExpression &a);
180 FMATVEC_EXPORT SymbolicExpression sign(const SymbolicExpression &a);
181 FMATVEC_EXPORT SymbolicExpression abs(const SymbolicExpression &a);
182 
183 #ifndef SWIG
184 namespace AST { // internal namespace
185 
186 // ***** Vertex *****
187 
189 class FMATVEC_EXPORT Vertex {
190  friend Operation;
191  public:
192 
196  virtual double eval() const=0;
198  virtual SymbolicExpression parDer(const IndependentVariable &x) const=0;
200  inline virtual bool isConstantInt() const;
203  bool isZero() const;
206  bool isOne() const;
208  const std::map<std::shared_ptr<const Symbol>, unsigned long>& getDependsOn() const;
209 
210  protected:
211 
212  // helper function to make it easy to implement new expression optimizations. See ast.cc Operation::create for details.
213  // Returns true if this Vertex the Vertex (SymbolicExpression) b. Every Symbol variables in this Vertex are free. This
214  // means that true is also returned if the Symbols in this Vertex can be replaced by anything such that the expressions
215  // are equal. All these required replacements are stored in m.
216  virtual bool equal(const SymbolicExpression &b, std::map<IndependentVariable, SymbolicExpression> &m) const=0;
217 
218  // the value of this map (the unsigned long = version) must be mutable
219  mutable std::map<std::shared_ptr<const Symbol>, unsigned long> dependsOn;
220 };
221 
222 inline bool Vertex::isConstantInt() const {
223  return false;
224 }
225 
226 // ***** Constant *****
227 
229 template<class T>
230 class FMATVEC_EXPORT Constant : public Vertex, public std::enable_shared_from_this<Constant<T>> {
231  friend SymbolicExpression;
232  public:
233 
234  static SymbolicExpression create(const T& c_);
235  inline double eval() const override;
236  SymbolicExpression parDer(const IndependentVariable &x) const override;
237  inline bool isConstantInt() const override;
239  inline const T& getValue() const;
240 
241  private:
242 
243  Constant(const T& c_);
244  const T c;
245  bool equal(const SymbolicExpression &b, std::map<IndependentVariable, SymbolicExpression> &m) const override;
246  typedef T CacheKey;
247  static std::map<CacheKey, std::weak_ptr<const Constant>> cache;
248 };
249 
250 template<>
251 inline bool Constant<double>::isConstantInt() const {
252  return false;
253 }
254 
255 template<>
256 inline bool Constant<int>::isConstantInt() const {
257  return true;
258 }
259 
260 template<class T>
261 double Constant<T>::eval() const {
262  return c;
263 }
264 
265 template<class T>
266 const T& Constant<T>::getValue() const {
267  return c;
268 }
269 
270 // ***** Symbol *****
271 
273 class FMATVEC_EXPORT Symbol : public Vertex, public std::enable_shared_from_this<Symbol> {
274  friend SymbolicExpression;
275  friend IndependentVariable;
276  public:
277 
278  static IndependentVariable create(const boost::uuids::uuid& uuid_=boost::uuids::random_generator()());
279  inline double eval() const override;
280  SymbolicExpression parDer(const IndependentVariable &x) const override;
283  inline void setValue(double x_) const;
286  inline unsigned long getVersion() const;
287 
288  std::string getUUIDStr() const;
289 
290  private:
291 
292  Symbol(const boost::uuids::uuid& uuid_);
293  bool equal(const SymbolicExpression &b, std::map<IndependentVariable, SymbolicExpression> &m) const override;
294  mutable double x = 0.0;
295  mutable unsigned long version;
296  boost::uuids::uuid uuid; // each variable has a uuid (this is only used when the AST is serialized and for caching)
297  typedef boost::uuids::uuid CacheKey;
298  static std::map<CacheKey, std::weak_ptr<const Symbol>> cache;
299 };
300 
301 void Symbol::setValue(double x_) const {
302  version++;
303  x=x_;
304 }
305 
306 double Symbol::eval() const {
307  return x;
308 }
309 
310 unsigned long Symbol::getVersion() const {
311  return version;
312 }
313 
314 // ***** Operation *****
315 
317 class FMATVEC_EXPORT Operation : public Vertex, public std::enable_shared_from_this<Operation> {
318  friend SymbolicExpression;
320  friend boost::spirit::qi::rule<boost::spirit::istream_iterator, SymbolicExpression()>&
321  fmatvec::getBoostSpiritQiRule<SymbolicExpression>();
322  friend boost::spirit::karma::rule<std::ostream_iterator<char>, SymbolicExpression()>&
323  fmatvec::getBoostSpiritKarmaRule<SymbolicExpression>();
324  public:
325 
327  enum Operator { Plus, Minus, Mult, Div, Pow, Log, Sqrt, Neg, Sin, Cos, Tan, Sinh, Cosh, Tanh, ASin, ACos, ATan, ASinh, ACosh, ATanh, Exp, Sign, Abs };
328  static SymbolicExpression create(Operator op_, const std::vector<SymbolicExpression> &child_);
329  inline double eval() const override;
330  SymbolicExpression parDer(const IndependentVariable &x) const override;
331 
332  Operator getOp() const { return op; }
333  const std::vector<SymbolicExpression>& getChilds() const { return child; }
334 
335  private:
336 
337  Operation(Operator op_, const std::vector<SymbolicExpression> &child_);
338  bool equal(const SymbolicExpression &b, std::map<IndependentVariable, SymbolicExpression> &m) const override;
339  Operator op;
340  std::vector<SymbolicExpression> child;
341  typedef std::pair<Operator, std::vector<std::weak_ptr<const Vertex>>> CacheKey;
342  struct CacheKeyComp {
343  bool operator()(const CacheKey& l, const CacheKey& r) const;
344  private:
345  std::owner_less<std::weak_ptr<const Vertex>> ol;
346  };
347  static std::map<CacheKey, std::weak_ptr<const Operation>, CacheKeyComp> cache;
348  mutable double cacheValue;
349  static const std::map<Operator, std::string> opMap;
350 };
351 
352 double Operation::eval() const {
353  if(!dependsOn.empty()) {
354  // we eval expressions having no dependency always (such expressions are optimized out during Operation creation)
355  bool useCacheValue=true;
356  for(auto &d : dependsOn) {
357  if(d.first->getVersion() > d.second)
358  useCacheValue=false;
359  d.second=d.first->getVersion();
360  }
361  if(useCacheValue)
362  return cacheValue;
363  }
364 #if !defined(NDEBUG) && !defined(SWIG)
365  SymbolicExpression::evalOperationsCount++;
366 #endif
367 
368  // we do not use "double a=child.size()>=1 ? child[0]->eval() : 0;" here
369  // for optimal performance, to avoid the child.size() call.
370  #define a child[0]->eval() // value of first argument
371  #define b child[1]->eval() // value of second argument
372  switch(op) {
373  case Plus:
374  return cacheValue = a + b;
375  case Minus:
376  return cacheValue = a - b;
377  case Mult:
378  return cacheValue = a * b;
379  case Div:
380  return cacheValue = a / b;
381  case Pow:
382  if(child[1]->isConstantInt())
383  return cacheValue = std::pow(a, static_cast<const Constant<int>*>(child[1].get())->getValue());
384  else
385  return cacheValue = std::pow(a, b);
386  case Log:
387  return cacheValue = std::log(a);
388  case Sqrt:
389  return cacheValue = std::sqrt(a);
390  case Neg:
391  return cacheValue = - a;
392  case Sin:
393  return cacheValue = std::sin(a);
394  case Cos:
395  return cacheValue = std::cos(a);
396  case Tan:
397  return cacheValue = std::tan(a);
398  case Sinh:
399  return cacheValue = std::sinh(a);
400  case Cosh:
401  return cacheValue = std::cosh(a);
402  case Tanh:
403  return cacheValue = std::tanh(a);
404  case ASin:
405  return cacheValue = std::asin(a);
406  case ACos:
407  return cacheValue = std::acos(a);
408  case ATan:
409  return cacheValue = std::atan(a);
410  case ASinh:
411  return cacheValue = std::asinh(a);
412  case ACosh:
413  return cacheValue = std::acosh(a);
414  case ATanh:
415  return cacheValue = std::atanh(a);
416  case Exp:
417  return cacheValue = std::exp(a);
418  case Sign:
419  return cacheValue = boost::math::sign(a);
420  case Abs:
421  return cacheValue = std::abs(a);
422  }
423  #undef a
424  #undef b
425  throw std::runtime_error("Unknown operation.");
426 }
427 
428 } // end namespace AST
429 #endif
430 
432  static_cast<const AST::Symbol*>(get())->setValue(x);
433  return *this;
434 }
435 
436 double eval(const SymbolicExpression &x) {
437  return x->eval();
438 }
439 
440 template<> boost::spirit::qi::rule<boost::spirit::istream_iterator, IndependentVariable()>& getBoostSpiritQiRule<IndependentVariable>();
441 template<> boost::spirit::qi::rule<boost::spirit::istream_iterator, SymbolicExpression()>& getBoostSpiritQiRule<SymbolicExpression>();
442 
443 template<> boost::spirit::karma::rule<std::ostream_iterator<char>, IndependentVariable()>& getBoostSpiritKarmaRule<IndependentVariable>();
444 template<> boost::spirit::karma::rule<std::ostream_iterator<char>, SymbolicExpression()>& getBoostSpiritKarmaRule<SymbolicExpression>();
445 
446 // for vectors/matrices of type IndependentVariable/SymbolicExpression throw exceptions instead of assert.
447 // these exceptions are thrown regardless whether NDEBUG is defined or not.
448 // this is done since vectors/matrix operations of this type are usually user input, should not abort/assert on errors,
449 // and it not time critical since it just build the expression once which is than evaluated at runtime.
450 template<> struct AssertUseException<IndependentVariable> { constexpr static bool value = true; };
451 template<> struct AssertUseException<SymbolicExpression> { constexpr static bool value = true; };
452 
453 } // end namespace fmatvec
454 
455 #endif
void setValue(double x_) const
Definition: ast.h:301
IndependentVariable & operator^=(double x)
Set the double value of the independent value.
Definition: ast.h:431
A vertex of the AST representing a constant (int or double)
Definition: ast.h:28
const T & getValue() const
Get the constant value of the vertex.
Definition: ast.h:266
bool isConstantInt() const override
Rreturn true if this Vertex is a constant integer.
virtual bool isConstantInt() const
Rreturn true if this Vertex is a constant integer.
Definition: ast.h:222
Definition: ast.h:102
A vertex of the AST representing a independent variable.
Definition: ast.h:273
unsigned long getVersion() const
Definition: ast.h:310
A vertex of the AST representing an operation.
Definition: ast.h:317
Definition: types.h:231
Namespace fmatvec.
Definition: _memory.cc:28
double eval() const override
Definition: ast.h:306
A abstract class for a Vertex of the AST (abstract syntax tree).
Definition: ast.h:189
friend FMATVEC_EXPORT double eval(const SymbolicExpression &x)
Definition: ast.h:436
SymbolicExpression subst(const SymbolicExpression &se, const IndependentVariable &a, const SymbolicExpression &b)
Substitutes in se the independent variable a with the expression b and returns the new expression.
Definition: ast.cc:234
Definition: ast.h:36
Operator
Defined operations.
Definition: ast.h:327
ostream & operator<<(ostream &s, const SymbolicExpression &se)
Write a SymbolicExpression to a stream using serialization.
Definition: ast.cc:169
double eval() const override
Definition: ast.h:261
double eval(const SymbolicExpression &x)
Definition: ast.h:436
SymbolicExpression parDer(const SymbolicExpression &dep, const IndependentVariable &indep)
Definition: ast.cc:282
double eval() const override
Definition: ast.h:352