[squeak-dev] intersection: method for dictionaries flaky

When I run the following code:

        | a b ans |
        ans := Array new: 2.
        a := Dictionary new.
        b := Dictionary new.
        a at: 1 put:  $a;  at: 2 put: $b;  at:  $3 put:  $c.
        b at: 1 put:  $a;  at: 2 put: $x;  at:  $3 put:  $b.
        self halt.
        ans at: 1 put: (a intersection: b).
        ans at: 2 put: (b intersection: a).
        ans
       
I get output:

         an Array(a Dictionary(1->$a 2->$b ) a Dictionary($3->$b 1->$a ))


In other words, the "intersection:"  method is not symmetric for Dictionaries.
As a mathematician I find this very disturbing.
I propose that the intersection of two Dictionaries should either
    a)  Return the intersection of the keys of the Dictionaries.
         Not an intuitive answer either but better than now.
         For example, what would you expect the intersection of two
MethodDictionaries
         to be?

    b)  Generate the shouldNotImplement error.


    My preference is for  b)  as it is straightforward to get answer  a)  or the
    current answer if that is what you want.  We could even make methods
    for these,  say  "intersectionKeys:"   and
                             "intersectionValues:"   (values are from receiver)


 I am asking because I am currently implementing  the  "intersection:"  method
 for sets as an optimization and unfortunately my code applies to
 dictionaries as well.  (And I change the result for dictionaries).
 Yet another example of why Dictionary should NOT be a subclass of Set.

Now the  tough question:   Does, and if so where, Squeak and the many
Squeak packages depend upon the current behavior of  "intersection:"   with
respect to dictionaries?
Perhaps  Dictionary should implement  "intersection:" and have it invoke
"intersectionValues".  The Dictionary "intersection:" method could
then be marked
as deprecated.
How ofter does a method become deprecated at its time of creation? :-)

Ralph Boland

2009/7/20 Ralph Boland <[hidden email]>: +1

> I propose that the intersection of two Dictionaries should either
>    a)  Return the intersection of the keys of the Dictionaries.
>         Not an intuitive answer either but better than now.
>         For example, what would you expect the intersection of two
> MethodDictionaries
>         to be?
>
>    b)  Generate the shouldNotImplement error.
>

c) make Dictionary be not the subclass of Set, then questions, like
wrong #intersection: symmetry will auto-become a non-issue. :)

>
>    My preference is for  b)  as it is straightforward to get answer  a)  or the
>    current answer if that is what you want.  We could even make methods
>    for these,  say  "intersectionKeys:"   and
>                             "intersectionValues:"   (values are from receiver)
>
good idea, to ask from user explicitly, what he has in mind!

>
>  I am asking because I am currently implementing  the  "intersection:"  method
>  for sets as an optimization and unfortunately my code applies to
>  dictionaries as well.  (And I change the result for dictionaries).
>  Yet another example of why Dictionary should NOT be a subclass of Set.
>
> Now the  tough question:   Does, and if so where, Squeak and the many
> Squeak packages depend upon the current behavior of  "intersection:"   with
> respect to dictionaries?

We discussed this topic a while ago on squeak-dev (and i was one, who
raised the same questions which you raising now).
True: in current state, using #intersection: on dictionaries having
not much sense , because it is unclear what behavior we should
imply/expect from it (symmetry , intersections on values, or keys
etc).

> Perhaps  Dictionary should implement  "intersection:" and have it invoke
> "intersectionValues".  The Dictionary "intersection:" method could
> then be marked
> as deprecated.
> How ofter does a method become deprecated at its time of creation? :-)
>
The problem with Dictionaries, is that they are part of ANSI standard
(as other Collections), so, i think we should preserve the protocol in
order to stay compatible with other forks/dialects.
So, removing or deprecating methods in Dictionaries is not so easy
task and requires good consideration , does that change/removal makes
us incompatible with others or not.

> Ralph Boland
>
>



--
Best regards,
Igor Stasenko AKA sig.

--
-=-=-=-=-=-=-=-=-=-=- http://blog.dloh.org/

2009/7/21 David Goehrig <[hidden email]>:
>
>
> On Mon, Jul 20, 2009 at 6:07 PM, Igor Stasenko <[hidden email]> wrote:
>>
>> The problem with Dictionaries, is that they are part of ANSI standard
>
> Truer words have never been spoken...
> Seriously, there's no better way to kill a language than to make it an ANSI standard... :)

Standartisation is a kind of contract between all interested parties
in what they like to see or need from particular artifact.
Its enabling us to build more advanced techs,  which depends on
standardized artifact, without the fear that some parts of it will
behave unpredictably and therefore could put the whole end product in
danger.

If ANSI standard was made for other purpose than that, then we should
abandon it altogether.


> --
> -=-=-=-=-=-=-=-=-=-=- http://blog.dloh.org/
>

--
Best regards,
Igor Stasenko AKA sig.

2009/7/21 Igor Stasenko <[hidden email]>:
Maybe Bruce Badger can do it better than me, convincing why standarts
is important :)

http://www.youtube.com/watch?v=Z9qBKlkUqCE&feature=related

>
>> --
>> -=-=-=-=-=-=-=-=-=-=- http://blog.dloh.org/
>>
>
> --
> Best regards,
> Igor Stasenko AKA sig.
>



--
Best regards,
Igor Stasenko AKA sig.

Igor Stasenko wrote: Well wouldn't you know, a vision with a process driven by philosophical
values... I wonder if it will catch on?
 
Keith

Folks,

IIRC #intersection: and/or #difference: pop up in squeak-dev every now and  
then.

