Frame 6:8 - 为何未陷入递归？关于alwayso控制流的疑问

代码示例 #

(defrel (alwayso)
  (conde
    (#s)
    ((alwayso))))

(run 1 q
  (alwayso)
  #u)

书籍原文（第二版）引用 #

"<alwayso>执行成功，随后#u触发(alwayso)重试，且再次执行成功"。

问题 #

我仍无法理解其控制流程。为何在执行#u之前，conde的两个分支不会全部被尝试（进而持续递归）？

控制流程拆解 #

首先得明确miniKanren里conde的核心特性：它是惰性分支选择，不是一口气跑完所有分支，而是先尝试第一个分支，成功后就暂停，把剩下的分支当作「备用回溯路径」存起来，只有当需要找下一个解或者触发回溯时，才会去碰这些备用路径。

现在一步步看这段代码的执行：

1. alwayso的定义里，conde包含两个分支：第一个#s是直接成功的分支，第二个是递归调用alwayso。
2. 进入run 1 q的执行流程，先执行(alwayso)：
   • 程序优先尝试第一个分支#s，这个分支直接执行成功。此时程序不会主动去触发第二个递归分支，而是把这个递归分支作为「回溯备选路径」保存起来，接着继续执行后面的#u。
3. 执行#u时：
   • #u会触发回溯检查，也就是去尝试之前保存的备用路径——也就是alwayso的第二个递归分支。
   • 这个递归调用的alwayso又会重复同样的逻辑：优先尝试自己的第一个#s分支，再次执行成功。

简单来说，你疑惑的「#u执行前不会持续递归」，根源就是conde的惰性机制：它不会主动遍历所有分支，第一个分支成功后就停在当前路径，只有#u触发回溯时，才会去尝试第二个递归分支，自然不会一开始就陷入无限递归。

内容的提问来源于stack exchange，提问作者Alper