fmatvec  0.0.0
ast.h
1 #ifndef _FMATVEC_AST_H_
2 #define _FMATVEC_AST_H_
3 
4 #include <map>
5 #include <array>
6 #include <memory>
7 #include <boost/uuid/uuid.hpp>
8 #include <boost/uuid/uuid_generators.hpp>
9 #include <fmatvec/stream.h>
10 
11 namespace fmatvec {
12 
13 // forward declarations
14 
15 class IndependentVariable;
16 
17 namespace AST {
18  class Vertex;
19  class Symbol;
20  class Operation;
21  template<class T> class Constant;
22  FMATVEC_EXPORT SymbolicExpression substScalar(const SymbolicExpression &se, const IndependentVariable& a, const SymbolicExpression &b);
23 }
24 
25 template<class... Arg> class Eval;
26 class EvalHelper;
27 
33 class FMATVEC_EXPORT SymbolicExpression : public std::shared_ptr<const AST::Vertex> {
34  template<class... Arg> friend class Eval;
35  friend class EvalHelper;
36  friend class AST::Operation;
37  friend class AST::Constant<int>;
38  friend class AST::Constant<double>;
39  friend FMATVEC_EXPORT SymbolicExpression parDer(const SymbolicExpression &dep, const IndependentVariable &indep);
40  friend SymbolicExpression AST::substScalar(const SymbolicExpression &se,
41  const IndependentVariable& a, const SymbolicExpression &b);
42  protected:
43  template<class T> SymbolicExpression(const shared_ptr<T> &x);
44 #ifndef SWIG
45  static const struct ConstructSymbol{} constructSymbol; // just used for tag dispatching
46 #endif
47  SymbolicExpression(ConstructSymbol);
48 
49  // do not allow to call these functions inherited from std::shared_ptr
53  public:
57  SymbolicExpression(const std::string &str);
59  SymbolicExpression(int x);
61  SymbolicExpression(double x);
62 
66  static void garbageCollect();
67 
68  // default ctors and assignment operators
69  SymbolicExpression(const SymbolicExpression& x) = default;
71  SymbolicExpression& operator=(const SymbolicExpression& x) = default;
72  SymbolicExpression& operator=(SymbolicExpression&& x) = default;
73  ~SymbolicExpression() = default;
74 
75  // operators
76 #ifndef SWIG
77  SymbolicExpression operator+(const SymbolicExpression &b) const;
78  SymbolicExpression operator-(const SymbolicExpression &b) const;
79  SymbolicExpression operator*(const SymbolicExpression &b) const;
80  SymbolicExpression operator/(const SymbolicExpression &b) const;
81 #endif
82  SymbolicExpression operator-() const;
83  SymbolicExpression& operator+=(const SymbolicExpression &b);
84  SymbolicExpression& operator-=(const SymbolicExpression &b);
85  SymbolicExpression& operator*=(const SymbolicExpression &b);
86  SymbolicExpression& operator/=(const SymbolicExpression &b);
87 
88  // We implement operator<<= to be able to use SymbolicExpression fully equivalent to the vector/matrix classes
89  // which have a assign method which redimension before assigning. Redimensioning is not required for a scalar
90  // type like assign
91  SymbolicExpression& operator<<=(const SymbolicExpression &src);
92 
93 #if defined(FMATVEC_DEBUG) && !defined(SWIG)
94  static signed long evalOperationsCount;
95 #endif
96 };
97 
101 class FMATVEC_EXPORT IndependentVariable : public SymbolicExpression {
102  friend class AST::Symbol;
103  friend FMATVEC_EXPORT std::istream& operator>>(std::istream& s, IndependentVariable &v);
104  public:
108  IndependentVariable(const std::string &str);
109 
110 #ifndef SWIG
111  inline IndependentVariable& operator^=(double x);
113 #endif
114 
115  private:
116  IndependentVariable(const shared_ptr<const AST::Symbol> &x);
117 };
118 
119 // define the operator results of SymbolicExpression and IndependentVariable with other AT types.
120 FMATVEC_OPERATORRESULT1(SymbolicExpression, SymbolicExpression)
121 
122 FMATVEC_OPERATORRESULT2(SymbolicExpression, int, SymbolicExpression)
123 FMATVEC_OPERATORRESULT2(SymbolicExpression, double, SymbolicExpression)
124 
125 FMATVEC_OPERATORRESULT1(IndependentVariable, SymbolicExpression)
126 
127 FMATVEC_OPERATORRESULT2(IndependentVariable, int, SymbolicExpression)
128 FMATVEC_OPERATORRESULT2(IndependentVariable, double, SymbolicExpression)
130 
131 // Some member function definition of SymbolicExpression/IndependentVariable are moved to the end of this file
132 // since they need the defintion of the other class defined in this file.
133 
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/(double 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 FMATVEC_EXPORT SymbolicExpression operator/(int a, const SymbolicExpression &b);
142 
145 FMATVEC_EXPORT SymbolicExpression parDer(const SymbolicExpression &dep, const IndependentVariable &indep);
146 
148 FMATVEC_EXPORT std::ostream& operator<<(std::ostream& s, const SymbolicExpression& se);
150 FMATVEC_EXPORT std::istream& operator>>(std::istream& s, SymbolicExpression &se);
152 FMATVEC_EXPORT std::istream& operator>>(std::istream& s, IndependentVariable &v);
153 
154 // function operations overloaded for SymbolicExpression
155 FMATVEC_EXPORT SymbolicExpression pow(const SymbolicExpression &a, const SymbolicExpression &b);
156 FMATVEC_EXPORT SymbolicExpression log(const SymbolicExpression &a);
157 FMATVEC_EXPORT SymbolicExpression sqrt(const SymbolicExpression &a);
158 FMATVEC_EXPORT SymbolicExpression sin(const SymbolicExpression &a);
159 FMATVEC_EXPORT SymbolicExpression cos(const SymbolicExpression &a);
160 FMATVEC_EXPORT SymbolicExpression tan(const SymbolicExpression &a);
161 FMATVEC_EXPORT SymbolicExpression sinh(const SymbolicExpression &a);
162 FMATVEC_EXPORT SymbolicExpression cosh(const SymbolicExpression &a);
163 FMATVEC_EXPORT SymbolicExpression tanh(const SymbolicExpression &a);
164 FMATVEC_EXPORT SymbolicExpression asin(const SymbolicExpression &a);
165 FMATVEC_EXPORT SymbolicExpression acos(const SymbolicExpression &a);
166 FMATVEC_EXPORT SymbolicExpression atan(const SymbolicExpression &a);
167 FMATVEC_EXPORT SymbolicExpression atan2(const SymbolicExpression &y, const SymbolicExpression &x);
168 FMATVEC_EXPORT SymbolicExpression asinh(const SymbolicExpression &a);
169 FMATVEC_EXPORT SymbolicExpression acosh(const SymbolicExpression &a);
170 FMATVEC_EXPORT SymbolicExpression atanh(const SymbolicExpression &a);
171 FMATVEC_EXPORT SymbolicExpression exp(const SymbolicExpression &a);
172 FMATVEC_EXPORT SymbolicExpression sign(const SymbolicExpression &a);
173 FMATVEC_EXPORT SymbolicExpression heaviside(const SymbolicExpression &a);
174 FMATVEC_EXPORT SymbolicExpression abs(const SymbolicExpression &a);
175 FMATVEC_EXPORT SymbolicExpression min(const SymbolicExpression &a, const SymbolicExpression &b);
176 FMATVEC_EXPORT SymbolicExpression max(const SymbolicExpression &a, const SymbolicExpression &b);
177 FMATVEC_EXPORT SymbolicExpression condition(const SymbolicExpression &c, const SymbolicExpression &gt, const SymbolicExpression &lt);
178 
179 #ifndef SWIG
180 namespace AST { // internal namespace
181 
182 /* ***** Struct for a "bytecode" for fast runtime evaluation *****
183  * This class uses very low-level technices like raw-pointers to gain maximal performance
184  * during runtime evaluation.
185  *
186  * This class store a kind of "bytecode" which can be used to evaluate an mathematical expression very fast.
187  * This class is not copyable and not moveable since it uses intern pointers between instances of this class.
188  * For optimal performance this class should be used in continous memory e.g. as std::vector<ByteCode>.
189  * For the same reason, to keep all data near together for best processor memory cache usage, all members
190  * of these class also to not use allocated memory: std::array instead of std::vector is used.
191  * The usage of std::vector<ByteCode> requires that the move-ctor must be provided at compile time
192  * (it cannot be delete'd) but the move-ctor throws at runtime when called to ensure its not used.
193  * Hence std::vector<ByteCode> can only be used without reallocation: std::vector::reserve must be called before use.
194  * To add an element only std::vector::emplace_back() can be used.
195 */
196 struct FMATVEC_EXPORT ByteCode {
197  static constexpr size_t N { 3 };
198  ByteCode();
199  ByteCode(const ByteCode &) = delete;
200  ByteCode(ByteCode &&) noexcept;
201  ByteCode &operator=(const ByteCode &) = delete;
202  ByteCode &operator=(ByteCode &&) = delete;
203  ~ByteCode() = default;
204  std::function<void(double*, const std::array<double*,N>&)> func; // the operation this byteCode entry executes
205  double retValue; // storage of the return value of the operation: retPtr may point to this value
206  double* retPtr; // a pointer to which the operation can write its result to
207  std::array<double ,N> argsValue; // storage for arguments of the operation: argsPtr may point to these values
208  std::array<double*,N> argsPtr; // pointers from which the operation reads its arguments
209 };
210 
211 // ***** Vertex *****
212 
214 class FMATVEC_EXPORT Vertex {
215  friend Operation;
216  public:
217 
219  virtual SymbolicExpression parDer(const IndependentVariable &x) const=0;
221  inline virtual bool isConstantInt() const;
224  bool isZero() const;
227  bool isOne() const;
228 
229  virtual std::vector<ByteCode>::iterator dumpByteCode(std::vector<ByteCode> &byteCode,
230  std::map<const Vertex*, std::vector<AST::ByteCode>::iterator> &existingVertex) const=0;
231 
232  virtual void walkVertex(const std::function<void(const std::shared_ptr<const Vertex>&)> &func) const=0;
233 
234  protected:
235 
236  // helper function to make it easy to implement new expression optimizations. See ast.cc Operation::create for details.
237  // Returns true if this Vertex the Vertex (SymbolicExpression) b. Every Symbol variables in this Vertex are free. This
238  // means that true is also returned if the Symbols in this Vertex can be replaced by anything such that the expressions
239  // are equal. All these required replacements are stored in m.
240  virtual bool equal(const SymbolicExpression &b, std::map<IndependentVariable, SymbolicExpression> &m) const=0;
241 };
242 
243 inline bool Vertex::isConstantInt() const {
244  return false;
245 }
246 
247 // ***** Constant *****
248 
250 template<class T>
251 class FMATVEC_EXPORT Constant : public Vertex, public std::enable_shared_from_this<Constant<T>> {
252  friend SymbolicExpression;
253  public:
254 
255  static SymbolicExpression create(const T& c_);
256  SymbolicExpression parDer(const IndependentVariable &x) const override;
257  inline bool isConstantInt() const override;
259  inline const T& getValue() const;
260  std::vector<ByteCode>::iterator dumpByteCode(std::vector<ByteCode> &byteCode,
261  std::map<const Vertex*, std::vector<AST::ByteCode>::iterator> &existingVertex) const override;
262 
263  void walkVertex(const std::function<void(const std::shared_ptr<const Vertex>&)> &func) const override;
264 
265  private:
266 
267  Constant(const T& c_);
268  const T c;
269  bool equal(const SymbolicExpression &b, std::map<IndependentVariable, SymbolicExpression> &m) const override;
270  using CacheKey = T;
271  static std::map<CacheKey, std::weak_ptr<const Constant>> cache;
272 };
273 
274 template<>
275 inline bool Constant<double>::isConstantInt() const {
276  return false;
277 }
278 
279 template<>
280 inline bool Constant<int>::isConstantInt() const {
281  return true;
282 }
283 
284 template<class T>
285 const T& Constant<T>::getValue() const {
286  return c;
287 }
288 
289 // ***** Symbol *****
290 
292 class FMATVEC_EXPORT Symbol : public Vertex, public std::enable_shared_from_this<Symbol> {
293  friend SymbolicExpression;
294  friend IndependentVariable;
295  public:
296 
297  static IndependentVariable create(const boost::uuids::uuid& uuid_=boost::uuids::random_generator()());
298  SymbolicExpression parDer(const IndependentVariable &x) const override;
301  inline void setValue(double x_) const;
302 
303  std::string getUUIDStr() const;
304 
305  std::vector<ByteCode>::iterator dumpByteCode(std::vector<ByteCode> &byteCode,
306  std::map<const Vertex*, std::vector<AST::ByteCode>::iterator> &existingVertex) const override;
307 
308  void walkVertex(const std::function<void(const std::shared_ptr<const Vertex>&)> &func) const override;
309 
310  private:
311 
312  Symbol(const boost::uuids::uuid& uuid_);
313  bool equal(const SymbolicExpression &b, std::map<IndependentVariable, SymbolicExpression> &m) const override;
314  mutable double x = 0.0;
315  boost::uuids::uuid uuid; // each variable has a uuid (this is only used when the AST is serialized and for caching)
316  using CacheKey = boost::uuids::uuid;
317  static std::map<CacheKey, std::weak_ptr<const Symbol>> cache;
318 };
319 
320 void Symbol::setValue(double x_) const {
321  x=x_;
322 }
323 
324 // ***** Operation *****
325 
327 class FMATVEC_EXPORT Operation : public Vertex, public std::enable_shared_from_this<Operation> {
328  friend SymbolicExpression;
329  friend SymbolicExpression fmatvec::AST::substScalar(const SymbolicExpression &se,
330  const IndependentVariable& a, const SymbolicExpression &b);
331  friend boost::spirit::qi::rule<boost::spirit::istream_iterator, SymbolicExpression()>&
332  fmatvec::getBoostSpiritQiRule<SymbolicExpression>();
333  friend boost::spirit::karma::rule<std::ostream_iterator<char>, SymbolicExpression()>&
334  fmatvec::getBoostSpiritKarmaRule<SymbolicExpression>();
335  public:
336 
338  enum Operator { Plus, Minus, Mult, Div, Pow, Log, Sqrt, Neg, Sin, Cos, Tan, Sinh, Cosh, Tanh, ASin, ACos, ATan, ATan2, ASinh, ACosh, ATanh, Exp, Sign, Heaviside, Abs, Min, Max, Condition };
339  static SymbolicExpression create(Operator op_, const std::vector<SymbolicExpression> &child_);
340  SymbolicExpression parDer(const IndependentVariable &x) const override;
341 
342  Operator getOp() const { return op; }
343  const std::vector<SymbolicExpression>& getChilds() const { return child; }
344  std::vector<ByteCode>::iterator dumpByteCode(std::vector<ByteCode> &byteCode,
345  std::map<const Vertex*, std::vector<AST::ByteCode>::iterator> &existingVertex) const override;
346 
347  void walkVertex(const std::function<void(const std::shared_ptr<const Vertex>&)> &func) const override;
348 
349  private:
350 
351  Operation(Operator op_, const std::vector<SymbolicExpression> &child_);
352  bool equal(const SymbolicExpression &b, std::map<IndependentVariable, SymbolicExpression> &m) const override;
353  Operator op;
354  std::vector<SymbolicExpression> child;
355  using CacheKey = std::pair<Operator, std::vector<std::weak_ptr<const Vertex>>>;
356  struct CacheKeyComp {
357  bool operator()(const CacheKey& l, const CacheKey& r) const;
358  private:
359  std::owner_less<std::weak_ptr<const Vertex>> ol;
360  };
361  static std::map<CacheKey, std::weak_ptr<const Operation>, CacheKeyComp> cache;
362 
363  struct OpMap {
364  std::string funcName; // used to dump/read the expression using boost spirit/karma: e.g.
365  // "plus"
366  std::function<void(double*, const std::array<double*,ByteCode::N>&)> func; // used for runtime evaluation: e.g.
367  // [](double* r, const std::array<double*,N>& a){ *r = *a[0] + *a[1]; }
368  };
369  static const std::map<Operator, OpMap> opMap;
370 };
371 
372 } // end namespace AST
373 #endif
374 
376  static_cast<const AST::Symbol*>(get())->setValue(x);
377  return *this;
378 }
379 
380 template<> boost::spirit::qi::rule<boost::spirit::istream_iterator, IndependentVariable()>& getBoostSpiritQiRule<IndependentVariable>();
381 template<> boost::spirit::qi::rule<boost::spirit::istream_iterator, SymbolicExpression()>& getBoostSpiritQiRule<SymbolicExpression>();
382 
383 template<> boost::spirit::karma::rule<std::ostream_iterator<char>, IndependentVariable()>& getBoostSpiritKarmaRule<IndependentVariable>();
384 template<> boost::spirit::karma::rule<std::ostream_iterator<char>, SymbolicExpression()>& getBoostSpiritKarmaRule<SymbolicExpression>();
385 
386 // for vectors/matrices of type IndependentVariable/SymbolicExpression throw exceptions instead of assert.
387 // these exceptions are thrown regardless whether NDEBUG is defined or not.
388 // this is done since vectors/matrix operations of this type are usually user input, should not abort/assert on errors,
389 // and it not time critical since it just build the expression once which is than evaluated at runtime.
390 template<> struct AssertUseException<IndependentVariable> { constexpr static bool value = true; };
391 template<> struct AssertUseException<SymbolicExpression> { constexpr static bool value = true; };
392 
393 } // end namespace fmatvec
394 
395 #endif
void setValue(double x_) const
Definition: ast.h:320
IndependentVariable & operator^=(double x)
Set the double value of the independent value.
Definition: ast.h:375
A vertex of the AST representing a constant (int or double)
Definition: ast.h:21
const T & getValue() const
Get the constant value of the vertex.
Definition: ast.h:285
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:243
Definition: ast.h:196
Definition: ast.h:363
Definition: types.h:81
Definition: ast.h:101
A vertex of the AST representing a independent variable.
Definition: ast.h:292
Definition: ast.h:25
A vertex of the AST representing an operation.
Definition: ast.h:327
Definition: types.h:219
Namespace fmatvec.
Definition: _memory.cc:28
A abstract class for a Vertex of the AST (abstract syntax tree).
Definition: ast.h:214
Definition: ast.h:33
Operator
Defined operations.
Definition: ast.h:338
ostream & operator<<(ostream &s, const SymbolicExpression &se)
Write a SymbolicExpression to a stream using serialization.
Definition: ast.cc:189
SymbolicExpression parDer(const SymbolicExpression &dep, const IndependentVariable &indep)
Definition: ast.cc:286