Smalltalk › Squeak › Squeak - Dev

Ideas about sets and dictionaries

_‹ Previous Topic Next Topic _›

Classic

List

Threaded

69 messages Options

1234

Levente Uzonyi-2

Ideas about sets and dictionaries

Hi,

Here are some ideas that I would like to see in the trunk:
- create a common superclass (HashedCollection) for Set and Dictionary
- since #valuesDo: is the same as #do: in dictionaries, we should only
implement one of them. I'd go for implementing #do: and #valuesDo:
would send #do:
- add Andres' changes (or something similar)
http://lists.gforge.inria.fr/pipermail/pharo-project/2009-November/015464.html
which help with weak hash values (#identityHash).
- enable Sets to contain nil by using another object for marking empty slots
- review/add tests
- review/add class/method comments
- since Dictionary >> #keys returns an Array, dictionaries could
implement #keySet which would return a set with the dictionary's keys,
the implementation could be nearly as fast as #keys
- harvest fixes/tweaks from mantis

Some of these would affect other parts of the system, some may not be
useful, so I'm interested about your opinion before I start commiting.

Cheers,
Levente

Russell N Hyer

Re: Ideas about sets and dictionaries

So you're really talking about having two types of null?

nil being the set that contains nothing

and nil & null being the set that contains nothing and an unknown.

How are we meant to do mathematical operations on those two sets ?

and isn't nil the same as the empty set ?

{} ?

2009/11/11, Levente Uzonyi <[hidden email]>:

> Hi,
>
> Here are some ideas that I would like to see in the trunk:
> - create a common superclass (HashedCollection) for Set and Dictionary
> - since #valuesDo: is the same as #do: in dictionaries, we should only
> implement one of them. I'd go for implementing #do: and #valuesDo:
> would send #do:
> - add Andres' changes (or something similar)
> http://lists.gforge.inria.fr/pipermail/pharo-project/2009-November/015464.html
>
> which help with weak hash values (#identityHash).
> - enable Sets to contain nil by using another object for marking empty slots
> - review/add tests
> - review/add class/method comments
> - since Dictionary >> #keys returns an Array, dictionaries could
> implement #keySet which would return a set with the dictionary's keys,
> the implementation could be nearly as fast as #keys
> - harvest fixes/tweaks from mantis
>
> Some of these would affect other parts of the system, some may not be
> useful, so I'm interested about your opinion before I start commiting.
>
> Cheers,
> Levente
>
>
>

Levente Uzonyi-2

Re: Ideas about sets and dictionaries

Hi!

On Wed, 11 Nov 2009, Russell N Hyer wrote:

> So you're really talking about having two types of null?
>
No. I'm talking about letting a set contain nil. Try evaluating Set with:
nil. and you will see what my problem is.

> nil being the set that contains nothing
>
nil is not a set. Set new gives you an empty set.

Cheers,
Levente

Russell N Hyer

Re: Ideas about sets and dictionaries

Sets already contain nil,

Evaluate this, for example:

| badger |

badger := Set new.
badger add: 1.
badger inspect

and you'll see there are already nils!

2009/11/11, Levente Uzonyi <[hidden email]>:

> Hi!
>
> On Wed, 11 Nov 2009, Russell N Hyer wrote:
>
>> So you're really talking about having two types of null?
>>
> No. I'm talking about letting a set contain nil. Try evaluating Set with:
> nil. and you will see what my problem is.
>
>> nil being the set that contains nothing
>>
> nil is not a set. Set new gives you an empty set.
>
> Cheers,
> Levente
>
>

Levente Uzonyi-2

Re: Ideas about sets and dictionaries

Hi!

On Wed, 11 Nov 2009, Russell N Hyer wrote:

> Sets already contain nil,
>
> Evaluate this, for example:
>
> | badger |
>
> badger := Set new.
> badger add: 1.
> badger inspect
>
> and you'll see there are already nils!

Not exactly. Just because you see nils in the inspector it doesn't mean
the set contains it. Try this: Set new add: 1; includes: nil.
Nils in the inspector only mean that empty slots in array are
marked with nil. You may find the class comment of Set helpful.

Cheers,
Levente

Igor Stasenko

Re: Ideas about sets and dictionaries

In reply to this post by Russell N Hyer

2009/11/11 Russell N Hyer <[hidden email]>:

> Sets already contain nil,
>
> Evaluate this, for example:
>
> | badger |
>
> badger := Set new.
> badger add: 1.
> badger inspect
>
> and you'll see there are already nils!
>

No no. This is cheating. Nobody is interested in the ways how object
manages its internal state. The most interesting is
how good its public interface.
The right test to check if set contains nil is to send:

badger includes: nil.

and what Levente proposing is obviously that such test should return
true, if you send

badger add: nil

before.

> 2009/11/11, Levente Uzonyi <[hidden email]>:
>> Hi!
>>
>> On Wed, 11 Nov 2009, Russell N Hyer wrote:
>>
>>> So you're really talking about having two types of null?
>>>
>> No. I'm talking about letting a set contain nil. Try evaluating Set with:
>> nil. and you will see what my problem is.
>>
>>> nil being the set that contains nothing
>>>
>> nil is not a set. Set new gives you an empty set.
>>
>> Cheers,
>> Levente
>>
>>
>
>

--
Best regards,
Igor Stasenko AKA sig.

Igor Stasenko

Re: Ideas about sets and dictionaries

Just want to add that enabling a set to contain nils already discussed before.

http://n4.nabble.com/squeak-dev-Letting-Set-contain-nils-td69437.html#a69437

... and as you may guess, i supporting Levente in this :)

--
Best regards,
Igor Stasenko AKA sig.

Russell N Hyer

Re: Ideas about sets and dictionaries

I still don't comprehend the purpose behind having more than one
flavour of empty in regards to empty set based mathematics.

2009/11/11, Igor Stasenko <[hidden email]>:

> Just want to add that enabling a set to contain nils already discussed
> before.
>
> http://n4.nabble.com/squeak-dev-Letting-Set-contain-nils-td69437.html#a69437
>
> ... and as you may guess, i supporting Levente in this :)
>
> --
> Best regards,
> Igor Stasenko AKA sig.
>
>

