Having collections that do not naively implement addAll: falls into that category I think. Just in case it isn't clear by now: It WILL break compatability with custom subclasses though. (which is why I think VW and Squeak will never do it) Personally, I feel the ANSI standard failed in this regard, specifying a behaviour for addAll: that automatically leads to implementing it the naive way. Instead of say, adding all the objects that you are able to add from the collection, then raising an error with the ones you could not Especially when using addAll: with an unordered collection as parameter, it leads to random results as to what is added and what is not before the error is raised... I agree with Ralph on the nil issue (and the implementation details if we do make one ;) ), slowing down 99.99999% of hashable collections to satisfy those few use-cases where there's a need for Sets which accept nil isn't really a super option... Cheers, Henry On Jul 3, 2009, at 11:47 26AM, Stéphane Ducasse wrote:

Our goal is to build an agile Smalltalk with faster, better.... code.

Stef

On Jul 3, 2009, at 8:53 AM, Ralph Boland wrote:

...

Please note the change of topic; adding the ability to add nil to sets won't make sets faster and may well make them slower so has nothing to to with the FasterSets package.

Since I am here allow me to state my opinion on the matter. We should not add the ability to add nil to Sets. While I admit I don't know for sure, I believe the number of instances where we need to add nil to a set is rare. For the rare cases in which it is needed we should create a class SetSupportingNils which has two instance variables: containsNil: a boolean set to true iff the SetSupportingNils instance contains nil.

set: an instance of Set or one of its subclasses and used to store any object added to the SetSupportingNils instance except of course nil.

This means that SetSupportingNils would need to recognize any message that Sets or its subclasses can understand. Any message not understood by SetSupportingNils would be forwarded to its set instance variable. My proposal is not very efficient when adding nil to a set is needed but it requires no modifications to Set or any of its subclasses. That a rarely used class is somewhat inefficient is acceptable.

Issue: I suppose we need a BagSupportingNils class too. Are there any other classes we need? Can they be combined into one class?

Regards,

Ralph Boland

_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

Something that could be considered down the road is restructuring the collection hierarchy to, among other things, allow pluggable hashed storage strategies for hashed collections. This approach should drastically reduce the number of classes in the hashed collection class hierarchy (c.f.: what happens in VW). Stéphane Ducasse wrote:

Thanks ralph. I think that this is not a so good idea to have nil as element.

BTW: just to make sure. Our is not to hijack people from the squeak community (because when I scanned some emails there I thought that we were considered as evil and bad guys - people have a short memory). Our goal is to build an agile Smalltalk with faster, better.... code. And to make sure that people can reinvent the future because they can use cool abstractions.

Stef

On Jul 3, 2009, at 8:53 AM, Ralph Boland wrote:

...

Please note the change of topic; adding the ability to add nil to sets won't make sets faster and may well make them slower so has nothing to to with the FasterSets package.

Since I am here allow me to state my opinion on the matter. We should not add the ability to add nil to Sets. While I admit I don't know for sure, I believe the number of instances where we need to add nil to a set is rare. For the rare cases in which it is needed we should create a class SetSupportingNils which has two instance variables: containsNil: a boolean set to true iff the SetSupportingNils instance contains nil.

set: an instance of Set or one of its subclasses and used to store any object added to the SetSupportingNils instance except of course nil.

This means that SetSupportingNils would need to recognize any message that Sets or its subclasses can understand. Any message not understood by SetSupportingNils would be forwarded to its set instance variable. My proposal is not very efficient when adding nil to a set is needed but it requires no modifications to Set or any of its subclasses. That a rarely used class is somewhat inefficient is acceptable.

Issue: I suppose we need a BagSupportingNils class too. Are there any other classes we need? Can they be combined into one class?

Regards,

Ralph Boland

_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project .

Oh... I meant to see what happens in VW, where there are numerous dictionary and set classes. Moreover, every so often there's the need for e.g.: a hash bucketed set with mutex protection, such as for the symbol table. Since the base classes do not have pluggable strategies, then the special set has to be reimplemented from scratch... Stéphane Ducasse wrote:

andres

...

Something that could be considered down the road is restructuring the collection hierarchy to, among other things, allow pluggable hashed storage strategies for hashed collections. This approach should drastically reduce the number of classes in the hashed collection class hierarchy (c.f.: what happens in VW).

andres do you mean that this is done in VW.

...

...

Thanks ralph. I think that this is not a so good idea to have nil as element.

BTW: just to make sure. Our is not to hijack people from the squeak community (because when I scanned some emails there I thought that we were considered as evil and bad guys - people have a short memory). Our goal is to build an agile Smalltalk with faster, better.... code. And to make sure that people can reinvent the future because they can use cool abstractions.

Stef

On Jul 3, 2009, at 8:53 AM, Ralph Boland wrote:

...

