为什么按分号后程序又回到深度递归？

Question

我正在尝试了解分号功能。

我有这个代码：

del(X,[X|Rest],Rest).
del(X,[Y|Tail],[Y|Rest]) :-
    del(X,Tail,Rest).

permutation([],[]).
permutation(L,[X|P]) :- del(X,L,L1), permutation(L1,P).

这是显示给定列表所有排列的简单谓词。

我在 SWI-Prolog 中使用了内置的图形调试器，因为我想了解它是如何工作的，并且我了解第一种情况 return 参数中给出的列表。这是我为更好地理解而制作的图表。

但我不明白另一个解决方案。当我按下分号时，它并没有从它结束的地方开始，而是从一些深度递归开始，其中 L=[] （就像在第 9 步中一样）。不明白，递归不是提前结束了吗？它必须走出递归 return 的答案，在分号之后它再次深入递归。

有人可以向我澄清一下吗？提前致谢。

Answer 1

functional/imperative 编程语言和 Prolog 中的递归有很大区别（直到最近 2 周左右我才真正清楚）：

在 functional/imperative 编程中，您递归调用链，然后返回，展开堆栈，然后输出结果。结束了。

在 Prolog 中，您向下递归 AND-OR tree（实际上，交替的 AND 和 OR 节点），选择一个谓词来调用 OR 节点（"choicepoint"），从左到右，并在 AND 节点上依次调用每个谓词，也是从左到右。一棵 可接受的树 在每个 OR 节点下只有一个谓词返回 TRUE，并且所有谓词在每个 AND 节点下都返回 TRUE。一旦构建了可接受的树，通过搜索过程，我们（即 "search cursor" 是）在 最右最底部的节点 上。

成功构建可接受的树也意味着找到了在 Prolog Toplevel（REPL）输入的查询的解决方案：输出变量值，但保留树（除非没有选择点）。

这也很重要：所有变量都是全局变量，因为如果变量 X 从谓词到调用链一路向下传递谓词到最右边的最底部节点，然后在最后可能的时刻通过将其与 2 统一来进行约束，例如 X = 2，那么 Prolog Toplevel 会毫不费力地意识到这一点：不需要向上传递调用链。

如果您现在按 ;，搜索不会在树的顶部重新开始，而是在底部重新开始，即在当前光标位置：要求最近的父 OR 节点以提供更多解决方案。在构建新的可接受树之前，这可能会导致大量搜索，我们处于新的最右最底部节点。输出新的变量值，您可以再次输入 ;.

这个过程循环，直到不能再构造出可接受的树，然后输出false。

请注意，将此 AND-OR 作为运行时可检查和可修改的数据结构可以部署一些神奇的技巧。

记录这棵树的调试工具肯定有很多强大的功能，以帮助用户从应该工作的 Prolog 程序中获得可怕的 sphynxian false。现在有 Time Traveling Debuggers 函数式和命令式语言，毕竟...

Answer 2

我发现一个有助于揭开 Prolog 神秘面纱的类比是，回溯就像嵌套循环，当最内层循环的变量值全部找到时，循环暂停，报告 vars 的值，然后恢复循环。

举个例子，让我们写下简单的生成和测试程序，找出所有大于 0 且总和为质数的自然数对。假设 is_prime/1 已经给了我们。

我们在 Prolog 中将其写为

above(0, N), between(1, N, M), Sum is M+N, is_prime(Sum).

我们用命令式伪代码写成

for N from 1 step 1:
  for M from 1 step 1 until N:
     Sum := M+N
     if is_prime(Sum):
        report_to_user_and_ask(Sum)

现在调用 report_to_user_and_ask 时，它会打印 Sum 并询问用户是中止还是继续。循环没有退出，相反，它们只是暂停。因此，所有让我们走到这一步的循环变量值——并且在循环链上可能有更多有时成功有时失败的测试——都被保留下来，即计算状态被保留，并且计算已准备好从中恢复那一点，如果用户按下 ;.

我第一次看到这个是在 Peter Norvig 的 AI 书中，在 Common Lisp 中实现了 Prolog。不过，他使用映射（Common Lisp 的 mapcan，即 Haskell 中的 concatMap 或许多其他语言中的 flatMap）作为循环结构，我花了很多年才看到 嵌套循环才是真正的意义所在。

目标连接表示为循环的嵌套；目标 disjunction 表示为要循环的 alternatives。

进一步的扭曲是嵌套循环的结构从一开始就不是固定的。它是 fluid，可以根据该循环的当前状态创建给定循环的嵌套循环，即取决于当前正在探索的替代方案； 我们边写边写循环。在（大多数）不可能动态创建嵌套循环的语言中，可以使用嵌套递归/函数调用/循环内部对其进行编码。（这里是，带有一些伪代码。）

如果我们在内存中保留所有此类循环（为每个备选方案创建），即使在它们完成后，我们得到的是 AND-OR 树（在另一个答案中提到）因此在搜索时创建space 正在探索并找到解决方案。

（非巧合，这种流动性也是"monad"的本质；非确定性由list monad; 而 list monad 的基本操作是我们在上面看到的 flatMap 操作。使用 fluid 结构个循环是"Monad"；固定结构是"Applicative Functor"；没有结构的简单循环（根本没有嵌套）：简单的"Functor"（[=中使用的概念104=] 等）。也有助于揭开它们的神秘面纱。）

因此，正确的口号可以是 回溯就像嵌套循环，要么是固定的，从一开始就知道，要么是在我们进行时动态创建的。不过时间有点长。 :)

Here's also a Prolog example, which "as if creates the code to be run first (N nested loops for a given value of N), and then runs it." (There's even a whole dedicated tag for it on SO, too, it turns out, recursive-backtracking.)

还有一个 in Scheme ("creates nested loops with the solution being accessible in the innermost loop's body"), and a C++ example ("create n nested loops at run-time, in effect enumerating the binary encoding of 2ⁿ, and print the sums out from the innermost loop").

为什么按分号后程序又回到深度递归？

Why after pressing semicolon program is back in deep recursion?

recursion

prolog

backtracking

recursive-backtracking