What does sort/2 do?

Help! Predicate
22

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.

23

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 :slight_smile: . 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. 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.

1 Like
25

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.

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.

27

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.

?- 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.

28

OK, what should happen here?

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

How about:

?- 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:

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…)

2 Likes
30

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

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.

1 Like
32

I did say that delayed goals can be less efficient. :laughing:

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.

1 Like
35

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:

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):

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 */
1 Like
37

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. :wink:

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).

2 Likes
40

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.

2 Likes
45

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 …

51

It says about that in the docs: (=)/2

It acts as if defined by the following fact:

=(Term, Term).
53

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

1 Like
55

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.)

57

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”.