Support of algebraic operations on sets

On Jun 15, 2007, at 19:33 , Bert Freudenberg wrote:
Could we agree that in a union, each element will only be there  
exactly once? This is why the 3.8 implementation of #union: on  
Dictionary is buggy:

| a b |
a := {$a->1. $b->2} as: Dictionary.
b := {$c->1. $d->2} as: Dictionary.
(a union: b) count: [:x | x = a anyOne]
"= 2"




- Bert -

On Fri, 15 Jun 2007 10:23:56 -0700, sig <[hidden email]> wrote:

>> > Or remove them from second book.
>>
>> new do: [:k | book2 removeKey: k].
>>
> instead of:
>   book2 difference: (book1 intersection: book2)
>
> can't you see the difference?

Hmmm. In algebra:

2+2*4 = 10

In Smalltalk:

2+2*4 = 16

Not to belabor the point, but Smalltalk isn't math or algebra. It does  
have its own internal consistency ("purity", some might say), though, and  
it's not reasonable to expect to conform to those of another discipline.  
To my mind Smalltalk is more like, well, talking than math. Which is why  
the above equation makes sense to me: ("Add two and two  
together...multiply by four...."). Messages above all, right?

Smalltalk's vocabulary has value because it is well defined and has been  
well defined for a long time. It's not hard to create a new class that  
does what you expect; are you suggesting that decades of code and  
documentation be broken because this interpretation of "difference"--which  
is exactly what I would expect if someone said, "tell me the difference  
between this dictionary and that one"--is somehow offensive to you on  
mathematical grounds?

Blake a écrit :
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

Fair point, and I apologize if I sounded snarky.

I tend to view these things from a language standpoint. If it makes sense  
the way I would read it, I think that's a good thing.

Interesting discussion.
Do not forget to write some little tests illustrating the new methods/
behavior if you want to get it harvested :)
It will help everybody at the end.
Stef

nicolas cellier a écrit :
Well inquiring a bit more on Set-Dictionary inheritance:

"methods in set not overriden in Dictionary"
(Set selectors difference: Dictionary selectors) size. "21"

"methods in set overriden in Dictionary"
(Set selectors intersection: Dictionary selectors) size. "15"

At first glance, Dictionary inherit more than it overrides.
To be fair, i should also include the count of overrides calling
super... that's only one, #do:

But let's look more in detail inherited stuff:

an IdentitySet(#doWithIndex: #like: #size #fullCheck #someElement
#comeFullyUpOnReload: #array #findElementOrNil: #swap:with: #atRandom:
#capacity #union: #growSize #add:withOccurrences: #copyWithout:
#withArray: #grow #initialize: #atNewIndex:put: #asSet #fixCollisionsFrom:)

Dictionary new asSet answers a Dictionary... arguable sig said it's not
a set of values, nor a set of associations (because Association values
are compared!). Only a set of keys, but that's a very poor view of
Dictionary... Bert suggested ^self values asSet

Dictionary union: is surprising as debatted in this thread because non
commutative... But well, maybe it is usefull as it is...

Dictionary doWithIndex: do not use keys as index... implementing this
message taylored for SequenceableCollection is arguable anyway (used by
atRandom:, anywhere else?).

Dictionary like: works only on keys... arguable (Bert would prefer
values i guess)

Dictionary copyWithout: will call a shouldNotImplement remove:ifAbsent:
and fail. not a valuable inheritance...

What is common and not arguable is the behavior of HashedCollection
( #size #fullCheck #someElement #comeFullyUpOnReload:
#findElementOrNil: #swap:with: #atRandom: #capacity #growSize
#withArray: #grow #initialize: #atNewIndex:put: #fixCollisionsFrom:)

Also, the class side messages are mostly HashedCollection:

"methods in set not overriden in Dictionary"
(Set class selectors difference: Dictionary class selectors) size. "5"

"methods in set overriden in Dictionary"
(Set class selectors intersection: Dictionary class selectors) size. "1"


So creating a HashedCollection above both Set and Dictionary would be an
interesting alternative.
Add the #union: message to it.
And another inherited from uniqueness of keys: #add:withOccurrences:

Well, maybe that does not add a lot of value, what difference between a
HashedCollection of unique elements and a Set? But semantically, it
disjoint Dictionary from Set, and that is consistent with Association
behavior. Since Dictionary are no more Set, no use to
have union: commutative.

Nicolas

On 16/06/07, nicolas cellier <[hidden email]> wrote:
AFAIK a pure algebra defines binary operators, but not their priority
in expressions. I'd call it a rules/conventions for writing ariphmetic
expressions rather than algebraic rules. This is the point where we
free to define own rules and still be conform with algebra.

I'd like to see useful code which uses #difference: for dictionaries
with current semantics. I'd also would like to see this code be
portable on different smalltalk dialects and still be functional.. :)

Exactly. I don't want to explain a newcomer about Set which behaves as
not set, because "it's implemented using language specific
standards/rules". Then there's no reasons to call it a set. I think
the choice to call a set 'Set' was to make it conforming with algebra
and implementing   #union:, #intersection:, #difference: too.
Otherwise if we step further onto road of defining own standards then
why caring of defining a '+' method for numbers to return sum of two
arguments? Maybe for someone's viewpoint its better to use '*'
character for this operation? :)

