SortedCollection>>addLast: problems [was: Re: [FIX] SortedCollectionFix-sr]

Stephan Rudlof squeak-dev at lists.squeakfoundation.org
Wed Oct 23 02:34:11 UTC 2002


Note for all: <SoundsLikeAClassName> denotes a protocol, not a class.
Without the '<>' a class is meant.

Richard A. O'Keefe wrote:
> 	attached screenshot first.
> 	
> My mail reader doesn't do attachments.  I treasure it for that reason.
> 	> Not a contradiction at all.  I wasn't suggesting *introducing* such
> 	> an operation, but fixing an operation that *already exists*.
> 	
> 	>>addLast:  doesn't exist for the <SortedCollection> *protocol*,
> 	if I've understood ANSI correctly (see below).  And the
> 	<SortedCollection> protocol does *not* inherit from <OrderedCollection>!
> 
> I thought we were talking about Squeak.
> 
> Squeak doesn't conform to the ANSI specification,
> never has, and such conformance doesn't seem to be a goal.
> One Squeaker put a LOT of work into providing some change
> sets to make Squeak closer to ANSI with particular
> emphasis on collection classes.  He even provided SUnit tests.
> 
> I gladly grabbed a copy of his work, and have been expecting it to
> be adopted in Squeak releases.  No such luck.  It appears that
> ANSI conformance is not very important to SqC.

Agreed.

> 
> 	That is, what I've meant with introducing a not existing operation.
> 	
> Whatever ANSI says, the operation *DOES* exist in Squeak.
> In fact, a lot of code in SortedCollection depends on it, as you
> no doubt found.
> 
> 	> Again, RunArray>>addLast:.  
> 	
> 	RunArray isn't defined by the standard as I see it.
> 	
> We seem to be talking at cross-purposes.
> I am talking about Squeak here, and only about Squeak.
> If you code in pure ANSI Smalltalk, more power to you and your
> traditional UNIX-like programs (file I/O only, no sound, no GUI,
> no mouse, no processes, no projects, no change sets, ...).
> 

> As a *Squeak* programmer, it is quite impossible for me to adopt
> a convention that "addLast: implies OrderedCollection" because in
> Squeak it isn't true.

This is the problem.

> 
> 	> I still don't have a copy of the final standard, but the 1.9 draft
> 	> says some funny things about SortedCollection.
> 	
> 	<...>
> 	
> 	> 	But I stay at my assumption to expect an OrderedCollection if using
> 	> 	>>addLast:. And if you introduce methods *** with the same name *** in other
> 	> 	protocols you break conventions (and ANSI is also a convention).
> 	> 	
> 	> You only break conventions if you do not follow the conventional rules
> 	> about refinement.  The way ANSI refines methods for SortedCollection
> 	> provides ample precedent for refining the *inherited* (NOT "introduced")
> 	> method #addLast:.
> 	<...>
> 	
> 	>From ANSI draft v1.9 (if you'd need it e.g. as *indexed* (very
> 	practical) PDF, I could send it to you):
> 
> I have the .doc file and a .txt file made from it.
> If indexed PDFs search fast, that would be most kind.
> 
> 	------
> 	5.7.17 Protocol: <SortedCollection>
> 	
> I have seen this and know what it says.
> 	
> 	<SortedCollection> does *not* conform to <OrderedCollection> which is the
> 	only one defining >>addLast:.
> 	

> Nononono.  The standard doesn't say that SortedCollection DOESN'T
> conform to OrderedCollection, only that it DOESN'T HAVE TO conform.

In the standard <SortedCollection> does *not* conform to <OrderedCollection>
 (as I've said) *and* your interpretation is correct.
But if you extent the conformance of <SortedCollection> to also be
conformant to <OrderedCollection>, you are responsible to give it a well
defined semantics.

> 
> And again, the standard defines #addLast: only for OrderedCollection,
> but that doesn't mean that only OrderedCollection may have it.

Agreed.

> A
> Smalltalk implementor may provide #addLast: implementations in hundreds
> of classes, if they make sense

Agreed.

My point is, that I think (I may be wrong here) the authors of ANSI have
consciously avoided this can of worms by not covering these extensions.

> 
> I don't need to recite a list of other Smalltalks which also have
> RunArray, do I?

No.

> 
> 	Note: here the term 'inherited' is applied to protocols, not to class
> 	inheritance!
> 	
> Not terribly relevant to this discussion.  The specification only
> *provides* protocols, not implementations.

I think this is relevant: inheritance given by the implementation doesn't
automatically give a well defined semantic. #addLast: in SortedCollection is
a good example.

> 
> The question at issue here is what one specific implementation of
> SortedCollection should do in one specific implementation of Smalltalk
> which is not, does not claim to be, and does not aim to be, ANSI-conformant.
> 
> 	Now I've found something better: in 5.7 there is a nice graphics showing the
> 	conformance relationships between protocols. I've attached a screenshot.
> 	
> 	There you can see that <SortedCollection> really does *not* inherit the
> 	<OrderedCollection> protocol!
> 	
> It does not say that at all.  It only says that the standard itself does
> not *require* this, so that a vendor need not implement such an inheritance
> and a customer may not assume it in code which is intended to be portable.

In the standard
- the <SortedCollection> *protocol* does *not* inherit the
<OrderedCollection> *protocol*,
in Squeak
- SortedCollection inherits the *implementation* of OrderedCollection>>addLast:.

The latter does not mean, that there is a well defined semantics for calling
#addLast: for SortedCollections.

ANSI says:
5.1.3.2 Refinement
...
We call a message specification in a protocol <P> a definition if it is not
included in any protocol to which <P> conforms.
...

This is one case for SortedCollection>>addLast: : it is not included in any
protocol to which <SortedCollection> conforms. So if we'd extent ANSI
<SortedCollection> by just adding #addLast: to this protocol (for e.g.
Squeak), we'd have a new definition. I don't like this extension, since I
don't know how to give it a well defined and intuitively correct semantics.

