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 rpboland@gmail.com:
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.
+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
On Mon, Jul 20, 2009 at 6:07 PM, Igor Stasenko siguctua@gmail.com 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... :)
2009/7/21 David Goehrig dave@nexttolast.com:
On Mon, Jul 20, 2009 at 6:07 PM, Igor Stasenko siguctua@gmail.com 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/
2009/7/21 Igor Stasenko siguctua@gmail.com:
2009/7/21 David Goehrig dave@nexttolast.com:
On Mon, Jul 20, 2009 at 6:07 PM, Igor Stasenko siguctua@gmail.com 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.
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.
Igor Stasenko wrote:
2009/7/21 Igor Stasenko siguctua@gmail.com:
2009/7/21 David Goehrig dave@nexttolast.com:
On Mon, Jul 20, 2009 at 6:07 PM, Igor Stasenko siguctua@gmail.com 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.
Maybe Bruce Badger can do it better than me, convincing why standarts is important :)
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.squeakfoun...
/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 bonzini@gnu.org:
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.
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 nicolas.cellier.aka.nice@gmail.com:
2009/7/28 Paolo Bonzini bonzini@gnu.org:
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.
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
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
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:Lou@Keystone-Software.com 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 schwa@fastmail.us:
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)
oops, i meant intersection.
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
squeak-dev@lists.squeakfoundation.org
-
David Goehrig -
Igor Stasenko -
Joshua Gargus -
Keith Hodges -
Klaus D. Witzel -
Louis LaBrunda -
Nicolas Cellier -
Paolo Bonzini -
Ralph Boland