Never-ending fill method, infinite loop that retur

Question

So I'm working on some prolog,and have been running into an issue that I don't understand why is appearing. The issue actually happens in a few of my methods, but hopefully I can figure it out with just some guidance in this method.

fill(3,a,L) -> L = [a,a,a]

here's my code

fill(0,x,[]).
fill(N,A,[A | As]) :-
  N1 is N-1,
  fill(N1,A,As).

Answer 1

The first clause should be:

fill(0, _, []).

Your code leaves a choice-point (for your sample query): when the counter reaches zero, both clause heads unify with the current goal. Only by trying to use the second clause, will the N1 >= 0 goal be reached. This goal will fail (as N1 is -1 at this point). Thus, the second clause will fail to provide an alternative solution. But the Prolog interpreter doesn't know that when it finds the first solution. Therefore, the first solution is presented and then the Prolog top-level interpreter waits for your input. Typing a return usually means that you don't want the Prolog inference engine to backtrack and look for alternative solutions. If you type a semi-colon instead, ";", you will be asking for alternative solutions.

You can change your fill/3 predicate to not leave a choice-point. A quick solution is to add a cut, "!/0", to the first clause:

fill(0, _, []) :-
    !.
fill(N, A, [A| As]) :-
    N > 0,
    N1 is N - 1,
    fill(N1, A, As).

A cut is a nasty little bugger that's always true but that's used for its side-effect: throwing away choice-points.

One issue with the quick solution above is that cuts, in general, make your code less declarative and introduce subtle (and not so subtle bugs). In this case, there's an apparently better solution: simply swap the order of the two clauses:

fill(N, A, [A| As]) :-
    N > 0,
    N1 is N - 1,
    fill(N1, A, As).
fill(0, _, []).

The second clause will only be tried when the N > 0test in the first clause fails. However, be aware that not all Prolog top-level interpreters detect that a query have no (more) solutions.

But this solution also have its own problem, depending on the Prolog system and how it indexes, or not indexes, clauses. Can you spot it? I will give you a hint: space complexity.