Towards Bottom-Up Enumeration in miniKanren via Pruning and Memoization
Two small library combinators on top of plain miniKanren, designed to bring bottom-up enumeration with observational deduplication — the standard tool in non-relational program-by-example synthesisers — into the relational setting. The first combinator, prune, deduplicates an answer stream by a user-supplied key, typically the input/output behaviour of the candidate. The second, defrel/bank, memoizes a relation against canonical fresh variables, so that a single pruned answer stream is built bottom-up and replayed at every call site.
We also discuss a weighted variant, defrel/bank-w, which attaches admissible upper bounds to immature streams to recover best-first enumeration. On a preliminary benchmark of arithmetic and string synthesis targets, defrel/bank substantially outperforms the depth-bounded baseline on most deep targets, while losing on a small family where the canonical depth-first enumeration order misses compact representatives.
Kudasov, N. (2026). "Towards Bottom-Up Enumeration in miniKanren via Pruning and Memoization." Proceedings of the 2026 miniKanren and Relational Programming Workshop, co-located with ICFP 2026, Indianapolis, USA. arXiv:2607.25373.