# What does sort/2 do?

**URL:** <https://swi-prolog.discourse.group/t/what-does-sort-2-do/2418>\
**Category:** Predicate\
**Created:** [May 28, 2020, 11:40am UTC](https://swi-prolog.discourse.group/t/what-does-sort-2-do/2418 "2020-05-28T11:40:35Z")\
**Posts on this page:** 15\
**Page:** 2

<div class="post-metadata">

**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:** [November 26, 2020, 3:08pm UTC](https://swi-prolog.discourse.group/t/what-does-sort-2-do/2418/22 "2020-11-26T15:08:06Z")

</div>

The problem is that a global ordering is defined on any Prolog term, including variables. A variable is smaller than any non-variable. But variables can stop being variables, jumping to any place within the global ordering. So while a “Prolog variable is immutable”, binding a variable does mutate it, at least in respect to the standard order.

When you unify two variables to each other they also become identical, which they weren’t before that.

This is of course all explained in the [docs on the standard order of terms](https://www.swi-prolog.org/pldoc/man?section=standardorder).

---

<div class="post-metadata">

**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:** [November 26, 2020, 3:41pm UTC](https://swi-prolog.discourse.group/t/what-does-sort-2-do/2418/23 "2020-11-26T15:41:36Z")

</div>

AFAIK, SWI-Prolog is (for a change) completely standard compliant wrt. this behavior of sort/2. That is easy as the ISO makes very minimal promises as we discussed before 🙂 . If there is anything worth considering it could be a standard order comparison that raises an exception if the standard order cannot be decided yet. This is a bit like [?=/2](https://www.swi-prolog.org/pldoc/doc_for?object=?%3D%20/%202). I guess that verifying that ?=/2 holds between every pair of consecutive elements of a list is sufficient to guarantee the order is stable because (1) if we can decide on (in)equality we can also decide on the order and (2) ordering is transitive.

So, in theory you could make an alternative sort/2 that complains if the stability of the order cannot be guaranteed.

A constraint would be a strange thing, I fear. The ordering of variables is barely predictable for a specific implementation of Prolog, so sorting a list with variables has little more value than getting rid of duplicates and, if no possibly conflicting unifications are done, to use the ordsets predicates on sets of variables. I could image a `sorted(List)` constraint. As instantiating variables makes the elements change order, this is practically impossible as it is either false to begin with or just about any unification would make the constraint false. In theory there could be a promise that every pair in List for which the order is stable must be in the the right order. This boils down to this constraint.

```
when(?=(A,B), A @< B).

```

If the list is _finally sufficiently instantiated_, using the above between all consecutive element should suffice, I suppose.

---

<div class="post-metadata">

**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:** [November 26, 2020, 4:31pm UTC](https://swi-prolog.discourse.group/t/what-does-sort-2-do/2418/25 "2020-11-26T16:31:53Z")

</div>

> [@anon95304481](#):
>
> You see this here an attributed variable is never bound to an ordinary variable

Unifying an attributed variable with a normal variable will always make the normal variable a reference to the attributed variable and the shared identity thus the identity of the attributed variable. I would be surprised if any systems having attributes would do this differently.

> [@anon95304481](#):
>
> Can we use attributed variables in [SWISH](https://swish.swi-prolog.org/)?

Practically not. You may define an attribute if the matching hook predicates are considered safe. Attributes in `user` won’t do as this is shared and thus protected. You can only define the attribute hook in the temporary pengine module. This module name is not fixed. You can get this module using pengine\_self/1, but the code analysis is not strong enough to know what pengine\_self/1 does, so it cannot know put\_attr/3 is safe. I guess the only route would be to add a put\_attr/2 that uses the current context module as attribute name and declare that safe under the condition that the hooks are safe.

SWISH has limitations unless you run it locally and disable the sandbox.

---

<div class="post-metadata">

**Author:** ![dtonhofer](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/dtonhofer/32/902_2.png) [@dtonhofer](https://swi-prolog.discourse.group/u/dtonhofer)\
**Post date:** [November 27, 2020, 1:02pm UTC](https://swi-prolog.discourse.group/t/what-does-sort-2-do/2418/27 "2020-11-27T13:02:44Z")

</div>

> [@Boris](#):
>
> The problem is that a global ordering is defined on any Prolog term, including variables.

You are thinking in the operational context of what `sort/2` _does_.

But that’s not really relevant.

The point is that `sort/2` says that `[3,1,2]` is sorted according to the standard order of terms.

```prolog
?- X=[3,2,1],sort([A,B,C],X).
X = [3, 2, 1],
A = 3,
B = 2,
C = 1.

% I see the Wiley Coyote moment coming.

?- X=[3,2,1],sort([A,B,C],X),
    sort(X,X).
false.

% Aieee

```

In other words, it’s buggy. Or at least it doesn’t sort and computes something different than what its name implies. It should be called `acme_sort/2`

It should _at least_ fail when it can’t ensure that its second argument is _not unsorted_.

---

<div class="post-metadata">

**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:** [November 27, 2020, 1:18pm UTC](https://swi-prolog.discourse.group/t/what-does-sort-2-do/2418/28 "2020-11-27T13:18:12Z")

</div>

> [@dtonhofer](#):
>
> The point is that `sort/2` says that `[3,1,2]` is sorted according to the standard order of terms.

OK, what should happen here?

```prolog
?- sort([1, A], Sorted), A = 2.

```

How about:

```prolog
?- sort([1, A], Sorted), A = 0.

```

You seem to be wishing for the first one. In fact, Prolog does the second one.

It seems clear enough from reading the docs:

> `sort(+List, -Sorted)`  
> True if Sorted can be unified with a list holding the elements of List, sorted to the standard order of terms.

It says other things but this is already not the same as what you are wishing for sort/2.

I agree that it would be interesting to have a “sorted” constraint, for example naively like this:

```prolog
sorted([]).
sorted([X|Xs]) :-
    maplist(ordered(X), Xs),
    sorted(Xs).

ordered(A, B) :-
    when(?=(A, B), A @< B).

```

Whether you do it like this or only build a chain is also interesting. I guess it depends on the situation which one is better.

To me however this doesn’t look like sorting. Especially if you have a mix of free variables and nonvars in the first argument to sort/2. (EDIT: … because further instantiating anything will make it greater than it was before. Also, there is some rules about what happens to the “age” of free variables so even doing this “sorted” thing above might swap variables in their standard order…)

---

<div class="post-metadata">

**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:** [November 27, 2020, 7:31pm UTC](https://swi-prolog.discourse.group/t/what-does-sort-2-do/2418/30 "2020-11-27T19:31:22Z")

</div>

sort/2 could become logical if its use of `@<` is replaced by a predicate that delays until the arguments are sufficiently instantiated.

An example of such a predicate is dif/2. For example, `X\==Y, X=3, Y=3` succeeds but `dif(X,Y), X=3, Y=3` fails. The latter query fails because dif/2 provisionally succeeds but leaves constraints that delay until `X` and `Y` are sufficiently instantiated. A delaying version of sort/2 could be written using a suitable `@<` – I think it’d be defined something like

```prolog
logical_lt(X, Y) :- when(?=(X,Y), X @< Y).

```

Many other predicates can also be made logical this way. There’s a moderate amount of literature on this approach – if you’re interested, look at NU-Prolog, which I think is the earliest example. The downsides are: somewhat lower performance and tricky debugging (constraints, in general, are not easy to debug; and the “logical less-than” is a constraint). They can also produce surprising results – a kind of “maybe” when the query contains insufficiently instantiated terms; but that’s probably less surprising than `sort([A,B,C], [3,2,1])` succeeding.

---

<div class="post-metadata">

**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:** [November 27, 2020, 8:16pm UTC](https://swi-prolog.discourse.group/t/what-does-sort-2-do/2418/32 "2020-11-27T20:16:59Z")

</div>

> [@anon95304481](#):
>
> would avoid backtracking explosion due to choice points

I did say that delayed goals can be less efficient. 😆

Another possibility, of course, is to make a version of `@<` that throws an error if the `when(?=(X,Y))` constraint would delay. Perhaps this could be made as efficient as `@<`. But it’s not clear to me that it’s worth doing this – I’ve never had sort/2 (or setof/3) surprise me.

---

<div class="post-metadata">

**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:** [December 1, 2020, 8:12pm UTC](https://swi-prolog.discourse.group/t/what-does-sort-2-do/2418/35 "2020-12-01T20:12:26Z")

</div>

> [@anon95304481](#):
>
> > [@peter.ludemann](#):
> >
> > ````prolog
> > > logical_lt(X, Y) :- when(?=(X,Y), X @< Y).
> > > ```
> > 
> > ````
> 
> It will not do something useful on `[A, B, C]` . I will just create a lot of choice points, you could equally well call [permutation/2](https://www.swi-prolog.org/pldoc/doc_for?object=permutation/2). You would need to remove the cut here, when you delay.

Or you could do something like the following (untested), which delays as soon as it finds something insufficiently instantiated and continues deterministically (no choice points) otherwise:

```prolog
parts([], _, [], []).
parts([X|L], Y, L1, L2) :-
    when(?=(X,Y), parts2(X, L, Y, L1, L2)).

parts2(X, L, Y, [X|L1], L2) :-
	X @=< Y, !,
	parts(L, Y, L1, L2).
parts2(X, L, Y, L1, [X|L2]) :-
	parts(L, Y, L1, L2).

```

And for even more steadfastness (also untested):

```prolog
parts(L0, Y, L1, L2) :-
    when(nonvar(L0), parts1(L0, Y, L1, L2)).

parts1([], _, [], []).
parts1([X|L], Y, L1, L2) :-
    when(?=(X,Y), parts2(X, L, Y, L1, L2)).

/* parts2 as above */

```

---

<div class="post-metadata">

**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:** [December 2, 2020, 12:47am UTC](https://swi-prolog.discourse.group/t/what-does-sort-2-do/2418/37 "2020-12-02T00:47:56Z")

</div>

I don’t think the ISO spec envisioned delayed goals; and from what I remember of the whole ISO spec process fiasco, I’m not very concerned about its minutiae. 😉

This little example shows that making a predicate “more steadfast” by using delayed goals can be tricky; in practice, I’ve found that generalized handling of delays isn’t necessary and when I have had a need (e.g., when solving a constraint puzzle using delayed goals such as all\_distinct/1), then I know the specific places where delays or constraints might happen and can write code that takes appropriate precautions.

It’s not clear to me when `sort([A,B,C], Z)` might be useful … perhaps when doing something like outputting top-level results from a query and wanting a canonical ordering; and there are other ways of doing that (e.g., read\_term/2 with the `variable_names` option).

---

<div class="post-metadata">

**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:** [December 2, 2020, 7:26pm UTC](https://swi-prolog.discourse.group/t/what-does-sort-2-do/2418/40 "2020-12-02T19:26:51Z")

</div>

To clarify my comment on the ISO standard … as I recall (it was a few decades ago), the committee tried to invent a new language rather than codify existing practice; and they ignored people like Richard O’Keefe, who had written some of the best documentation and rationales for the existing practice. I’m not saying that existing practice was best; but changing a specification to be different from existing implementations didn’t help the spread of Prolog. Hence my non-interest in the ISO core standard. (I’ve worked on 2 language standards, by the way; although I don’t claim to be particularly good at such work.)

I agree that changing the definition of sort/2 to delay would be a mistake; a new `sorted/2` predicate that can delay would be better than adding semantics to sort/2. However, I’m unconvinced that a delaying `sorted/2` is of much benefit, other than an exercise in exploring the pluses and minuses of delays.

I used to be a big fan of delayed evaluation; I’ve become less convinced of its benefits, partly because of the difficulty in debugging code that delays. But I think that there is room for language design innovation that pushes Prolog to be more “logical” and reduces the need for cuts, and discussing things like the meaning of `sort([A,B,C], Z)` is useful in thinking about what such innovations might look like.

---

<div class="post-metadata">

**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:** [December 3, 2020, 9:02pm UTC](https://swi-prolog.discourse.group/t/what-does-sort-2-do/2418/45 "2020-12-03T21:02:43Z")

</div>

If you’re trying to do 2nd-order logic, Prolog doesn’t seem to be the best tool, and using Prolog variables for that seems to dangerously close to “defaulty” representation, which is known to be problematic.

Or maybe I misunderstand what you’re trying to do …

---

<div class="post-metadata">

**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:** [December 22, 2020, 12:53pm UTC](https://swi-prolog.discourse.group/t/what-does-sort-2-do/2418/51 "2020-12-22T12:53:10Z")

</div>

> [@anon95304481](#):
>
> This means we could define [(=)/2](https://www.swi-prolog.org/pldoc/doc_for?object=(%3D)/2) as follows:
> 
> `eq(X, X).`

It says about that in the docs: [(=)/2](https://www.swi-prolog.org/pldoc/doc_for?object=(%3D)/2)

> It acts as if defined by the following fact:
> 
> ```
> =(Term, Term).
> 
> ```

---

<div class="post-metadata">

**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:** [December 22, 2020, 12:57pm UTC](https://swi-prolog.discourse.group/t/what-does-sort-2-do/2418/53 "2020-12-22T12:57:30Z")

</div>

Linguistic titbit, did you know that “Mostowski Collapse” sounds very much like “Catastrophic Bridge Failure” to my Bulgarian ears?

---

<div class="post-metadata">

**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:** [December 22, 2020, 1:17pm UTC](https://swi-prolog.discourse.group/t/what-does-sort-2-do/2418/55 "2020-12-22T13:17:00Z")

</div>

I know where the name comes from. The question is, did you know how it sounds to my Bulgarian ears?

“Most” or “Мост” (Cyrillic) written exactly with these 4 letters means “bridge” in: Belarusian, Bosnian, Bulgarian, Croatian, Czech, Macedonian, **Polish** , Russian, Serbian, Slovak, Slovenian. Andrzej Mostowski, had he been born in the German-speaking realm, would have probably been Andreas Brücke. (The “owski” at the end is grammar, it doesn’t have inherent meaning on its own.)

---

<div class="post-metadata">

**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:** [December 22, 2020, 1:21pm UTC](https://swi-prolog.discourse.group/t/what-does-sort-2-do/2418/57 "2020-12-22T13:21:05Z")

</div>

Yes, I added a sentence about this. Those endings are necessary to make “family” (belonging) grammatically correct. Similar to “Monika Lewinsky”. However, in her case, the grammar is misleading, since it genders her “masculine”.

[Previous page](https://swi-prolog.discourse.group/t/what-does-sort-2-do/2418.md?page=1)