Towards Bottom-Up Enumeration in miniKanren via Pruning and Memoization
本文引入了两个 miniKanren 库组合子 `prune` 和 `defrel/bank`，它们通过观测去重和记忆化实现了自底向上的枚举，从而显著提高了在深层目标上进行关系程序合成的性能，同时还提出了一种加权变体，以解决规范深度优先排序无法找到紧凑代表的情况。
原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。 阅读完整免责声明
想象一下你是一名正在破解谜题的侦探，但你的任务不是寻找线索，而是试图制造一台能够完成特定工作的机器，比如把数字 2 变成 4，把 3 变成 9，把 4 变成 16。你并不知道这台机器使用的确切公式，你只知道结果。这被称为“通过示例进行编程”（Programming by Example）。为了找到答案，你可以尝试构建每一种可能的机器，一个接一个地尝试，从最简单的齿轮和杠杆开始，并测试每一个是否有效。这有点像一位厨师试图通过尝试面粉、糖和鸡蛋的所有可能组合，直到做出一种味道正确的配方。
在计算机科学的世界里，有一种特殊的思维方式叫做“关系式编程”（relational programming）。你不是告诉计算机如何一步步寻找答案，而是描述答案看起来是什么样的，然后让计算机自己去寻找路径。这就像是告诉机器人，“在迷宫中为我找一条路”，而不是“向左转，走三步，然后再向右转”。计算机非常擅长同时探索许多路径，但它有一个棘手的习惯：它倾向于反复探索相同的死胡同，或者卡在一个漫长且曲折的隧道里，而错过了就在旁边的短小精悍的捷径。这篇论文旨在解决这个问题，通过教计算机如何成为一个更聪明、更有组织的探索者。
问题所在：在迷宫中迷失
想象一下，你正在一个堆满了数百万把钥匙的巨大且杂乱的阁楼里寻找一把特定的钥匙。大多数钥匙看起来各不相同，但它们都能打开完全相同的门。如果你是一个笨拙的探索者，你可能会拿起一把钥匙，试了一下，发现它有用，然后又花好几个小时去拿起其他看起来不同但同样有用的钥匙，仅仅为了确认一下。你在浪费时间检查那些做着完全相同工作的钥匙。
在计算机程序的领域，这种情况经常发生。当计算机试图构建一个程序将输入转化为输出时，它会生成成千上万个看起来不同的代码片段。其中许多片段是伪装起来的“双胞胎”——尽管内部看起来不同，但它们执行的功能完全一样。一种标准的计算机搜索方法（其工作原理类似于深度探索者）会检查一个双胞胎，接着是下一个，再下一个，速度变得越来越慢。这就像是在草堆里找针，但这个草堆是由数百万根看起来略有不同的针组成的。
解决方案：“剪枝”与“银行”
这篇论文的作者 Nikolai Kudasov 想出了两个聪明的工具来解决这个混乱局面。把它们想象成一个神奇的过滤器和一个智能图书馆。
1. “剪枝”（Prune）工具（过滤器）
想象你有一条传送带，机器正在不断生产钥匙。 “剪枝”工具就像站在传送带旁的一名守卫。每当一把钥匙到达时，守卫都会检查它能打开哪扇门。如果守卫已经见过一把能打开同一扇门的钥匙，他就会直接把新钥匙扔进垃圾桶，甚至不去测试它。他们只保留第一把能打开特定门的钥匙。这样一来，传送带上只携带唯一的、有用的钥匙。计算机停止了在重复项上浪费时间。
2. “银行”（Bank）工具（智能图书馆）
现在，想象一下，你不再是每次需要钥匙时都从头开始制造，而是拥有一个神奇的图书馆。当你向图书馆要一把钥匙时，它不仅仅给你一把；它会从底层开始，一次性构建出一整排独特的钥匙并保存起来。如果你稍后再次需要一把钥匙，图书馆只需把已经造好的那把交给你即可。
在论文的语言中，这被称为 defrel/bank。它强制计算机以一种特定的、有组织的方式（从最简单的程序开始）来构建它的候选程序列表，并保存结果。如果计算机稍后需要使用程序的一个小部分，它不会重新构建，而是直接从“银行”中抓取那个部分。这节省了大量时间，因为计算机永远不必做重复的工作。
转折：有时“快”并不代表“好”
作者们还意识到，仅仅有组织是不够的。有时，“银行”构建书架的顺序对计算机来说很快，但对人类来说却很慢。例如，银行可能会先构建所有的“乘法”机器，直到很久之后才构建“加法”机器。如果答案是一台“加法”机器，计算机可能必须在找到你需要的机器之前，先检查数千台乘法机器。
为了解决这个问题，他们创建了第三个工具 defrel/bank-w（“加权”银行）。这个工具就像一位知道哪些类型的钥匙更有可能成为答案的图书管理员。它使用一个特殊的“分数”来决定先向你展示哪些钥匙。它会尝试先向你展示最简单、最紧凑的钥匙，即使这些钥匙被埋在图书馆的深处。如果你想要的是最优雅的解决方案，这非常好，但如果答案本身是一个复杂的、深层的机器，这可能会变慢。
他们的发现：速度 vs. 策略
作者们在一些数学和字符串谜题（比如把 "Hello" 变成 "Hello, World!"）上测试了这些工具。以下是他们的发现：
- “银行”是速度达人： 在 8 个困难的数学问题中，有 6 个问题的
defrel/bank工具比旧的标准搜索方法快了 9 到 99 倍。它如此之快，以至于在旧方法需要几分钟才能完成的任务中，它仅用了不到一秒钟就解决了问题。 - 但它有盲点： 银行由于过于有组织，如果答案隐藏在它访问较晚的部分，它有时会错过答案。例如，如果答案涉及以特定方式进行加法（如 ），银行可能会卡在检查成千上万个乘法示例的过程中。在这些情况下，旧的、较慢的方法反而胜出了，因为它以不同的顺序进行检查。
- “加权”银行是一种权衡：
defrel/bank-w工具非常擅长寻找最紧凑、最优雅的答案。它在 10.4 毫秒 内找到了一个棘手的字符串谜题的正确答案，击败了标准方法的 31.5 毫秒。然而，对于非常深的数学问题，它有时会因为试图检查太多可能性而导致超时。
核心结论
这篇论文并不声称已经解决了计算机科学中的所有问题。相反，它表明通过加入一点“剪枝”（过滤掉重复项）和“银行”（为以后保存工作），我们可以让构建其他程序的程序运行得快得多。
作者建议，如果你正在构建一个解决谜题的系统，你应该将 “银行” 工具作为你的默认选择，因为它是通常最快的。然而，如果你在寻找一个非常特定的、紧凑的解决方案，或者如果问题是浅显且简单的，你可能想要使用 “加权银行” 甚至传统的旧方法。这并不是说一种工具是完美的，而是要看你是否有合适的工具来应对你试图解决的谜题形状。论文最后建议，未来的工作将在更复杂的谜题（如构建理解列表或类型化数据的程序）上测试这些工具，以观察这种加速效果在现实世界中是否依然成立。
您所在领域的论文太多了？
获取与您研究关键词匹配的最新论文每日摘要——附技术摘要，使用您的语言。