Relational Programming in miniKanren: an Interactive TutorialmkTut2023

Relational Programming is a paradigm in which programs represent mathematical relations (in contrast to functional programming, in which programs represent mathematical functions). Unlike traditional programs, relational programs do not distinguish between inputs and outputs. Instead, any argument to a relational program can be treated as either an input or an output. This unusual property makes relational programs extremely flexible, and able to automatically perform tasks that would be complicated to implement using standard techniques. For example, an interpreter written as a relation is able to perform program synthesis, automatically generating programs from input/output examples.

In this in-depth, interactive, two day tutorial, we will explore the world of relational programming using miniKanren, a language specifically designed for writing interesting programs as relations. Together we will implement the core of the miniKanren relational programming language. We will also implement an interpreter for a subset of Racket, written as a miniKanren relation. We will then use this “relational interpreter” to perform simple program synthesis, and discuss techniques that can speed up synthesis by many orders of magnitude.

The tutorial will be highly interactive. We will implement all the code together, using the Racket programming language (a variant of Scheme). We will begin with a short introduction to basics of the Racket language, which can be learned in a few minutes. If you would like to implement all the code yourself, please bring a laptop with DrRacket installed (https://racket-lang.org/). If you don’t want to implement the code yourself, you can participate by helping me as I write the code at the projector! :)

Topics we will cover in the tutorial:

• fundamental concepts of relational programming
• a brief introduction to the Racket programming language
• introduction to the miniKanren relational programming language
• writing recursive relations in miniKanren
• writing a simple Racket interpreter as a function in Racket
• writing a simple Racket interpreter as a relation in miniKanren
• using the relational Racket interpreter to perform simple program synthesis
• optimizations and extensions to the relational Racket interpreter
• implementing the core of miniKanren (microKanren)
• open research problems in relational programming
• lots of other interesting related topics