>
> 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.

As i said before, if Association uses both key and value in
comparison, then this class have no value at all and degenerates into
array of two elements.
And dictionary degenerates to something in the middle between Set and
OrderedCollection.
Dictionary is a subclass of Set, it must be more specific, while still
behave as set. But to what we see, it magically becomes less specific
by violating rules defined in parent class(es).

>
> 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...

I see nothing surprising in this. If we considering Association as
implication (a then b), then value doesn't involved in comparison and
two implications considered equivalent if and only if their key values
are equivalent.
>From my point of view a Dictionary is a Set, which additionally having
associated value(s) for each set element. And from this point it
cannot violate the set rules.

>
> 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...

No, i would like to keep a Dictionary be subclass of Set. And for
those who don't like its behaviour - implement HashedCollection or
something like that, which elements are indexed by keys, but behaving
as regular objects in comparison.

On 15/06/07, Bert Freudenberg <[hidden email]> wrote:
Hmm.. what of my statements has lead you to this conclusion? On the
contrary, I tried to show you that current behavior of Dictionary in
squeak is something like you describing and that's what i don't like.


> - Bert -
>
>
>
>

On Jun 16, 2007, at 9:10 , nicolas cellier wrote:
> So creating a HashedCollection above both Set and Dictionary would  
> be an
> interesting alternative.

Possibly, yes. The main reason for Dictionary to inherit from Set is  
to reuse the hashing.

The current inconsistencies come from Dictionary being a subclass of  
Set, but not behaving as a proper Set. One manifestation of that is  
#union: which relies on #asSet actually answering a collection with  
Set semantics.

Not having Dictionary be a Set subclass seems a lot cleaner to me  
than trying to patch it up with more overrides.

- Bert -

On 16/06/07, Bert Freudenberg <[hidden email]> wrote:
A Set overrides a #union:, which is not using #asSet for this
operation anymore.

>
> Not having Dictionary be a Set subclass seems a lot cleaner to me
> than trying to patch it up with more overrides.
>
Honestly i can't see what must be overriden in Dictionary to make it
consistent with Set.
It's all about Association, which makes Dictionary to not comform with
sets semantics.
Maybe it's because i considering a Dictionary as set of keys with
associated values instead of collection of arbitrary elements, where
each one of them having unique key.

> - Bert -
>
>
>
>

On Jun 16, 2007, at 11:25 , sig wrote:

I'm sorry, but apparently you don't get it. Compare #union: in  
Collection and Set. Set *has* to override this because Collection  
uses #asSet which is a no-op in Set. So instead of #asSet it uses  
#copy. The intent of #asSet in #union: is to get a variable-sized  
Collection with unique elements. Dictionary's behavior in response to  
#asSet violates that assumption.

>> Not having Dictionary be a Set subclass seems a lot cleaner to me
>> than trying to patch it up with more overrides.
>>
> Honestly i can't see what must be overriden in Dictionary to make it
> consistent with Set.
> It's all about Association, which makes Dictionary to not comform with
> sets semantics.

No, it's because Dictionary is a Collection. Indices or keys in a  
Collection are secondary. Look at the protocols in Collection - it  
does neither define nor use #at:.

> Maybe it's because i considering a Dictionary as set of keys with
> associated values instead of collection of arbitrary elements, where
> each one of them having unique key.

This is not unreasonable, but it is *not* what Dictionaries in  
Smalltalk are. You want, in your own words, a "set of keys with  
associated values". So use it instead of a Dictionary! Have a Set of  
LookupKeys then. Or even better, rather than in these oversimplified  
examples, reify your concept - for language translation have a  
TranslationEntry class that implements #= and #hash based on the  
original word and use a Set to store them.

Let me put it this way: The main property of Sets is that its  
elements are unique. The invariant would be

        aSet allSatisfy: [:element | (aSet occurrencesOf: element) = 1]

This indeed holds for each Set, but not for Dictionaries - you can  
have the same value multiple times.

So please, to get this discussion to a fruitful end, let's fix  
Dictionaries, but not redefine their semantics to suit your specific  
needs. Maybe using Nicholas' suggestion (which I find cleaner but has  
potentially more severe consequences) or by patching up Dictionary,  
in this case by overriding #asSet.

