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

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 中使用了内置的图形调试器，因为我想了解它是如何工作的，并且我了解返回参数中给定列表的第一种情况。这是我为更好地理解而制作的图表。

但我不明白另一个解决方案。当我按下分号时，它不会从它结束的地方开始，而是从 L=[] 的某个深度递归开始(就像在第 9 步中一样)。不明白，递归不是提前结束了吗？它必须走出递归才能返回答案，在分号之后它再次深入递归。

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

Answer 1

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

例如，让我们写下简单的生成和测试程序，以找出所有大于 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)作为循环结构，我花了多年后才看到嵌套循环才是真正的意义所在。

目标连词表示为循环的嵌套；目标析取表示为要循环的选择。

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

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

(非巧合的是，这种流动性也是 “monad” 的本质；nondeterminism 由 list monad 建模；并且本质列表 monad 的操作是我们在上面看到的 flatMap 操作。对于循环的流体结构，它是“Monad”；具有固定结构的是“Applicative Functor”；具有无结构的简单循环(根本没有嵌套):简单 “Functor”(Haskell 等中使用的概念)。也有助于揭开这些概念的神秘面纱。)

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

---

Here's 也是一个 Prolog 示例，“好像创建了要首先运行的代码(N 给定值 N 的嵌套循环)，并且然后运行它。”(事实证明，在 SO 上什至还有一个完整的专用标签，recursive-backtracking。)

这是一个 in Scheme(“创建嵌套循环，解决方案可在最内层循环的主体中访问”)和一个 C++ example(“创建 n在运行时嵌套循环，实际上枚举 2ⁿ 的二进制编码，并从最内层循环打印出总和")。