Eliot Miranda-2

Re: Ideas about sets and dictionaries

On Wed, Nov 11, 2009 at 3:14 PM, Russell N Hyer <[hidden email]> wrote:

I still don't comprehend the purpose behind having more than one
flavour of empty in regards to empty set based mathematics.

nil is an object like any other, and Sets can contain arbitrary objects.

An empty Set contains no objects. The fact that internally an empty Set has some slots intialized to nil is an implementation detail that in no way implies that it contains nil.

So if sets are capable of including arbitrary objects they should be able to contain nil. There are lots of contexts in which having collections that can include nil is useful. The compiler is one. Storing and reconstituting object graphs is another.

Or in summary nil ~~ #isEmpty.

HTH

Eliot

2009/11/11, Igor Stasenko <[hidden email]>:
> Just want to add that enabling a set to contain nils already discussed
> before.
>
> http://n4.nabble.com/squeak-dev-Letting-Set-contain-nils-td69437.html#a69437
>
> ... and as you may guess, i supporting Levente in this :)
>
> --
> Best regards,
> Igor Stasenko AKA sig.
>
>

Igor Stasenko

Re: Ideas about sets and dictionaries

@Levente..
there is no need to introduce a 'containsNil' flag, nor use other than
nil filler object.
The tally ivar, which is already there can be used to reflect if set
contains nil:

tally >= 0 - set contains tally number of elements without nil
tally == -1 - set contains only single element - nil
tally < -1 - set contains a (tally abs) number of elements including nil

i can implement it, if you want.

The number of changes is quite minimal, and won't make image to die
violently, because:
- currently all sets having tally >=0, so even if you change things
to support nils as i proposing, no existing sets having chances to
behave differently
- currently all sets can't meaningfully include nil, and there is no
code which intentionally puts nil in sets, because it leads to error.

2009/11/12 Eliot Miranda <[hidden email]>:

