Semantics of partition with "partial evaluation"

If I call

partition('='([_]), [1,2,[3],4,[5]],A,B).

I expect

A = [[3],[5]],
B = [1,2,4].

but I get

A = [[3]],
B = [1,2,4,[5]].

It’s not clear to me if my expectation is off, or if the implementation needs a fix.
I understand the “fix” of partition (if required) is to use copy_term before call(Pred, H) in

If the fix is my expectation, then I’d appreciate any insights as to why it would be typical to expect what actually happens.

What you want is:

partition([X]>>(X = [_]), [1,2,[3],4,[5]],A,B).

but I’m also a bit baffled that the two expressions don’t return the same answers.

As I mentioned, I can make my code do what I want my code to do. That’s one issue.

What I also really want, is for my expectation of the word predicate (a reusable test), and my expectation of Prolog common practice to align with my expectation of what partition does. This has multiple solutions but I don’t know which is best.

1 Like

Fair enough, bad wording on my part :slight_smile:
Just wanted to mention the other form, which doesn’t require an explicit copy_term.

1 Like

To the best of my understanding, it is not typical to expect what happens. However, copy_term would make the predicate slower.

Another conundrum is the text of the documentation, where it says:

All predicates support partial application in the Goal argument. This means that these calls are identical:

?- maplist(=, [foo, foo], [X, Y]).
?- maplist(=(foo), [X, Y]).

Yeah, well, in this example, we meant to unify. In your example, you meant to test, not to unify. Again, I am not standing on firm ground when I use this terminology, but unification does have an obvious “before” and “after” (before unification, and after unification). Tests shouldn’t have a before and after…

Stating the obvious, the workaround for what you are doing would be define a helper predicate:

?- [user].
|: one_element_list([_]).
|: ^D% user://1 compiled 0.00 sec, 1 clauses

?- partition(one_element_list, [1,2,[3],4,[5]],A,B).
A = [[3], [5]],
B = [1, 2, 4].

What has changed here is that the variable that gets unified is no longer in the same context as the call to partition.

I admit I have been bitten by exactly this behaviour more than once and after scratching my head for a minute or an hour I would figure it out and move on, until it bites me again.


The issue is unwanted unification:

?- partition('='([X]), [1,2,[3],4,[5]],A,B).
X = 3,
A = [[3]],
B = [1, 2, 4, [5]].

Could instead use:

?- partition(\=([X]), [1,2,[3],4,[5]], B, A).
B = [1, 2, 4],
A = [[3], [5]].

As I’ve said repeatedly, I understand the technical side. I even mentioned a possible update to the partition predicate to align it with my expectations.

Which part of my post made it seem like I needed help making code work, instead of help with the meanings of words among Prolog developers? I can try to clear it up.

I wanted clarity on the meanings of “partition” and “predicate” in the circles of logic programming and Prolog. That’s why the first word of the title is “semantics”.

I’m surprised that partitioning a list can have an effect on the predicate and on each entry of the list. I would expect “partition” to never be able to do anything beyond “partition” a list.

So, wouldn’t \+ \+ be appropriate, rather than copy_term?

1 Like

Not a simple question… to be true, i would prefer a fix of the library, more or less as you suggested (I would add a preliminary check for ground(Pred)).

I encountered a similar problem in library(dcg/high_order), because I was ‘optimizing’ the grammar in size, expecting the Sep non terminal (in sequence/3 or sequence/5) to work smootly also when non ground…

All in all, I think these are cases of ‘too early optimization’, that as someone could say, it’s the root of all evils.

Well, Prolog code has also operational semantics that must be taken into account. These say that partition/4 (as currently defined) processes the list in order, and there may be side effects, such as binding variables. Perhaps the documentation should explicitly state that the first argument is applied to the list in order, but then again this seems to go without saying.

I do sympathize with the idea of not binding any variables in the test. partition/4 joins include/3 and exclude/3 though and these traditionally preserve the bindings of the test. A more logical solution would be to allow backtracking to get the next solution with another on-element list. I don’t see a simple way to implement this though.

I have my doubts between either more clearly documenting this or avoid the instantiation (and clearly document that).

1 Like

How about:

:- meta_predicate partition_no_inst(1,+,-,-).

partition_no_inst(Pred, List, Included, Excluded) :-
    partition_no_inst_(List, Pred, Included, Excluded).

