miniKanren, Relational Interpreters, and Synthesis of Lisp Programs
William E. Byrd
Functional programmers write definitions that model mathematical functions. These functions clearly distinguish between input arguments and output values. In contrast, relational programming treats programs as mathematical relations, eliminating the distinction between input and output. miniKanren is an embedded domain specific language for constraint logic programming, designed for writing interpreters, type inferencers, theorem provers, and other interesting programs as relations.
In this talk we will describe miniKanren, and show how a Scheme interpreter--written as a relation--can be used to perform synthesis of Scheme programs.
William E. Byrd is a Research Assistant Professor 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 loves StarCraft (BW & SC2). Ask him about the scanning tunneling microscope (STM) he is building.