>
>
> On Wed, Nov 11, 2009 at 3:14 PM, Russell N Hyer
> <[hidden email]> wrote:
>>
>> I still don't comprehend the purpose behind having more than one
>> flavour of empty in regards to empty set based mathematics.
>
> nil is an object like any other, and Sets can contain arbitrary objects.
> An empty Set contains no objects. The fact that internally an empty Set has
> some slots intialized to nil is an implementation detail that in no way
> implies that it contains nil.
> So if sets are capable of including arbitrary objects they should be able to
> contain nil. There are lots of contexts in which having collections that
> can include nil is useful. The compiler is one. Storing and reconstituting
> object graphs is another.
> Or in summary nil ~~ #isEmpty.
> HTH
> Eliot
>>
>> 2009/11/11, Igor Stasenko <[hidden email]>:
>> > Just want to add that enabling a set to contain nils already discussed
>> > before.
>> >
>> >
>> > http://n4.nabble.com/squeak-dev-Letting-Set-contain-nils-td69437.html#a69437
>> >
>> > ... and as you may guess, i supporting Levente in this :)
>> >
>> > --
>> > Best regards,
>> > Igor Stasenko AKA sig.
>> >

--
Best regards,
Igor Stasenko AKA sig.

Eliot Miranda-2

Re: Ideas about sets and dictionaries

On Wed, Nov 11, 2009 at 3:56 PM, Igor Stasenko <[hidden email]> wrote:

@Levente..
there is no need to introduce a 'containsNil' flag, nor use other than
nil filler object.
The tally ivar, which is already there can be used to reflect if set
contains nil:

tally >= 0 - set contains tally number of elements without nil
tally == -1 - set contains only single element - nil
tally < -1 - set contains a (tally abs) number of elements including nil

Neat. It might be even easier to use floating point to indicate nil :)

So if

tally class = SmallInteger

it doesn't include nil, but if

tally class = Float

it does. Once tally has been set to a Double all the loops still work, increasing the tally still works, etc.

i can implement it, if you want.

The number of changes is quite minimal, and won't make image to die
violently, because:
- currently all sets having tally >=0, so even if you change things
to support nils as i proposing, no existing sets having chances to
behave differently
- currently all sets can't meaningfully include nil, and there is no
code which intentionally puts nil in sets, because it leads to error.

2009/11/12 Eliot Miranda <[hidden email]>:

>
>
> On Wed, Nov 11, 2009 at 3:14 PM, Russell N Hyer
> <[hidden email]> wrote:
>>
>> I still don't comprehend the purpose behind having more than one
>> flavour of empty in regards to empty set based mathematics.
>
> nil is an object like any other, and Sets can contain arbitrary objects.
> An empty Set contains no objects. The fact that internally an empty Set has
> some slots intialized to nil is an implementation detail that in no way
> implies that it contains nil.
> So if sets are capable of including arbitrary objects they should be able to
> contain nil. There are lots of contexts in which having collections that
> can include nil is useful. The compiler is one. Storing and reconstituting
> object graphs is another.
> Or in summary nil ~~ #isEmpty.
> HTH
> Eliot
>>
>> 2009/11/11, Igor Stasenko <[hidden email]>:
>> > Just want to add that enabling a set to contain nils already discussed
>> > before.
>> >
>> >
>> > http://n4.nabble.com/squeak-dev-Letting-Set-contain-nils-td69437.html#a69437
>> >
>> > ... and as you may guess, i supporting Levente in this :)
>> >
>> > --
>> > Best regards,
>> > Igor Stasenko AKA sig.
>> >

--

Best regards,
Igor Stasenko AKA sig.

Igor Stasenko

Re: Ideas about sets and dictionaries

2009/11/12 Eliot Miranda <[hidden email]>:

>
>
> On Wed, Nov 11, 2009 at 3:56 PM, Igor Stasenko <[hidden email]> wrote:
>>
>> @Levente..
>> there is no need to introduce a 'containsNil' flag, nor use other than
>> nil filler object.
>> The tally ivar, which is already there can be used to reflect if set
>> contains nil:
>>
>> tally >= 0 - set contains tally number of elements without nil
>> tally == -1 - set contains only single element - nil
>> tally < -1 - set contains a (tally abs) number of elements including nil
>>
>
> Neat. It might be even easier to use floating point to indicate nil :)
> So if
> tally class = SmallInteger
> it doesn't include nil, but if
> tally class = Float
> it does.

Hehe.. just another way. But it having certain risks, i think, because
5.0 is quite same as 5
from arithmetic POV while 5 and -5 are distinct values from all POV,
which can't be mixed unintentionally.

A test if set contains nil, then could be just
tally isInteger ifFalse: [... contains nil ]

