ANN: Logos 0.1 - An Optimized miniKanren Logic Programming Library for Clojure

[David Nolen]

I announced it earlier this week on Twitter, but it's now come far along enough to be usable. You can write fun stuff like the following:

(defn likes

  [x y]

  (cond-e

   ((== x 'john) (== y 'mary))

   ((== x 'mary) (== y 'john))))

(defn musician [x]

  (cond-e

   ((== x 'john))

   ((== x 'bob))))

(run* [q]

  (likes q 'mary)

  (musician q))

;; [john]

(run* [q]

  (musician q))

;; [john bob]

(run* [q]

  (exist [x y]

    (likes x y)

    (== [x y] q)))

;; [[john mary] [mary john]]

My inspiration to start on this was Jim Duey's implementation. However I had two specific goals -

* Focus on performance. While developing I compared performance against miniKanren under Racket - I made sure the Clojure implementation ran at least as fast, and in many cases it runs quite a bit faster

* Implement "growable" sequences without resorting to Scheme's dotted pairs. This required me to develop a new protocol in which iteration might return a logic var instead of nil or a Seq.

The implementation started with the one described William Byrd's dissertation. However a considerable number of changes were made-

* substitutions are implemented as a protocol and a defrecord

* substitutions internally use a PersistentHashMap as well as PersistentVector (for debugging)

* supports unification of all the Clojure data structures supported by clojure.walk

* goal and goal constructors are implements as deftypes (Mzero, Unit, Choice, Inc) and those implement IMPlus and IBind protocols.

The code base is compact, some ~450 lines of Clojure.

Future directions:

* Friendlier interface for defining facts and running queries

* There are many great ideas in William Byrd's thesis that need looking into. In particular I'm interested in tabling.

* Investigating replacing the PersistentHashMap with a Skew Binary Random Access List or a Finger Tree. This would speed up the performance of the most expensive functions in the system, walk. In the Scheme implementations SBRALs can lead to 2.5X-100X in performance.

* Modifying the core macros to optimize logic programs.

* Parallel logic programming.

Source and more info here, https://github.com/swannodette/logos.

[jim]

Very, very nice. Excellent work. I look forward to using it.

I was looking at porting Kanren proper to Clojure. There appear to be
some really good ideas in there that maybe could be added to Logos.

Very well done.

Jim

[Jules]

Interesting. Is Byrd's dissertation available online?

[David Nolen]

On Sat, Dec 4, 2010 at 6:39 PM, Jules <jules...@gmail.com> wrote:

Interesting. Is Byrd's dissertation available online?

Yes I added that and several other resource links to the bottom of the project's description on the GitHub repo.

David 

 

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

[David Nolen]

On Sat, Dec 4, 2010 at 5:58 PM, jim <jim....@gmail.com> wrote:

Very, very nice. Excellent work. I look forward to using it.

I was looking at porting Kanren proper to Clojure. There appear to be
some really good ideas in there that maybe could be added to Logos.

Very well done.

Jim

I agree that there are many clever optimizations there that should be looked into. But my sense is that Kanren is an earlier project and miniKanren is the distillation of its lessons.

David