Correct use of is/2 predicate in Prolog recursion

Question

I am a Prolog beginner with an imperative programming background. While solving assignments from this site, I bumped into two exercises: the first one regards finding the k-th elements of a list, the second one is about finding a list's length. Those are classical list-processing problems with a pretty straightforward solution, also for a beginner like me. What I was unable to understand was the (apparently) different use of the built-in is/2 predicate. As far as I am concerned, this predicate forces Prolog to carry on an arithmetic calculation and possibly assign the result to the left-hand side term. What I was told to be aware of is that, although it's possible to use variables in the right-hand side, those have to be instantiated with a variable-free term at the moment of evaluation.

For the first exercise the proposed solution is the following:

element_at(X,[X|_],1).
element_at(X,[_|L],K) :- K > 1, K1 is K - 1, element_at(X,L,K1).

and the way is is used makes sense to me: since K is provided as an argument, K1 can be immediately evaluated and supplied as a new argument in the recursive call.

By writing a solution to the second exercise, namely finding a list length, I came up with the following:

my_length([], 0).
my_length([_|L], K) :- K is K1 + 1, my_length(L, K1).

and was notified by Prolog that "arguments are not sufficiently instantiated".
The correct solution turned out to be this one:

my_length([], 0).
my_length([_|L], K) :- my_length(L, K1), K is K1 + 1.

In this case, the recursive call is made before evaluating K by means of is. In the previous exercise, it was made after evaluating K is K-1.

I think I misunderstood some key concepts. What are the cases in which is/2 has to be used before the recursive call and, on the other hand, when has it to be used after? Why is it so?
Any help and explanation is appreciated (I am using SWI-Prolog 7.6.4).

As you're defining your own list length predicates, you likely shouldn't be calling the Prolog system length/2 predicates in your definitions... — Paulo Moura
See also the related question stackoverflow.com/questions/51994448/… — Paulo Moura
In your examples did you meant to say K is K1 + 1 instead of K1 is K + 1 ?? (K is the length of [_|L], K1 is the length of L, so K>K1, K1 is K +1 doesn't makes sense...) — coder
@PauloMoura I checked the question you linked and it was a good contribution for clarifying my doubts. If you mind to put it as an answer, I will accept it gladly (otherwise I will do it by myself for future reference). — kernel_panic
@kernel_panic You can always vote that other question and answers and edit/update your question with a link to it. Repeating those two answers here doesn't seem correct. — Paulo Moura

Will Ness Will Ness · Accepted Answer · 2018-08-25T10:43:35

is should only be used when all the variables in its right-hand side term are already instantiated. You say as much yourself. So, in your at predicate, it is designed so that K must already be instantiated to a numerical expression when the predicate is called in a query -- i.e., any other query will cause an error. Since K is already instantiated, it's OK to call is.

In the second predicate, K is the output you're expecting (as well as, possibly, an input to be validated). Since it is not guaranteed to be known when the call is made, such a query must be allowed to work. This means, K mustn't be assumed to be known. And if it's unknown, is can't be called at that time, otherwise it will cause an error.

Thus we make the recursive call first, as it will surely instantiate K, if it weren't already.

Correct use of is/2 predicate in Prolog recursion

1 Answers