Can anybody help me understanding this prolog program?

Question

maxi([X],X).

maxi([K|R],X):- maxi(R,X), X > K.

maxi([K|R],K):- maxi(R,X), X =< K.

?- maxi([4,5,3,8,2],X), write(X).        

So the output of the program is 8, which is correct, but I don't understand how it works. Can anybody just shortly explain each step of the program? Would be much appreciated :)

Answer 1

So you have

maxi([X],X).
maxi([K|R],X) :- maxi(R,X), X > K.
maxi([K|R],K) :- maxi(R,X), X =< K.

The way to understand maxi([4,5,3,8,2],X) is to first start from the simplest case, and then try the more involved ones, building your understanding along the way.

So what is the result of querying maxi([], Y)? It is, according to the three clauses of maxi's definition,

maxi([],Y)
==>
  maxi([], Y) = maxi([X],X)    ,  true                    %%  first clause 
; maxi([], Y) = maxi([K|R],X)  ,  maxi(R,X), X > K        %%  second clause 
; maxi([], Y) = maxi([K|R],K)  ,  maxi(R,X), X =< K       %%  third clause 
==>
fail

isn't it? And what is the result of querying maxi([2],Y)? It is

maxi([2],Y)
==>
  maxi([2], Y) = maxi([X],X)    ,  true
; maxi([2], Y) = maxi([K|R],X)  ,  maxi(R,X), X > K
; maxi([2], Y) = maxi([K|R],K)  ,  maxi(R,X), X =< K
==>
  [2]=[X],   Y=X
; [2]=[K|R], Y=X                ,  maxi(R,X), X > K
; [2]=[K|R], Y=K                ,  maxi(R,X), X =< K
==>
  X=2,       Y=X
; K=2,       Y=X                ,  maxi([],X), X > K      %%  ***
; K=2,       Y=K                ,  maxi([],X), X =< K     %% 
==>
             Y=2
;                                  fail                   %%  as seen before
;                                  fail                   %%
==>
             Y=2

right? And maxi([8,2],Y) is

maxi([8,2],Y)
==>
  maxi([8,2], Y) = maxi([X],X)    ,  true
; maxi([8,2], Y) = maxi([K|R],X)  ,  maxi(R,X), X > K
; maxi([8,2], Y) = maxi([K|R],K)  ,  maxi(R,X), X =< K
==>
  [8,2]=[X],   Y=X
; [8,2]=[K|R], Y=X                ,  maxi(R,X), X > K
; [8,2]=[K|R], Y=K                ,  maxi(R,X), X =< K
==>
               Y=X                ,  maxi([2],X), X > 8        %%  ***
;              Y=8                ,  maxi([2],X), X =< 8       %%
==>
               Y=X                ,  X=2        , X > 8        %%  as seen before
;              Y=8                ,  X=2        , X =< 8       %%  
==>
               Y=8        %% the second alternative is chosen

And maxi([3,8,2],Y):

maxi([3,8,2],Y)
==>
  maxi([3,8,2], Y) = maxi([X],X)    ,  true
; maxi([3,8,2], Y) = maxi([K|R],X)  ,  maxi(R,X), X > K
; maxi([3,8,2], Y) = maxi([K|R],K)  ,  maxi(R,X), X =< K
==>
  [3,8,2]=[X], Y=X                  ,  true
; maxi([3,8,2], Y) = maxi([K|R],X)  ,  maxi(R,X), X > K
; maxi([3,8,2], Y) = maxi([K|R],K)  ,  maxi(R,X), X =< K
==>
  maxi([3,8,2], Y) = maxi([K|R],X)  ,  maxi(R,X), X > K
; maxi([3,8,2], Y) = maxi([K|R],K)  ,  maxi(R,X), X =< K
==>
  [3,8,2]=[K|R], Y=X                ,  maxi(R,X), X > K
; maxi([3,8,2], Y) = maxi([K|R],K)  ,  maxi(R,X), X =< K
==>
                 Y=X                ,  maxi([8,2],X), X > 3    %% seen above
; maxi([3,8,2], Y) = maxi([K|R],K)  ,  maxi(R,X), X =< K
==>
                 Y=X                ,  X=8,           X > 3
; maxi([3,8,2], Y) = maxi([K|R],K)  ,  maxi(R,X), X =< K
==>
                 Y=8
; [3,8,2]=[K|R], Y=K                ,  maxi(R,X), X =< K
==>
                 Y=8
; 3=K,           Y=K                ,  maxi([8,2],X), X =< K   %% and again,
==>
                 Y=8
;                Y=3                ,  X=8,           X =< 3
==>
                 Y=8        %% the first alternative is chosen

We can see from this that in general, the code could be made a bit clearer as

maxi([X],Y) :- Y=X.
maxi([K|R],Y) :- maxi(R,X), X > K, Y=X.
maxi([K|R],Y) :- maxi(R,X), X =< K, Y=K.

or

maxi([X],Y) :- Y=X.
maxi([K|R],Y) :- maxi(R,X), (X > K, Y=X ; X =< K, Y=K).

or even

