Algorithms beyond Rete

[alex-dixon]

Yesterday, @mikegai had a very fruitful discussion with me about significantly enhancing the performance characteristics of Precept for certain operations without compromising its declarative language.

This is intended to be a broad issue warranting thought and discussion about how we, as a dependent of Clara and its Rete implementation, might implement general purpose algorithms that work alongside Rete and effectively access those algorithms from within a rule's LHS.

Candidate algorithms

• A*
• Dijkstra's
• Quadtree

This is currently on the roadmap for post OSS release. That said, we may need it a version of this implementation for internal projects pre-release (or very shortly thereafter), so a prototype for the public API may surface sooner.

How it might work

• Find and require a CLJ/CLJS implementation of the algorithm 😄
• Determine whether the API should be wrapped to facilitate ease of use with tuples or ease of use generally
• Write macros for dsl ns that may be used in the left hand side of the rule to, e.g., (distance ?a ?b). Like entities these may generate rules and facts from the values of bindings elsewhere in the LHS. Generated rules may insert from their RHS facts that are the result of the algorithm with the arguments supplied, which may then be accessed by a rewritten version of rule that included the macro.

[boxxxie]

would recommend looking into constraint solvers. also, would not recommend baking any optimizations into the rules engine, unless they are proven good in the general case (quadtree/Octtree are suboptimal in most cases).

but, this is such a huge solution space, it may be better to make a simple, less specific rule, use that output in an optimization algorithm, then use that result as a way to make rules that are not subject to poor performance with the rules engine.

[alex-dixon]

@boxxxie Thanks for the recommendations. Overall this issue was created when considering some things we'd want to do that Rete might not be the best at performance-wise, or that rules might not be the easiest to express without some work. I think part of the thought was that we could/should APIify that with separate libraries from the core to make it easier to use rules for things like pathfinding. I think you're right that the space is so large and solutions are possible to implement in a fairly straightforward fashion now, which makes me think we should probably wait until specific problems/requests are encountered before expending much energy here. We haven't run into anything in practice that a combination of rules and Clojure(script) haven't been able to address simply and performantly. If and when we do, at least we have a start on thinking about how to add the best tools for the job to our toolbox.