issues regarding prolog backtracking to find other solution

Question

I am beginner of Prolog.

what I have is a function traverse a list and return true when it satisfies the condition.

for example, check_version checks if the package version met the condition(eg. the version satisfies the condition such as greater than or less than the specific version) and check_all checks takes a list of versions and conditions to check one by one.

package('python', '2.6.5').
package('python', '2.5.4').
package('python', '1.5.2').
package('python', '3.1.0').

check_version(Pac, Ver, Cmp, V):-
   package(Pac, V),
   cmp_version(V, Ver, Cmp).

check_all( Pac, [], [], V):-
   package(Pac, V).
check_all(Pac, [Ver], [Cmp], V):-
   check_version(Pac, Ver, Cmp, V).
check_all(Pac, [Ver|VerS], [Cmp|CmpS], V):-
   check_version(Pac, Ver, Cmp, V),
   check_all(Pac, VerS, CmpS, V).

The problem I have is when try to find other solutions, it gives me duplicate solution.

I get:

check_all('python', ['3.0','2.4'], [lt,ge], V).

V = '2.6.5' ;
V = '2.6.5' ;
V = '2.5.4' ;
V = '2.5.4' .

expected:

check_all('python', ['3.0','2.4'], [lt,ge], V).
V = '2.6.5' ;
V = '2.5.4' .

I used trace to track it, and the problem I found, when it try to find another solution it back tracks and will return fail until find the right solution. Like the example above, apparently, it will return true for V='2.6.5' at first and take that to back track and run the functions, and we expect it returns false and then when it reach the beginning it run package('python', V) and V will take another value.

...

Exit: (7) check_all(python, ['3.0', '2.4'], [lt, ge], '2.6.5') ? creep
V = '2.6.5' 

...

 Fail: (9) check_version(python, '2.4', ge, '2.6.5') ? creep
 Redo: (8) check_all(python, ['2.4'], [ge], '2.6.5') ? creep
 Call: (9) check_version(python, '2.4', ge, '2.6.5') ? creep
 Call: (10) package(python, '2.6.5') ? creep
 Exit: (10) package(python, '2.6.5') ? creep

when back tracking, in check_all, it fails at check_all as we expected, but it returns true when it backtracks check_version and run package(python, '2.6.5') as V=2.6.5 a new value. so it return true again when V=2.6.5. is there any way to solve this problem?

Answer 1

To localize your problem, first reduce the size of your input. A single element suffices:

?- check_all('python', ['3.0'], [lt], V).

Now, which rules apply for a single element?

Both rules apply! So remove the more specialized one.

There is also another way how to localize such a problem. Simply compare the rules to each other and try to figure out a case where they both apply. The last rule applies for VerS = [] when also the first applies.

Answer 2

Applying a predicate to each element of a list is best done by a predicate that has the list as its first argument. Without going into detail, this makes the predicate succeed when the iteration is complete, if the argument is a list and not a variable (i.e. when it is an input argument). You should have two clauses: one to deal with the empty list and one for the general case:

foo([]). % succeed
foo([X|Xs]) :-
    /* apply a predicate to X */
    foo(Xs). % apply predicate to the rest of the list

An important thing here is that you don't need a third clause that deals with lists with one element only, since a list with one element is actually a list with an element and an empty list as its tail:

?- [a] == [a|[]].
true.

?- [a] = [a|[]].
true.

Another important thing is that there is nothing you should be doing in the base case, empty list (at least for your example).

To the problem now: your inputs are

• the package name
• two lists holding pairs of arguments to a predicate you have defined elsewhere (cmp_version/3). This is your list of conditions.

Implementation:

• Known packages are available as facts: they can be enumerated by backtracking.
• Conditions are an input arguments, provided as a list: you need to apply the condition to each element of the list(s).

The predicate:

check_all([], [], _, _).
check_all([V|Vs], [C|Cs], Name, Version) :-
    package(Name, V), % enumerate all known packages by backtracking
    cmp_version(Version, V, Cmp), % condition
    check_all(Vs, Cs, Name, Version). % apply condition to the rest of the list(s)

You should read the documentation of maplist. You can express the query for example as:

?- maplist(check_version(python), ['3.0', '2.4'], [lt, ge], Versions).

where you have defined a predicate check_version/4 that looks something like:

check_version(Name, V, Cmp, Version) :-
    package(Name, Version),
    cmp_version(Version, V, Cmp).

As a side note, maplist will reorder its arguments to make it behave like the explicit iteration above.

EDIT

Naming issues, after @mat's comments: one very useful naming convention is to use a name that has descriptive one-word names for the arguments, delimited by underscores. For example, package/2 becomes package_version/2 since its first argument is the package and the second one the version.