Strange Loop

Program Synthesis Using miniKanren

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). The workshop will be broken into three parts: 1) an introduction to the miniKanren language, using Scheme as a host language; 2) an introduction to writing relational interpreters and reducers in miniKanren; 3) experimentation with program synthesis using these interpreters and reducers, and discussion of more advanced techniques useful for relational program synthesis.

All code will be in Scheme, but the general techniques are also applicable to cKanren (Racket) and core.logic (Clojure). Students should install either Vicare Scheme or Petite Chez Scheme on their laptops, and should have an editor and command line capable of editing, loading, and running Scheme code.

We will provide a pointer to the latest version of miniKanren, with extensions for writing relational interpreters.

Other material on miniKanren and relational program synthesis attendees may find useful can be found at and include:

Daniel P. Friedman, William E. Byrd and Oleg Kiselyov The Reasoned Schemer The MIT Press, Cambridge, MA, 2005

William E. Byrd Relational Programming in miniKanren: Techniques, Applications, and Implementations. Indiana University, Bloomington, IN, September 30, 2009.

William E. Byrd, Eric Holk, and Daniel P. Friedman. miniKanren, Live and Untagged: Quine Generation via Relational Interpreters (Programming Pearl). 2012 Workshop on Scheme and Functional Programming, Copenhagen, Denmark, 2012.

Daniel P. Friedman and William E. Byrd Relational Programming in miniKanren Strange Loop 2012, St. Louis, MO, September 24, 2012

William E. Byrd and Daniel P. Friedman Fun with Relational Interpreters in miniKanren flatmap 2013, Oslo, Norway, May 14, 2013 (keynote).

William Byrd

William Byrd

William Byrd is a Postdoctoral Researcher in the School of Computing at the University of Utah. He is co-author of The Reasoned Schemer, and co-designer of several declarative languages. His StarCraft 2 handle is ‘Rojex’ (character code 715).

Daniel Friedman

Daniel Friedman

Indiana University

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.