10

I'm looking for suggestions of portable lightweight libraries written in C++, that support mathematical and business rule expression and evaluation. I understand C++ doesn't provide such functionality in the STL.

The basic requirement is as follows:

The expressions to be evaluated will be comprised of numbers and strings and variables either representing numbers or strings.

Some of the expressions are expected to be evaluated many times per second (1000-2000 times), hence there is a requirement for high performance evaluations of the expressions.

Originally the project at my company, we encode all the business rules as classes that derived from a base expression class. The problem is that this approach does not scale well as the number of expressions increases.

I've googled around, but most "libraries" I could find are pretty much simple examples of the shunting yard algorithm, most of the expression parsers, perform parsing and evaluation in the same step making them unsuitable for continuous reevaluations, and most only support numbers.

What I'm looking for:

  1. Library written in C++ (C++03 or C++11)
  2. Stable/production worthy
  3. Fast evaluations
  4. Portable (win32/linux)
  5. Any suggestions for building high performance business rules engine.

Example business rule:

'rule_result = (remaining_items < min_items) and (item == "beach ball")'

Zamfir Kerlukson
  • 1,046
  • 1
  • 10
  • 20
  • See [schematron](http://www.schematron.com) (reflecting, I doubt it could handle these speeds unless, perhaps, the rules were batched together) – user2246674 Oct 06 '13 at 23:07
  • 1
    Looks interesting, but I'm more after what happens with the rule, not necessarily how it's stored or represented. I'll definitely look into schematron as it seems to have some other neat ideas. – Zamfir Kerlukson Oct 06 '13 at 23:09
  • I was searching for RETE algorithm based library for a long time, never exactly found what I need. I might have some suggestions, but I haven’t had the chance to confront them. – Arpegius Oct 07 '13 at 00:28
  • possible duplicate of [Is there any kind of "expression class" (C++)](http://stackoverflow.com/questions/978247/is-there-any-kind-of-expression-class-c) – Macke Oct 07 '13 at 20:08
  • just out of curiosity, why don't you use an embeddable scripting language, such as [Lua]http://www.lua.org/? That would give you the maximum flexibiliy without too much overhead – Dmitry Ledentsov Oct 07 '13 at 20:08
  • @DmitryLedentsov We've tried similar with embedding Python. But the revaluation rates were too slow, hence looking for a more native to c++ solution. – Zamfir Kerlukson Oct 11 '13 at 17:30
  • @Arpegius please feel free to provide any insights you may have. – Zamfir Kerlukson Oct 11 '13 at 17:43
  • @ZamfirKerlukson, python might have been not the best choice. Apart from the binding itself, you can gain a lot by design of your expression library. If you use =[memoization](http://en.wikipedia.org/wiki/Memoization) or simply caching your results, you might be quite better off than just using even the fastes c++ business rule expression evaluation. Lua has a very low overhead, and [LuaJIT](http://luajit.org/) might give an extra kick. – Dmitry Ledentsov Oct 22 '13 at 07:29
  • Are your rules known at compile-time? – ManuelAtWork Jul 28 '17 at 11:18

2 Answers2

13

See the C++ Mathematical Expression Library outlined in this answer.

But, if you really want speed, consider compiling the expressions as C/C++ directly, then load them dynamically (shared objects/DLLs).

Community
  • 1
  • 1
Macke
  • 24,812
  • 7
  • 82
  • 118
  • 9
    We gave exprtk library a go, and its a good fit for the expression eval thanks for the suggestion. – Zamfir Kerlukson Oct 11 '13 at 17:33
  • wrt "compiling expression" that is what we're doing now, the problem is that this approach doesn't scale as the number of expressions increase and customers want to be able to add new expressions or modify current expressions. So a dynamic expression library like the one you suggested seems to be the best balance. – Zamfir Kerlukson Oct 11 '13 at 17:46
  • @ZamfirKerlukson: I'm talking about having your framework/app generate and compile DLLs on the fly, based on customer input. That would scale slightly better, although loading text is easier than binaries, that's for sure. ;) – Macke Oct 22 '13 at 17:41
1

Have you considered generating your own parser with Bison + Flex? It uses a FSM-based LALR parser implementation that is fast and is easy to write, and supports evaluation of expressions while you're parsing them, as well as AST generation for repeated evaluation.

Renan Gemignani
  • 2,683
  • 1
  • 21
  • 23