Prolog Range of Numbers

Question

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.

In Prolog you don't work with functions, but with predicates that describe relations. And predicates can be true or false, they do not return anything. So the answer for your second question is No. — Tudor Berariu, Dec 07 '14 at 18:49
Take a look at this question, it may answer yours. http://stackoverflow.com/questions/18337235/can-you-write-between-3-in-pure-prolog — Tudor Berariu, Dec 07 '14 at 18:53
Sorry for my ignorance. I updated my question to be a bit more clear as to what I am asking. — user2327195, Dec 07 '14 at 19:04
I assume that the predicate `range(U, K)` should be true for all `K`s between 1 and `U`. The next question is "How do you want to use your predicate?". There might be a difference in implementation between `range(+U, -K)` and `range(+U, ?K)`. More precisely, do you only want to satisfy `range/2` goals for with `K` being a free variable or you also want to check if a given `K` is between 1 and `U`? — Tudor Berariu, Dec 07 '14 at 19:15
K will be a free variable. So I want K to range from 1 to U only. — user2327195, Dec 07 '14 at 19:19

score 1 · Accepted Answer · answered Dec 07 '14 at 19:51

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.

Prolog Range of Numbers

1 Answers1