This workshop will cover the fundamentals of programming in miniKanren (http://minikanren.org/), an embedded domain specific language for constraint logic programming. We will begin with an overview of the miniKanren language, and will write a few simple miniKanren relations that "run backward." We will then write a more sophisticated miniKanren program: an environment-passing Scheme interpreter, written as a relation. We will extend the interpreter in various ways, and explore how the interpreter can be used for program synthesis.
No prior knowledge of miniKanren, logic/relational programming, or interpreters is necessary. Some exposure to Scheme/Lisp, or another functional language, would be helpful, but is not necessary.
Will Byrd and Rob Martin guide the tutorial participants through concatentive programming - in some ways, the most functional of functional programming languages. Made up of only functions and compositions, concatenative languages are "point free" - no variables or named state needed. And we already use them every day. Forth, Postscript, even CPython and the JVM are based on concatenative principles of function composition and a stack. Imperative, highly efficient, easily optimized - concatenative languages are almost trivial. This tutorial works with a simplified language called Puppy, and is hands-on: participants will be both programmer and computer.
miniKanren is an embedded constraint logic programming language designed for writing programs as *relations*, rather than as functions or procedures. Unlike a function, a miniKanren relation makes no distinction between its inputs and outputs, leading to a variety of fascinating behaviors. For example, an interpreter written as a relation can also perform code synthesis, symbolic execution, and many other tasks.
This talk will introduce the ideas of relational programming and miniKanren, demonstrate the current state of relational programming through a series of examples, and explore the advancements needed to make relational programming fulfill its promise.
- give an introduction to miniKanren and relational programming
- show interesting relational programs, such as a relational interpreter
- demonstrate the remarkable flexibility of these relational programs
- show the current limitations of this programming style
- present a long-term vision, and a concrete medium-term plan, for making relational programming more useful
- Anyone interested in the long-term promise of very high-level declarative programming.
William E. Byrd is a Postdoctoral Researcher in the School of Computing at the University of Utah. He is co-author of 'The Reasoned Schemer', and is co-designer of the miniKanren relational programming language. He is also interested in the intersection of programming languages and synthetic biology.