Prolog Recursion and Variables

Question

I have this insertion sort to sort a list in descending order in Prolog and it works:

insert(X,[],[X]).
insert(X, [Y|Tail], [X,Y|Tail]):- X > Y, !.
insert(X, [Y|Tail], [Y|NTail]):- insert(X, Tail, NTail).
ins_sort([], []).   
ins_sort([X|Tail], Sorted):- ins_sort(Tail, STail), insert(X, STail, Sorted).

I am running it on SWISH and trying to understand how it functions with the following trace:

 Call:ins_sort([1, 2, 3, 4, 5], _12162)
 Call:ins_sort([2, 3, 4, 5], _12358)
 Call:ins_sort([3, 4, 5], _12358)
 Call:ins_sort([4, 5], _12358)
 Call:ins_sort([5], _12358)
 Call:ins_sort([], _12358)
 Exit:ins_sort([], [])
 Call:insert(5, [], _12360)
 Exit:insert(5, [], [5])
 Exit:ins_sort([5], [5])
 Call:insert(4, [5], _12366)
 Call:4>5
 Fail:4>5
 Redo:insert(4, [5], _12370)
 Call:insert(4, [], _12282)
 Exit:insert(4, [], [4])
 Exit:insert(4, [5], [5, 4])
 Exit:ins_sort([4, 5], [5, 4])
 Call:insert(3, [5, 4], _12378)
 Call:3>5
 Fail:3>5
 Redo:insert(3, [5, 4], _12382)
 Call:insert(3, [4], _12294)
 Call:3>4
 Fail:3>4
 Redo:insert(3, [4], _12294)
 Call:insert(3, [], _12300)
 Exit:insert(3, [], [3])
 Exit:insert(3, [4], [4, 3])
 Exit:insert(3, [5, 4], [5, 4, 3])
 Exit:ins_sort([3, 4, 5], [5, 4, 3])
 Call:insert(2, [5, 4, 3], _12396)
 Call:2>5
 Fail:2>5
 Redo:insert(2, [5, 4, 3], _12400)
 Call:insert(2, [4, 3], _12312)
 Call:2>4
 Fail:2>4
 Redo:insert(2, [4, 3], _12312)
 Call:insert(2, [3], _12318)
 Call:2>3
 Fail:2>3
 Redo:insert(2, [3], _12318)
 Call:insert(2, [], _12324)
 Exit:insert(2, [], [2])
 Exit:insert(2, [3], [3, 2])
 Exit:insert(2, [4, 3], [4, 3, 2])
 Exit:insert(2, [5, 4, 3], [5, 4, 3, 2])
 Exit:ins_sort([2, 3, 4, 5], [5, 4, 3, 2])
 Call:insert(1, [5, 4, 3, 2], _12162)
 Call:1>5
 Fail:1>5
 Redo:insert(1, [5, 4, 3, 2], _12162)
 Call:insert(1, [4, 3, 2], _12336)
 Call:1>4
 Fail:1>4
 Redo:insert(1, [4, 3, 2], _12336)
 Call:insert(1, [3, 2], _12342)
 Call:1>3
 Fail:1>3
 Redo:insert(1, [3, 2], _12342)
 Call:insert(1, [2], _12348)
 Call:1>2
 Fail:1>2
 Redo:insert(1, [2], _12348)
 Call:insert(1, [], _12354)
 Exit:insert(1, [], [1])
 Exit:insert(1, [2], [2, 1])
 Exit:insert(1, [3, 2], [3, 2, 1])
 Exit:insert(1, [4, 3, 2], [4, 3, 2, 1])
 Exit:insert(1, [5, 4, 3, 2], [5, 4, 3, 2, 1])
 Exit:ins_sort([1, 2, 3, 4, 5], [5, 4, 3, 2, 1])

I get lost once I get beyond the first "Exit". I understand all of the recursive calls until we get to an empty list, which stops the recursive calls because of the other fact and begins going back, but why after the first exit on line 7 does the undefined STail become an empty list [] in the insert call?

Has the exit of ins_sort([], []) set STail to an empty set [] and does this mean that the last argument of a fact is a return value or something?

Answer 1

Traces are much too hard. Re-writing is usually much easier, especially with the deterministic predicates like you have here. Long variable names are also too distracting. Instead of reading and remembering, it just might be easier simply seeing:

insert(X, [],    [X]).                                                                %1
insert(X, [Y|T], [X,Y|T] ):- X > Y, !.            % X was indeed greater than Y:      %2
                                                  %   accept the solution and stop;   %3
insert(X, [Y|T], [  Y|NT]):- insert(X, T, NT).    %   otherwise, insert into tail.    %4
                                                                                      %5
