William Byrd

Ooo I love anything miniKanren related. I did a close reading of the implementation in the original miniKanren paper; you can see my write-up and implementation here: https://codeberg.org/ashton314/microKanren miniKanren paper: http://webyrd.net/scheme-2013/papers/HemannMuKanren2013.pdf Also relevant—a practical use-case for miniKanren: https://aphyr.com/posts/354-unifying-the-technical-interview

I would look at uKanren, the smallest mini-kanren cousin. I like Bodil Stokke's [1] introduction, but if you are not afraid of lisp, you can read/re-implement the original(?) [2] paper :) It is basically bunch of combinators for depth-first search? So if you think "I kinda want to brute-force solution for these hard-coded constraints", you might instead want to create a simple logic-programming environment first :-) Last time I played with these, I used it for implementing a toy cryptograhic protocol verification system for a term project. It have barely worked :D A.f.a.i.k. type-checkers often use some sort of logic programming at their core. [1] https://paperswelove.org/2015/video/bodil-stokke-%CE%BCkanren/ [2] http://webyrd.net/scheme-2013/papers/HemannMuKanren2013.pdf

I second the recommendation in Sir Whinesalot's post (which I haven't fully read yet) to look at miniKanren and microKanren. I found it extremely educational to port microKanren to OCaml a few years ago, and I think the result is somewhat more comprehensible than the original Scheme, though you'll still probably have to read the paper to understand it: http://canonical.org/~kragen/sw/dev3/mukanren.ml The most astonishing result of miniKanren is a Scheme interpreter that you can run forwards, backwards, or both. http://webyrd.net/quines/quines.pdf demonstrates using it to generate a Scheme quine, that is, a Scheme program whose output when run is itself ("miniKanren, Live and Untagged: Quine Generation via Relational Interpreters (Programming Pearl)", Byrd, Holk, and Friedman). §4.4 of SICP http://sarabander.github.io/sicp/html/4_002e4.xhtml also has an implementation of logic programming in Scheme which is extremely approachable. Unlike the post, I don't think Datalog is the place to look for deep insights about logic programming. Instead, it's the place to look for deep insights about databases.

> This sounds really interesting! Cheers! > I'm happy my article was helpful to you. It was just the thing! Very helpful. Thank you for writing it. > I really like how your notebooks integrate (judiciously chosen) execution trace display with explanation. I think this is something literate programming benefits a lot from. Cheers again. I find those traces aesthetically pleasing in and of themselves. I can imagine a (strange, niche) art gallery that had large prints of them on display. Jupyter notebooks have so many good things going on. (Not that they're perfect, but they hit a sweet spot IMO.) > I wonder if there's a way to include a smooth gradient from specific examples like your V('80 P') to more general cases, either with abstract interpretation or a Bret-Victor-style overwhelming battery of data points. I'm sure there is, there are so many possibilities. Just the traces alone could be animated or made into (partial) graphs (have you seen http://pythontutor.com/ ?) Concerning abstract interpretation, if you squint a little, the Prolog code already does that. Markus Triska suggested using the CLP(FD) integer constraints for the math primitives, which was brilliant, so it's doing a kind of abstract interpretation. You can give it a completely general stack "type" (just a logic variable) and it will tell you, e.g. '+' is: int(A), int(B) -> int(A+B) and so on. It's also pretty easy to replace the main operators to get a different (but related)…

Thanks for the question! I've heard of MPS but I don't know much about it. I need to watch the demos/screencasts! I'm very much interested in "tools for thought," which could include deduction assistants, but also other tools to augment human intellect. Barliman is the first program I've worked on with this tools-for-though mindset, which I've found very stimulating. I've been influenced by Englebart, Vannevar Bush, Licklider, Alan Kay, Alan Borning, Brett Victor, Alex Warth, Michael Nielsen, among others. I can point you to lots of resources on this topic, if you are interested. Michael Ballantyne and I started a mailing list/set of Google Hangouts called "As We May Thunk" to explore some of these ideas. You might find some of the hangouts interesting: http://webyrd.net/thunk.html https://groups.google.com/forum/#!forum/as-we-may-thunk I'm not sure I fully understand your question though. It sounds like you may have a specific tool or feature in mind. Can you elaborate a little more? I'm always up for email or a hangout if this isn't the best venue.

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.

Personally, I wasn't a fan of The Reasoned Schemer's format, https://io.livecode.ch/learn/webyrd/webmk worked better as my introduction. See also: µKanren (http://webyrd.net/scheme-2013/papers/HemannMuKanren2013.pdf) and various ports like CL (https://github.com/rgc69/si-kanren) or Clojure (https://github.com/clojure/core.logic)

This kind of reminds me of what happens when you implement an interpreter in a relational programming language, which lets you do cool stuff like generating quines by specifying that the program and it’s output should be the same. Quick search lead to this paper which is exactly what I’m talking about: http://webyrd.net/quines/quines.pdf

You can write a minikanren program that will generate quines. > We will teach attendees how to use the relational (logic) language miniKanren to write several relational interpreters and reducers capable of automatically synthesizing recursive, symbolic programs, including quines (programs that evaluate to themselves) and fixpoint combinators (such as the famous Y-combinator). https://www.thestrangeloop.com/2014/program-synthesis-using-minikanren… - miniKanren, live and untagged: quine generation via relational interpreters (programming pearl) (http://webyrd.net/quines/quines.pdf) by William E. Byrd, Eric Holk, and Daniel P. Friedman

What would be some advantages of this design over the µKanren design [0] which uses a search monad [1] and expresses unification and relations directly as plain values and functions? [0] http://webyrd.net/scheme-2013/papers/HemannMuKanren2013.pdf [1] http://homes.soic.indiana.edu/ccshan/logicprog/LogicT-icfp2005.pdf

Barliman is written in miniKanren[0], a logic/relational programming system built by Daniel Friedman[1], Will Byrd[2] & Oleg Kiselyov[3]. There are implementations of miniKanren in languages other than Scheme, one of the prominent being Clojure[4]. To oversimplify, in the miniKanren world programs are written using relational logic, wherein there are "variables" and then certain "relationships" between the variables. That is the program specification. Now we can run the specification and allow miniKanren to generate one or more variables that satisfy the relations. Thus a miniKanren program can have more than one answers. One interesting side-effect of this kind of an abstraction is that programs can also be run backwards to generate more programs that satisfy certain relations. That's pretty much what's happening with Barliman. [0] http://minikanren.org/ [1] https://en.wikipedia.org/wiki/Daniel_P._Friedman [2] http://webyrd.net/ [3] http://okmij.org/ftp/ [4] https://github.com/clojure/core.logic