- Bert -

On Jun 16, 2007, at 10:37 , sig wrote:

> I'd like to see useful code which uses #difference: for dictionaries
> with current semantics.

I'd like #difference: to have the same semantics for every  
Collection. Including, of course, Sets and Dictionaries.

> I don't want to explain a newcomer about Set which behaves as
> not set, because "it's implemented using language specific
> standards/rules". Then there's no reasons to call it a set. I think
> the choice to call a set 'Set' was to make it conforming with algebra
> and implementing   #union:, #intersection:, #difference: too.

Completely agreed.

> As i said before, if Association uses both key and value in
> comparison, then this class have no value at all and degenerates into
> array of two elements.

I'm not sure why this was changed, but one could argue either way.  
Anyhow, this is secondary to the Collection discussion, as it is an  
implementation detail of Dictionaries.

> And dictionary degenerates to something in the middle between Set and
> OrderedCollection.
> Dictionary is a subclass of Set, it must be more specific, while still
> behave as set. But to what we see, it magically becomes less specific
> by violating rules defined in parent class(es).

That is exactly the point. That's why it should not be a subclass of  
Set, as Nic already suggested.

> No, i would like to keep a Dictionary be subclass of Set.

I'm trying hard to understand you. Do you suggest that a Dictionary  
method like #includes: operates on the keys while #do: operates on  
the values? Isn't that ridiculous? Or should all collection  
operations work on the keys to be like a Set? How would you access  
the values then? In any case, this would be a completely new concept  
and should not be called Dictionary.

- Bert -

On 16/06/07, Bert Freudenberg <[hidden email]> wrote: Yes, and that's why its abstract. To define generic operations on
different collection types, which introducing own indexing/ordering
schemes later.

Another example of breaking protocol rules. Do you see any practical
and good use in overriding #do: in Dictionary to iterate through list
of values instead of associations by default? I don't. I'm serious.

I'm agree that Dictionary must behave as Collection at first place and
only then as Set. But it isn't:
TestClass >> isAdded: value to: collection
   collection add: value.
   ^ collection includes: value.
--
self isAdded: (a -> b) to: Dictionary new.    --- returns false

Does it behaves correctly in this example?

> So please, to get this discussion to a fruitful end, let's fix
> Dictionaries, but not redefine their semantics to suit your specific
> needs. Maybe using Nicholas' suggestion (which I find cleaner but has
> potentially more severe consequences) or by patching up Dictionary,
> in this case by overriding #asSet.

I understand your position. If you consider Dictionary as collection,
lets fix it conform to Collection first. :)

>
> - Bert -
>
>

On 16/06/07, Bert Freudenberg <[hidden email]> wrote:
Yes, but if it still is, then it must follow the rules.

>
> > No, i would like to keep a Dictionary be subclass of Set.
>
> I'm trying hard to understand you. Do you suggest that a Dictionary
> method like #includes: operates on the keys while #do: operates on
> the values? Isn't that ridiculous?

Its obvious:  both #includes: and #do: must operate on associations.
Because from viewpoint of Collection, element of Dictionary must be an
association, not key or value.

Sig,

I'm still trying to follow this conversation, is your argument simply that
#= should be implemented in dictionary only comparing keys and not values,
so that

(Dictionary at: #a put: 1) = (Dictionary at: #a put: 2)

Which means that

 | dict1 dict2 result1 result2 |
 dict1 := Dictionary new.
 dict2 := Dictionary new.
 dict1 at: 1 put: 5.
 dict2 at: 1 put: 6.
 
 result1 := dict1 union: dict2.
 result2 := dict2 union: dict1.

result1 = #(1->6) = result2 = #(1->5)

and

 result1 includes: #(1->5) = true

 because
        #(1->6) = #(1->5)?

Ron Teitelbaum

> sig wrote:
> To what i propose is to be the following:
>
> SigAssociation methodsFor: 'comparision'
> = argv
>      ^ key = argv key
>
>

On Jun 16, 2007, at 13:53 , sig wrote:

> Another example of breaking protocol rules. Do you see any practical
> and good use in overriding #do: in Dictionary to iterate through list
> of values instead of associations by default? I don't. I'm serious.

Again - if that is really what you want, use a Set of Associations then.

Besides, your proposed change of Dictionary semantics would break a  
lot of code. I just tested this - even just accepting a method  
invokes Dictionary>>do:. You can't possibly be seriously suggesting  
that.

> I'm agree that Dictionary must behave as Collection at first place and
> only then as Set. But it isn't:
> TestClass >> isAdded: value to: collection
>   collection add: value.
>   ^ collection includes: value.
> --
> self isAdded: (a -> b) to: Dictionary new.    --- returns false
>
> Does it behaves correctly in this example?

No, because Dictionary wrongly inherits #add: from Set. E.g., #add:  
and #remove: surely should be symmetric, but see Dictionary>>remove:  
which is forbidden. #add: on a dictionary would only make sense if a  
default key was provided - like, in an OrderedCollection a new  
"default" index is added, too. To add something to a Dictionary use  
#at:put:. You need to provide a key. Having an #addAssociation: would  
be consistent with #associationAt: etc.

We both seem to agree Dictionary is inconsistent, it's a rather  
pragmatic hack instead of a clean design. I don't really see a need  
to completely revamp it, but if we do so, I'd strongly advocate  
compatibility with current usage.  Not inheriting from Set anymore at  
least would spare us discussions like this in the future. It *is*  
confusing to newcomers, so much is sure.

>> So please, to get this discussion to a fruitful end, let's fix
>> Dictionaries, but not redefine their semantics to suit your specific
>> needs. Maybe using Nicholas' suggestion (which I find cleaner but has
>> potentially more severe consequences) or by patching up Dictionary,
>> in this case by overriding #asSet.
>
> I understand your position. If you consider Dictionary as collection,
> lets fix it conform to Collection first. :)