I suggest to also have a look @ what was discussed resp. done so far, just  
to be sure:

http://www.google.com/search?q=intersection+difference+site:lists.squeakfoundation.org

/Klaus

>> I propose that the intersection of two Dictionaries should either
>>     a)  Return the intersection of the keys of the Dictionaries.
>>          Not an intuitive answer either but better than now.
>>          For example, what would you expect the intersection of two
>> MethodDictionaries
>>          to be?

I second this.  It is extremely unlikely that someone is using to
intersect values, since the unique values of a Dictionary (the
"Set"-like values) are actually the keys.

>>     b)  Generate the shouldNotImplement error.
>>
>
> c) make Dictionary be not the subclass of Set, then questions, like
> wrong #intersection: symmetry will auto-become a non-issue. :)

Paolo

2009/7/28 Paolo Bonzini <[hidden email]>:
I would rather tend to explicitly type (a keys intersection: b keys).

>>>    b)  Generate the shouldNotImplement error.
>>>
>>
>> c) make Dictionary be not the subclass of Set, then questions, like
>> wrong #intersection: symmetry will auto-become a non-issue. :)
>
> Paolo
>
>

I already implemented c) once for fun.
See the thread starting at
http://lists.squeakfoundation.org/pipermail/squeak-dev/2007-June/117840.html
... and my arguments for moving Dictionary and Set under a common
HashedCollection
http://lists.squeakfoundation.org/pipermail/squeak-dev/2007-June/117894.html

Nicolas

> I already implemented c) once for fun.
> See the thread starting at
> http://lists.squeakfoundation.org/pipermail/squeak-dev/2007-June/117840.html
> ... and my arguments for moving Dictionary and Set under a common
> HashedCollection
> http://lists.squeakfoundation.org/pipermail/squeak-dev/2007-June/117894.html

Well, that changes things.  I thought it would break a lot to change the
superclass of Dictionary. :-( GNU Smalltalk also uses HashedCollection
for the record.

Paolo

2009/7/28 Nicolas Cellier <[hidden email]>: right. i remember that topic :)
The summary of it is below:

--------------
Blake, I can understand your argument, Smalltalk cannot serve every
different logics. Though they can eventually coexist with subclasses
sometimes. Choices have to be made. Lots of ambiguity come from our
language: different guys have differnt understandings (even math
language is ambiguous and strongly contextual, and that's part of its
power for sure).

But common, no math means no geometry, no windows, no menu, no Smalltalk
math/algebra is everywhere/behind/inside Smalltalk.

And enforcing the well-behaved / least surprising / strongly logical
kernel with good mathematical background cannot be a bad thing.

I feel that's what's in the mind of sig.

Beside, most Smalltalk have Associations compared only on key. So this
pecularity of Squeak can be argued and should have been argued. Maybe
it's a very arbitrary choice designed for a very particular application
without deeper thought of all implications and without consensus. Maybe
it's a very good choice superior to other Smalltalk...
I can't say if sig point of view is right or wrong. But i can say he is
right to open the question.

The fact that Dictionary are subclasses of Set means there are a kind of
  Set. So its element should be unique, so Association should compare
only on key. But in this case, Dictionary with equal keys and different
values should be equal, something we all find... Hmm surprising...

So, making Association comparing on values seems to be a remedy to this
surprise. But in this case, Dictionary don't behave like Set anymore...
So the logic would be to detach them from Set hierarchy. Only the list
of keys is a set...

Maybe we kept it there for saving a few methods duplication? But when it
is necessary to define more methods to contradict super behaviour than
methods we inherit, maybe it's time for a move in hierarchy. Leave your
super and be adopted by a new family.

Nicolas
--------------

so, if Dictionary is a subclass of Set, then , as any Set it should
conform with Set rules, i.e.:

(setA difference: setB) = (setB difference: setA)
and
(setA union: setB) = (setB union:setA)

where setA, setB could be any (sub)instance of Set.

And if its not (as in fact Dictionary behaves), then it should not
belong to Set hierarchy.


> HashedCollection
> http://lists.squeakfoundation.org/pipermail/squeak-dev/2007-June/117894.html
>
> Nicolas
>


--
Best regards,
Igor Stasenko AKA sig.

In VA Smalltalk (former IBM Visual Age Smalltalk) Dictionary is a subclass
of KeyedCollection which is a subclass of Collection and Set is a subclass
of Collection.  I don't mean to imply that VA Smalltalk has the right
answer to this question but it does show the choice others have made.

Lou
-----------------------------------------------------------
Louis LaBrunda
Keystone Software Corp.
SkypeMe callto://PhotonDemon
mailto:[hidden email] http://www.Keystone-Software.com

Igor Stasenko wrote:

so, if Dictionary is a subclass of Set, then , as any Set it should

conform with Set rules, i.e.:

(setA difference: setB) = (setB difference: setA)
  

Forgive a small nitpick that doesn't affect your argument:  set difference is not symmetric, neither in set theory nor in the implementation in Collection.

#(1 2 3 4 5) difference: #(4 5 6 7 8)
gives #(1 2 3)

and #(4 5 6 7 8) difference: #(1 2 3 4 5)
gives #(6 7 8)

Cheers,
Josh

and
(setA union: setB) = (setB union:setA)

where setA, setB could be any (sub)instance of Set.

And if its not (as in fact Dictionary behaves), then it should not
belong to Set hierarchy.


  

HashedCollection
http://lists.squeakfoundation.org/pipermail/squeak-dev/2007-June/117894.html

Nicolas

    

2009/7/28 Joshua Gargus <[hidden email]>:
oops, i meant intersection.



--
Best regards,
Igor Stasenko AKA sig.