Prolog附加切割操作符

Question

当我们使用带有cut运算符的append时会出现什么问题？

   append2([],L,L):-!.
   append2([H|T],L,[H|TL]):-append2(T,L,TL).

我尝试了几种不同的输入,但它总是成功的.

?- append2([1,2],[5],L).
L = [1, 2, 5].

?- append2([1,2],[1,2],L).
L = [1, 2, 1, 2].

?- append2([],[1,2],L).
L = [1, 2].

?- append2([1,2],[],L).
L = [1, 2].

Answer 1

有时真的有必要引入绿色切割 - 即使是append/3,但必须注意这样的切割仍然是绿色切割.也就是说,这种切割可以提高效率(在某个水平上)并且不会影响答案.

引入绿色切割有一个非常简单的经验法则:如果你在没有任何防范的情况下将切割添加到纯粹的单调程序中,你可以非常肯定它将是一个破坏你的程序含义的红色切割.

这个经验法则很少有例外.例如,如果没有进一步的规则等,你可以在一个可变的自由目标之后添加一个切口.试图找出受切割影响的案例绝对是一个很好的训练.

但回到你的程序append2/3.目前,即使替代规则确实适用,剪辑总是会削减,在这种情况下,剪辑会删除我们想要避免的答案.

那么第一个条款何时才是唯一的相关条款？

如果第一个参数是[],因此append2([], Xs, Ys).-而且如果最后一个参数是[](有更多的情况下这是更复杂).让我们尝试使用原始无切割定义的两种情况:

?- append([], Ys, Zs).
Ys = Zs.

?- append(Xs, Ys, []).
Xs = Ys, Ys = [] ;
false.

因此,在第一种情况下,系统能够立即确定存在单个解决方案,同时产生答案.在第二种情况下,然而,Prolog的系统是不肯定另一个答案是否会是必要的-它"留下了一个选择点开"可以这么说.这是一个遗憾,因为确定在这种情况下,只有一个答案存在是相当微不足道的.切割本来是理想的帮助.但无人看守的伤害比伤害更有害.

如果第三个参数是[]:

append3(Xs, Ys, Zs) :-
   (  Zs == [] -> ! ; true ),
   Xs = [],
   Ys = Zs.
append3([X|Xs], Ys, [X|Zs]) :-
   append3(Xs, Ys, Zs).

如果只知道第三个参数,那么这个程序现在更有效,因为它不会使选择点保持打开状态.

?- append(Xs,Ys,[1]).
Xs = [],
Ys = [1] ;
Xs = [1],
Ys = [] ;
false.

?- append3(Xs,Ys,[1]).
Xs = [],
Ys = [1] ;
Xs = [1],
Ys = [].

该程序不一定更快,因为测试本身可能很昂贵.理想情况下,Prolog系统可以在内部执行此类操作,但有时程序员必须提供帮助.

Answer 2

有两种削减方式 ; 绿色削减和红色削减.插入绿色剪切只是为了提高效率,而不是改变程序的语义.另一方面,红色削减.根据定义,绿色切割不会造成任何问题.

那么,如果削减不存在,行为会有什么变化吗？

让我们来看看; 对于匹配的第一个子句,L1应该与[],L2与L和L3与L一致,或者换句话说,L2与L3一致.

当L1为[]时,第二个子句不匹配; 所以切割没有任何影响

当L1没有被实例化时:如果此时已知L2和L3的长度,则它们必须相等,否则第一个子句将不匹配; 因此,第二个子句不能匹配,因为在每个步骤L3的长度减少1并且终止的唯一方法需要L2 = L3

如果L3或L2的长度未知:那么我们就有问题,因为第二个子句可能产生解决方案.

确实:

    3 ?- append2(L1,L2,[1,2,3]).
    L1 = [],
    L2 = [1, 2, 3].

    4 ?- append2(L1,[1,2,3],L3).
    L1 = [],
    L3 = [1, 2, 3].

    5 ?- append2(L1,L2,L3).
    L1 = [],
    L2 = L3.

    6 ?- append2(L1,[E1,E2],L3).
    L1 = [],
    L2 = [E1, E2].

    7 ?- append2(L1,L2,[E1,E2]).
    L1 = [],
    L2 = [E1, E2].

我们期待:

8 ?- append(L1,L2,[1,2,3]).
L1 = [],
L2 = [1, 2, 3] ;
L1 = [1],
L2 = [2, 3] ;
L1 = [1, 2],
L2 = [3] ;
L1 = [1, 2, 3],
L2 = [] ;
false.

9 ?- append(L1,[1,2,3],L3).
L1 = [],
L3 = [1, 2, 3] ;
L1 = [_G24],
L3 = [_G24, 1, 2, 3] ;
L1 = [_G24, _G30],
L3 = [_G24, _G30, 1, 2, 3] ;
L1 = [_G24, _G30, _G36],
L3 = [_G24, _G30, _G36, 1, 2, 3] ;
L1 = [_G24, _G30, _G36, _G42],
L3 = [_G24, _G30, _G36, _G42, 1, 2, 3] ;
...

10 ?- append(L1,L2,L3).
L1 = [],
L2 = L3 ;
L1 = [_G22],
L3 = [_G22|L2] ;
L1 = [_G22, _G28],
L3 = [_G22, _G28|L2] ;
....

11 ?- append(L1,[E1,E2],L3).
L1 = [],
L3 = [E1, E2] ;
L1 = [_G78],
L3 = [_G78, E1, E2] ;
L1 = [_G78, _G84],
L3 = [_G78, _G84, E1, E2] ;
L1 = [_G78, _G84, _G90],
L3 = [_G78, _G84, _G90, E1, E2] ;
...

12 ?- append(L1,L2,[E1,E2]).
L1 = [],
L2 = [E1, E2] ;
L1 = [E1],
L2 = [E2] ;
L1 = [E1, E2],
L2 = [] ;
false.

Answer 3

试试最常见的查询:

?- append2(X, Y, Z).