Revise the implementation of logical expressions

[thomaskeller79]

Original report by geisserf (Bitbucket: 557058:e7a9f9a5-3ea8-4154-97d2-10446425dce3, GitHub: geisserf).

---

Our current implementation of logical expressions and related functions has three major disadvantages:

• no memory management. Whenever a new logical (sub-)expression is created, we have a new raw pointer which never gets deleted, even if the expression is not used anymore. This leads to problems when we implement algorithms with many expression transformations (e.g. EVMDD implementations in our icaps2016 paper).

• due to the way logical expressions are implemented, methods transforming logical expressions have to do dynamic casting if their logic requires the knowledge of the specific type. This not only leads to boilerplate code, but has also influence on the runtime of such methods, e.g. state evaluation.

• the current implementation is cumbersome to extend. When we want a new method which works on expressions, it has to be implemented in every expression type (logical_expressions.h has already nearly 1000 lines of code).

A new implementation should consider all three points.

[thomaskeller79]

Original comment by geisserf (Bitbucket: 557058:e7a9f9a5-3ea8-4154-97d2-10446425dce3, GitHub: geisserf).

---

I've already done some research on other implementations of domain-specific languages (DSL). [1] and [2] considers the visitor pattern. Another popular framework is the Boost Proto Library. However, I'm currently investigating Catamorphisms; they have the advantage that they are an algebraic sound tool to evaluate functions and are powerful enough to support arbitrary methods applied on expressions. Eric Niebler (the author of the Proto library) considered them one time for Proto and they are a popular tool in Haskell. I'm currently investigating the C++ approach, how easy it is to implement, and if it suits our requirements.

[geisserf]

We will try out whether we can replace the LogicalExpression class with the expression library exprtk. This could potentially allow us to get rid of the caching of evaluatables alltogether, since it is possible that the expression evaluation of the library is fast enough to not warrant caching anymore.

[geisserf]

I mentioned that it might be possible that the evaluations can not be generated dynamically and instead have to be known at compile time. I think this example shows that this is wrong. Here, the program allows a user to input an expression which is then evaluated. The variables in the example are pre-specified, but from my read of the manual that is not necessary.

[speckdavid]

Here, is a profiling example (#108): ./search-profil earth-observation_inst_mdp__01 "[Prost -s 1 -se [THTS -act [UCB1] -out [UMC] -backup [PB] -init [Expand -h [IDS]]]]"

• CACHING ABORTED IN STEP 6 OF ROUND 1
• first 20 steps of each round: ~35 trials
• getApplicableActions seems to be a bottleneck