Re: Nondeterministic "functions" in OCL and implications



Date view Thread view Subject view Author view

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


Date view Thread view Subject view Author view