4 ms·

MiniKanren – An embedded DSL for logic programming

michaelsbradley 12y ago
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 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 http://gradworks.umi.com/33/80/3380156.html
- agumonkey 12y ago
  Is it the talk where they infer programs that will return 6 ?
Quequau 12y ago
Why do they call it "Mini"?
- derefr 12y ago
  It's a simplified version of http://kanren.sourceforge.net http://kanren.sourceforge.net
  - michaelsbradley 12y ago
    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 http://minikanren.org/#microKanrenPaper https://github.com/jasonhemann/microKanren https://github.com/jasonhemann/microKanren
- keithflower 12y ago
  It's a minimal version of Kanren, which was originally developed by Dan Friedman and Oleg Kiselyov: http://kanren.sourceforge.net/ 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 http://apps.keithflower.org/?p=238 Those interested will probably want to read "The Reasoned Schemer": http://mitpress.mit.edu/books/reasoned-schemer http://mitpress.mit.edu/books/reasoned-schemer
  - Quequau 12y ago
    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?
whitten 12y ago
Is there a standard syntax for Kanren or is it a standard set of Kanren specific functionality ?
- yepguy 12y ago
  There's no standard syntax. It's supposed to be embeddable into existing programming languages, using the normal syntax for that language.
daveloyall 12y ago
I'd never considered the possibility of DSLs being implemented in more than one host language. And now, I'm glad I have.
- e12e 12y ago
  Integer math and regular expressions come to mind... ;)
  - daveloyall 12y ago
    Eureka!
MisterMashable 12y ago
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.
Foxboron 12y ago
Hylang (https://github.com/hylang/hy https://github.com/hylang/hy), a lisp ontop of Python, got a MiniKanren implementation that is pretty neat: https://github.com/algernon/adderall https://github.com/algernon/adderall
sklogic 12y ago
A very impressive use of cKanren is in Harlan ( https://github.com/eholk/harlan https://github.com/eholk/harlan ) - it is doing the region inference there.
sigjuice 12y ago
Relevant podcast episode http://www.functionalgeekery.com/episode-9-william-e-byrd/ http://www.functionalgeekery.com/episode-9-william-e-byrd/
asolove 12y ago
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 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/ http://adamsolove.com/microScopeKanren/ Definitely worth the time if you're interested in relational programming.
pselbert 12y ago
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 http://blog.cognitect.com/cognicast/063-will-byrd
jgalt212 12y ago
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 12y ago
  Solving constraint problems. Like a Sudoku solver: https://news.ycombinator.com/item?id=4325746 https://news.ycombinator.com/item?id=4325746
- sklogic 12y ago
  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-bddbddb-05.pdf http://www.cs.cmu.edu/~aldrich/courses/654/tools/bierhoff-bd...
  - jgalt212 12y ago
    That's a nice read. Thanks for the rec.

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 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 http://gradworks.umi.com/33/80/3380156.html

agumonkey 12y ago
Is it the talk where they infer programs that will return 6 ?

Quequau 12y ago

Why do they call it "Mini"?

derefr 12y ago
It's a simplified version of http://kanren.sourceforge.net http://kanren.sourceforge.net
- michaelsbradley 12y ago
  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 http://minikanren.org/#microKanrenPaper https://github.com/jasonhemann/microKanren https://github.com/jasonhemann/microKanren
keithflower 12y ago
It's a minimal version of Kanren, which was originally developed by Dan Friedman and Oleg Kiselyov: http://kanren.sourceforge.net/ 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 http://apps.keithflower.org/?p=238 Those interested will probably want to read "The Reasoned Schemer": http://mitpress.mit.edu/books/reasoned-schemer http://mitpress.mit.edu/books/reasoned-schemer
- Quequau 12y ago
  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?

whitten 12y ago

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

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

daveloyall 12y ago

I'd never considered the possibility of DSLs being implemented in more than one host language. And now, I'm glad I have.

e12e 12y ago
Integer math and regular expressions come to mind... ;)
- daveloyall 12y ago
  Eureka!

MisterMashable 12y ago

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.

Foxboron 12y ago

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

sklogic 12y ago

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

sigjuice 12y ago

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

asolove 12y ago

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 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/ http://adamsolove.com/microScopeKanren/ Definitely worth the time if you're interested in relational programming.

pselbert 12y ago

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 http://blog.cognitect.com/cognicast/063-will-byrd

jgalt212 12y ago

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 12y ago
Solving constraint problems. Like a Sudoku solver: https://news.ycombinator.com/item?id=4325746 https://news.ycombinator.com/item?id=4325746
sklogic 12y ago
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-bddbddb-05.pdf http://www.cs.cmu.edu/~aldrich/courses/654/tools/bierhoff-bd...
- jgalt212 12y ago
  That's a nice read. Thanks for the rec.