(its faster & we don't care about particular class, isn't?)

> Once tally has been set to a Double all the loops still work,
> increasing the tally still works, etc.

Loops do not refer to tally (all iterations using array ivar and its
size), so there no iterations in sets which may require floating point
value, and hence producing a lot of garbage & waste cycles on it.

Tally comes into play only when you adding or removing objects, and
testing if element is included in set.

>From this point i even consider it could be better than using negative
values, if you provide a little more arguments
that there are no any risks :)

>>
>> i can implement it, if you want.
>>
>> The number of changes is quite minimal, and won't make image to die
>> violently, because:
>> - currently all sets having tally >=0, so even if you change things
>> to support nils as i proposing, no existing sets having chances to
>> behave differently
>> - currently all sets can't meaningfully include nil, and there is no
>> code which intentionally puts nil in sets, because it leads to error.
>>
>> 2009/11/12 Eliot Miranda <[hidden email]>:
>> >
>> >
>> > On Wed, Nov 11, 2009 at 3:14 PM, Russell N Hyer
>> > <[hidden email]> wrote:
>> >>
>> >> I still don't comprehend the purpose behind having more than one
>> >> flavour of empty in regards to empty set based mathematics.
>> >
>> > nil is an object like any other, and Sets can contain arbitrary objects.
>> > An empty Set contains no objects. The fact that internally an empty Set
>> > has
>> > some slots intialized to nil is an implementation detail that in no way
>> > implies that it contains nil.
>> > So if sets are capable of including arbitrary objects they should be
>> > able to
>> > contain nil. There are lots of contexts in which having collections
>> > that
>> > can include nil is useful. The compiler is one. Storing and
>> > reconstituting
>> > object graphs is another.
>> > Or in summary nil ~~ #isEmpty.
>> > HTH
>> > Eliot
>> >>
>> >> 2009/11/11, Igor Stasenko <[hidden email]>:
>> >> > Just want to add that enabling a set to contain nils already
>> >> > discussed
>> >> > before.
>> >> >
>> >> >
>> >> >
>> >> > http://n4.nabble.com/squeak-dev-Letting-Set-contain-nils-td69437.html#a69437
>> >> >
>> >> > ... and as you may guess, i supporting Levente in this :)
>> >> >
>> >> > --
>> >> > Best regards,
>> >> > Igor Stasenko AKA sig.
>> >> >
>>
>>
>>
>> --
>> Best regards,
>> Igor Stasenko AKA sig.
>>
>
>
>
>
>

--
Best regards,
Igor Stasenko AKA sig.

Andreas.Raab

Re: Ideas about sets and dictionaries

In reply to this post by Eliot Miranda-2

Eliot Miranda wrote:
> Neat. It might be even easier to use floating point to indicate nil :)
> So if
> tally class = SmallInteger
> it doesn't include nil, but if
> tally class = Float
> it does. Once tally has been set to a Double all the loops still work,
> increasing the tally still works, etc.

Ouch! Can we please step back a little and instead of coming up with
ever more clever hacks think a bit about how we'd solve the problem if
we would address it from first principles? Nothing against cool hacks
but that is getting so obscure that I'd rather not have nil in sets at
all than having to live with the hacks that have been proposed.

Seriously, how *would* you address this problem if you weren't trying to
make it fit exactly?

Cheers,
- Andreas

Randal L. Schwartz

Re: Re: Ideas about sets and dictionaries

>>>>> "Andreas" == Andreas Raab <[hidden email]> writes:

Andreas> Seriously, how *would* you address this problem if you weren't trying to make
Andreas> it fit exactly?

I like the proposal that each set have an additional instance var that gets an
"Object new" stuffed in it to indicate what "nil" does today, for that
*particular* set. That seems relatively cost effective *and* space effective.
Every "isNil" for "this slot is empty" just becomes "== myEmptyVal".

--
Randal L. Schwartz - Stonehenge Consulting Services, Inc. - +1 503 777 0095
<[hidden email]> <URL:http://www.stonehenge.com/merlyn/>
Smalltalk/Perl/Unix consulting, Technical writing, Comedy, etc. etc.
See http://methodsandmessages.vox.com/ for Smalltalk and Seaside discussion

Igor Stasenko

Re: Re: Ideas about sets and dictionaries

