请解释 Bubblesort Prolog 程序中的削减? [英] Please explain the cut in the Bubblesort Prolog program?

问题描述

我目前正在阅读 Bratko Prolog 书，并且正在研究冒泡排序程序.我似乎无法弄清楚为什么 cut(!) 是必要的.假设剪辑不存在，Prolog 会回溯，它怎么可能找到错误的答案?因为如果我把它删掉，Prolog 会先给我正确的答案，然后也会给出替代的错误答案.

I'm currently working trough the Bratko Prolog book and I am looking at the bubble-sort Program. I can't seem to figure out why the cut(!) is necessary. Say the cut isn't there, and Prolog would backtrack, how could it possibly find bad answers? Because if I leave the cut out of it, Prolog begins by giving me the correct answer but then also gives alternative bad answers.

在我看来，swap 怎么会返回一个未排序的列表?一个未排序的列表怎么可能达到目标bubblesort(Sorted, Sorted).

As I see it, how can swap ever return a non sorted list? And how is it possible that a non sorted list ever hits the goal bubblesort(Sorted, Sorted).

当然，除非第一个列表也被更改...无法理解它.

Unless of course the first List is also being changed... Can't get my head around it.

Prolog BubbleSort 程序:

Prolog BubbleSort program:

gt(X,Y) :- X > Y.

bubblesort(List, Sorted) :-
  swap(List, List1), !,           % A useful swap in List?
  bubblesort(List1, Sorted).
bubblesort(Sorted, Sorted).       % Otherwise list is already sorted

swap([X,Y|Rest], [Y,X|Rest]) :-   % Swap first two elements
  gt(X,Y).
swap([Z|Rest], [Z|Rest1]) :-      % Swap elements in tail
  swap(Rest, Rest1).

留下它给我的切口:

?- bubblesort([5,7,3,6,8,9,2,6], Sorted).

Sorted = [2, 3, 5, 6, 6, 7, 8, 9] ;

Sorted = [2, 3, 5, 6, 7, 6, 8, 9] ;

Sorted = [2, 3, 5, 6, 7, 8, 6, 9] ;

Sorted = [2, 3, 5, 6, 7, 8, 9, 6] ;

我想我明白了，但我不确定.难道是在某个时刻，它回溯到 swap(List, List1) 去第二个冒泡排序谓词并达到目标，这意味着两个列表 Sorted 是相等的?

I think that somehow I get it, but I am not sure. Could it be that at a certain moment, it backtracks over swap(List, List1) going to the second bubble-sort predicate and hitting the goal, meaning the two lists Sorted are equal?

在英语中，这是否意味着冒泡排序需要继续进行交换，直到无法再进行交换，然后才需要终止?或者这是否意味着每次成功的交换完成后，回溯该成功是没有用的?

In English, does this mean that bubble-sort needs to continue doing swaps until no more swaps are possible, but then needs to terminate? Or does it mean that every-time a successful swap has been done, there's no use backtracking over that success?

推荐答案

有几种可能导致目标 swap(List, List1) 失败.List 是长度为 0 或 1 的列表；或者它不包含两个紧随其后的元素，其中第二个小于第一个.

There are several possibilities to make the goal swap(List, List1) fail. Either List is a list of length 0 or 1 ; or it does not contain two immediately succeeding elements where the second is smaller than the first.

剪切的放置方式使其既剪切了 swap/2 又剪切了 bubblesort/2.

The cut is placed in such a manner that it both cuts swap/2 and the alternative of bubblesort/2.

这是一个很好的例子，深切"(切入 swap/2)仍然可以很好地工作.但是，这种情况非常罕见.大多数时候，削减太多.大多数此类程序使用起来非常脆弱，如果已经给出了第二个参数，则更是如此.他们往往不是坚定的.

This is a good example, where a "deep cut" (cutting deep into swap/2) still works somewhat nicely. However, such situations are very rare. Most of the time, the cut cuts too much. The largest majority of such programs is very brittle to use, even more so, if the second argument is given already. They are often not steadfast.

啊，我差点错过了:即使在这个程序中，我们也有 bubblesort(nonlist,L) 成功，或者 bubblesort([1|nonlist],L)这可能不是故意的，会导致细微的编程错误.

Ah, I almost missed it: Even in this program, we have bubblesort(nonlist,L) succeeding, or bubblesort([1|nonlist],L) which probably is not intended and leads to subtle programming errors.

这个程序没有呈现理想的逻辑编程风格还有另一个原因:bubblesort/2的第二条规则单独阅读时说:一切都是排序列表`.要理解这一点，我们必须同时阅读这两个规则并将其缩小到Everything but ....

There is also another reason why this program does not present the ideal logic programming style: The second rule of bubblesort/2 when read alone says: Everything is a sorted list`. To understand this, we have to read both rules at the same time and narrow it down to Everything but ....

在英语中，这是否意味着冒泡排序需要继续进行交换，直到无法再进行交换，然后才需要终止?或者这是否意味着每次成功的交换完成后，回溯该成功是没有用的?

In English, does this mean that bubble-sort needs to continue doing swaps until no more swaps are possible, but then needs to terminate? Or does it mean that every-time a successful swap has been done, there's no use backtracking over that success?

这是适用于此的第一个程序含义.当然，将成功回溯到 bubblesort/2 的第二个子句将是一个错误.

It is the first procedural meaning that applies here. And certainly, backtracking over the success to the second clause of bubblesort/2 would be an error.

另一个非常不直观的细节不是特定于剪切的，即除了数字之外，该程序还可以成功处理像 bubblesort([1,1+1],L) 这样的表达式再次可能会导致细微的差异.

A further quite unintuitive detail which is not specific to the cut, is that in addition to numbers, the program also succeeds for expressions like bubblesort([1,1+1],L) which again might lead to subtle differences.

这篇关于请解释 Bubblesort Prolog 程序中的削减?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！