Prolog and reverse tracking restrictions

Question

This is probably the most trivial implementation of a function that returns the length of a list in Prolog

count([], 0). count([_|B], T) :- count(B, U), T is U + 1. 

one thing about Prolog that I still can't wrap up is the flexibility of using variables as parameters.

So, for example, I can run count([a, b, c], 3). and get true . I can also run count([a, b], X). and get the answer X = 2. .. Oddly enough (at least for me), I can also run count(X, 3). and get at least one result that looks something like X = [_G4337877, _G4337880, _G4337883] ; before the interpreter disappears into an infinite loop. I can even run something really “flexible” like count(X, A). , and get X = [], A = 0 ; X = [_G4369400], A = 1. X = [], A = 0 ; X = [_G4369400], A = 1. , which is clearly incomplete, but somehow very nice.

Therefore, my multifaceted question. Can I somehow explain Prolog not to look at the first result when doing count(X, 3). ? Can I somehow get Prolog to generate any number of solutions for count(X, A). ? Is there a limit to what solutions I can create? What is this particular predicate that prevents me from generating all solutions for all possible types of queries?

Answer 1

This is perhaps the most trivial implementation

Depends on the point of view: consider

 count(L,C) :- length(L,C). 

Shorter and more functional. And it also works for your use case.

change

library CLP (FD) allows

 :- use_module(library(clpfd)). count([], 0). count([_|B], T) :- U #>= 0, T #= U + 1, count(B, U). ?- count(X,3). X = [_G2327, _G2498, _G2669] ; false. 

(further) by replying to comments

It was clearly sarcasm

No, sorry for that impression. It was an attempt to give you a synthetic answer to your question. All the details of the implementation of length / 2 - indeed much longer than your code, were carefully weighed to give us a common and efficient building block.

There must be some general concept

I would call the (complete) Prologue such a general concept. From the very beginning, Prolog requires us to solve computational problems that describe the relationship between predicate arguments. Once we have described our relationship, we can query our “knowledge database,” and Prolog tries to list all the answers in a specific order.

High-level concepts such as unification and backtracking are the keys to this model.

Now I think you're looking for second-order constructs, such as var / 1, that allow us to reason about our predicates. Such constructs cannot be written in (pure) Prolog, and a growing school of thought should avoid them because they are quite difficult to use. So I posted an alternative using CLP (FD) that effectively protects us in some situations. In this matter, the specific context, he actually gives us a simple and elegant solution.

I am not trying to reimplement length

Well, I know about this, but since count / 2 aliases length / 2, why not explore the reference model? (The watched source was used on the SWI-Prolog website, but it seems to be broken right now)

Answer 2

The answer you get for the request count(X,3) is actually not odd. You ask which lists have a length of 3. And you will get a list of 3 items. An infinite loop appears because the variables B and U in the first goal of your recursive rule are unbound. You have nothing before this goal, which may fail. Therefore, you can always monitor recursion. In the CapelliC version, you have 2 goals in the second rule before recursion, which fail if the second argument is less than 1. Perhaps it becomes clearer if you consider this slightly modified version:

 :- use_module(library(clpfd)). count([], 0). count([_|B], T) :- T #> 0, U #= T - 1, count(B, U). 

Your request

 ?- count(X,3). 

will not match the first rule, and the second will continue recursively until the second argument is 0. At this point, the first rule will match and give the result:

 X = [_A,_B,_C] ? 

The head of the second rule will also be consistent, but its first goal will not be fulfilled, because T=0 :

 X = [_A,_B,_C] ? ; no 

In your previous version, however, Prolog will try to find the recursive target of the second rule due to the unrelated variables B and U and therefore the loop is infinite.