Prolog中的剪切操作符与append操作

Question

当我们使用剪切操作符和追加操作符时，会出现什么问题？

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

- Ali Ismayilov

Answer 1

有时候在append/3等纯函数中引入green cut是有道理的，但必须小心保证这种cut仍然是green cut，即在一定程度上提高效率而不影响答案。

引入green cut的一个简单经验法则是：如果你将cut添加到纯的单调程序中而没有任何守卫条件，那么可以肯定它会变成red cut，从而破坏程序的含义。这个规则的例外很少，比如在一个变量自由的目标之后添加一个cut，前提是没有进一步的规则等等。训练自己找出哪些情况受到cut的影响也是非常有好处的。

返回到你的程序中的append2/3。当前，cut总是生效，即使应用替代规则的情况下，cut会切掉我们想要避免的答案。

那么什么情况下只有第一个子句是相关的？

如果第一个参数是[]，即append2([], Xs, Ys). - 但是如果最后一个参数是[]（甚至还有更复杂的情况）。现在用原始无cut定义尝试这两种情况：

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

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

因此，在第一种情况下，系统能够立即确定只有一个解，同时产生答案。然而，在第二种情况下，Prolog系统并不确定是否需要另一个答案，它“留下了一个可选择点”。这很遗憾，因为也可以很容易地确定，即使在这种情况下，只有一个解。在这里使用cut会非常理想，但是无保护的cut比有益更有害。

如果第三个参数是[]，则cut可以切掉：

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系统应该能够在内部完成这些操作，但有时程序员需要稍微帮助一下。

- false

---

这个问题是关于括号表达式中的剪枝符是否具有整个谓词作为其范围（恕我直言，这里应该使用什么术语？）的标准。我记得在某个地方看到过这方面的讨论。一个给定的Prolog实现可以将表达式本身作为剪枝符的范围，这种情况下剪枝符就不会产生任何效果。是这样吗？另外，您没有展示append3(Xs,Ys,[])。额外的剪枝符是否有助于消除选择点？您用哪个Prolog来运行它？ - Will Ness

@Will Ness：切割符号（',')/2, (;)/2, (->)/2和（在某种意义上）(:-)/2。然而，为了这样做，切割必须存在于术语到主体/目标转换的时间点。对于一个简单的Prolog文本规则，这意味着它必须出现为一个具体的！而不是稍后实例化为！的变量。call((!,fail;true))失败，而call((G=!,G,fail;true))成功，因为实际上执行的是call((G=!,call(G),fail;true))。对于append3(Xs,Ys,[])，我所知道的所有Prologs都可以工作：它们具有第一个参数索引，但没有或弱索引其他参数。 - false

@Will Ness：当然，append(Xs,Ys,[])不会留下任何选择点。你为什么认为它不会呢？它执行了Zs == []，因此有了!。 - false

谢谢。我只是想确认一下（我的安装的SWI版本很旧，即使是第一个例子append([], Ys, Zs).也会重试，我总是不得不按;键）。 - Will Ness

@WillNess：重新阅读我的第一条评论后，发现这个切割并没有切断(->)/2的第一个参数。 - false

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.

- Thanos Tintinidis

Answer 3

例如，尝试使用最常用的查询：

?- append2(X, Y, Z).

- mat

Answer 4

当前面两个参数是变量时，它将无法工作：

?- append(X, Y, [1, 2, 3]).
X = [],
Y = [1, 2, 3] ;
X = [1],
Y = [2, 3] ;
X = [1, 2],
Y = [3] ;
X = [1, 2, 3],
Y = [] ;
false.

?- append2(X, Y, [1, 2, 3]).
X = [],
Y = [1, 2, 3].

- Fred Foo