Efficient Predicate Dispatch [was ANN: Logos v0.6]

[David Nolen]

When things begin to get recursive you may be on the right track :D

Initially I was going to implement Nominal Logic Programming for Logos a la William Byrd's dissertation, but I realized that his implementation requires pattern matching. All the pattern matching libs I've seen thus far for Clojure are too naive and too slow. Even more importantly pattern matching is subsumed by predicate dispatch (CiteSeerX — Efficient Predicate Dispatching).

Rich Hickey mentioned many moons ago that he'd like to see a predicate dispatch implementation for Clojure that didn't have the kind of hardwiring found in the Chambers/Chen paper. He suggested investigating Datalog. After much reading, I've decided that a runtime in-memory Datalog that handles dispatching is going to be too slow for many useful scenarios (an efficient Datalog based on Binary Decision Diagrams might be possible, but this is an incredibly complex undertaking in itself, meh).

What we want is Standard MLs efficient compilation from decision diagrams to switch statements (CiteSeerX — Optimizing Pattern Matching). However Standard ML (Haskell, OCaml, Scala as well) pattern-matching has issues with order among other things (Programming in Standard ML).

What if we allow a logic engine to drive the compilation of the decision diagram? This would be done by users mapping logic predicates to Clojure predicate functions. Relationships between predicates can be added to the logic engine allowing compilation to produce a very efficient decision diagram. Nothing is hard coded, everything is driven by the kinds of predicates and relationships between predicates that a user actually cares about.

All this is to say that this means Logos needs the ability to load database of facts, index those facts, and to accept new facts and relationships and update accordingly. So this going to happen sooner rather then later.

I welcome any feedback from anyone who has thoughts on this approach to implementing predicate dispatch efficiently!

Some thoughts on what this might look like is evolving here, https://github.com/swannodette/match/wiki/Crazy-Ideas.

David

On Mon, Apr 11, 2011 at 3:08 PM, David Nolen <dnolen...@gmail.com> wrote:

On Mon, Apr 11, 2011 at 2:01 PM, Vagif Verdi <vagif...@gmail.com> wrote:

Can it be used as an inference (rule) engine ?

If you mean in the same way that you can build inference (rule) engines in Prolog - I don't see why not.

However there is a bit of work to be done in order to make building efficient rule engines easier:

* Be able to load a database (aka Clojure collection) of facts

* Indexing of facts

* Intelligently use indexed facts

Currently I'm a bit more interested in exploring type inference (via nominal logic) so I'm not sure when exactly I'll get to these, tho I'll gladly take patches from people who want such features sooner rather than later :)

David

[John Newman]

In order to answer a SO question I ended up whipping up a quick and dirty implementation of predicate dispatch here. (unless I'm misunderstanding the definition of "predicate dispatch")

If you know your dispatch set is going to be small, a first-one-wins strategy should be good enough, right? And we can't really measure the complexity of a user's supplied predicate function a priori anyway, so if an isa? hierarchy isn't supplied, we might as well just check them in the order they're provided from the user and let the first one win, right?

V/r

John

[Khalid Jebbari]

https://github.com/swannodette/match/wiki/Crazy-Ideas is 404, as well as https://github.com/swannodette/match

[John Newman]

Update the example to leverage isa? hierarchies and allow prefer-poly, a la prefer-method: https://stackoverflow.com/questions/53329709/dispatching-function-calls-on-different-formats-of-maps/53354967#53354967

V/r

John

[Aleš Roubíček]

It was promoted to contrib since then. https://github.com/clojure/core.match/wiki/Crazy-Ideas and https://github.com/clojure/core.match are links you are looking for. 

[Khalid Jebbari]

Oups, I didn't notice that the original message was from 2011...

--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clo...@googlegroups.com
Note that posts from new members are moderated - please be patient with your first post.
To unsubscribe from this group, send email to
clojure+u...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to a topic in the Google Groups "Clojure" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/clojure/peL04odPuCo/unsubscribe.
To unsubscribe from this group and all its topics, send an email to clojure+u...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.