Re: ANN: Logos 0.1 - An Optimized miniKanren Logic Programming Library for Clojure
On Sat, Dec 4, 2010 at 5:58 PM, jim 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 -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@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+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: ANN: Logos 0.1 - An Optimized miniKanren Logic Programming Library for Clojure
On Sat, Dec 4, 2010 at 6:39 PM, Jules 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 > On Dec 4, 9:41 pm, David Nolen wrote: > > 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. > > -- > You received this message because you are subscribed to the Google > Groups "Clojure" group. > To post to this group, send email to clojure@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+unsubscr...@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 post to this group, send email to clojure@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+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: ANN: Logos 0.1 - An Optimized miniKanren Logic Programming Library for Clojure
Interesting. Is Byrd's dissertation available online? On Dec 4, 9:41 pm, David Nolen wrote: > 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. -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@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+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: ANN: Logos 0.1 - An Optimized miniKanren Logic Programming Library for Clojure
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 On Dec 4, 2:41 pm, David Nolen wrote: > 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. -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@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+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
ANN: Logos 0.1 - An Optimized miniKanren Logic Programming Library for Clojure
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. -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@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+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
