为什么按分号后程序又回到深度递归? [英] Why after pressing semicolon program is back in deep recursion?

问题描述

我正在尝试理解分号的功能.

I'm trying to understand the semicolon functionality.

我有这个代码:

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).

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

It's the simple predicate to show all permutations of given list.

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

I used the built-in graphical debugger in SWI-Prolog because I wanted to understand how it works and I understand for the first case which returns the list given in argument. Here is the diagram which I made for better understanding.

但我不明白另一个解决方案.当我按下分号时，它不会从结束的地方开始，而是从 L=[] 的一些深度递归开始(如步骤 9 中).我不明白，递归不是更早结束了吗?它必须退出递归才能返回答案，并且在分号之后它再次深入递归.

But I don't get it for the another solution. When I press the semicolon it doesn't start in the place where it ended instead it's starting with some deep recursion where L=[] (like in step 9). I don't get it, didn't the recursion end earlier? It had to go out of the recursions to return the answer and after semicolon it's again deep in recursion.

有人可以向我澄清一下吗?提前致谢.

Could someone clarify that to me? Thanks in advance.

推荐答案

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

One analogy that I find useful in demystifying Prolog is that Backtracking is like Nested Loops, and when the innermost loop's variables' values are all found, the looping is suspended, the vars' values are reported, and then the looping is resumed.

作为一个例子，让我们编写一个简单的生成和测试程序来查找所有大于 0 且总和为素数的自然数对.假设 is_prime/1 已经给我们了.

As an example, let's write down simple generate-and-test program to find all pairs of natural numbers above 0 that sum up to a prime number. Let's assume is_prime/1 is already given to us.

我们在 Prolog 中这样写

We write this in Prolog as

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

我们用命令式伪代码写成

We write this in an imperative pseudocode as

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 并询问用户是中止还是继续.循环不会退出，相反，它们只是暂停.因此，让我们走到这一步的所有循环变量值 - 并且循环链上可能有更多测试有时成功有时失败 - 被保留，即计算状态被保留，并且计算准备好从那一点，如果用户按下 ;.

Now when report_to_user_and_ask is called, it prints Sum out and asks the user whether to abort or to continue. The loops are not exited, on the contrary, they are just suspended. Thus all the loop variables values that got us this far -- and there may be more tests up the loops chain that sometimes succeed and sometimes fail -- are preserved, i.e. the computation state is preserved, and the computation is ready to be resumed from that point, if the user presses ;.

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

I first saw this in Peter Norvig's AI book's implementation of Prolog in Common Lisp. He used mapping (Common Lisp's mapcan which is concatMap in Haskell or flatMap in many other languages) as a looping construct though, and it took me years to see that nested loops is what it is really all about.

Goals 连接表示为循环的嵌套；目标 disjunction 表示为要循环的替代项.

Goals conjunction is expressed as the nesting of the loops; goals disjunction is expressed as the alternatives to loop through.

进一步的转折是嵌套循环的结构从一开始就不是固定的.它是 fluid，给定循环的嵌套循环可以根据该循环的当前状态创建，即取决于在那里探索的当前替代方案；循环是边写边写的.在(大多数)无法动态创建嵌套循环的语言中，可以使用嵌套递归/函数调用/在循环内对其进行编码.(这里是一个示例，带有一些伪代码.)

Further twist is that the nested loops' structure isn't fixed from the outset. It is fluid, the nested loops of a given loop can be created depending on the current state of that loop, i.e. depending on the current alternative being explored there; the loops are written as we go. In (most of the) languages where such dynamic creation of nested loops is impossible, it can be encoded with nested recursion / function invocation / inside the loops. (Here's one example, with some pseudocode.)

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

If we keep all such loops (created for each of the alternatives) in memory even after they are finished with, what we get is the AND-OR tree (mentioned in the other answer) thus being created while the search space is being explored and the solutions are found.

(非巧合的是，这种流动性也是 "monad" 的本质；nondeterminism 由 list monad 建模；而本质list monad 的操作是我们上面看到的 flatMap 操作.使用 fluid structure 循环它是 "Monad"; 固定结构是Applicative Functor"; 没有结构的简单循环(根本没有嵌套):简单函子"(Haskell 等中使用的概念).也有助于揭开它们的神秘面纱.)

(non-coincidentally this fluidity is also the essence of "monad"; nondeterminism is modeled by the list monad; and the essential operation of the list monad is the flatMap operation which we saw above. With fluid structure of loops it is "Monad"; with fixed structure it is "Applicative Functor"; simple loops with no structure (no nesting at all): simply "Functor" (the concepts used in Haskell and the like). Also helps to demystify those.)

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

So, the proper slogan could be Backtracking is like Nested Loops, either fixed, known from the outset, or dynamically-created as we go. It's a bit longer though. :)

这里也是一个 Prolog 示例，它好像创建了要首先运行的代码(N 为给定的 N 值循环嵌套循环)，然后运行它." (在 SO 上什至还有一个完整的专用标签，事实证明, recursive-backtracking.)

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.)

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

And here's one 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").

这篇关于为什么按分号后程序又回到深度递归?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！