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<http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.4553>
).

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<http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.6.5507>).
However Standard ML (Haskell, OCaml, Scala as well) pattern-matching has
issues with order among other things (Programming in Standard
ML<http://www.cs.cmu.edu/~rwh/smlbook/book.pdf>
).

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

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
* 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
<https://stackoverflow.com/questions/53329709/dispatching-function-calls-on-different-formats-of-maps/53354967#53354967>.
(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

Post by 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
<http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.4553>).
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
<http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.6.5507>).
However Standard ML (Haskell, OCaml, Scala as well) pattern-matching has
issues with order among other things (Programming in Standard ML
<http://www.cs.cmu.edu/~rwh/smlbook/book.pdf>).
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

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
* 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

--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to ***@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+***@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 the Google Groups "Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email to clojure+***@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[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

Post by John Newman
In order to answer a SO question I ended up whipping up a quick and dirty
implementation of predicate dispatch here
<https://stackoverflow.com/questions/53329709/dispatching-function-calls-on-different-formats-of-maps/53354967#53354967>.
(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

Post by 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
<http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.4553>).
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
<http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.6.5507>).
However Standard ML (Haskell, OCaml, Scala as well) pattern-matching has
issues with order among other things (Programming in Standard ML
<http://www.cs.cmu.edu/~rwh/smlbook/book.pdf>).
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

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
* 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

--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to ***@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+***@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 the Google Groups "Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email to clojure+***@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Khalid Jebbari]

https://github.com/swannodette/match/wiki/Crazy-Ideas
<https://www.google.com/url?q=https%3A%2F%2Fgithub.com%2Fswannodette%2Fmatch%2Fwiki%2FCrazy-Ideas&sa=D&sntz=1&usg=AFQjCNEXPd6rtfgrvqXsfNgHMPGx0Wjw7A> is
404, as well as https://github.com/swannodette/match
<https://www.google.com/url?q=https%3A%2F%2Fgithub.com%2Fswannodette%2Fmatch%2Fwiki%2FCrazy-Ideas&sa=D&sntz=1&usg=AFQjCNEXPd6rtfgrvqXsfNgHMPGx0Wjw7A>

Post by 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
<http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.4553>).
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
<http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.6.5507>).
However Standard ML (Haskell, OCaml, Scala as well) pattern-matching has
issues with order among other things (Programming in Standard ML
<http://www.cs.cmu.edu/~rwh/smlbook/book.pdf>).
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

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
* 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

--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to ***@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+***@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 the Google Groups "Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email to clojure+***@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[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.

Post by David Nolen
https://github.com/swannodette/match/wiki/Crazy-Ideas
<https://www.google.com/url?q=https%3A%2F%2Fgithub.com%2Fswannodette%2Fmatch%2Fwiki%2FCrazy-Ideas&sa=D&sntz=1&usg=AFQjCNEXPd6rtfgrvqXsfNgHMPGx0Wjw7A> is
404, as well as https://github.com/swannodette/match
<https://www.google.com/url?q=https%3A%2F%2Fgithub.com%2Fswannodette%2Fmatch%2Fwiki%2FCrazy-Ideas&sa=D&sntz=1&usg=AFQjCNEXPd6rtfgrvqXsfNgHMPGx0Wjw7A>

Post by 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
<http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.4553>).
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
<http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.6.5507>).
However Standard ML (Haskell, OCaml, Scala as well) pattern-matching has
issues with order among other things (Programming in Standard ML
<http://www.cs.cmu.edu/~rwh/smlbook/book.pdf>).
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

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
* 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

--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to ***@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+***@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 the Google Groups "Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email to clojure+***@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Khalid Jebbari]

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

Post by 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.

Post by David Nolen
https://github.com/swannodette/match/wiki/Crazy-Ideas
<https://www.google.com/url?q=https%3A%2F%2Fgithub.com%2Fswannodette%2Fmatch%2Fwiki%2FCrazy-Ideas&sa=D&sntz=1&usg=AFQjCNEXPd6rtfgrvqXsfNgHMPGx0Wjw7A> is
404, as well as https://github.com/swannodette/match
<https://www.google.com/url?q=https%3A%2F%2Fgithub.com%2Fswannodette%2Fmatch%2Fwiki%2FCrazy-Ideas&sa=D&sntz=1&usg=AFQjCNEXPd6rtfgrvqXsfNgHMPGx0Wjw7A>

Post by 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
<http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.4553>).
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
<http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.6.5507>).
However Standard ML (Haskell, OCaml, Scala as well) pattern-matching has
issues with order among other things (Programming in Standard ML
<http://www.cs.cmu.edu/~rwh/smlbook/book.pdf>).
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

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
* 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

--

You received this message because you are subscribed to the Google Groups "Clojure" group.
Note that posts from new members are moderated - please be patient with your first post.
To unsubscribe from this group, send email to
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
For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to ***@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+***@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 the Google Groups "Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email to clojure+***@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.