Clojure and Logic: Lojic Part Two | Hacker News Reader

Clojure and Logic: Lojic Part Two

clojure.com

81 pointsfogus10 comments

If anyone knows about it, I'm curious about any of the history and evolution of Kanren/miniKanren (the original Scheme versions) not found in standard reference papers, and wonder if any of the authors frequent HN.

There seem to be three distinct implementations in the Kanren family at:

http://kanren.sourceforge.net/

1) Kanren (v4.50) - the full-blown logic system by Dan Friedman and Oleg.

2) "minikanren.scm" (v4.50) - this isn't the miniKanren that's used in The Reasoned Schemer (RS) - it appears to be a trimmed-down version of Kanren that may have been used in Univ. of Indiana classes, e.g:

http://www.cs.indiana.edu/l/www/classes/c311/minilop.pdf

It's an interesting version in its own right, and I've used it for some Datalog-like experiments. I wonder if this was an early attempt to adapt Kanren for teaching, or if anything else drove its implementation.

3) "mk.scm" (v1.3) - the RS' miniKanren by Friedman, Oleg Kiselyov, William Byrd, and Chung-chieh Shan...also described in Byrd's dissertation:

https://scholarworks.iu.edu/dspace/bitstream/handle/2022/877...

There are other versions as well - a microKanren, a couple of implementations by the U. of Indiana folks for things like nominal logic programming (alphaKanren) and constraint logic programming (cKanren), and of course the Clojure version discussed in the link.

These are all fascinating projects, and the full-blown Kanren implementation (in Scheme) is quite fast for things I've used it for. Much of the work you see recently on the web discusses the core.logic (miniKanren/Clojure) implementation. I'd be interested in hearing from others who've used any of these systems.

miniKanren is also a "full-blown" logic system. Kanren is mostly about optimizations. From what I've seen these can be applied to miniKanren implementations.

That's cool that you found minilop! It looks like that was an early attempt to whittle down Kanren to its essence which became the miniKanren used in The Reasoned Schemer.

2) is a version of miniKanren not much different from the one used in Byrd's dissertation.

cKanren is not really a "different" version of miniKanren. It retains most of the miniKanren core and adds constraint logic programming. From what I can tell, you can consider this the new miniKanren.

Great research by the way, it's awesome to see this kind of thing on HN.

Many thanks for the info. I'll have to delve into cKanren more - I kind of glossed over it.

For anyone else interested, it looks like Claire Alvis is leading development of cKanren. Here's a background paper and a link to the source on github:

http://scheme2011.ucombinator.org/papers/Alvis2011.pdf

https://github.com/calvis/cKanren

And here's a short example and discussion of use of cKanren by (I think) one of the core.logic creators:

http://dosync.posterous.com/another-taste-of-ckanren

http://groups.google.com/group/clojure/browse_thread/thread/...

Also, the Friedman group maintains some other source here:

https://github.com/iucs/relational-research

which includes...wait for it...babyMiniKanren (babymk)!

The dosync.posterous.com link is me ;)

Heh...excellent, David! Thanks for the great work - I've read several pieces you've done on Kanren stuff (and read some of your past logic programming comments here), and I've learned a lot.

EDIT: You supplemented Clojure's implementation of miniKanren (core.logic) with great macros like defrel, facts, extend-rel, and a lot of other stuff. Those are the kinds of things that seemed a bit more convenient to me in Kanren (the optimized Scheme version), maybe because they seem more "Prolog-like" to me, especially extend-rel. I need to go back and look at RS miniKanren again to see how easy/desirable it would be to have those macros. Any thoughts?

I showed my extensions to Dan & Will and they both liked them. I think miniKanren could benefit from clear, simple implementations of something like defrel, fact, etc.

I would email Prof. Friedman, I've spoke with him in the past and he was very friendly and extremely eager to discuss his work (of course keep in mind he is very busy). As far as I could tell chatting with him the whole Kanren system is a continually evolving project to make a better and better logic programming system in scheme. He's an amazing hacker and extremely dedicated to pushing Scheme to it's absolute limits, I remember him showing me all the places where him and his co-author were able to reduce 6 loc to 4 here and 10 to 8 there etc. You could tell that he's continually reviewing code saying "I know this can be more abstract, more simple but how?" I think they've reduced the implementation used in the reasoned schemer from 2 to 1 1/2 pages at this point (edit: originally said 6 to 4 pages but reviewing some notes from the meeting, after seeing keithflower's reply, I've adjusted it accordingly ). If you can't get in touch with Friedman definitely try some of the other co-authors, Friedman gives them a ton of credit for making the system as awesome as it is today.

Thanks, good idea. I've got he and Mitchell Wand's well-known Essentials of Programming Languages and it taught me a ton.

You're right about the conciseness of RS miniKanren - it's just two pages in the "Connecting the Wires" part of the text.

Ah yes it is 2 pages, I've edited my comment above, believe it or not they actually have reduced it even further to roughly a page and a half. I was really inspired by the extreme dedication and passion it takes to look at a full logic programming implementation in 2 pages of code and say "nope, we can do better". Dan is definitely one of my all time heroes.

I bought "The Reasoned Schemer" several years ago, but did not work all the way through it. I am using Clojure a lot now on customer and personal projects so I'll give Lojic a good look.

Reply on news.ycombinator.com