为什么在按分号程序后又返回了深度递归? [英] 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书中在Common Lisp中实现Prolog时看到了这一点.他将映射(普通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.

目标合取表示为循环的嵌套；目标 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" 的本质； 不确定性是由 list monad建模的；以及列表monad的操作是我们在上面看到的 flatMap 操作.对于循环的流体结构，它是"Monad" ；具有固定结构，它是应用函子" ；具有无结构(根本没有嵌套)的简单循环:只需"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 嵌套循环，然后运行它."，递归回溯的问题.)

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

这是计划中的一个(创建嵌套循环，解决方案可以在最里面的循环主体中访问" )和示例(在运行时创建 n 个嵌套循环，实际上是枚举2 n ，然后从最里面的循环中打印出总和" ).

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屋！