© 2020 Strange Loop
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 http://minikanren.org/ and include:
Daniel P. Friedman, William E. Byrd and Oleg Kiselyov The Reasoned Schemer The MIT Press, Cambridge, MA, 2005 http://mitpress.mit.edu/books/reasoned-schemer
William E. Byrd Relational Programming in miniKanren: Techniques, Applications, and Implementations. Indiana University, Bloomington, IN, September 30, 2009. http://gradworks.umi.com/33/80/3380156.html
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. http://webyrd.net/quines/quines.pdf
Daniel P. Friedman and William E. Byrd Relational Programming in miniKanren Strange Loop 2012, St. Louis, MO, September 24, 2012 http://www.infoq.com/presentations/miniKanren
William E. Byrd and Daniel P. Friedman Fun with Relational Interpreters in miniKanren flatmap 2013, Oslo, Norway, May 14, 2013 (keynote). http://vimeo.com/user18356272/review/66548859/4f724d6341
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 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.