Monadic nature of backtracking tree-exploring operations

[Ichthyostega]

Do we need Monads?

Not sure about that one...

It is not clear if an basically imperative state based language like C++ can benefit from Monads.
Even more, it is not clear if »Monads« are a Design Pattern, which means they would pave the way
towards clear, concise, self explanatory and sane code. It could well be, that Monads are rather some
kind of Anti-Pattern -- something which seems obvious and fascinating, yet in fact increases the
code complexity for no good reason.

That being said — it is obvious we have a recurring pattern when it comes to "resolving solutions":
Due to a basic trend in the overall design of Lumiera, at various places we get the task to search for
a solution, or to figure out a binding from given configuration, rather than executing predetermined
hard-wired logic. All these algorithms share the common property that some kind of opaque state
need to be explored and expanded upon, and typically the (highly complex) mechanics of performing
this exploration can (and in fact should) be separated from the specifics of the target domain in question.
To add to this challenge, in most cases we've encountered thus far, it is desirable, or even mandatory
to perform this algorithmic computation demand-driven (pull principle), because this is the only way
to get along with a more-or-less fixed, pre-allocated memory buffer.

From the theoretical side of computer science (or mathematics, you'd might say) we know, that any
computation with these properties (tree expanding, backtracking) can be cast as a combination of
Monads. So the question to investigate and clarify would be, if taking such an approach will

• allow for generic algorithm building blocks, which can be combined more easily than developing the computation logic from scratch each time
• lead to more readable code, which focuses better on the actual point in question
• allows for a clean separation between the »mechanics« of the evaluation and the specifics of the target domain logic
• can be implemented without producing serious overhead (to be clear: garbage collection is not desirable).

[Ichthyostega]

The first experiences with the design chosen for the new pipeline builder, the TreeExplorer (#1117) look promising. This second design attempt is a compromise, insofar we do not attempt to build a classic monad structure (as in IterExplorer, which incidentally can be now completely superseded by the new design); rather we mostly stick to the well established functional pipeline pattern, but integrate a "monadic element" in the form of the expandChildren() operation.

• writing evaluation code on top of that design is slick and fun
• however, debugging the implementation of the pipeline building blocks can be quite a challenge, as soon as imperative side-effect loaded behaviour enters the scene. Not really a surprise.
• moreover, we should keep an eye on the performance side. Code built on top of TreeExplorer has the tendency to bloat the executable, both by heavy inlining and the generation of lots of very special nested template instantiations.

[Ichthyostega]

• the initial design, directly based on the »Monads« from functional programming, was a failure and has been retracted now
• yet the second design built around a pipeline builder is able to adapt to various situations and can also integrate monad-like exploration patterns as a special case

So this second design is now renamed to IterExplorer and used to build exploring and backtracking evaluations.

Questions to re-assess later

• can this solution be reconciled with the ranges from the standard library, and with evaluation pipelines?
• can the obnoxious error messages be improved when using appropriate Concepts (C++20)
• how does it behave in terms of performance and code size?

[Undercover Agent]

Migration MasterTickets ⟼ Subtickets-plugin