partition_no_inst_([], _, [], []).
partition_no_inst_([H|T], Pred, Incl, Excl) :-
    (   \+ call(Pred, H)
    ->  Excl=[H|E],
        partition_no_inst_(T, Pred, Incl, E)
    ;   Incl=[H|I],
        partition_no_inst_(T, Pred, I, Excl)
?- partition_no_inst(=([X]), [1,2,[3],4,[5]], A, B).
A = [[3], [5]],
B = [1, 2, 4].

I am inclined to agree on this comment, because, IMO, =([X]) is
a derived predicate of arity 1 from =/2 with global variable X.
BTW, my pack pac (clojure) is faithfully aware of such operational semantics as
queries below. SWI-Prolog has library(yall), which seems widely accepted.
So my pac is almost obsolete and deprecated, but I have to keep it because it can represent mutual recursive anonymous predicates, which is used as intermediate language to compile regex into DCG. Unfortunately it is still in my private use.

% ?- pred_partition(=([X]), [1,2,[3],4,[5]], A, B).
%@ X = 3,
%@ A = [1, 2, 4, [5]],
%@ B = [[3]].

% ?- pred_partition(pred([[_]]), [1,2,[3],4,[5]], A, B).
%@ A = [1, 2, 4],
%@ B = [[3], [5]].

% ?- X=3, pred_partition(pred(X, [[X]]), [1,2,[3],4,[5]], A, B).
%@ X = 3,
%@ A = [1, 2, 4, [5]],
%@ B = [[3]].

% ?- X=5, pred_partition(pred(X, [[X]]), [1,2,[3],4,[5]], A, B).
%@ X = 5,
%@ A = [1, 2, [3], 4],
%@ B = [[5]].

% ?- pred_partition(pred(X, [[X]]), [1,2,[3],4,[5]], A, B).
%@ X = 3,
%@ A = [1, 2, 4, [5]],
%@ B = [[3]].

pred_partition(_, [], [], []):-!.
pred_partition(Pred, [H|T], I, [H|E]):-	call(Pred, H), !,
	pred_partition(Pred, T, I, E).
pred_partition(Pred, [H|T], [H|I], E):-	pred_partition(Pred, T, I, E).

Probably the semantics of this are better. What I do not like is a new name. True, this surely doesn’t break anything. More predicates to choose from makes the system uglier though. The same reasoning applies to include/3 and exclude/3. maplist/2 is an interesting case though. It uses negation nor cuts, which makes instantiation logically sound. It used to be in SWI-Prolog as checklist/2 as well though (it is still in the backward compatibility library), so to check all elements are lists of at least two elements you may be tempted to use

 maplist(=([_,_|_]), List).

Which only succeeds if all elements of List can be unified to each other and are lists of at least two elements. I surely would not like to change maplist/2 though.

This problem seems to be a general one, due to Prolog’s lack of variable scoping within clauses. I know of at least the following “solutions”:

  • explicitly mention variables that are local (“exists” notation (using ^) in setof/3, bagof/3; see also free_variables/4)
  • explicitly mention variables that are not local ({...} notation in library(yall)) – this can be problematic, sometimes giving different semantics for compiled vs interpreted code.
  • two versions of the meta-predicates (e.g., aggregate/4 vs aggregate_all/4; bagof/3 vs findall/3)
  • double negation (\+ \+ Pred)
  • copy_term/2

The scoping rules (or, rather, lack of scoping) in Prolog clauses is usually a nice feature, but the problems with maplist(=[_,_],L) shows where it’s problematic - it would be nice to have maplist(X^Y^(=([X,Y])),L). (Incidentally, people often criticise Python for its “strange” scoping rules, which remind me a bit of Prolog’s scoping rules).

1 Like

Very good observations!

In Prolog we seem to have two issues though: instantiation and visibility. The yall {…} seems a case of reducing visibility (when the yall expression is compiled). In the other cases it seems we are more interested in controlling instantiation. The desire to do so seems to be related to non-logical constructs (negation or standard order of terms). I fear it is something we have to live with and a clear understanding is as good as it gets.

Could you explain visibility and instantiation using the goal =([X]) if they are applicable to it ?
Are they related to “global variables” ?

They are new to me and I am curious because of reason following. When LAMBDA was discussed in SWI-Prolog mailing list long time ago, one of difficulty for me was the notion of global variables. Someone on the list kindly helped me on this by explaing that it is difference in passing arguments. Usually argument is passed by the head unification, the other one is passed by context. I forgot details, but due to the explanation, I got clear enough about global variables, then I could write my package pac for clojure with explicit syntax for the context .

So far I thought X in =([X]) is treated automatically as global.
However I noticed there may be useful cases in which X should be
treated as local, and I ignore such cases in which arity of p of p([X]) is unknown. Although this problem might not relevant to your visibility and instnatiation problem, I have to see more detail on this point. I had no explicit syntax for such cases.

This seems to work:

?- maplist({}/[]>>(=([_,_])), [[1,2],[3,4]]).

?- maplist({}/[]>>(=([_,_])), [[1,2],[3,4,5]]).

or this abbreviated form:

?- maplist({}/(=([_,_])), [[1,2],[3,4,5]]).

?- maplist({}/(=([_,_])), [[1,2],[3,4]]).

This is an obvious copy-term solution following your
well classification of possible fixes. Unfortunately it requires run time helper predicates, which should not be recommended, I think.

user:local(X):- copy_term(X, Y), call(Y).
user:local(X,A):- copy_term(X, Y), call(Y,A).
user:local(X,A,B):- copy_term(X, Y), call(Y,A,B).
user:local(X,A,B,C):- copy_term(X, Y), call(Y,A,B,C).

% ?- maplist(local(=([_,_])), [[a,b], [c,d]]).
%@ true.
% ?- maplist(=([_,_]), [[a,b], [c,d]]).
%@ false.

BTW, as for checklist/2, I like the double negation fix due to @brebs.

I don’t know what you mean by “global”. In my terminology, global variables are things you handle using b_setval/2 and friends. If we look at V^Goal in setof/3, the instantiation of V is ignored when grouping the results of Goal, but V is still scoped to the clause in which it appears. Also in \+ \+ p(V), V is shared with all other Vs in the same clause. Only, calling \+ \+ p(V) does not instantiate V. Well, p/1 may instantiate it, but these changes are reverted by the (double) negation.

Note that double negation is almost always to be preferred over copy_term/2 to avoid unwanted binding. copy_term/2 may process huge terms, while the double negation only affects variables bound by the goal and reclaims garbage cheaply as a bonus rather than creating garbage as copy_term/2 in this scenario does.