In reply to this post by Andreas.Raab

2009/11/12 Andreas Raab <[hidden email]>:

> Eliot Miranda wrote:
>>
>> Neat. It might be even easier to use floating point to indicate nil :)
>> So if
>> tally class = SmallInteger
>> it doesn't include nil, but if
>> tally class = Float
>> it does. Once tally has been set to a Double all the loops still work,
>> increasing the tally still works, etc.
>
> Ouch! Can we please step back a little and instead of coming up with ever
> more clever hacks think a bit about how we'd solve the problem if we would
> address it from first principles? Nothing against cool hacks but that is
> getting so obscure that I'd rather not have nil in sets at all than having
> to live with the hacks that have been proposed.
>
> Seriously, how *would* you address this problem if you weren't trying to
> make it fit exactly?
>

err.. you don't mind, if i remind you that there a lot of ugly hacks
around , like compact classes,
implicit message sends (#class , #==) and nobody saying a word against
them, #ifTrue:ifFalse: inlining
instead of true message send and finally immediate objects -
smallintegers which you can't subclass?!?!

Do you really think that way how to represent the presence of nil in
set worst than the listed above?

In attachment a changeset which allow nils to have sets.. or sets to
have nils.. whatever :)

All tests in CollectionTests are green except one unrelated
(ArrayTest>>testPrinting)

> Cheers,
> - Andreas
>
>

--
Best regards,
Igor Stasenko AKA sig.

Sets-with-nils.1.cs (3K) Download Attachment

Andreas.Raab

Re: Ideas about sets and dictionaries

Igor Stasenko wrote:

>> Seriously, how *would* you address this problem if you weren't trying to
>> make it fit exactly?
>
> err.. you don't mind, if i remind you that there a lot of ugly hacks
> around , like compact classes,
> implicit message sends (#class , #==) and nobody saying a word against
> them, #ifTrue:ifFalse: inlining
> instead of true message send and finally immediate objects -
> smallintegers which you can't subclass?!?!
>
> Do you really think that way how to represent the presence of nil in
> set worst than the listed above?

No, but that's not my point. There are reasons why the hacks you refer
to are there (performance, compactness) but we measure those tradeoffs
against a "canonical" implementation, i.e., one that does not require
these hacks. I'm trying to do the same - I am asking for how a Set with
nil would look like if you'd start it from scratch so that we can
compare and contrast between the proposals.

For example, the tradeoff in Randal's proposal (having a flag) is that
we a) add a variable to all sets (the flag) b) change the implementation
from comparing with nil to comparing with the flag and c) that Sets
cannot contain the flag element itself. That sounds quite reasonable to me.

Cheers,
- Andreas

Igor Stasenko

Re: Re: Ideas about sets and dictionaries

2009/11/12 Andreas Raab <[hidden email]>:

> Igor Stasenko wrote:
>>>
>>> Seriously, how *would* you address this problem if you weren't trying to
>>> make it fit exactly?
>>
>> err.. you don't mind, if i remind you that there a lot of ugly hacks
>> around , like compact classes,
>> implicit message sends (#class , #==) and nobody saying a word against
>> them, #ifTrue:ifFalse: inlining
>> instead of true message send and finally immediate objects -
>> smallintegers which you can't subclass?!?!
>>
>> Do you really think that way how to represent the presence of nil in
>> set worst than the listed above?
>
> No, but that's not my point.

Ok, then, sorry for above :)

> There are reasons why the hacks you refer to
> are there (performance, compactness) but we measure those tradeoffs against
> a "canonical" implementation, i.e., one that does not require these hacks.
> I'm trying to do the same - I am asking for how a Set with nil would look
> like if you'd start it from scratch so that we can compare and contrast
> between the proposals.
>
i think it will look similar unless you introduce a discrimination,
that set could contain
any object except some filler. Be it nil or some other unique object
not really matters, because
the main condition not met:
- pick any existing, or create a new Set

- pick any object in object memory, no matter where it comes from and
try to put it in that Set.
If set is able to handle all such objects without discrimination, it
is good set.. if not - bad.

Does that sounds reasonable?

> For example, the tradeoff in Randal's proposal (having a flag) is that we a)
> add a variable to all sets (the flag) b) change the implementation from
> comparing with nil to comparing with the flag and c) that Sets cannot
> contain the flag element itself. That sounds quite reasonable to me.
>
> Cheers,
> - Andreas
>
>
>

