trace route of the quicksort algorithm - prolog

Question

I have that previous question about this quicksort here.The prolog code for quicksort:

gt(X,Y):- X @>Y.
conc([],List, List).
conc([Head|Tail], List1, [Head|List2]):- conc(Tail, List1, List2).

quicksort([],[]).
quicksort([X|Tail],Sorted):-
    split(X,Tail,Small,Big),
    quicksort(Small,SortedSmall),
    quicksort(Big,SortedBig),
    conc(SortedSmall,[X|SortedBig],Sorted).

[1]split(X,[],[],[]).
[2]split(X,[Y|Tail],[Y|Small],Big):-
    gt(X,Y),!,
    split(X,Tail,Small,Big).
[3]split(X,[Y|Tail],Small,[Y|Big]):-
    split(X,Tail,Small,Big).

The array for example is [3,2,4,1,5]. This is the first part of the trace route:

?- trace, quicksort([3,2,4,1,5], Sorted).
1  Call: (7) quicksort([3, 2, 4, 1, 5], _G4136) ? creep
2  Call: (8) split(3, [2, 4, 1, 5], _G4269, _G4270) ? creep
3  Call: (9) gt(3, 2) ? creep
4  Call: (10) 3@>2 ? creep
5  Exit: (10) 3@>2 ? creep
6  Exit: (9) gt(3, 2) ? creep
7  Call: (9) split(3, [4, 1, 5], _G4261, _G4273) ? creep
8  Call: (10) gt(3, 4) ? creep
9  Call: (11) 3@>4 ? creep
10 Fail: (11) 3@>4 ? creep
11 Fail: (10) gt(3, 4) ? creep
12 Redo: (9) split(3, [4, 1, 5], _G4261, _G4273) ? creep
13 Call: (10) split(3, [1, 5], _G4261, _G4264) ? creep

At the line 2, prolog apply the rule [2] of split and we have Call: (8) split(3, [2, 4, 1, 5], _G4269, _G4270) and we have _G4269 is [2|Small] and _G4270 is Big.

It then compare 3 and 2, gt(3,2) return true and it does not execute the cut. Continue with split(X,Tail,Small,Big) which is Call: (9) split(3, [4, 1, 5], _G4261, _G4273)

If the gt(X,Y) return false, prolog will execute the cut and then apply the rule [3] of the split (line 11-12).

Am I doing right and why the last variable has become a new one (_G4237 instead of _G4270)? Because in the code I thought it is the same.

Anyone could help me clear things out? Many thanks!

Answer 1

To be precise: your question concerns this part of the trace:

2  Call: (8) split(3, [2, 4, 1, 5], _G4269, _G4270) ? creep
3  Call: (9) gt(3, 2) ? creep
4  Call: (10) 3@>2 ? creep
5  Exit: (10) 3@>2 ? creep
6  Exit: (9) gt(3, 2) ? creep
7  Call: (9) split(3, [4, 1, 5], _G4261, _G4273) ? creep

which corresponds to the call to:

split(X,[Y|Tail],[Y|Small],Big):-
    gt(X,Y),!,
    split(X,Tail,Small,Big).

and you are right there is no VISIBLE reason to obtain different variables since the same variable Big is used. I admit it is confusing. And, you could obtain the same variable. This can be shown calling directly split(3, [2, 4, 1, 5], S, B) the trace is then (with swi v6.6.6):

[trace]  ?- split(3, [2, 4, 1, 5], S, B).
   Call: (6) split(3, [2, 4, 1, 5], _G4537, _G4538) ? creep
   Call: (7) gt(3, 2) ? creep
   Call: (8) 3@>2 ? creep
   Exit: (8) 3@>2 ? creep
   Exit: (7) gt(3, 2) ? creep
   Call: (7) split(3, [4, 1, 5], _G4630, _G4538) ? creep

And the same variable is used (_G4538).

However, the interpreter can have INVISIBLE reason to unify a variable X with a brand new one Y and use Yinstead of X in subsequent computations. It is what occurs in your example. You can use the command g (goals) when debugging to obtain a backtrace, which will show the current stack trace with current variable bindings. Returning to your example, when you reach

7  Call: (9) split(3, [4, 1, 5], _G4261, _G4273) ? 

type g to have a backtrace and you obtain something like:

  [9] split(3, [4, 1, 5], _G4261, _G4273)
  [8] split(3, [2, 4, 1, 5], [2|_G4261], _G4273)
  [7] quicksort([3, 2, 4, 1, 5], _G4136)
   Call: (9) split(3, [4, 1, 5], _G4261, _G4273) ? 

And now you can see that _G4273 is the same variable in depth [8] and [9].