Prolog - How this program work

2
votes

I have this program written in prolog language. The problem is that i cant understand how it works.

even_number([],[]).
even_number([H|T],S):-even_number(T,W),Z is H mod 2,Z==0,S=[H|W].
even_number([_|T],S):-even_number(T,S).

All it does is to extract the even numbers from a list and store it to another list. I know that it works using recursion but i cant understand the steps that are made during execution. Can anyone explain?

2
prolog
Ted's answer is good, but try saving that program to a file, starting a prolog interpreter, loading the program ([filename].), start tracing (using trace.) and then calling the even_number rule with a list. Seeing its execution step by step is very helpful when trying to understand how it works. – André Paramés

2 Answers

2
votes

The program consists of three rules that are applied as a group. They work together basically as if ... else if ... else if ... [else fail].

The first rule is: the even numbers in an empty list is the empty list. This is easy enough.

The second rule is applied if the first rule fails (i.e., the first argument isn't the empty list). This is a bit more complicated, but basically says to include the first element of the list if it is even. The logic breaks down as follows. The even numbers in a list that starts with H and has a tail of T is S if all the terms on the right are true: that the even numbers in T is some list W; that Z is the remainder after dividing H by 2; that Z is zero; and that S is H followed by W (whatever W turned out to be). (Note that this rule would be more efficient if the first term was moved to after the test Z==0.)

If that rule fails (i.e., H is odd), then the last rule is applied: the even numbers in the list are the even numbers in the tail of the list.

0
votes

It's written rather poorly. It might be easier to understand if you refactor it a bit and make it tail recursive:

even_numbers( X , R ) :-
  even_numbers( X , [] , T ) ,
  reverse( T , R ).

even_numbers( [] , T , T ).
even_numbers( [X|Xs] , T , R ) :-
  Z is X mod 2 ,
  Z == 0 ,
  ! ,
  even_numbers( Xs , [X|T] , R ).
even_numbers( [_|Xs] , T , R ) :-
  even_numbers( Xs , T , R ).

The first predicate, even_numbers/2 predicate is the public wrapper. It invokes the private helper, even_numbers/3, which hands back the list of even numbers in reverse order. It reverses that and tries to unify it with the result passed in the wrapper. The helper method does this:

  • if the source list is empty: unify the accumulator (T) with the result.
  • if the source list is not empty, and the head of the list (X) is even,
    • recurse down on the tail of the list (Xs), pushing X onto the accumulator.
  • if the source list is not empty, and the head of the list (X) is odd,
    • recurse down on the tail of the list (Xs) without modifying the accumulator.

But as noted by @André Paramés, work through it in the debugger and it will become clear what's going on.