6 ms·
Annotated implementation of microKanren: an embeddable logic language
- Jtsummers 4y agoAlong with μKanren, miniKanren is introduced in the book The Reasoned Schemer. The language is pretty straightforward to implement in other languages (or at least other lisps). http://minikanren.org/ http://minikanren.org/
- qsort 4y agoObligatory reference: https://aphyr.com/posts/354-unifying-the-technical-interview https://aphyr.com/posts/354-unifying-the-technical-interview
- gavinray 4y agoWhat in the absolute f*ck did I just read?
- thebeardisred 4y agoBecause of the way the line wrapped on my phone I initially read that as "Annotated implementation of microKaren". At that point my brain just went nuts and filled in the rest with "an embeddable non-logic language". :)
- avmich 4y agoFor those knowledgeable enough in Scheme the original microKanren - and some immediate extensions towards miniKanren - should be rather clear. It's for users of other languages, with other popular mechanisms, that questions arise. More comments for them would be welcome.
- ashton314 4y agoThe original microKanren is pretty clear; the one struggle I had with the paper was some of the variable names were a little too "cute": e.g. `s/c` all over the place; I assume this was a contraction for "substitution/counter" (i.e. the state) which is what I expanded it to. Super terse variable names are difficult for me to grok when I'm looking at something new. I did hew to the standard convention of representing a type environment with Γ (Gamma); hopefully that's not too confusing for people looking at the type checker. :)
- ejdo 4y agoI did a mostly-true-to-the-paper python implementation a while back, that may be helpful as well: https://github.com/Erik-J-D/microKanren-py https://github.com/Erik-J-D/microKanren-py
- ashton314 4y agoAuthor here: very happy to see some interest in microKanren. It's such a lovely little gem. Has anyone used microKanren as part of a production program?
- avmich 4y agoNo, and for me the problem is the following. I (can) have a variant of microKanren embedding in my environment, but the microKanren interface is rather inconvenient to use. miniKanren would be better, but to implement miniKanren in other languages is a bigger problem - actually I hoped to get some help with that using this annotation article.
- ashton314 4y ago> but the microKanren interface is rather inconvenient to use What specifically would make it easier? I'm not that familiar with miniKanren. Is it stuff covered by the convenience macros from the paper?
- avmich 4y agoGood question. I suspect the problem is in that the goals are expressed as functions in microKanren, and it's hard to figure out how to represent what is needed to get as such functions. It looks like Prolog approach is more understandable - there are symbols and rules; not sure if Prolog would be easier to embed in, say, Java and switch between Java objects and Prolog rules. microKanren is practically by definition for embeddability - so it's this aspect which for me present a problem.
- lukev 4y agoClojure's core.logic (a Clojure implementation of miniKanren) definitely gets some use in production.
- rscho 4y agoNot really production, but probably THE most impressive biomedicine research work I've seen (and I'm an academic MD): https://github.com/webyrd/mediKanren https://github.com/webyrd/mediKanren This is a FOL theorem prover that uses medical research articles as terms. They use it to do genetics and drug repurposing metaresearch. It's like the wet dream of all the biomed machine learning fanboys out there, except that: 1. it's not machine learning and 2. it really works
- nerdponx 4y agoLet's assume I'm a hipster and I wanted an excuse to embed a logic programming DSL in my application. What is a valid excuse / usecase? Does anyone here have any real-world success stories from something like this? Logic programming always appealed to me, but I always felt like I never understood what to actually do with it other than write toy programs about parent-child relationships (I tried learning Prolog a few times, but stopped for this reason).
- giraffe_lady 4y agoYeah I've had the same questions for a while. What specific concrete problem can you solve with this, that does not have as-good solutions available in any language powerful enough to easily implement it? I am kind of half-considering it for mud scripting? Each line from the mud represents a fact or relation so this could be used to query for specific information as needed. For this case though, it doesn't really seem better than writing a regex-based DSL though, something I'm far more familiar with and that is better supported.
- ModernMech 4y agoLogic languages are great for expressing database queries, so you can treat your program like a database. And if your program is a database you can do database-y things on it like using transactions to "rewind" the program state. Or in the context of distributed programming, well... distributed databases are a thing, and we know how to handle updates to databases in that context, so writing your distributed logic program is as easy as forming a series of database queries, and you can let the DBMS do the magic of distributing it. I guess I think of logic languages as SQL but I actually want to write my whole program in it.
- rscho 4y agoConstraint programming. Everyone will tell you that C++ and Java solvers are so much faster. That's true, but prolog for example is incredibly easy to use in comparison, and in fact not that slow. So if you're prototyping or aiming for something exotic that doesn't easily fit into existing libs, LP will be miles ahead. Generally speaking, you'll see the same pattern for any problem involving searching a space of potential solutions. In a word, the strength of LP is flexibility when facing the unkown (future feature requirement). EDIT: you mention parsing. If you're planning anything context-sensitive, you have to check out eDCGs. You probably won't use them, but they'll give you an idea of what's possible.
- giraffe_lady 4y agoLove all the racket I'm seeing around here recently. Most underrated lisp imo.