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

The point of the program is to calculate the sum of all even numbers in a list of integers.

    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 .

Whenever the is_even predicate succeeds there is no problem, it normally goes back to calculate the sum. However when the number is not even and is_even checks it, it fails, goes back to the recursion and fails everything that follows, doesn't even check if the number is even anymore and just returns false. In a list full of even numbers it works as intended, it returns the sum of all numbers in the list. This here is the trace of the code

CodePudding user response：

Using an accumulator with tail-end recursion is fastest:

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

Performance comparison in 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.

CodePudding user response：

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

Used with 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

(I am curious, if they both do exactly 4,000,002 inferences how come the sum_even seems to get higher LIPS throughput and finish slightly faster?)