microKanren with Delayed Goals

Abstract

miniKanren is a relational programming language embedded in Scheme. This paper studies the problem of supporting delayed goals in the context of µKanren, the core of miniKanren. It explores different representations of delayed goals and tradeoffs between them. In the presented approach, delayed goals are both accumulated and dispatched throughout the execution of a program, and the ones that remain at the end are returned to the programmer as a continuation. A novel interface, inspired by the concept of engines, allows continuously supplying µKanren code to partially computed program outputs.