# Semantics of partition with "partial evaluation" **URL:** \ **Category:** General\ **Created:** [October 25, 2023, 4:16pm UTC](https://swi-prolog.discourse.group/t/semantics-of-partition-with-partial-evaluation/6920 "2023-10-25T16:16:05Z")\ **Posts on this page:** 20\ **Page:** 1
**Author:** ![z5h](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/z5h/32/5445_2.png) [@z5h](https://swi-prolog.discourse.group/u/z5h)\ **Post date:** [October 25, 2023, 4:16pm UTC](https://swi-prolog.discourse.group/t/semantics-of-partition-with-partial-evaluation/6920/1 "2023-10-25T16:16:05Z")
If I call ```prolog partition('='([_]), [1,2,[3],4,[5]],A,B). ``` I expect ```prolog A = [[3],[5]], B = [1,2,4]. ``` but I get ```prolog 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 apply.pl. If the fix is my expectation, then I’d appreciate any insights as to why it would be typical to expect what actually happens. ---
**Author:** ![meditans](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/meditans/32/1768_2.png) [@meditans](https://swi-prolog.discourse.group/u/meditans)\ **Post date:** [October 25, 2023, 4:30pm UTC](https://swi-prolog.discourse.group/t/semantics-of-partition-with-partial-evaluation/6920/2 "2023-10-25T16:30:16Z")
> [@z5h](#): > > `partition('='([_]), [1,2,[3],4,[5]],A,B).` What you want is: ```prolog 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. ---
**Author:** ![z5h](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/z5h/32/5445_2.png) [@z5h](https://swi-prolog.discourse.group/u/z5h)\ **Post date:** [October 25, 2023, 4:40pm UTC](https://swi-prolog.discourse.group/t/semantics-of-partition-with-partial-evaluation/6920/3 "2023-10-25T16:40:19Z")
> [@meditans](#): > > What you want … 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. ---
**Author:** ![meditans](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/meditans/32/1768_2.png) [@meditans](https://swi-prolog.discourse.group/u/meditans)\ **Post date:** [October 25, 2023, 4:57pm UTC](https://swi-prolog.discourse.group/t/semantics-of-partition-with-partial-evaluation/6920/4 "2023-10-25T16:57:13Z")
> [@z5h](#): > > As I mentioned, I can make my code do what I want my code to do Fair enough, bad wording on my part 🙂 Just wanted to mention the other form, which doesn’t require an explicit `copy_term`. ---
**Author:** ![Boris](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/boris/32/7486_2.png) [@Boris](https://swi-prolog.discourse.group/u/Boris)\ **Post date:** [October 25, 2023, 6:44pm UTC](https://swi-prolog.discourse.group/t/semantics-of-partition-with-partial-evaluation/6920/5 "2023-10-25T18:44:28Z")
> [@z5h](#): > > If the fix is my expectation, then I’d appreciate any insights as to why it would be typical to expect what actually happens. 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: ```prolog ?- [user]. |: one_element_list([_]). |: ^D% user://1 compiled 0.00 sec, 1 clauses true. ?- 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. ---
**Author:** ![brebs](https://avatars.discourse-cdn.com/v4/letter/b/e9c0ed/32.png) [@brebs](https://swi-prolog.discourse.group/u/brebs)\ **Post date:** [October 25, 2023, 8:47pm UTC](https://swi-prolog.discourse.group/t/semantics-of-partition-with-partial-evaluation/6920/6 "2023-10-25T20:47:52Z")
The issue is unwanted unification: ```prolog ?- partition('='([X]), [1,2,[3],4,[5]],A,B). X = 3, A = [[3]], B = [1, 2, 4, [5]]. ``` Could instead use: ```prolog ?- partition(\=([X]), [1,2,[3],4,[5]], B, A). B = [1, 2, 4], A = [[3], [5]]. ``` ---
**Author:** ![z5h](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/z5h/32/5445_2.png) [@z5h](https://swi-prolog.discourse.group/u/z5h)\ **Post date:** [October 25, 2023, 8:54pm UTC](https://swi-prolog.discourse.group/t/semantics-of-partition-with-partial-evaluation/6920/7 "2023-10-25T20:54:43Z")
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. ---
**Author:** ![brebs](https://avatars.discourse-cdn.com/v4/letter/b/e9c0ed/32.png) [@brebs](https://swi-prolog.discourse.group/u/brebs)\ **Post date:** [October 25, 2023, 9:21pm UTC](https://swi-prolog.discourse.group/t/semantics-of-partition-with-partial-evaluation/6920/8 "2023-10-25T21:21:56Z")
So, wouldn’t `\+ \+` be appropriate, rather than `copy_term`? ---
**Author:** ![CapelliC](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/capellic/32/17_2.png) [@CapelliC](https://swi-prolog.discourse.group/u/CapelliC)\ **Post date:** [October 26, 2023, 6:55am UTC](https://swi-prolog.discourse.group/t/semantics-of-partition-with-partial-evaluation/6920/10 "2023-10-26T06:55:46Z")
> [@z5h](#): > > why it would be typical to expect what actually happens 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. ---
**Author:** ![oskardrums](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/oskardrums/32/3594_2.png) [@oskardrums](https://swi-prolog.discourse.group/u/oskardrums)\ **Post date:** [October 26, 2023, 7:37am UTC](https://swi-prolog.discourse.group/t/semantics-of-partition-with-partial-evaluation/6920/11 "2023-10-26T07:37:15Z")
> [@z5h](#): > > 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. 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. ---
**Author:** ![jan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/jan/32/4_2.png) [@jan](https://swi-prolog.discourse.group/u/jan)\ **Post date:** [October 27, 2023, 8:24am UTC](https://swi-prolog.discourse.group/t/semantics-of-partition-with-partial-evaluation/6920/13 "2023-10-27T08:24:12Z")
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). ---
**Author:** ![brebs](https://avatars.discourse-cdn.com/v4/letter/b/e9c0ed/32.png) [@brebs](https://swi-prolog.discourse.group/u/brebs)\ **Post date:** [October 27, 2023, 1:49pm UTC](https://swi-prolog.discourse.group/t/semantics-of-partition-with-partial-evaluation/6920/14 "2023-10-27T13:49:15Z")
How about: ```prolog :- 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) ). ``` ```prolog ?- partition_no_inst(=([X]), [1,2,[3],4,[5]], A, B). A = [[3], [5]], B = [1, 2, 4]. ``` ---
**Author:** ![kuniaki.mukai](https://avatars.discourse-cdn.com/v4/letter/k/c67d28/32.png) [@kuniaki.mukai](https://swi-prolog.discourse.group/u/kuniaki.mukai)\ **Post date:** [October 27, 2023, 4:47pm UTC](https://swi-prolog.discourse.group/t/semantics-of-partition-with-partial-evaluation/6920/15 "2023-10-27T16:47:39Z")
> [@oskardrums](#): > > Prolog code has also operational semantics that must be taken into account. 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. ```prolog % ?- 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). ``` ---
**Author:** ![jan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/jan/32/4_2.png) [@jan](https://swi-prolog.discourse.group/u/jan)\ **Post date:** [October 29, 2023, 12:50pm UTC](https://swi-prolog.discourse.group/t/semantics-of-partition-with-partial-evaluation/6920/16 "2023-10-29T12:50:56Z")
> [@brebs](#): > > `partition_no_inst` 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. ---
**Author:** ![peter.ludemann](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/peter.ludemann/32/48_2.png) [@peter.ludemann](https://swi-prolog.discourse.group/u/peter.ludemann)\ **Post date:** [October 29, 2023, 4:02pm UTC](https://swi-prolog.discourse.group/t/semantics-of-partition-with-partial-evaluation/6920/17 "2023-10-29T16:02:02Z")
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). ---
**Author:** ![jan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/jan/32/4_2.png) [@jan](https://swi-prolog.discourse.group/u/jan)\ **Post date:** [October 29, 2023, 4:14pm UTC](https://swi-prolog.discourse.group/t/semantics-of-partition-with-partial-evaluation/6920/18 "2023-10-29T16:14:12Z")
Very good observations! > [@peter.ludemann](#): > > due to Prolog’s lack of variable scoping within clauses 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. ---
**Author:** ![kuniaki.mukai](https://avatars.discourse-cdn.com/v4/letter/k/c67d28/32.png) [@kuniaki.mukai](https://swi-prolog.discourse.group/u/kuniaki.mukai)\ **Post date:** [October 29, 2023, 5:12pm UTC](https://swi-prolog.discourse.group/t/semantics-of-partition-with-partial-evaluation/6920/19 "2023-10-29T17:12:35Z")
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 . **EDIT** 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. ---
**Author:** ![peter.ludemann](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/peter.ludemann/32/48_2.png) [@peter.ludemann](https://swi-prolog.discourse.group/u/peter.ludemann)\ **Post date:** [October 29, 2023, 6:03pm UTC](https://swi-prolog.discourse.group/t/semantics-of-partition-with-partial-evaluation/6920/20 "2023-10-29T18:03:53Z")
> [@jan](#): > > `maplist(=([_,_|_]), List)` This seems to work: ```prolog ?- maplist({}/[]>>(=([_,_])), [[1,2],[3,4]]). true. ?- maplist({}/[]>>(=([_,_])), [[1,2],[3,4,5]]). false. ``` or this abbreviated form: ```prolog ?- maplist({}/(=([_,_])), [[1,2],[3,4,5]]). false. ?- maplist({}/(=([_,_])), [[1,2],[3,4]]). true. ``` ---
**Author:** ![kuniaki.mukai](https://avatars.discourse-cdn.com/v4/letter/k/c67d28/32.png) [@kuniaki.mukai](https://swi-prolog.discourse.group/u/kuniaki.mukai)\ **Post date:** [October 29, 2023, 9:18pm UTC](https://swi-prolog.discourse.group/t/semantics-of-partition-with-partial-evaluation/6920/21 "2023-10-29T21:18:44Z")
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. ```prolog 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. ---
**Author:** ![jan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/jan/32/4_2.png) [@jan](https://swi-prolog.discourse.group/u/jan)\ **Post date:** [October 30, 2023, 8:59am UTC](https://swi-prolog.discourse.group/t/semantics-of-partition-with-partial-evaluation/6920/22 "2023-10-30T08:59:58Z")
> [@kuniaki.mukai](#): > > Are they related to “global variables” ? 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. [Next page](https://swi-prolog.discourse.group/t/semantics-of-partition-with-partial-evaluation/6920.md?page=2)