--
Best regards,
Igor Stasenko AKA sig.

Igor Stasenko

Re: Re: Ideas about sets and dictionaries

In reply to this post by Randal L. Schwartz

2009/11/12 Randal L. Schwartz <[hidden email]>:

>>>>>> "Andreas" == Andreas Raab <[hidden email]> writes:
>
> Andreas> Seriously, how *would* you address this problem if you weren't trying to make
> Andreas> it fit exactly?
>
> I like the proposal that each set have an additional instance var that gets an
> "Object new" stuffed in it to indicate what "nil" does today, for that
> *particular* set. That seems relatively cost effective *and* space effective.
> Every "isNil" for "this slot is empty" just becomes "== myEmptyVal".
>

Sorry, didn't commented earlier.
Such proposal make little difference comparing to currently existing
implementation,
and i'd prefer to not having it, and leave things as they are, given
an additional costs which it implies.

The main purpose to be able to handle nils in sets as an elements is to make Set
be able to hold _any_ potentially existing objects in image.

But your solution could be described as:
a) we having a basket full of differently colored balls.
b) while counting balls in basket lets count all balls, except
transparent ones.
..and your idea:
rewrite b: while counting balls in basket lets count all balls,
except red ones.

> --
> Randal L. Schwartz - Stonehenge Consulting Services, Inc. - +1 503 777 0095
> <[hidden email]> <URL:http://www.stonehenge.com/merlyn/>
> Smalltalk/Perl/Unix consulting, Technical writing, Comedy, etc. etc.
> See http://methodsandmessages.vox.com/ for Smalltalk and Seaside discussion
>
>

--
Best regards,
Igor Stasenko AKA sig.

Randal L. Schwartz

Re: Re: Ideas about sets and dictionaries

>>>>> "Igor" == Igor Stasenko <[hidden email]> writes:

Igor> But your solution could be described as:
Igor> a) we having a basket full of differently colored balls.
Igor> b) while counting balls in basket lets count all balls, except
Igor> transparent ones.
Igor> ..and your idea:
Igor> rewrite b: while counting balls in basket lets count all balls,
Igor> except red ones.

No, it *does* solve the problem, because "red" is very very very local
to this set.

The only problem would be if you have a set add itself's instance vars. And
that would be problematic for other issues.

But it would always be able to represent *every* other set in the image.

--
Randal L. Schwartz - Stonehenge Consulting Services, Inc. - +1 503 777 0095
<[hidden email]> <URL:http://www.stonehenge.com/merlyn/>
Smalltalk/Perl/Unix consulting, Technical writing, Comedy, etc. etc.
See http://methodsandmessages.vox.com/ for Smalltalk and Seaside discussion

Igor Stasenko

Fwd: Re: Ideas about sets and dictionaries

2009/11/12 Randal L. Schwartz <[hidden email]>:

>>>>>> "Igor" == Igor Stasenko <[hidden email]> writes:
>
> Igor> But your solution could be described as:
> Igor> a) we having a basket full of differently colored balls.
> Igor> b) while counting balls in basket lets count all balls, except
> Igor> transparent ones.
> Igor> ..and your idea:
> Igor> rewrite b: while counting balls in basket lets count all balls,
> Igor> except red ones.
>
> No, it *does* solve the problem, because "red" is very very very local
> to this set.
>

It is, and inspector will show us this very very very local object , and
#instVarAt: as well as #someInstance and #allInstances and many others
(debugger, OODBs etc).
Then at some point it could become not so very very very local, and
then you will meet the same problem
as we currently having with inability to have a nils in Set.

> The only problem would be if you have a set add itself's instance vars. And
> that would be problematic for other issues.
>
> But it would always be able to represent *every* other set in the image.
>

indeed, that's why i don't like it and treat it similar to current
implementation without strong reasons why we would
want to employ it.

A simple illustration:

set := Set new.
Object allInstancesDo: [:obj | set add: obj ] "using 'Object new'
as filler, right?"

we could argue very long why one would want to do that, but the fact
is clear: your proposal have nothing
to offer to developer how to get around that.

--
Best regards,
Igor Stasenko AKA sig.

1234