Agreed.

Anyway, I think I've made my position clear. Lets hear what others  
think.

- Bert -

On 16/06/07, Ron Teitelbaum <[hidden email]> wrote: I think you meant:
 #( a->b ) to be just (a->b) everywhere, because #(1->5) is the array
with 3 elements in my squeak.. not association.


>  because
>         #(1->6) = #(1->5)?
>

And then yes. As you can see, then everything is at right places.

It wasn't meant to be evaluated.  I was trying to convey conceptually a
collection of associations.  Still your point is well taken.

>
>
> >  because
> >         #(1->6) = #(1->5)?
> >
>
> And then yes. As you can see, then everything is at right places.
>

Ok I see and this is where Bert's point about #do: comes in.  Since #do:
iterates over values and not keys your suggested include doesn't work.  Your
suggestion is that #do iterate over associations is so that #= can compare
keys and forget about values.

The #= message on dictionary is not a major concern for me.  Although

Dictionary new at: #a put #b; yourself = Dictionary new at: #a put: #c;
yourself   seems odd to me, even if I do see the use in set operations.  The
set operational consistency also does not seem very useful either.
Certainly no more useful then the current implementation of #= on
Dictionary.  I would suggest that we do not change #= for the sake of set
operational consistency and would agree with Bert that Dictionaries are not
sets.

Changing #do: is a major concern for me.  There is a huge amount of value to
iteration over values and therefore we can predict a lot of people have used
it in their code.  This form of iteration makes Dictionary consistent with
Collection.  Again it is not consistent with Set operations but I don't see
the value of set operations on dictionaries since only the keys are sets.  I
don't see these relationships of keys to sets translating into dictionaries
are sets.  We expect to find only one entry per index on a dictionary, but
this is true of collections too.

Changing Dictionary must be done extremely carefully, I would vote against
changing it to support set operations.

(I still like my suggestion of collection of values resulting from set
operations but that's me).

I don't see that this precludes you from doing what you need to do.  If we
change the superclass of Dictionary to be Collection or HashedCollection as
was suggested then you could then add your set methods implemented the way
you want them.  Maybe something like #asSetSymetricDifference: or
#asSetIncludes:  With a nice comment that says something like "The
comparisons for equality in set operations only consider keys so that the
resulting set matches algebraic rules.  For example #asSetUnion: results are
commutative using #asSetEquals.  Set operations can result in unexpected
differences in the values of your resulting dictionary since only keys are
used for set operations.  Set operations may throw out your values.  For
example ..."

Come to think of it we could just implement the set operations as
#shouldNotImplement and we can replace that functionality with the methods
above.

Dictionaries are widely used in Smalltalk, too much so in my opinion (I'm as
guilty as anyone).  In many cases modeling your dictionary into proper
objects eliminates a shortcut but provides greater clarity to your model.

Happy coding!

Ron Teitelbaum

On Sat, 16 Jun 2007 06:45:35 -0700, Bert Freudenberg  
<[hidden email]> wrote:

> Anyway, I think I've made my position clear. Lets hear what others think.

I haven't checked it out but if Dictionary inherits from Set to exploit  
the hashing code, couldn't traits fix that?

When damien started to use traits to write Nile (which is really cool  
- please have a look and give feedback)
we talked also about the collection hierarchy which would be a really  
nice candidate for traits.

I think that what would be good would be to write a new library based  
on traits the same way we build Nile.
This is true that subclassing instead of subtyping introduced a lot  
of problems in the collection hierarchy.

On 17 juin 07, at 08:42, Blake wrote: