First-order miniKanren representation: Great for tooling and search
We present a first-order implementation of miniKanren that makes it easy to build a miniKanren debugger, and allows any other processes (including a human or a neural network) to guide the search. Typical miniKanren implementations use procedures to represent data structures like goals and streams. Instead, our implementation uses Racket structs, which are transparent, decomposible, manipulable, and not coupled with a particular search strategy. We obtain this first-order implementation by carefully applying defunctionalization rules to a higher-order implementation, deriving two compatible versions with the same search behavior and comparable performance. Decoupling the search in the first-order implementation makes it possible to analyze, transform, and optimize miniKanren programs, even while that program is running. We use a “human guided” search as a miniKanren debugger, and to demonstrate the breath of supported search strategies. The flexibility in how we interpret goals and streams opens up possibilities for new tools, and we hope to inspire the community to build better miniKanren tooling.
Thu 22 Aug
|15:20 - 15:55|
Gregory Rosenblatt, Lisa ZhangUniversity of Toronto, William E. ByrdUniversity of Alabama at Birmingham, USA, Matthew MightUniversity of Alabama at Birmingham | Harvard Medical SchoolLink to publication
|15:55 - 16:30|
|Link to publication|