maxi([X],Y) :- Y=X.
maxi([K|R],Y) :- maxi(R,X), (X > K -> Y=X ; Y=K).

since the arithmetic comparison, X > K, means that the predicate's first argument must always be fully known (a.k.a. ground) anyway.

And so the meaning of the predicate is:

• for a singleton list [X], its maximum is X
• for a non-empty list [K|R], its maximum is
• • X, if the maximum of R, X, satisfies X > K, or
• • K, otherwise

which makes sense indeed.

Answer 2

The predicate expresses:

maxi(List,X) is true if X is the maximum (numeric) element in List

And so we have three cases:

• maxi([X],X).: The maximum of a one-element list is the element itself. Certainly true.
• maxi([K|R],X) :- ... The maximum of the 1-or-more element list [K|R] is X (rather than K) if:
  • maxi(R,X): the maximum of the tail R of the original list is X and
  • X > K: X is actually larger than the head K of the original list.
• maxi([K|R],K) :- ... The converse of the case above: The maximum of the 1-or-more element list [K|R] is K (rather than X) if:
  • maxi(R,X): the maximum of the tail R of the original list is X and
  • X =< K: X is actually smaller or equal than the head K of the original list. As an alternative to the =< here, one could use < and have a third clause for equality: maxi([K|R],K):- maxi(R,K). but one doesn't have to.

The above declarative description allows the Prolog Processor to consider a list that shrinks by 1 on each recursive call to maxi/2 until a list of length 1 is reached.

This explanation hides information about the precise ordering of the recursive calls, in other words what the lower-level operations are that lead to a concrete result.

This is actually hard to explain clearly in text. Do you know about the Byrd Box model?

Stepping through the debugger (trace instruction) may help. On the other, debugger output is not entirely clear. Another possibility is to entomb the program in print instructions, but this is only a one off-solution:

maxi(Depth,[X],X) :-
   format("Clause 0, depth ~d: maxi[~q],~q~n",[Depth,X,X]).

maxi(Depth,[K|R],X):- 
   format("Clause 1, depth ~d: maxi[~q|~q],~q~n",[Depth,K,R,X]),
   rider("Clause 1, depth ~d: before recursive call",[Depth]),
   DepthP is Depth+1,
   maxi(DepthP,R,X), 
   rider("Clause 1, depth ~d: after recursive call, before test",[Depth]),
   format("Clause 1, depth ~d: test: ~q > ~q~n",[Depth,X,K]),   
   X > K.

maxi(Depth,[K|R],K):-
   format("Clause 2, depth ~d: maxi[~q|~q],~q~n",[Depth,K,R,K]),
   rider("Clause 2, depth ~d: before recursive call",[Depth]),
   DepthP is Depth+1,
   maxi(DepthP,R,X),
   rider("Clause 2, depth ~d: after recursive call, before test",[Depth]),
   format("Clause 2, depth ~d: test: ~q <= ~q~n",[Depth,X,K]),   
   X =< K.
   
rider(Text,List) :-
   format(Text,List),
   format(", going forward ~n",[]).
   
rider(Text,List) :-
   format(Text,List),
   format(", going backward ~n",[]),
   fail.

But at least it gives a discussable trace showing the "rider" moving forwards or backwards for each "predicate activation" (basically, in each stack frame)

?- maxi(0,[4,5,3,8,2],X).
Clause 1, depth 0: maxi[4|[5,3,8,2]],_7982
Clause 1, depth 0: before recursive call, going forward 
Clause 1, depth 1: maxi[5|[3,8,2]],_7982
Clause 1, depth 1: before recursive call, going forward 
Clause 1, depth 2: maxi[3|[8,2]],_7982
Clause 1, depth 2: before recursive call, going forward 
Clause 1, depth 3: maxi[8|[2]],_7982
Clause 1, depth 3: before recursive call, going forward 
Clause 0, depth 4: maxi[2],2
Clause 1, depth 3: after recursive call, before test, going forward 
Clause 1, depth 3: test: 2 > 8
Clause 1, depth 3: after recursive call, before test, going backward 
Clause 1, depth 4: maxi[2|[]],_7982
Clause 1, depth 4: before recursive call, going forward 
Clause 1, depth 4: before recursive call, going backward 
Clause 2, depth 4: maxi[2|[]],2
Clause 2, depth 4: before recursive call, going forward 
Clause 2, depth 4: before recursive call, going backward 
Clause 1, depth 3: before recursive call, going backward 
Clause 2, depth 3: maxi[8|[2]],8
Clause 2, depth 3: before recursive call, going forward 
Clause 0, depth 4: maxi[2],2
Clause 2, depth 3: after recursive call, before test, going forward 
Clause 2, depth 3: test: 2 <= 8
Clause 1, depth 2: after recursive call, before test, going forward 
Clause 1, depth 2: test: 8 > 3
Clause 1, depth 1: after recursive call, before test, going forward 
Clause 1, depth 1: test: 8 > 5
Clause 1, depth 0: after recursive call, before test, going forward 
Clause 1, depth 0: test: 8 > 4
X = 8 

You need to be more precise in what you know.