Search customization & instrumentation

Notes

Currently if you want search that's different from miniKanren search, you're out of luck. Jamie Brandon has done some work to make this more flexible but I think we can take it a step further.

The key insight is that search is completely driven by data structures. The problem is that what data structures we produce is hard coded to a particular type Substitution. Instead Substitution should contain a new field, call it st for "strategy" which is a ISearch (a protocol) instance. We could imagine that ISearch looks something like the following:

(defprotocol ISearch
  (conjunct [_])
  (disjunct [_])
  (commit [_])
  (cut [_]))

We should of course be skeptical of commit and cut, perhaps it better to put those in a seperate protocol.

(defprotocl IMKSearch
  (commit [_])
  (cut [_]))

Eventually we should see if these could be constructed on lower level primitives, for example as described in Search Combinators.

Going down this route would also free us to experiment with instrumenting search for custom debugging and things like that.

The main thing to be concerned with here is affect search perfomance, but seeing as it's only one more inline protocol dispatch I'm pretty confident that this can perform well.