带有剪切运算符的 Prolog 追加 [英] Prolog append with cut operator

问题描述

使用 append 和 cut 操作符会出现什么问题?

What problem can occur when we use append with cut operator?

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

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

I have tried several different inputs, but it always succeeds.

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

推荐答案

剪辑;绿色切割和红色切割.插入绿色剪切只是为了提高效率而不改变程序的语义.另一方面，红色切口可以.根据定义，绿色切割不会造成任何问题.

There are two kinds of cuts; green cuts and red cuts. Green cuts are inserted just to improve efficiency and don't change the semantics of the program. Red cuts, on the other hand, do. By definition, green cuts do not cause any problems.

那么，如果没有切口，有没有办法改变行为?

So, is there any way that the behaviour would change if the cut wasn't there?

让我们看看；对于要匹配的第一个子句，L1 应与 [] 统一，L2 与 L 一致，L3 与 L 一致，或者换句话说，L2 与 L3 一致.

Lets see; for the first clause to match, L1 should be unifiable with [], L2 with L and L3 with L or, in other words, L2 unifiable with L3.

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

When L1 is [] the second clause cannot match; so the cut doesn't have any effect

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

When L1 is not instantiated: if the length of L2 and L3 are known at this point, then they must be equal otherwise the first clause wouldn't match; thus, the second clause cannot match since at each step the length of L3 is decreased by 1 and the only way to terminate requires L2=L3

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

if the length of L3 or L2 is not known: then we have a problem since the second clause may produce solutions.

确实:

    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.

这篇关于带有剪切运算符的 Prolog 追加的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！