Will using member within a forall clause in SWI-Prolog always output the elements in the same order?

Question

Having recently got into Prolog I've been using it for a few simple tasks and began to wonder about using member within forall loops like the one in the trivial example below:

forall(member(A,[1,2,3,4]), print(A)).

In the case that you do something like this is it always true that forall will process the elements within the list in the same order every time its called? Does it have to be enforced by say doing something like:

A = [1,2,3,4], sort(A, B), forall(member(C,B), print(C)).

From what little research I've initially done I'm guessing that it comes down to the behaviour of member/2 but the documentation for the function on SWI-Prolog's website is very brief. It does however mention determinism with regards member/2 which gave me an inkling I might be on the right path in saying that it would always extract the elements in the same order, though I'm far from certain.

Can anyone give me any guarantees or explanations on this one?

Answer 1

Non-determinism in Prolog simply refers to a predicate having potentially more than one solution. Clearly, member/2 is such a predicate. This does not mean that you have to be worried about your computation becoming unpredictable. Prolog has a well-defined computation rule which essentially says that alternative solutions are explored in a depth-first, left-to-right manner. Thus your goal member(X,[1,2,3,4]) will generate solutions to X in the expected order 1,2,3,4.

Sorting the list [1,2,3,4] will not make any difference, as it is already sorted (according to Prolog's standard term order).

A word of caution about forall/2: some Prologs define this, but it is probably less useful than you imagine, because it is not really a "loop". You can use it in your example because you only perform a print side effect in each iteration. For most other purposes, you should familiarize yourself with recursive patterns like

print_list([]).
print_list([X|Xs]) :- print(X), print_list(Xs).

Answer 2

Strictly speaking, there is no guarantee in SWI on several levels:

1mo, that member/2 or forall/2 will perform in exactly this manner, since you can redefine them.

?- [user].
member(X,X).
|: % user://1 compiled 0.00 sec, 2 clauses
true.

?- forall(member(A,[1,2,3,4]), print(A)).
[1,2,3,4]
true.

However, member/2 is defined in the Prolog prologue which covers all the details you are interested in. As for forall(A,B) it is safer to write \+ (A, \+B) instead, since this relies on standard features only. There is no definition of forall/2 as such, so it is difficult to tell what is the "right" behavior.

2do, that SWI will be standard conforming. If you read the documentation, you will note that there is no self-declaration (as for, e.g. SICStus Prolog) for standard conformance. In fact, \+ (A, \+B) is not fully conforming, as in the following example that should silently fail, but rather prints nonconforming

?-  \+ ( C= !, \+ (C,fail;writeq(nonconforming))).

Answer 3

N208 has forall/2 defined + (call(Generator), + call(Test)), so this makes it less dubious. But by virtue that the ISO core standard (+)/1 does already a call/1 and that the ISO core standard (,)/2 will be subject to body conversion one can simply define it as follows in an ISO core standard Prolog:

forall(Generator, Test) :-
   \+ (Generator, \+ Test).

SWI-Prolog has also implemented this way, and the error observed by Ulrich Neumerkel will not be seen when using forall/2:

Welcome to SWI-Prolog (threaded, 64 bits, version 7.7.18)
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software.

?- \+ ( C= !, \+ (C,fail;writeq(nonconforming))).
nonconforming
true.

?- forall(C=!, (C,fail;writeq(nonconforming))).
false.

Side remark:

I don't know how useful it is for loop. It seems to me using it for loops is not the right approach, since the test might fail, and then the construct also fails. I have also seen by Striegnitz and Blackburn the following definition of a helper predicate that they call failiure driven loop.

doall(Goal) :-
   Goal, fail.
doall(_).

I find myself directly writing Goal, fail; true which also does the job:

Welcome to SWI-Prolog (threaded, 64 bits, version 7.7.18)
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software.

?- member(A,[1,2,3,4]), write(A), nl, fail; true.
1
2
3
4
true.