miniKanren 如何实现自底向上枚举

Towards Bottom-Up Enumeration in miniKanren via Pruning and Memoization

这篇论文提出了两个基于 plain miniKanren 的小型库组合子，旨在将非关系型程序示例合成（PBE）中标准的自底向上枚举与观察去重技术引入关系型设置。第一个组合子 prune 通过用户提供的键（通常是候选项的输入/输出行为）对答案流进行去重。第二个组合子 defrel/bank 针对规范的新鲜变量对关系进行记忆化，从而构建单一的修剪后答案流，并在每个调用站点回放。此外，还讨论了带权重的变体 defrel/bank-w，它通过为未成熟流附加可接受的边界来恢复最佳优先枚举。在算术和字符串合成目标的初步 PBE 基准测试中，defrel/bank 在大多数深层目标上显著优于深度受限基线，但在少数因规范深度优先枚举顺序遗漏紧凑代表项的情况下表现不佳。