ins_sort( [],   []).              % rule {1}                                          %6
ins_sort( [X|T], S):-             % rule {2}                                          %7
   ins_sort( T,     ST),                                                              %8
   insert( X,       ST,                                                               %9
                 S).                                                                 %10

Let's try it with a shorter list,

  ins_sort([1, 2, 3], S) ?                                                S.         %11
=           \                                                            /           %12
  {2:      [X1|T1]=[1,2,3] }                                            /            %13
      ins_sort(T1, ST1),                               insert(X1, ST1, S).           %14 
=               \                                                 /                  %15
      {2:      [X2|T2]=T1=[2,3] }                                /                   %16
          ins_sort(T2, ST2),                    insert(X2, ST2, ST1).                %17
=                   \                                      /                         %18
          {2:      [X3|T3]=T2=[3] }                       /                          %19
              ins_sort(T3, ST3),         insert(X3, ST3, ST2).                       %20
=                       \                          /                                 %21
              {1:      T3=[]                     ST3=[] }.                           %22

and we go by the V-shaped trace from the top left corner down to the middle, winding up the recursion until we reach the base case, and then up and to the right while unwinding the recursion and building the result on our way back from the base case, as usual. Thus we proceed to establish, from the bottom up,

  ST3 = [].                                                                          %22
  insert( {X3=3}, {ST3=[]}, ST2 ):- ST2 = [3].                                       %20
  insert( {X2=2}, {ST2=[3]}, ST1 ):- ST1 = [3,2].                                    %17
  insert( {X1=1}, {ST1=[3,2]}, S ):- S = [3,2,1].                                    %14

And that's that.

Answer 2

I think the problem here is you are having some difficulty understanding what happens with variables during recursion. Let's take a simplified case:

count([], 0).
count([X|Xs], N) :- count(Xs, N0), succ(N0, N).

What happens when I call count([a,b], N) is this:

count([a, b], N)
 +-> count([b], N)

The first thing we have to do upon entering count([a,b], N) is a recursive call to count/2. When Prolog re-enters count, we suddenly have a new set of bindings for X and Xs. In the outer call, X=a and Xs=[b], but in the inner call, X=b and Xs=[]. There will then be a third inner call, which begins with the Xs value []. This corresponds to the first three lines of this trace:

Call: (8) count([a, b], _8636) ? creep
Call: (9) count([b], _8866) ? creep
Call: (10) count([], _8866) ? creep

What the tracer is telling you here is "I am trying to enter this predicate with these values and variables." Note that the variable actually changed for N between the first and second calls.

Now, you'll notice that the [] cannot match the second clause, only the first. The first doesn't have a body but it does establish a binding. So the next line of the trace will reflect that:

Exit: (10) count([], 0) ? creep

See the numbers on the side? That's telling you the depth of the call stack. It's convenient to use numbers for traces instead of showing the nesting visually because eventually our call stacks are going to get pretty deep!

Now that we have a value for the variable, it's going to move on to the next expression in the clause we're in:

Call: (10) succ(0, _8866) ? creep
Exit: (10) succ(0, 1) ? creep

Nesting level went up one but was immediately resolved; this is par for the course with built-ins like succ/2. Now let's look at the rest of the trace:

Exit: (9) count([b], 1) ? creep
Call: (9) succ(1, _8636) ? creep
Exit: (9) succ(1, 2) ? creep
Exit: (8) count([a, b], 2) ? creep

So now that we had a binding for the recursive call, we can enter the next step in the parent call, and so on, until the whole call is resolved and we get 2.

Let's see it again, this time with nesting instead of numbers:

[trace]  ?- count([a,b],N).
  Call: (8) count([a, b], _8636) ? creep
    Call: (9) count([b], _8866) ? creep
      Call: (10) count([], _8866) ? creep
      Exit: (10) count([], 0) ? creep
      Call: (10) succ(0, _8866) ? creep
      Exit: (10) succ(0, 1) ? creep
    Exit: (9) count([b], 1) ? creep
    Call: (9) succ(1, _8636) ? creep
    Exit: (9) succ(1, 2) ? creep
  Exit: (8) count([a, b], 2) ? creep
N = 2.

This should make what's going on in your own trace a little easier to understand.

Answer 3

Prolog works with unification and pattern matching.You are removing the Head and calling the predicate again with tail which keeps removing Head and tries to find matches after each call and at some later time you have an empty list so prolog search your file for a match and at this point it finds a match ins_sort([], []). At 6th call you have Call:ins_sort([], _12358) where _12358 is a variable and this variable will get the value from ns_sort([], []). which is a fact. It simply means that if you have one empty list in ns_sort and one variable then set that variable also equals to the empty list, variable gets instantiated with anything if you have all other "terms" matching.

Prolog can be easily understood by learning Backtracking and backtracking is an algorithm so prolog self is an algorithm.