Towards Bottom-Up Enumeration in miniKanren via Pruning and Memoization

View PDF HTML (experimental) Abstract:We present 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 (PBE) synthesizers, into the relational setting. The first combinator, prune, deduplicates an answer stream by a user-supplied key, typically the input/output behavior 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 in cases where the natural depth-first canonical order misses compact representatives. On a preliminary PBE 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. We leave a broader empirical evaluation to an extended version of this paper. Comments: 18 pages, plus appendices with full source code (60 pages total). Camera-ready for the miniKanren and Relational Programming Workshop 2026 (miniKanren'26) Subjects: Programming Languages (cs.PL); Logic in Computer Science (cs.LO) Cite as: arXiv:2607.25373 [cs.PL] (or arXiv:2607.25373v1 [cs.PL] for this version) https://doi.org/10.48550/arXiv.2607.25373 arXiv-issued DOI via DataCite (pending registration) Submission history From: Nikolai Kudasov [view email] [v1] Tue, 28 Jul 2026 07:28:51 UTC (94 KB)