The other case: if we'd extent the conformance of <SortedCollection> to also
be conformant to <OrderedCollection> supplying a good semantics would be far
more difficult, since we'd need to define it for all methods in
<OrderedCollection>.

> 
> 	And this is also the reason, why >>addLast: is *not* refined by
> 	<SortedCollection>: it doesn't need to.
> 	
> Nobody ever said that the ANSI specification of #addLast: did or
> ought to refine #addLast:.
> 
> My claim was that it DOESN'T (which you agree with)
> but that there are several weird refinements of not entirely
> dissimilar operations which provide *precedent* (that is,
> analogies which strongly suggest how a case not previously covered
> should be handled).
> 
> A particularly interesting one is
>     coll copyReplaceFrom: start to: finish with: anotherColl.
> 
> For an OrderedCollection,
>     oc copy addLast: x
> has the same effect as
>     oc copyReplaceFrom: oc size + 1 to: oc size with: {x}

> 
> If anything, this would suggest that
>     sc copy addLast: x
> should have the same effect as
>     sc copyReplaceFrom: sc size + 1 to: sc size with: {x}
> which has the same effect as
>     sc add: x
>
> This is rather strange;

No, if there is no well defined semantic for SortedCollection>>addLast:,
which is my assumption.

> the stranger thing is that ANSI requires
> copyReplaceFrom:to:with: to apply to SortedCollection instances
> in the first place.

May be (don't have an opinion right now), but ANSI says there: 'Collections
that enforce an ordering on their elements are permitted to refine this
message to reorder the result.' This allows a well defined semantics.
Possibly reordering should be 'enforced' instead of 'permitted' here though.

> 
> Now copyReplaceFrom:to:with: is in the <sequencedReadableCollection>
> protocol in ANSI>.  An even closer analogue is
> 
>     n := coll size.
>     coll copyReplaceFrom: n+1 to: n withObject: x
> 
> which is not in fact implemented ANYWHERE in Squeak.  So
> <CSOTD>
>     SequenceableCollection>>
>     copyReplaceFrom: start to: stop withObject: replacementElement
> 	^self copyReplaceFrom: start to: stop
> 	      with: (Array with: replacementElement)
> </CSOTD>
> 
> 	Hopefully I've reduced confusion a little bit.
> 	

> You haven't reduced any confusion about what the ANSI standard is or says.
> If anything, you've created confusion in my mind.

I'm sorry about that.

> 
> If we're talking about the ANSI specification, there is nothing to fix.
> (Not because the ANSI spec. is perfect, far from it, but because it doesn't
> provide any code that could be broken.)
> 
> If we're talking about Squeak, the fact that the ANSI standard does not
> *require* SortedCollection to inherit from OrderedCollection is of little
> or no interest as long as the standard doesn't *forbid* such inheritance.
> And for obvious historical reasons, it doesn't.

But there are reasons, why the standard does not require <SortedCollection>
*protocol* to inherit from <OrderedCollection>. And - as stated in other
words before - implementation inheritance is not protocol inheritance and
may be somewhat say 'arbitrary', so long as the messages in the defined
protocols - a subset of all messages of the implementation! - are working as
expected.
In my opinion Squeak's SortedCollection>>addLast: is incidentally (since the
implementors have been sloppy here) inherited from OrderedCollection, and we
shouldn't try to give it a (protocol) semantic.

> 
> With respect to Squeak, defining a method only counts as introducing
> a new method if the method was not previously defined or inherited by
> the class in question.

This is true regarding the implementation.
This is not neccessarily true regarding a well defined protocol semantics:
the implementor needn't be aware of all implications of his/her choice of
inheritance chains.

> 
> A strict ANSI Smalltalk would be an interesting beast.  With a suitable
> interpretation of file I/O, I think it should be possible to squeeze
> such a system into a 32kB micro-controller.  It could be extremely useful.
> But it wouldn't be Squeak.

Agreed.

> 
> 
> 


Greetings,

Stephan
-- 
Stephan Rudlof (sr at evolgo.de)
   "Genius doesn't work on an assembly line basis.
    You can't simply say, 'Today I will be brilliant.'"
    -- Kirk, "The Ultimate Computer", stardate 4731.3




More information about the Squeak-dev mailing list