如果其中一个语句失败，为什么 Prolog 会进一步跳过递归中的所有 if 语句？

Question

程序的重点是计算整数列表中所有偶数的总和。

    is_even(Q):- Q mod 2 =:= 0.  

    sum_even([],0).
    sum_even([A|L],X) :-  sum_even(L,X1) -> is_even(A) -> X is X1 + A .

只要is_even谓词成功就没有问题，它通常会返回计算总和。然而，当数字不是偶数并且 is_even 检查它时，它失败了，返回递归并且失败了随后的所有事情，甚至不再检查数字是否是偶数并且只是 returns 错误。在充满偶数的列表中，它按预期工作，它 returns 列表中所有数字的总和。 This here is the trace of the code

Answer 1

使用具有 tail-end 递归的累加器是最快的：

is_even(N) :-
    N mod 2 =:= 0.

sum_even(Lst, Sum) :-
    sum_even_(Lst, 0, Sum).

sum_even_([], Sum, Sum).
sum_even_([H|T], Upto, Sum) :-
    (   is_even(H) ->
        Upto1 is Upto + H
    ;   Upto1 = Upto
    ),
    sum_even_(T, Upto1, Sum).


sum_even_slow([], 0).
sum_even_slow([H|T], Sum) :-
    sum_even_slow(T, Sum0),
    (   is_even(H) ->
        Sum is Sum0 + H
    ;   Sum = Sum0
    ).

swi-prolog 中的性能比较：

?- numlist(1, 1_000_000, L), time(sum_even(L, Sum)).
% 4,000,002 inferences, 0.765 CPU in 0.759 seconds (101% CPU, 5228211 Lips)
Sum = 250000500000.

?- numlist(1, 1_000_000, L), time(sum_even_slow(L, Sum)).
% 4,000,001 inferences, 4.062 CPU in 4.023 seconds (101% CPU, 984755 Lips)
Sum = 250000500000.

Answer 2

add_even(X, Buffer, Sum) :-
    (0 =:= X mod 2 -> 
        Sum is Buffer + X
    ;   Sum = Buffer).

与foldl(add_even, Nums, 0, Sum) is about as fast as brebs' tail recursion. Using SWISH Online一起使用：

?- numlist(1, 1_000_000, _L), time(sum_even(_L, Sum)).
4,000,002 inferences, 0.699 CPU in 0.699 seconds (100% CPU, 5724382 Lips)
Sum = 250000500000

?- numlist(1, 1_000_000, _L), time(foldl(add_even, _L, 0, Sum)).
4,000,002 inferences, 0.712 CPU in 0.712 seconds (100% CPU, 5621314 Lips)
Sum = 250000500000

（我很好奇，如果他们都精确地进行了 4,000,002 次推理，那么 sum_even 为何似乎获得了更高的 LIPS 吞吐量并且完成速度稍快？）

Answer 3

这是

的原因

is_even(Q):- Q mod 2 =:= 0.  

sum_even([],0).
sum_even([A|L],X) :- sum_even(L,X1) -> is_even(A) -> X is X1 + A .

当列表中有奇数时失败是因为 '->'/2，“隐含”运算符，是一个 soft cut。它消除了选择点。这意味着回溯到它失败，从而展开整个事情并使整个谓词失败。

您的代码大致等同于

sum_even([],0).
sum_even([A|L],X) :- sum_even(L,X1), !, is_even(A), !, X is X1 + A .

你需要

消除 '->'/2 — ',' 运算符不必是 AND 运算符，并且
提供一种替代方法来处理奇数项的情况。

例如，你可以这样说：

is_even( Q ) :- Q mod 2 =:= 0.  

sum_even( []    , 0 ) .
sum_even( [A|L] , X ) :-
  sum_even(L,X1),
  ( is_even(A) ->
      X is X1 + A
    ;
      X is X1
  ) .

或者像这样：

is_even( Q ) :- Q mod 2 =:= 0.  

sum_even( []    , 0 ) .
sum_even( [A|L] , X ) :-
  sum_even(L,X1),
  add_even(A,X1,X) .

add_even(X,Y,Z) :- is_even(X), !, Z is X + Y .
add_even(_,Z,Z) .

但最简单、快速的方法是使用带有额外状态的辅助谓词。给定一个足够长的列表，上面的谓词将死于堆栈溢出。这不会：Prolog内置了TRO（tail recursion optimization），它通过重用栈帧有效地将递归调用转化为迭代，因此它可以处理任何深度的递归：

sum_even( Xs , S ) :- sum_even(Xs,0,S) .

sum_even( []     , S , S ) .
sum_even( [X|Xs] , T , S ) :- is_even(X), !, T1 is T+X, sum_even(Xs,T1,S) .

is_even( Q ) :- Q mod 2 =:= 0.

如果其中一个语句失败，为什么 Prolog 会进一步跳过递归中的所有 if 语句？

Why does Prolog skip all further if statements in recursion if one of them fails?

recursion

if-statement

prolog