[HN Gopher] Annotated implementation of microKanren: an embeddab...
___________________________________________________________________
Annotated implementation of microKanren: an embeddable logic
language
Author : ashton314
Score : 60 points
Date : 2022-05-25 15:31 UTC (7 hours ago)
(HTM) web link (github.com)
(TXT) w3m dump (github.com)
| avmich wrote:
| For 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 wrote:
| The 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 G (Gamma); hopefully that 's not too confusing
| for people looking at the type checker. :)
| ejdo wrote:
| I 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
| ashton314 wrote:
| Author 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?
| rscho wrote:
| Not really production, but probably THE most impressive
| biomedicine research work I've seen (and I'm an academic MD):
|
| 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
| lukev wrote:
| Clojure's core.logic (a Clojure implementation of miniKanren)
| definitely gets some use in production.
| avmich wrote:
| No, 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 wrote:
| > 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 wrote:
| Good 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.
| qsort wrote:
| Obligatory reference: https://aphyr.com/posts/354-unifying-the-
| technical-interview
| gavinray wrote:
| What in the absolute f*ck did I just read?
| ashton314 wrote:
| Now go read _Hexing the technical interview_ and others:
| https://aphyr.com/posts/341-hexing-the-technical-interview
| qsort wrote:
| I noticed just now that it was also linked at the bottom of
| the article. Definitely a fun one :)
| Jtsummers wrote:
| Along with mKanren, 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/
| giraffe_lady wrote:
| Love all the racket I'm seeing around here recently. Most
| underrated lisp imo.
| nerdponx wrote:
| Let'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).
| YeGoblynQueenne wrote:
| Here's some stuff I've written in Prolog, some for my own
| enjoyment, one for my degree project.
|
| Most of the benefits I found come down to two things:
|
| a) Prolog, like the various kanrens, is a relational language
| so a program is effectively a database. There's no need to do
| anything special to glue together a data layer and a logic
| layer, because you have both written in Prolog. No object-
| relational impedance mismatch whatsoever.
|
| b) Prolog's declarative style makes translating rules and
| directives into code a breeze. The three projects below are all
| games and benefit heavily from this feature. The same would go
| for business logic of any shape or form.
|
| 1. Warhammer 40K simulation:
|
| https://github.com/stassa/wh40ksim
|
| Runs simulations of combat between WH40k units.
|
| 2. Gleemin, a Magic: the Gathering expert system:
|
| https://github.com/stassa/Gleemin
|
| Doesn't work anymore! Because backwards compatibility. Includes
| a) a parser for the rules text on M:tG cards written in
| Prolog's Definite Clause Grammars notation, b) a rules engine
| and c) a (primitive) AI player. The parser translates rules
| text from cards into rules engine calls. The cards themselves
| are Prolog predicates. Your data and your program are one and
| now you can also do stuff with them.
|
| 3. Nests & Insects, a roguelike TTRPG:
|
| https://github.com/stassa/nests-and-insects
|
| WIP! Here I use Prolog to keep the data about my tabletop rpg
| organised, and also to automatically fill-in the character
| sheets typeset in the rulebook. The Prolog code runs a
| character creation process and generates completed character
| sheets. I plan to do the same for enemies' stat blocks, various
| procedural generation tables, etc. I also use Prolog to typeset
| the ASCII-styled rulebook, but that's actually _not_ a good
| application of Prolog (too imperative).
|
| You asked about "logic programming" in general and not
| miniKanren in particular. I haven't actually used miniKanren,
| so I commented about the logic programming language I've used
| the most, Prolog. I hope that's not a thread hijack!
|
| All three of the projects above are basically games. I have
| more "serious" stuff on my github but I am currently
| experiencing a certain shortfall of gravitas.
| [deleted]
| qsort wrote:
| You have to find a valid assignment of resources according to
| some business rules that are unstable/partially unknown/very
| likely to change.
|
| You have to solve some kind of 3-SAT-reducible problem that
| would be difficult to implement otherwise.
|
| You have to do some heavy pattern-matching.
|
| Closely related:
| https://en.wikipedia.org/wiki/Answer_set_programming
| giraffe_lady wrote:
| Yeah 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.
| rscho wrote:
| Constraint 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.
| mncharity wrote:
| > you have to check out eDCGs.
|
| https://github.com/kamahen/edcg ,
| https://occasionallycogent.com/prolog_edcgs/index.html
| mncharity wrote:
| > You probably won't use them,
|
| Curious - I fuzzily recall usually ending up manually
| threading state (eg, doing a Perl-Compatible Regular
| Expression engine), but I don't recall just why...
| giraffe_lady wrote:
| Ahhhh this is extremely helpful, thank you. I've been
| puzzling at the mud parsing thing because while it's in the
| _shape_ of natural language (and somewhat annotated in it
| eg there is spurious "decorative" information), it does
| represent a 1:1 mapping with computation already.
|
| This feels like a much better path than trying to get it
| into an AST with like yacc or whatever. But since it _isn
| 't_ actually natural language NLP didn't seem right either.
| I've got a lot of reading to do but this is very
| interesting.
| ModernMech wrote:
| Logic 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.
| evnc wrote:
| I'm casually exploring using logic programming to define rules
| for games, as an embedded scripting language in a game engine,
| which would handle input and rendering etc. and be written in a
| more "conventional" language.
|
| We'll see if performance is an issue, but the space I'm most
| interested in is turn based strategy / board games, where it
| doesn't seem to be a big deal if things are as fast as
| possible.
|
| It feels like a pretty natural fit, e.g.:
| can_move_to(unit_id, tile) :- Unit(unit_id),
| Tile(tile), reachable_to(unit_id, tile, move_cost),
| unit_move_points_remaining(unit_id, mv), move_cost <=
| mv.
|
| You can define a lot of rules from basic unit movement to "what
| happens when you activate Super Special Rule-Bending Ability"
| this way, and it's pretty easy to change the definitions if you
| want to experiment with different game rules / logic. In
| practice, you want various syntactic sugar.
|
| Haven't got a chance to take this very far yet, just casual
| experimentation, but it seems like there's potential.
| rscho wrote:
| You want pure I/O in an untyped language. DCGs are the easiest
| way to have that (although they also have their limits).
| nerdponx wrote:
| What do you mean by "pure I/O" in this case? And how does
| logic programming help with that?
|
| I've seen things like this in the context of "algebraic
| effects", where instead of performing I/O (and instead of
| using monadic I/O) you build up what amounts to an execution
| graph of effectful operations, which is then "interpreted" at
| runtime. Is that what you're describing?
| rscho wrote:
| No, what I'm describing is the "monadic" behaviour of
| `phrase_from_file/2` and similar predicates. In conjunction
| with definite clause grammars, this means that your I/O
| operations either conform to the provided spec or fail.
| This is a "hot topic" (if LP topics can really still be
| "hot") and sees active development in new prolog systems.
|
| Check this out for prolog:
|
| https://youtu.be/Dqpxy4W7fAo
|
| https://www.swi-prolog.org/pldoc/man?section=pio
|
| https://github.com/mthom/scryer-
| prolog/blob/084fc845902f7b43...
|
| "New" stuff in the MiniKanren world:
|
| https://staff.fnwi.uva.nl/c.u.grelck/nl-fp-
| talks/kourzanov.p...
|
| https://ifl2014.github.io/submissions/ifl2014_submission_18
| ....
| lukev wrote:
| One thing I'd love to see logic programming used for is in an
| infrastructure-as-code platform to provision cloud resources.
|
| I don't want to have to define security groups, subnets, route
| tables, etc. Instead, I want to declaratively say "Service A
| must communicate with Service B", and based on the properties
| of those services, all the correct cloud resources will be
| defined. Subject, of course, to constraints around security,
| etc.
|
| We are tantalizingly close to this with current IaC tools (CDK,
| Pulumi, etc) but at the end of the day you still need to define
| each granular cloud resource (even if the code to do so can be
| tucked away in a library abstraction.)
|
| I'm busy with my current gig now, but if you forced me to
| launch a startup at gunpoint, this would definitely be it.
| thebeardisred wrote:
| Because 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". :)
___________________________________________________________________
(page generated 2022-05-25 23:01 UTC)