Declarative interpretation of Bubble Sort algorithm in Prolog -

i have doubt how work following implementation of bubblesort algorithm in prolog.

i have clear how bubblesort algorithm work doubt related prolog first order logic , declarative interpretation.

this code:

bubblesort(list, sortedlist) :- swap(list, list1),                                 !,                                 bubblesort(list1, sortedlist).  bubblesort(sortedlist, sortedlist).  /* swap predicate swap 2 element if x come after y in lexicographical order */ swap([x,y|tail], [y,x|tail]) :- x @> y.  /* if not true x come after y in lexicographical order let head in    original position , call swap predicate on sublist */  swap([z|tail], [z|tail1]) :- swap(tail, tail1). 

so have doubt declarative interpretation of program:

the core of program bubblesort/2 predicate perform scansion of list in performed eventual swap of adjacent elements.

so swap/2 predicate work procedural if:

1) if first element in sublist (x) follow second element in sublist (y) in lexicographical order not good, perform swap.

2) otherwise x , y in right order , try execute te swap on sublist tail

so example if perform following query:

[trace]  ?- bubblesort([3,2,1], sorted). 

i obtain:

call: (7) bubblesort([3, 2, 1], _g399) ? creep call: (8) swap([3, 2, 1], _g478) ? creep call: (9) 3@>2 ? creep exit: (9) 3@>2 ? creep exit: (8) swap([3, 2, 1], [2, 3, 1]) ? creep call: (8) bubblesort([2, 3, 1], _g399) ? creep 

here call first version of bubblesort/2 on original list. true call first version of swap/2 predicate check if first 2 elements of list not in lexicographical order each other, fact true swap these elements. swap/2 predicate verified, come backtracking , (to satisfy bubblesort/2) call again bubblesort2 saying original list order list after swap (the list in first , second element swapped)

so call again bubblesort , happen:

call: (8) bubblesort([2, 3, 1], _g399) ? creep call: (9) swap([2, 3, 1], _g484) ? creep call: (10) 2@>3 ? creep fail: (10) 2@>3 ? creep redo: (9) swap([2, 3, 1], _g484) ? creep call: (10) swap([3, 1], _g480) ? creep call: (11) 3@>1 ? creep exit: (11) 3@>1 ? creep exit: (10) swap([3, 1], [1, 3]) ? creep exit: (9) swap([2, 3, 1], [2, 1, 3]) ? creep  

so try satisfy swap/2 on list [2,3,1] not true first 2 elements not in lexicographical order each other, first version of swap/2 predicate fail, use second version call swap/2 on sublist **[3,1] true 3 don't follow 1, swap , obtain [1,3] list.

here have first doubt: after swap on sublist (from [3,1] [1,3]) obtain list: [2, 1, 3] in line:

exit: (9) swap([2, 3, 1], [2, 1, 3]) ? creep  

why? because after have satisfied swap(tail, tail1) predicate:

swap([z|tail], [z|tail1]) :- swap(tail, tail1). 

i have tail1 [1,3] z old head 2 , [z|tail1] [2,1,3] ?

however, end first scansion of bubble sort algorithm have take "bigger" element @ end of list

the execution continues in same way have doubt end of program execution is:

   redo: (10) bubblesort([1, 2, 3], _g399) ? creep    exit: (10) bubblesort([1, 2, 3], [1, 2, 3]) ? creep    exit: (9) bubblesort([2, 1, 3], [1, 2, 3]) ? creep    exit: (8) bubblesort([2, 3, 1], [1, 2, 3]) ? creep    exit: (7) bubblesort([3, 2, 1], [1, 2, 3]) ? creep sorted = [1, 2, 3]. 

so @ end call bubblesort/2 predicate on ordered list by:

 redo: (10) bubblesort([1, 2, 3], _g399) ? creep 

where [1,2,3] list1.

now in second version of bubblesort/2 predicate, one:

bubblesort(sortedlist, sortedlist). 

where list sort , sorted list same (so means original list totatly sorted).

so this? base case that, once verified, program execution have end?

so execute backtracking previous bubblesort/2 verified, untill reach first bubblesort/2 call , vierified , unify sorted [1,2,3] list

is reasoning correct? there more declarative interpretation of this?

i think key understand algorithm it's fact swap/2 fails when list sorted - there no match on empty list.

from here necessity of second bubblesort/2 rule.