© 2018 Strange Loop
We will give a whirlwind tour of relational programming in miniKanren, a logic programming language we designed with Oleg Kiselyov, and which is described in 'The Reasoned Schemer' (MIT Press, 2005). miniKanren is simple but powerful, with only three core language forms. miniKanren's implementation is designed to be easily modified and extended, and has been ported from Scheme to more than a dozen host languages, most recently in the form of Clojure's 'core.logic' standard library.
We will present a variety of increasingly complicated miniKanren relations that "run backwards." For example, the addition relation can calculate that 3 + 4 = X has the solution X = 7, but can also calculate that 3 + X = 7 has the solution X = 4. More interestingly, the addition relation can generate all integer pairs (X, Y) such that X + Y = 7. We will demonstrate a relational Scheme interpreter that can generate programs that evaluate to a specified value (if any such programs exist!). Finally, we will show how the relational interpreter can be made to generate quines, which are programs that evaluate to themselves.