Impact of arguments order in maplist

Help!
1

Hello:

While playing with the implementation of the maplist/2 predicate, I have noticed that the order of the arguments in the predicate may matter. For example:

  1. If maplist/2 is implemented with the goal as first argument (using SWISH):
map1(_, []).
 map1(Goal, [H|T]) :-
        call(Goal, H),
        map1(Goal,T).

Then the query " ?- map1(integer, [])." provides true, makes a redo (?? I do not see why…) and then false.

  1. If maplist/2 is implemented with the goal as second argument (using SWISH):
map2([], _).
 map2([H|T], Goal) :-
        call(Goal, H),
        map2(T, Goal).

then the same query just answers “true” (no redo).

I have also found that this issue is explicitly mentioned in the SWI-Prolog implementation:

maplist(:Goal, ?List)
True if Goal can successfully be applied on all elements of List. Arguments are reordered to gain performance as well as to make the predicate deterministic under normal circumstances.

maplist(Goal, List) :-

  • maplist_(List, Goal). *
    maplist_([], _).
    maplist_([Elem|Tail], Goal) :-
  • call(Goal, Elem),*
  • maplist_(Tail, Goal).*

Could someone tell me:

  1. Where does the “redo” in the query " ?- map1(integer, [])." come from?
  2. Why the reordering “gains performance” and “makes the predicate deterministic under normal cirscuntance”? What does “normal circunstances” mean?
  3. Is there a general rule on arguments ordering, or only for second-order predicates, or …?

Thanks a lot in advance !!

2 Likes
2

The retry happens because there is another map1 clause below the initial matched clause which potentially matches. Your map2 version doesnt retry because SWI knows that the second map2 clause won’t match due to special case processing on the first index.
See https://www.swi-prolog.org/pldoc/man?section=jitindex (Special Purpose Code).

3 Likes
3

Richard O’Keefe in The Craft of Prolog (p14 in the copy I have) suggested this precedence for argument ordering:

  1. Templates (eg as in findall(+Template, :Goal, -Bag)) come first.
  2. Meta-arguments, as in :Goal in maplist(:Goal, ?List1, ?List2) and findall/3 above come next.
  3. Streams, as created by open(+SrcDest, +Mode, --Stream) are third. Good style is to place these within setup_call_cleanup/3. Since Stream is the output of open/3, it’s not a good example. Whatever predicate uses it (ie the second argument of setup_call_cleanup) would follow this convention.
  4. Selectors or indices as in arg(?Idx, +Term, ?Value).
  5. Collections as in Lists, Dictionaries, and context arguments like context_name(A,B,C,D,…).
  6. Input arguments which the predicate solves or tests for (which could be bidirectional, doubling as outputs).
  7. Outputs come last (which in the case of bidirectional predicates may sometimes be inputs. O 'Keefe suggests ordering bidirectional arguments by which is most commonly used input and output).

While many of these are just stylistic, it’s very important for outputs to come last and inputs to come second last for predicates to work as second_order functions for the apply family of predicates listed in https://www.swi-prolog.org/pldoc/man?section=apply as in maplist/3, include/3, exclude/3 etc.

5 Likes
4

An educated guess of what might be meant by “deterministic under normal circumstances”.

Example 1, deterministic, “normal circumstances”?:

?- maplist(integer, [1,2,3]).
true.

?- maplist(integer, []).
true.

Example 2, non-deterministic, “abnormal circumstances”?:

?- length(L, 2), maplist(between(1, 2), L).
L = [1, 1] ;
L = [1, 2] ;
L = [2, 1] ;
L = [2, 2].
2 Likes