fmatvec  2.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 
112  inline IndependentVariable& operator&=(double x);
113 
114  private:
115  IndependentVariable(const shared_ptr<const AST::Symbol> &x);
116 };
117 
118 // define the operator results of SymbolicExpression and IndependentVariable with other AT types.
119 FMATVEC_OPERATORRESULT1(SymbolicExpression, SymbolicExpression)
120 
121 FMATVEC_OPERATORRESULT2(SymbolicExpression, int, SymbolicExpression)
122 FMATVEC_OPERATORRESULT2(SymbolicExpression, double, SymbolicExpression)
123 
124 FMATVEC_OPERATORRESULT1(IndependentVariable, SymbolicExpression)
125 
126 FMATVEC_OPERATORRESULT2(IndependentVariable, int, SymbolicExpression)
127 FMATVEC_OPERATORRESULT2(IndependentVariable, double, SymbolicExpression)
129 
130 // Some member function definition of SymbolicExpression/IndependentVariable are moved to the end of this file
131 // since they need the defintion of the other class defined in this file.
132 
133 FMATVEC_EXPORT SymbolicExpression operator+(double a, const SymbolicExpression &b);
134 FMATVEC_EXPORT SymbolicExpression operator-(double a, const SymbolicExpression &b);
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+(int a, const SymbolicExpression &b);
138 FMATVEC_EXPORT SymbolicExpression operator-(int 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 
144 FMATVEC_EXPORT SymbolicExpression parDer(const SymbolicExpression &dep, const IndependentVariable &indep);
145 
150 inline double eval(const SymbolicExpression &x);
151 
153 FMATVEC_EXPORT std::ostream& operator<<(std::ostream& s, const SymbolicExpression& se);
155 FMATVEC_EXPORT std::istream& operator>>(std::istream& s, SymbolicExpression &se);
157 FMATVEC_EXPORT std::istream& operator>>(std::istream& s, IndependentVariable &v);
159 FMATVEC_EXPORT SymbolicExpression subst(const SymbolicExpression &se, const IndependentVariable& a, const SymbolicExpression &b);
160 
161 // function operations overloaded for SymbolicExpression
162 FMATVEC_EXPORT SymbolicExpression pow(const SymbolicExpression &a, const SymbolicExpression &b);
163 FMATVEC_EXPORT SymbolicExpression log(const SymbolicExpression &a);
164 FMATVEC_EXPORT SymbolicExpression sqrt(const SymbolicExpression &a);
165 FMATVEC_EXPORT SymbolicExpression sin(const SymbolicExpression &a);
166 FMATVEC_EXPORT SymbolicExpression cos(const SymbolicExpression &a);
167 FMATVEC_EXPORT SymbolicExpression tan(const SymbolicExpression &a);
168 FMATVEC_EXPORT SymbolicExpression sinh(const SymbolicExpression &a);
169 FMATVEC_EXPORT SymbolicExpression cosh(const SymbolicExpression &a);
170 FMATVEC_EXPORT SymbolicExpression tanh(const SymbolicExpression &a);
171 FMATVEC_EXPORT SymbolicExpression asin(const SymbolicExpression &a);
172 FMATVEC_EXPORT SymbolicExpression acos(const SymbolicExpression &a);
173 FMATVEC_EXPORT SymbolicExpression atan(const SymbolicExpression &a);
174 FMATVEC_EXPORT SymbolicExpression asinh(const SymbolicExpression &a);
175 FMATVEC_EXPORT SymbolicExpression acosh(const SymbolicExpression &a);
176 FMATVEC_EXPORT SymbolicExpression atanh(const SymbolicExpression &a);
177 FMATVEC_EXPORT SymbolicExpression exp(const SymbolicExpression &a);
178 FMATVEC_EXPORT SymbolicExpression sign(const SymbolicExpression &a);
179 FMATVEC_EXPORT SymbolicExpression abs(const SymbolicExpression &a);
180 
181 #ifndef SWIG
182 namespace AST { // internal namespace
183 
184 // ***** Vertex *****
185 
187 class FMATVEC_EXPORT Vertex {
188  friend Operation;
189  public:
190 
194  virtual double eval() const=0;
196  virtual SymbolicExpression parDer(const IndependentVariable &x) const=0;
198  inline virtual bool isConstantInt() const;
201  bool isZero() const;
204  bool isOne() const;
206  const std::map<std::weak_ptr<const Symbol>, unsigned long, std::owner_less<std::weak_ptr<const Symbol>>>& getDependsOn() const;
207 
208  protected:
209 
210  // helper function to make it easy to implement new expression optimizations. See ast.cc Operation::create for details.
211  // Returns true if this Vertex the Vertex (SymbolicExpression) b. Every Symbol variables in this Vertex are free. This
212  // means that true is also returned if the Symbols in this Vertex can be replaced by anything such that the expressions
213  // are equal. All these required replacements are stored in m.
214  virtual bool equal(const SymbolicExpression &b, std::map<IndependentVariable, SymbolicExpression> &m) const=0;
215 
216  // the value of this map (the unsigned long = version) must be mutable
217  mutable std::map<std::weak_ptr<const Symbol>, unsigned long, std::owner_less<std::weak_ptr<const Symbol>>> dependsOn;
218 };
219 
220 inline bool Vertex::isConstantInt() const {
221  return false;
222 }
223 
224 // ***** Constant *****
225 
227 template<class T>
228 class FMATVEC_EXPORT Constant : public Vertex, public std::enable_shared_from_this<Constant<T>> {
229  friend SymbolicExpression;
230  public:
231 
232  static SymbolicExpression create(const T& c_);
233  inline double eval() const override;
234  SymbolicExpression parDer(const IndependentVariable &x) const override;
235  inline bool isConstantInt() const override;
237  inline const T& getValue() const;
238 
239  private:
240 
241  Constant(const T& c_);
242  const T c;
243  bool equal(const SymbolicExpression &b, std::map<IndependentVariable, SymbolicExpression> &m) const override;
244  typedef T CacheKey;
245  static std::map<CacheKey, std::weak_ptr<const Constant>> cache;
246 };
247 
248 template<>
249 inline bool Constant<double>::isConstantInt() const {
250  return false;
251 }
252 
253 template<>
254 inline bool Constant<int>::isConstantInt() const {
255  return true;
256 }
257 
258 template<class T>
259 double Constant<T>::eval() const {
260  return c;
261 }
262 
263 template<class T>
264 const T& Constant<T>::getValue() const {
265  return c;
266 }
267 
268 // ***** Symbol *****
269 
271 class FMATVEC_EXPORT Symbol : public Vertex, public std::enable_shared_from_this<Symbol> {
272  friend SymbolicExpression;
273  friend IndependentVariable;
274  public:
275 
276  static IndependentVariable create(const boost::uuids::uuid& uuid_=boost::uuids::random_generator()());
277  inline double eval() const override;
278  SymbolicExpression parDer(const IndependentVariable &x) const override;
281  inline void setValue(double x_) const;
284  inline unsigned long getVersion() const;
285 
286  std::string getUUIDStr() const;
287 
288  private:
289 
290  Symbol(const boost::uuids::uuid& uuid_);
291  bool equal(const SymbolicExpression &b, std::map<IndependentVariable, SymbolicExpression> &m) const override;
292  mutable double x = 0.0;
293  mutable unsigned long version;
294  boost::uuids::uuid uuid; // each variable has a uuid (this is only used when the AST is serialized and for caching)
295  typedef boost::uuids::uuid CacheKey;
296  static std::map<CacheKey, std::weak_ptr<const Symbol>> cache;
297 };
298 
299 void Symbol::setValue(double x_) const {
300  version++;
301  x=x_;
302 }
303 
304 double Symbol::eval() const {
305  return x;
306 }
307 
308 unsigned long Symbol::getVersion() const {
309  return version;
310 }
311 
312 // ***** Operation *****
313 
315 class FMATVEC_EXPORT Operation : public Vertex, public std::enable_shared_from_this<Operation> {
316  friend SymbolicExpression;
318  friend boost::spirit::qi::rule<boost::spirit::istream_iterator, SymbolicExpression()>&
319  fmatvec::getBoostSpiritQiRule<SymbolicExpression>();
320  friend boost::spirit::karma::rule<std::ostream_iterator<char>, SymbolicExpression()>&
321  fmatvec::getBoostSpiritKarmaRule<SymbolicExpression>();
322  public:
323 
325  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 };
326  static SymbolicExpression create(Operator op_, const std::vector<SymbolicExpression> &child_);
327  inline double eval() const override;
328  SymbolicExpression parDer(const IndependentVariable &x) const override;
329 
330  Operator getOp() const { return op; }
331  const std::vector<SymbolicExpression>& getChilds() const { return child; }
332 
333  private:
334 
335  Operation(Operator op_, const std::vector<SymbolicExpression> &child_);
336  bool equal(const SymbolicExpression &b, std::map<IndependentVariable, SymbolicExpression> &m) const override;
337  Operator op;
338  std::vector<SymbolicExpression> child;
339  typedef std::pair<Operator, std::vector<std::weak_ptr<const Vertex>>> CacheKey;
340  struct CacheKeyComp {
341  bool operator()(const CacheKey& l, const CacheKey& r) const;
342  private:
343  std::owner_less<std::weak_ptr<const Vertex>> ol;
344  };
345  static std::map<CacheKey, std::weak_ptr<const Operation>, CacheKeyComp> cache;
346  mutable double cacheValue;
347  static const std::map<Operator, std::string> opMap;
348 };
349 
350 double Operation::eval() const {
351  if(!dependsOn.empty()) {
352  // we eval expressions having no dependency always (such expressions are optimized out during Operation creation)
353  bool useCacheValue=true;
354  for(auto &d : dependsOn) {
355  auto dFirst=d.first.lock();
356  if(dFirst->getVersion() > d.second)
357  useCacheValue=false;
358  d.second=dFirst->getVersion();
359  }
360  if(useCacheValue)
361  return cacheValue;
362  }
363 #if !defined(NDEBUG) && !defined(SWIG)
364  SymbolicExpression::evalOperationsCount++;
365 #endif
366 
367  // we do not use "double a=child.size()>=1 ? child[0]->eval() : 0;" here
368  // for optimal performance, to avoid the child.size() call.
369  #define a child[0]->eval() // value of first argument
370  #define b child[1]->eval() // value of second argument
371  switch(op) {
372  case Plus:
373  return cacheValue = a + b;
374  case Minus:
375  return cacheValue = a - b;
376  case Mult:
377  return cacheValue = a * b;
378  case Div:
379  return cacheValue = a / b;
380  case Pow:
381  if(child[1]->isConstantInt())
382  return cacheValue = std::pow(a, static_cast<const Constant<int>*>(child[1].get())->getValue());
383  else
384  return cacheValue = std::pow(a, b);
385  case Log:
386  return cacheValue = std::log(a);
387  case Sqrt:
388  return cacheValue = std::sqrt(a);
389  case Neg:
390  return cacheValue = - a;
391  case Sin:
392  return cacheValue = std::sin(a);
393  case Cos:
394  return cacheValue = std::cos(a);
395  case Tan:
396  return cacheValue = std::tan(a);
397  case Sinh:
398  return cacheValue = std::sinh(a);
399  case Cosh:
400  return cacheValue = std::cosh(a);
401  case Tanh:
402  return cacheValue = std::tanh(a);
403  case ASin:
404  return cacheValue = std::asin(a);
405  case ACos:
406  return cacheValue = std::acos(a);
407  case ATan:
408  return cacheValue = std::atan(a);
409  case ASinh:
410  return cacheValue = std::asinh(a);
411  case ACosh:
412  return cacheValue = std::acosh(a);
413  case ATanh:
414  return cacheValue = std::atanh(a);
415  case Exp:
416  return cacheValue = std::exp(a);
417  case Sign:
418  return cacheValue = boost::math::sign(a);
419  case Abs:
420  return cacheValue = std::abs(a);
421  }
422  #undef a
423  #undef b
424  throw std::runtime_error("Unknown operation.");
425 }
426 
427 } // end namespace AST
428 #endif
429 
431  static_cast<const AST::Symbol*>(get())->setValue(x);
432  return *this;
433 }
434 
435 double eval(const SymbolicExpression &x) {
436  return x->eval();
437 }
438 
439 template<> boost::spirit::qi::rule<boost::spirit::istream_iterator, IndependentVariable()>& getBoostSpiritQiRule<IndependentVariable>();
440 template<> boost::spirit::qi::rule<boost::spirit::istream_iterator, SymbolicExpression()>& getBoostSpiritQiRule<SymbolicExpression>();
441 
442 template<> boost::spirit::karma::rule<std::ostream_iterator<char>, IndependentVariable()>& getBoostSpiritKarmaRule<IndependentVariable>();
443 template<> boost::spirit::karma::rule<std::ostream_iterator<char>, SymbolicExpression()>& getBoostSpiritKarmaRule<SymbolicExpression>();
444 
445 // for vectors/matrices of type IndependentVariable/SymbolicExpression throw exceptions instead of assert.
446 // these exceptions are thrown regardless whether NDEBUG is defined or not.
447 // this is done since vectors/matrix operations of this type are usually user input, should not abort/assert on errors,
448 // and it not time critical since it just build the expression once which is than evaluated at runtime.
449 template<> struct AssertUseException<IndependentVariable> { constexpr static bool value = true; };
450 template<> struct AssertUseException<SymbolicExpression> { constexpr static bool value = true; };
451 
452 } // end namespace fmatvec
453 
454 #endif
void setValue(double x_) const
Definition: ast.h:299
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:264
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:220
Definition: ast.h:102
A vertex of the AST representing a independent variable.
Definition: ast.h:271
unsigned long getVersion() const
Definition: ast.h:308
A vertex of the AST representing an operation.
Definition: ast.h:315
Definition: types.h:222
Namespace fmatvec.
Definition: _memory.cc:28
double eval() const override
Definition: ast.h:304
A abstract class for a Vertex of the AST (abstract syntax tree).
Definition: ast.h:187
IndependentVariable & operator&=(double x)
Set the double value of the independent value.
Definition: ast.h:430
friend FMATVEC_EXPORT double eval(const SymbolicExpression &x)
Definition: ast.h:435
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:325
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:259
double eval(const SymbolicExpression &x)
Definition: ast.h:435
SymbolicExpression parDer(const SymbolicExpression &dep, const IndependentVariable &indep)
Definition: ast.cc:282
double eval() const override
Definition: ast.h:350