MiniKanren – An embedded DSL for logic programming

[asolove]

After you learn to write miniKanren programs, you'll want to know how it works. The original miniKanren implementation combines the core of the logic processing with some crazy Scheme macrology for building a nice syntax. I spent several days puzzling through the back page of "The Reasoned Schemer" without really getting it.

Luckily, you can now read the microKanren paper (http://webyrd.net/scheme-2013/papers/HemannMuKanren2013.pdf) which breaks apart the "core" portion of the logic processing into a purely-functional bit, separate from the macros for the nice syntax.

That little core can be implemented very easily in almost any language with closures. For some fun, I implemented it in JavaScript using some sweet.js macros on top. It took about an hour to get something working, and a day or two to fix more bugs, and now I understand how kanren works. Plus I added some tracing in so I can see how different steps in the program cause the logic variables to get bound: http://adamsolove.com/microScopeKanren/

Definitely worth the time if you're interested in relational programming.

[michaelsbradley]

My first introduction to miniKanren was Dan Friedman and Will Byrd's joint presentation at Strange Loop 2012 – what a blast!

http://www.infoq.com/presentations/miniKanren

Byrd's dissertation on miniKanren is an accessible introduction to the concepts involved in relational programming:

http://gradworks.umi.com/33/80/3380156.html

[agumonkey]

Is it the talk where they infer programs that will return 6 ?

[jgalt212]

What's the best use case for these sort of languages? My guess is rule-based expert systems, but I'd love to hear what the crowd suggests as well.

[kyllo]

Solving constraint problems. Like a Sudoku solver: https://news.ycombinator.com/item?id=4325746

[sklogic]

This kind of languages is extremely useful, since many problems maps nicely to a logical or relational model.

I'm using a PAIP-style embedded Prolog and an optimised Datalog for fast prototyping compiler passes - things like alias analysis, implementing type systems (e.g., Hindley-Milner maps to Prolog naturally), constant folding, DCE, Array-SSA, and many more.

Harlan is using cKanren for region inference and some other passes.

A nice motivational paper (on Datalog): http://www.cs.cmu.edu/~aldrich/courses/654/tools/bierhoff-bd...

[Foxboron]

Hylang (https://github.com/hylang/hy), a lisp ontop of Python, got a MiniKanren implementation that is pretty neat: https://github.com/algernon/adderall

[sklogic]

A very impressive use of cKanren is in Harlan ( https://github.com/eholk/harlan ) - it is doing the region inference there.

[MisterMashable]

Minikanren is featured in a follow up to 'Seven Programming Languages in 7 Weeks' by Manning Pubs. 'Seven More Programming Languages in Seven Weeks'. I think Elixir and Julia are also going to be included in the book. Anyway, if anyone here is into Manning books there's a MiniKanren chapter to look forward to. Disclaimer?!: I do not work for Manning. Just a reader.

[pselbert]

There was a nice interview with Will Byrd a couple episodes ago on the Cognicast (Cognitect's Podcast). He discussed MiniKanren along with a ton of other work and thoughts. Recommended listening.

http://blog.cognitect.com/cognicast/063-will-byrd

[daveloyall]

I'd never considered the possibility of DSLs being implemented in more than one host language.

And now, I'm glad I have.

[e12e]

Integer math and regular expressions come to mind... ;)

[Quequau]

Why do they call it "Mini"?

[keithflower]

It's a minimal version of Kanren, which was originally developed by Dan Friedman and Oleg Kiselyov:

http://kanren.sourceforge.net/

I give a simple example of a toy use of Kanren and made a few observations about logic programming systems, here:

http://apps.keithflower.org/?p=238

Those interested will probably want to read "The Reasoned Schemer":

http://mitpress.mit.edu/books/reasoned-schemer

[derefr]

It's a simplified version of http://kanren.sourceforge.net

[whitten]

Is there a standard syntax for Kanren or is it a standard set of Kanren specific functionality ?

[yepguy]

There's no standard syntax. It's supposed to be embeddable into existing programming languages, using the normal syntax for that language.

[sigjuice]

Relevant podcast episode http://www.functionalgeekery.com/episode-9-william-e-byrd/