CODEWITHSUNDEEP
prolog
user2327195
user2327195

Reputation: 263

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.

Upvotes: 1

Views: 3714

Answers (1)

Tudor Berariu
Tudor Berariu

Reputation: 4910

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.

Upvotes: 1

Related Questions