Please note the change of topic; adding the ability to add nil to sets won't make sets faster and may well make them slower so has nothing to to with the FasterSets package.

Since I am here allow me to state my opinion on the matter. We should not add the ability to add nil to Sets. While I admit I don't know for sure, I believe the number of instances where we need to add nil to a set is rare. For the rare cases in which it is needed we should create a class SetSupportingNils which has two instance variables: containsNil: a boolean set to true iff the SetSupportingNils instance contains nil.

set: an instance of Set or one of its subclasses and used to store any object added to the SetSupportingNils instance except of course nil.

This means that SetSupportingNils would need to recognize any message that Sets or its subclasses can understand. Any message not understood by SetSupportingNils would be forwarded to its set instance variable. My proposal is not very efficient when adding nil to a set is needed but it requires no modifications to Set or any of its subclasses. That a rarely used class is somewhat inefficient is acceptable.

Issue: I suppose we need a BagSupportingNils class too. Are there any other classes we need? Can they be combined into one class?

Regards,

Ralph Boland

_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project .

_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

.

On Jul 3, 2009, at 9:53 AM, Reinout Heeck wrote:

I think that Andres' suggestion of using self as sentinel might be hitting a very sweet spot as a tradeoff between special cases and run- time efficiency.

The idea of using 'self' as a special flag sure seems like a special case; and while I have never created a self referential sets... it just seems like someday somebody will get burned badly discovering this implementation (as a matter of debugging their app). As someone still on the learning curve (less than two years of smalltalk scattered over time), I have come to assume that anything storing data with "holes" in it (a/k/a sparse) will fill those holes will nil, and therefore nil is NOT an acceptable element to be stored. That said, let me add that it seems like I have to create a NullDatum (a nil'ish singleton) type object with some frequency. I seem to remember the first axiom from modern Set Theory goes something like this: the empty set (nil) is a set (value)! So, in principle, why not allow nil on the public interface (which could be mapped to some singleton in the implementation)? There would be no speed penalty -- in the most minimal form of always remapping nil in the public interface to NullDatum (or whatever it would be called) would be insignificant. I suppose it could break some existing code... somewhere outside the collection classes. On the other hand, using a specialized subclass is OK too, especially given that I do not have the time to go change the all of the collection classes to make certain they are consistent in allowing nil. -Cam

Heh, I just realized that weak sets won't be able to hold their weak object tombstone either... I think the game can't be won as framed. Reinout Heeck wrote:

On Jul 3, 2009, at 8:53 AM, Ralph Boland wrote:

...

Since I am here allow me to state my opinion on the matter. We should not add the ability to add nil to Sets. While I admit I don't know for sure, I believe the number of instances where we need to add nil to a set is rare.

I am of the opposite opinion (and quite strongly so :-)

When writing code that uses sets I don't want to be bothered with the need to think about special cases (like nil). I agree that the number of instances where it *actually* happens is small but it does force authors to think of it *every* time they write code that adds objects to sets -- particularly hard to keep up when those objects are handed in from yet another module not under their control.

Smalltalk being about abstractions and Pharo being about raising squeak to a 'professional' level I think it is very important to isolate the Pharo programmer from such library implementation idiosyncrasies -- they should be allowed to write abstract (naive if you will) code without fear that it breaks on such special cases.

...

For the rare cases in which it is needed we should create a class SetSupportingNils which has two instance variables: containsNil: a boolean set to true iff the SetSupportingNils instance contains nil.

IMO such a set should be named 'Set' and the one that optimizes for not holding nil should be the one that is given a special name.

As a critique of the proposed implementation: If you put the sentinel in the newly introduced ivar (instead of a boolean) the implementation will be simplified (all nil checks become checks against the sentinel as opposed to introducing 'case statements' in most of its implementation).

I think that Andres' suggestion of using self as sentinel might be hitting a very sweet spot as a tradeoff between special cases and run- time efficiency.

...

Issue: I suppose we need a BagSupportingNils class too.

Yes, and it should be named 'Bag' ;-)

Now there clearly are costs associated with doing this:

Set instantiation requires overwriting nils put there by the VM, this could be mitigated in the future by adding object instantiation protocol that is handed the sentinel. Perhaps in the short run this can be decoupled from the VM by using a plugin -- but I don't know if a plugin is allowed to take over object allocation.

Custom set subclasses will break (but only if they explicitly check for nilled slots) -- but this seems like a mostly fail-fast scenario to me so it requires a code maintenance investment that seems mostly limited to a one-off cost. Anyway, finding all subclasses of Set doesn't seem too hard to me ;-)

In short: Set is cheating and it is doing it poorly, it gets caught when code happens to stuff a very public object called nil in it. It should be taught to cheat better so it doesn't pollute code at other levels of abstraction with special cases.

And yes: this requires an investment...

R -

_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project .