# Re: Nondeterministic "functions" in OCL and implications

Perdita Stevens (Perdita.Stevens@dcs.ed.ac.uk)
Sun, 27 Feb 2000 16:56:43 +0000 (GMT)

```
[posting comments on personal mail back to the list, as Joaquin's comments
made me realise what I'd said wasn't complete.]

Joaquin Miller writes:

JM> If the same item appears twice in a bag, would it appear only once in
JM> the result of sorting the bag using a total ordering < operator?

A total order is a relation on a (mathematical) _set_ so the easy answer is
that the question doesn't arise, but in fact it's true I hadn't thought the
issue through. The OCL standard that I quoted says < has to be defined on
the type of the expression being used for sorting, and seems to imply that
this will induce a (total) ordering on the collection. But as your comment
implicitly points out that's not actually true, even if there's a total
order on the (set of elements of the) type of the expression.

For example, let myCollection be a collection of 3 objects of class T,
where class T has an integer attribute called i, and the objects in
myCollection have values 1, 1 and 2 for i, respectively. What should
myCollection -> sortedBy (i) return? Type integer has < defined on it, and
< on integers is a total order, but this still doesn't tell us what
sortedBy should do about those two objects. In other words the total order
on integer does not induce a total order on myCollection. So my suggestion
of insisting < be a total order may be a necessary part of the answer --
because if it isn't a total order, we're definitely stuck! -- but it isn't
the whole answer -- because even if it is a total order, we may still be
stuck :-(

In functional programming the usual way to deal with sorting is to have the
sorting function take as argument something like a function
lessThanOrEqualTo that takes two objects directly from the collection to be
sorted and returns true or false; then one imposes conditions on the
function's behaviour. This is simpler than the OCL version with a sorting
expression, because you don't have to worry, in your definition of the
sorting function, about the actual sorting criterion and the connection
between that and the sorting relation on what you really want to sort. But
OCL doesn't have function types, which is presumably why it doesn't do it
this way. (Jos?)

JM> Isn't it possible that there are sets for which there is no total
JM> ordering other than one realized by the introduction of some completely
JM> arbitrary additional {something} to the definition of the < operator or
JM> to the items in the set?

Not sure I understand what you're getting at, let me try two options...

1) It's certainly possible to have sets for which there is no "naturally
meaningful" total order; for example, the set of three fruits {apple,
melon, grape}. There are (6) ways of totally ordering them, and for some
you could give a justification (alphabetical by names; by typical size;
alphabetical by their names in Basque; whatever). If you wanted to define <
on the set, you'd just have to pick one. You always could pick one (for any
finite set, clearly; and in fact for any set at all provided we're happy to
use the "Axiom of Choice" -- but that's probably not too relevant here!)

In practice, I guess if you're wanting to sort a collection at all, it's
likely that you have a total order in mind, so this is not likely to be too
much of a problem. As a writer you'd have to make sure that there was no
confusion caused by different sorting orders being used on the same set --
this is why in OO libraries a "sorted collection" should encapsulate its
own sorting function.

2) It's also possible, though unlikely perhaps, that you could have a
collection of things for which it wasn't easy to write an expression that
"meaningfully involved" the objects and had a type on which < was defined.
Consider for example Set {true, false} of type Set(Bool). In OCL there is
no < defined on Bool. So what could you possibly give as the expression if
you wanted these sorted? I've seen people bend OCL in ways that amount to
writing function definitions, which would do it -- but this may be held to
back up the idea that functions perhaps ought to be in OCL as honest
citizens.

JM> [I can't figure out how to ask the second question in a clear and
JM> succinct way. What i am thinking is that there may be sets with
JM> elements that are distinct, but can not be distinguished by their
JM> properties. Consider electrons. Or identical (yes: identical, but not
JM> the same) balls in a (excuse me) bag.]

Objects, unlike values of basic types, have identity as well as state,
which is why we get this idea of there being objects in the same state but
with different identities. But the point about things being equal is that
you can't distinguish them in any way. So if two objects have different
identities then they are not equal in this sense, even if they have the
same values for all their attributes. For purposes of "true" equality
testing, the object's identity is just as much part of its state as its
attributes are. Concretely, we may sometimes care in which order two
objects turn up in a list, even when their attributes are the same, because
it may make a difference. So they aren't equal.

(Of course, sometimes it _is_ possible to ignore the object's identity,
when although philosophically they may have different identities it's not
possible to distinguish between them. IIRR Java calls these value objects,
reflecting exactly that although they're objects you can think of them as
values. Of course you may not want to look too closely, e.g. in C++ you can
always tell the difference between two objects that occupy different places
in memory.)

I've been thinking a little more about nondeterminacy, its causes and
effects, and jotting some notes; I'll post them or a reference to them
if/when I think they make sense. For now, any comment on the view that

Sequence {Set {1,2}}

is itself a nondeterministic expression in the sense we've been
considering, in that OCL doesn't currently specify whether this means
Sequence {1,2} or Sequence {2,1}? (Actually, it doesn't even specify that
it should be any kind of sequence, but that seems a reasonable assumption?)

Perdita
--
Dr. Perdita Stevens
Division of Informatics, University of Edinburgh
www.dcs.ed.ac.uk/home/pxs Fax: +44 131 667 7209
```