Q:

Prolog Range of Numbers

I came across this question where someone could generate a range of numbers from Low to High.
I am Very new to prolog so I am having a hard time understanding exactly how the solution works. So I was wondering if someone would kindly walk through how it works for me.
More specifically, I am having a hard time understanding the backtracking and how the Prolog interpreter is getting the solutions.
I am also wondering how I could create a predicate like
range(Upper,K) ....
so that when i call
range(5,K).
K = 1;
K = 2;
.
.
K = 5;
Edited for clarity.

A:

For your range(+U, -K) the best answer is to use the between/3 built-in predicate. But here's one possible implementation:
range(_, 1).
range(U, K):- range(U, K1), (K1 >= U, !, false ; K is K1+1).

There are better solutions than this one, but I think it's good to be used for an explanation. It's not perfect as giving a negative U would give you one wrong solution, but you can make it perfect starting from here.
An example
Suppose you run the following query:
?- range(2, K).

Prolog will try to satisfy the given goal by looking for rules whose heads would unify with it. The first rule (range(_, 1)) can be used and a choice-point is created as there are alternatives to be considered (i.e. the second rule). So, because the anonymous variable _ unifies with 2 and 1 unifies with K, you get your first answer:
K = 1 ;

Now Prolog backtracks to the last choice-point and tries to satisfy range(2, K) using the second rule. It does that by unifying U with 2, your variable K with variable K from the rule and putting the conditions on the goals stack which now looks like this:
range(2, K1), (K1 >= 2, !, false ; K is K1 + 1)

In order to satisfy the first goal, Prolog considers the first rule and creates a choice-point. K1 is instantiated to 1 and the stack of goals becomes:
(1 >= 2, !, false ; K is 1 + 1)

Now, because there is an or operator (;), Prolog will try to satisfy the first set of sub-goals and creates anothe choice-point here. But, 1>=2 is false, so it backtracks to that last choice-point and tries to satisfy K is 1 + 1 which succeeds by instantiating K to 2. Hence, you get your second result:
K = 2 ;

Prolog backtracks now to the choice-point created for range(2, K1) and uses the second rule. The goals stack becomes:
range(2, K2), (K2 >= 2, !, false ; K1 is K2+1), (K1 >= 2, !, false ; K is K1 + 1)

Again, Prolog tries to satisfy range(2, K2) using the first rule which unifies K2 with 1 and creates a choice point.
(1 >= 2, ! false ; K1 is 1+1), (K1 >= 2, !, false ; K is K1+1)

Now Prolog has two alternatives due to the or operator, but the first one fails as 1 >= 2 is false. The second one is satisfied with K1 being instantiated to 2.
(2 >= 2, !, false ; K is 2 + 1)

Now, Prolog creates a choice-point, takes the first set of goals (2 >= 2, !, false) and tries to satisfy them. 2>=2 is true and then the cut operator (!) destroys all previous choice-points. false is false and execution stops.

