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