MiniKanren – An embedded DSL for logic programming | Hacker News Reader

MiniKanren – An embedded DSL for logic programming

minikanren.org

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.

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

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

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.

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

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

That's a nice read. Thanks for the rec.

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

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

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.

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

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

And now, I'm glad I have.

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

Eureka!

Why do they call it "Mini"?

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

So... Kanren doesn't look like it's actively developed anymore and now folks are working on MiniKanren. The guys doing MiniKanren appear to always work in Scheme, although lots of other folks re-implement the work they publish in whatever language they're currently infatuated with.

Clojure's Core-Logic is one such project and it appears to have the most active community... but it's not really accurate to call it a faithful implementation of either Kanren or MiniKanren; rather they've used those projects as a starting point and by now they've added various other capabilities or avoided/removed others.

Is that a fair summary?

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

And now there's microKanren, an even more simplified implementation that is "entirely functional and devoid of macros ... [making it] more directly portable than that of other miniKanren languages."

http://minikanren.org/#microKanrenPaper

https://github.com/jasonhemann/microKanren

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

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

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

Reply on news.ycombinator.com