Relational Programming in miniKanren
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.
Daniel P. Friedman is Professor of Computer Science at Indiana University. He is co-author of The Little Schemer, The Seasoned Schemer, The Reasoned Schemer, Scheme and the Art of Programming, and Essentials of Programming Languages, 3rd Edition, all published by MIT Press.
William E. Byrd is a Postdoctoral Fellow at the Center for Research in Extreme Scale Technologies (CREST) at Indiana University. He is co-author of The Reasoned Schemer, and co-designer of several declarative languages: miniKanren (logic programing), Harlan (GPU programming), and Kanor (cluster programming). His StarCraft 2 handle is ‘Rojex’ (character code 715).