ANN: set-0.1 module available
Coady
for Python 2.2+ which implements a set type. It's similar to the
specification in PEP 218.
You can find it in the Vaults of Parnassus or more directly at:
Comments are welcome,
-Coady
Roman Suzi
BTW, what are the chances of PEP218 being built into Python?
(I mean, as built-in type, not library)
I can't find any more discussions about that. My opinion is that set
built-in type is very useful and using dictionaries for that is ugly.
And I also think set type will not bloat Python much.
Sincerely yours, Roman Suzi
--
\_ Russia \_ Karelia \_ Petrozavodsk \_ r...@onego.ru \_
Thomas Heller
> On 10 May 2002, Coady wrote:
>
> BTW, what are the chances of PEP218 being built into Python?
> (I mean, as built-in type, not library)
It's listed as deferred (and its not mentioned in Guido's PEP
parade).
Maybe it needs a new champion?
Thomas
Roman Suzi
Hmmm... What do you mean? Set functionality is being asked every day
(for example, sorted list vs. dictionary thread). Implementation
(as I understand) is there. Why does Guido have any objections?
>Thomas
Sincerely yours, Roman Suzi
--
\_ Russia \_ Karelia \_ Petrozavodsk \_ r...@onego.ru \_
\_ Wednesday, May 15, 2002 \_ Powered by Linux RedHat 7.2 \_
\_ "No warp, Captain. There's cat hair all over the engine!" \_
Denis S. Otkidach
RS> >It's listed as deferred (and its not mentioned in Guido's
RS> PEP
RS> >parade).
RS> >Maybe it needs a new champion?
RS>
RS> Hmmm... What do you mean? Set functionality is being asked
RS> every day
RS> (for example, sorted list vs. dictionary thread).
RS> Implementation
RS> (as I understand) is there. Why does Guido have any
RS> objections?
There are still unresolved issues. E.g. should set object be
hashable? Somebody wish sets of sets or set as dict key that
require set to be hashable. Solution in kjSet is certanly bad,
look at the example below:
# s is set and d is dictionary
if d.has_key(s):
# do smth.
else:
# modify s -- this will raise exception
Here s _is not_ in dictionary but nevertheless is frozen. This
will confuse users that know nothing about set _implementation_.
Taking into account that very most users don't know about hashing
at all, such implementation is suitable only for third party
modules but not for Python builtin type.
Roman Suzi
>On Thu, 16 May 2002, Roman Suzi wrote:
>
>RS> >It's listed as deferred (and its not mentioned in Guido's
>RS> PEP
>RS> >parade).
>RS> >Maybe it needs a new champion?
>RS>
>RS> Hmmm... What do you mean? Set functionality is being asked
>RS> every day
>RS> (for example, sorted list vs. dictionary thread).
>RS> Implementation
>RS> (as I understand) is there. Why does Guido have any
>RS> objections?
>
>There are still unresolved issues.
>E.g. should set object be hashable?
Yes, I know this discussion. Math is dealing with
abstract objects while programming language is a model,
which must take efficiency vs. flexibility into account.
In Pascal set type was implemented for limited types of elements
(IIRC) and thus lacked flexibility. It's not Pythonic way.
So, probably Python will implement more flexible, universal sets?
(for example, using hashes when possible or falling back to
other schemes when impossible).
But in the current state of affairs lists and dicts are used to implenet
sets, which is probably not always nice.
>Somebody wish sets of sets or set as dict key that
>require set to be hashable. Solution in kjSet is certanly bad,
>look at the example below:
>
># s is set and d is dictionary
>if d.has_key(s):
> # do smth.
>else:
> # modify s -- this will raise exception
>Here s _is not_ in dictionary but nevertheless is frozen. This
>will confuse users that know nothing about set _implementation_.
>Taking into account that very most users don't know about hashing
>at all, such implementation is suitable only for third party
>modules but not for Python builtin type.
While object identity holds, its the same object.
Sincerely yours, Roman Suzi
--
\_ Russia \_ Karelia \_ Petrozavodsk \_ r...@onego.ru \_
\_ Thursday, May 16, 2002 \_ Powered by Linux RedHat 7.2 \_
\_ "Can't learn to do something well? Learn to enjoy doing it badly!" \_
Sandy Norton
I get the following error message after doing a 'python setup.py
build'
running build
running build_ext
building 'set' extension
set.c
set.c(1214) : error C2099: initializer is not a constant
set.c(1216) : warning C4047: 'initializing' : 'int ' differs in levels
of indirection from 'char [4]'
set.c(1217) : warning C4047: 'initializing' : 'char *' differs in
levels of indirection from 'unsigned int '
set.c(1219) : warning C4047: 'initializing' : 'int ' differs in levels
of indirection from 'void (__cdecl *)(struct _object *)'
set.c(1224) : warning C4047: 'initializing' : 'int (__cdecl *)(struct
_object *,struct _object *)' differs in levels of indirection from
'struct _object *(__cdecl *)(struct _object *)'
set.c(1225) : warning C4047: 'initializing' : 'struct _object
*(__cdecl *)(struct _object *)' differs in levels of indirection from
'struct PyNumberMethods *'
set.c(1226) : warning C4133: 'initializing' : incompatible types -
from 'struct PySequenceMethods *' to 'struct PyNumberMethods *'
set.c(1228) : warning C4047: 'initializing' : 'struct PyMappingMethods
*' differs in levels of indirection from 'long (__cdecl *)(struct
_object *)'
set.c(1235) : warning C4047: 'initializing' : 'struct PyBufferProcs *'
differs in levels of indirection from 'const int '
set.c(1236) : warning C4047: 'initializing' : 'long ' differs in
levels of indirection from 'char *'
set.c(1237) : warning C4047: 'initializing' : 'char *' differs in
levels of indirection from 'int (__cdecl *)(struct _object *,int
(__cdecl *)(struct _object *,void *),void *)'
set.c(1239) : warning C4047: 'initializing' : 'int (__cdecl *)(struct
_object *)' differs in levels of indirection from 'struct _object
*(__cdecl *)(struct _object *,struct _object *,int )'
set.c(1241) : warning C4047: 'initializing' : 'long ' differs in
levels of indirection from 'struct _object *(__cdecl *)(struct _object
*)'
set.c(1243) : warning C4047: 'initializing' : 'struct _object
*(__cdecl *)(struct _object *)' differs in levels of indirection from
'struct PyMethodDef *'
set.c(1251) : warning C4047: 'initializing' : 'long ' differs in
levels of indirection from 'int (__cdecl *)(struct _object *,struct
_object *,struct _object *)'
set.c(1252) : warning C4047: 'initializing' : 'int (__cdecl *)(struct
_object *,struct _object *,struct _object *)' differs in levels of
indirection from 'struct _object *(__cdecl *)(struct _typeobject *,int
)'
set.c(1254) : warning C4047: 'initializing' : 'struct _object
*(__cdecl *)(struct _typeobject *,struct _object *,struct _object *)'
differs in levels of indirection from 'void (__cdecl *)(struct _object
*)'
set.c(1324) : error C2099: initializer is not a constant
set.c(1326) : warning C4047: 'initializing' : 'int ' differs in levels
of indirection from 'char [13]'
set.c(1327) : warning C4047: 'initializing' : 'char *' differs in
levels of indirection from 'unsigned int '
set.c(1329) : warning C4047: 'initializing' : 'int ' differs in levels
of indirection from 'void (__cdecl *)(struct _object *)'
set.c(1344) : warning C4047: 'initializing' : 'struct PyBufferProcs *'
differs in levels of indirection from 'const int '
set.c(1350) : warning C4047: 'initializing' : 'long ' differs in
levels of indirection from 'struct _object *(__cdecl *)(struct _object
*)'
set.c(1352) : warning C4047: 'initializing' : 'struct _object
*(__cdecl *)(struct _object *)' differs in levels of indirection from
'struct PyMethodDef *'
It looks like the old 'initializer is not a constant' error... But
I've never confronted it before and I don't know how to fix it in this
case.
regards,
Sandy
Denis S. Otkidach
RS> >There are still unresolved issues.
RS>
RS> >E.g. should set object be hashable?
RS>
RS> Yes, I know this discussion. Math is dealing with
RS> abstract objects while programming language is a model,
RS> which must take efficiency vs. flexibility into account.
RS>
RS> In Pascal set type was implemented for limited types of
RS> elements
RS> (IIRC) and thus lacked flexibility. It's not Pythonic way.
RS> So, probably Python will implement more flexible, universal
RS> sets?
RS> (for example, using hashes when possible or falling back to
RS> other schemes when impossible).
That's to complex. Maybe sets should be always immutable like
tuples?
James J. Besemer
"Denis S. Otkidach" wrote:
Python has clear precedent for doing so, in that strings, tuples
and long integers all are immutable.
Regards
--jb
--
James J. Besemer 503-280-0838 voice
http://cascade-sys.com 503-280-0375 fax
mailto:j...@cascade-sys.com
Denis S. Otkidach
JJB> > That's to complex. Maybe sets should be always immutable
JJB> like
JJB> > tuples?
JJB>
JJB> Python has clear precedent for doing so, in that strings,
JJB> tuples
JJB> and long integers all are immutable.
Following these traditions we should have 2 types for sets: one
immutable but hashable (like tuple) and one mutable (like list).
James J. Besemer
"Denis S. Otkidach" wrote:
That would suit me just fine, though most would feel compelled to
pick just one or the other.
Right now, IIRC, lists and tuples are the ONLY pair of types that
seem to come in a mutable and unmutable pair. Seems there's a good
reason for this in their case.
All the other basic types (numbers, strings, longs) are immutable
and all the other aggregate types (dicts, files, modules, etc.) are
mutable.
You could further argue that we must have a immutable form of SETs,
so they could serve as dictionary indices. What's the argument for
having a mutable form, other than tuple has it? Let alone both?
Roman Suzi
> On Fri, 17 May 2002, James J. Besemer wrote:
>
> JJB> You could further argue that we must have a immutable form
> JJB> of SETs,
> JJB> so they could serve as dictionary indices. What's the
> JJB> argument for
> JJB> having a mutable form, other than tuple has it? Let alone
> JJB> both?
>
> We often need a collection that is extended step-by-step avoiding
> duplicates. Certainly we can use immutable sets:
>
> s = {-}
> for item in some_sequence:
> if is_good(item):
> s &= {item} # create new set if it's immutable or just
> # add otherwise
I think, that is
s = set(filter(is_good, some_sequence))
is for.
> but such code will be too expensive for large sets.
>
> If we write similar code for strings we'll use StringIO (consider
> it's some kind of mutable string) or intermidiate list (and join
> items afterwards). Collecting in list is OK with sets too if we
> don't need intermediate results as sets. But what about StringIO
> equivalent for sets? Other immutable types are not agregates
> (except complex numbers, but this is a special case) and we need
> not mutable form for them.
I hope for mutable sets so. I even think, sets could use
a generalised member function:
N in Integers
f in SecureFunctions
where membership function is substituted. So, set built-in type is more
about setting a protocol for set type. At first, implementation doesn't
matter much.
I see sets as constracts similar to lists but with automatic duplicate
exclusion and as efficient as possible lookup. And also with irrelevant
order of elements. And it doesn't matter if they will be implemented as
bit fields (for integers and chars), hashes or lists/dicts under the
cover. Protocol will be their to change implementation later.
And I hope those who know what set is, is also aware of the costs of the
set operations.
Sincerely yours, Roman A.Suzi
--
- Petrozavodsk - Karelia - Russia - mailto:r...@onego.ru -
Denis S. Otkidach
JJB> You could further argue that we must have a immutable form
JJB> of SETs,
JJB> so they could serve as dictionary indices. What's the
JJB> argument for
JJB> having a mutable form, other than tuple has it? Let alone
JJB> both?
We often need a collection that is extended step-by-step avoiding
duplicates. Certainly we can use immutable sets:
s = {-}
for item in some_sequence:
if is_good(item):
s &= {item} # create new set if it's immutable or just
# add otherwise
but such code will be too expensive for large sets.
Denis S. Otkidach
RS> > We often need a collection that is extended step-by-step
RS> avoiding
RS> > duplicates. Certainly we can use immutable sets:
RS> >
RS> > s = {-}
RS> > for item in some_sequence:
RS> > if is_good(item):
RS> > s &= {item} # create new set if it's immutable or
RS> just
RS> > # add otherwise
RS>
RS> I think, that is
RS>
RS> s = set(filter(is_good, some_sequence))
RS>
RS> is for.
This is OK but inefficient if intermediate list is very large
with many duplicates. But there are many situations where no
such functional solution (or it's not obvious):
def func(item):
...
result = {item}
result &= func(other_item) # other_item can be already in
# result
return result
and so on.
RS> I hope for mutable sets so. I even think, sets could use
RS> a generalised member function:
RS>
RS> N in Integers
RS>
RS> f in SecureFunctions
Python doen't support interfaces. Interface of sequences is
defined in documentation only. Should we define set in
documentation the same way as object with __contains__?
RS> where membership function is substituted. So, set built-in
RS> type is more
RS> about setting a protocol for set type. At first,
RS> implementation doesn't
RS> matter much.
Michael Gilfix
opinion) but why not use large integers to represent sets and set
members using bit vectors. A hash table can then map the bit vector
back to the original object. The nice thing about this is that
operations are done using bitwise & (yeah on longs, but it should
provide decent performance), and the hash table will allow quick
lookups. That should definitely speed things up some. Or perhaps
someone else is suggesting exactly this and I'm misreading someone
else's post?
-- Mike
--
Michael Gilfix
mgi...@eecs.tufts.edu
For my gpg public key:
http://www.eecs.tufts.edu/~mgilfix/contact.html
Erik Max Francis
> "Denis S. Otkidach" wrote:
>
> > On Thu, 16 May 2002, Roman Suzi wrote:
> >
> > That's to complex. Maybe sets should be always immutable like
> > tuples?
>
> Python has clear precedent for doing so, in that strings, tuples
> and long integers all are immutable.
Why is that a precedent? Lists aren't immutable, and you're as likely
to want to add and remove objects from a set as you are to modify a
list.
--
Erik Max Francis / m...@alcyone.com / http://www.alcyone.com/max/
__ San Jose, CA, US / 37 20 N 121 53 W / ICQ16063900 / &tSftDotIotE
/ \ Who'd ever think it / Such a squalid little ending
\__/ The American and Florence, _Chess_
Church / http://www.alcyone.com/pyos/church/
A lambda calculus explorer in Python.
Erik Max Francis
> There are still unresolved issues. E.g. should set object be
> hashable? Somebody wish sets of sets or set as dict key that
> require set to be hashable.
I would say yes, a set should require an immutable object, for the same
reason that a dictionary key should. You couldn't have dictionaries
themselves as dictionary keys, and nobody seems to have a problem with
that.
I'm presuming that what's being considered is something close to the
mathematical definition of a set, where a set contains some number of
unique objects, in no defined order. Adding an object to a set which
already contains it does nothing, since it can only be in the set at
most once.
A set can't contain an infinite number of objects -- although you could
create a proxy object that has the interface of a set and behaves like
it does.
I'm envisioning an implementation which behaves much like a dictionary,
with the elements of the set as keys, and with dummy values. What's
wrong with that?
Bjorn Pettersen
> "James J. Besemer" wrote:
>
> > "Denis S. Otkidach" wrote:
> >
> > > On Thu, 16 May 2002, Roman Suzi wrote:
> > >
> > > That's to complex. Maybe sets should be always immutable like
> > > tuples?
> >
> > Python has clear precedent for doing so, in that strings,
> tuples and
> > long integers all are immutable.
>
> Why is that a precedent? Lists aren't immutable, and you're
> as likely to want to add and remove objects from a set as you
> are to modify a list.
From the experience with our set class here, sets are never modified
once they're created. What is frequent is creating new sets based on the
union, intersection, and set difference of two sets, but there is almost
always a requirement that the original set stays the same. YMMV of
course :-)
Personally, I would be more than happy if Tim Peter's Python
implementation of a set was put in the std lib (I don't really care that
much about performance though as long as I have the functionality...)
-- bjorn
Erik Max Francis
> From the experience with our set class here, sets are never modified
> once they're created. What is frequent is creating new sets based on
> the
> union, intersection, and set difference of two sets, but there is
> almost
> always a requirement that the original set stays the same. YMMV of
> course :-)
In my usage, I've frequently wanted mutable sets (though not mutable set
elements). For instance, in tracking the equivalent of user logins and
logouts, a set (as being discussed here) is useful for tracking the set
of users currently logged in, since I'm not concerned with tracking
multiple instances (for this example), and the order in which the users
logged in is irrelevant.
James J. Besemer
"Denis S. Otkidach" wrote:
> We often need a collection that is extended step-by-step avoiding
> duplicates. Certainly we can use immutable sets:
That's the position I took initially when first thinking about the
problem. But as I thought more of it, I had to abandon
'efficiency'. In practice, I routinely manipulate immutable strings
100K long. For a lot of text processing I read the whole file into a
string and whack away at it. Yup, each string replace makes a copy
of the string but performance has never been an issue.
> s = {-}
> for item in some_sequence:
> if is_good(item):
> s ?= {item} # create new set if it's immutable or just
> # add otherwise
It's a matter of English semantics.
A smart compiler/interpreter would recognize that the modify-in-place
does not require that the original value of s be saved and thus
modification could be performed in place and reuse the data rep.
even though the language Semantics said sets were immutable.
I onced worked on an APL interpreter that worked this way. You made
deep copies of aggregate results on the stack only if you absolutely
had to and wherever possible you reused temporary results in place.
This was strictly an interpreter issue. The compiler didn't even
have to know. 'Language semantics' were essentially that everything
was immutable.
> but such code will be too expensive for large sets.
> If we write similar code for strings we'll use StringIO (consider
> it's some kind of mutable string) or intermidiate list (and join
> items afterwards). Collecting in list is OK with sets too if we
> don't need intermediate results as sets. But what about StringIO
> equivalent for sets? Other immutable types are not agregates
> (except complex numbers, but this is a special case) and we need
> not mutable form for them.
IF the proposal on the table is (a) sets are immutable but (b) we
also have a SetIO library function that allows us to manipulate them
as if they were mutable THEN I wholeheartedly agree.
IF you're saying the base implementation of sets MUST be mutable
because of performance reasons, then I don't get it, as it seems
there are a variety of solutions to minimize the performance issue
(which is very small for most practical applications in the first
place).
James J. Besemer
Erik Max Francis wrote:
"Denis S. Otkidach" wrote:? There are still unresolved issues. E.g. should set object be
? hashable? Somebody wish sets of sets or set as dict key that
? require set to be hashable.
I would say yes, a set should require an immutable object, for the same
reason that a dictionary key should. You couldn't have dictionaries
themselves as dictionary keys, and nobody seems to have a problem with
that.
Actually Denis seemed to be suggesting that sets themselves should be immutable so they could Serve as dictionary keys. I think it's very plausable that sets would be used in this manner..
I'm envisioning an implementation which behaves much like a dictionary,
with the elements of the set as keys, and with dummy values. What's
wrong with that?
Fernando Pérez
> Actually Denis seemed to be suggesting that sets themselves should be
> immutable so they could Serve as dictionary keys. I think it's very
> plausable that sets would be used in this manner..
I beg to differ. Mathematically, there's nothing in the idea of a set that
makes it immutable. I know that Python is not a mathematics-only language,
but much of the cleanliness of its design does come from following abstract
ideas as much as is reasonable. And enforcing immutability on a set is one
hell of a breakage for an object as basic to many mathematical ideas as a set
is.
I guess if you want to insist on sets being usable as keys you might come up
with a pair of set-like types just like we have lists/tuples. But if sets are
ever going to be part of the language, _please_ don't make them immutable. In
my mind, that's like saying that you add integers to a language but you can't
do arithmetic with them ;)
Cheers,
f.
Erik Max Francis
> I beg to differ. Mathematically, there's nothing in the idea of a set
> that
> makes it immutable. I know that Python is not a mathematics-only
> language,
> but much of the cleanliness of its design does come from following
> abstract
> ideas as much as is reasonable. And enforcing immutability on a set is
> one
> hell of a breakage for an object as basic to many mathematical ideas
> as a set
> is.
Sure, but when translating mathematical concepts to programming,
practicality always gets in the way. A dictionary, for instance, in
essence just a function which maps a set into another. The practical
measures of dealing with a dictionary with mutable keys is what dictates
that keys must be immutable; enforcing this limitation is a far better
alternative than implementing a standard dictionary that must take into
account all the nasty side effects of key objects which can change
state, thereby affecting the lookup table. (Likely it would involve
adding complexity to the _objects_ themselves, such as with notifiers
and callbacks to handle the case of changes and conflicts.)
I see the same thing happening here. It certainly would be nice if sets
could have mutable objects as elements -- in the same way it would be
nice if dictionaries could have mutable keys -- but it is not worth the
added complexity and headache.
Erik Max Francis
> Actually Denis seemed to be suggesting that sets themselves should be
> immutable so they could Serve as dictionary keys. I think it's very
> plausable that sets would be used in this manner..
I see. Certainly it's not inconceivable that some might use sets in
this manner, but it seems just as likely, if not more so, that people
would want sets (themselves) to be mutable, so that objects can be added
and removed.
Certainly having the sets themselves, like tuples, being immutable
eliminates the question of what kind of elements can be contained within
them, but that seems extremely limiting. The goal here is finding the
right balance between usefulness and arbitrary limitations.
Fernando Pérez
> Sure, but when translating mathematical concepts to programming,
> practicality always gets in the way. A dictionary, for instance, in
> essence just a function which maps a set into another.
And therefore means that the keys must never change, by the very definition of
mapping. At a given value of the domain (the key) we have a value in the
range (the value), and the domain value can't start jumping around. So for
dictionaries thought as mappings, it's actually perfectly reasonable to
expect the keys to be immutable.
For sets, on the other hand, it's a strange and unnatural restriction. Maybe
for implementation reasons it will be practical to have them be _internally_
immutable and have them 'simulate' mutability like strings do (s = 'hi';
s+='ho' works 'in place' even though it doesn't ;)
Language design and implementation is always a balancing act: you want
abstract, flexible and general features but you want them to be realistically
implementable by normal humans in a finite amount of time. Where to draw the
line is always a decision that involves as much gut and intuition as it does
'science'. So far I think the python team has done an admirable job of
finding a great balance. IMHO for sets, making them immutable would fall too
far in the direction of 'practicality' and lose too much in the 'flexibility
and power of abstraction' department. But again, that's my opinion.
Cheers,
f.
Erik Max Francis
> Language design and implementation is always a balancing act: you want
> abstract, flexible and general features but you want them to be
> realistically
> implementable by normal humans in a finite amount of time. Where to
> draw the
> line is always a decision that involves as much gut and intuition as
> it does
> 'science'. So far I think the python team has done an admirable job of
> finding a great balance. IMHO for sets, making them immutable would
> fall too
> far in the direction of 'practicality' and lose too much in the
> 'flexibility
> and power of abstraction' department. But again, that's my opinion.
Of course; we're just disagreeing on where that line should be drawn in
this case.
What would, then, be a reasonable implementation of a set (with mutable
objects) in Python? The immutable keys in Python dictionaries already
sets a precedent for this effort being on the far side of practicality.
Fernando Pérez
> Of course; we're just disagreeing on where that line should be drawn in
> this case.
>
> What would, then, be a reasonable implementation of a set (with mutable
> objects) in Python? The immutable keys in Python dictionaries already
> sets a precedent for this effort being on the far side of practicality.
Oh, I'm just jumping in the middle of a discussion, I haven't given the
implementation problem any thought at all, and don't have the need/time to do
it right now. So I'll just be cheering from the sidelines in this case ;)
Cheers,
f.
James J. Besemer
Erik Max Francis wrote:
> I see. Certainly it's not inconceivable that some might use sets in
> this manner, but it seems just as likely, if not more so, that people
> would want sets (themselves) to be mutable, so that objects can be added
> and removed.
But fundamentally, this is like saying long integers must be mutable because
people will want to set and clear individual bits. Or that strings must be
mutable because people will want to append and truncate. Sure it's
necessary to compute new set values but they don't require that the
underlying type be mutable.
I wonder if you are perhaps too deeply attached to a particular
implementation?
> Certainly having the sets themselves, like tuples, being immutable
> eliminates the question of what kind of elements can be contained within
> them, but that seems extremely limiting. The goal here is finding the
> right balance between usefulness and arbitrary limitations.
I hadn't considered the implication of mutable objects as set members. If
you allow an arbitrary list/tree structure to be members, how do you decide
if it's in the set or not? You only consider the list object itself or do
you look at its overall value?
Regards
James J. Besemer
Fernando Pérez wrote:
> I beg to differ. Mathematically, there's nothing in the idea of a set that
> makes it immutable. I know that Python is not a mathematics-only language,
> but much of the cleanliness of its design does come from following abstract
> ideas as much as is reasonable. And enforcing immutability on a set is one
> hell of a breakage for an object as basic to many mathematical ideas as a set
> is.
I beg to differ. Mathematically, there's no notion of assignment like we have in
programming. From a traditional mathematics view " x = x + 1" is a nonsensical
statement. At best it's a contradiction in terms. In Mathematics, you don't
have assignment that can be done over and over. You can only make statements
about equality or inequality. At bottom all mathematics is defined in terms of
sets and predicates about sets.
In the context of mathematics I would argue that ALL objects are immutable. When
you say "2 + 3 = 5", the 2 and the 3 don't cease to exist. Numbers are
immutable. Similarly, when you say B union C you are defining a third, new set,
composed of the union of the first two. The first two don't go away. They
continue to exist (necessarily) to maintain the definition of the result. You
don't destroy or reuse the previous ones. In set theory you can say (assume + is
union)
A = B + C
but you cannot say
A += B
or
A = {1,2,3} ; A = A + {4}
There is no ";" sequential operation in mathematics. Closest would be to
introduce a new variable, say somethig like:
A = {1,2,3} ; A' = A + {4}
I've studied the mathematical subject of 'semantics' and modelling things like
assignment is extremely complicated. You define sets of all possible states of
your computation and then you make statements about the particular states before
and after, say, a particular assignment (multiple IMMUTABLE sets.))
This is complexity of the underlying mathematics is the theoretical justification
some purists (ones who know what they are talking about) use to argue to
eliminate assignment and looping altogether from programming in preference for
lambda and recursion.
It may be the case that sets in Python should be mutable but you can't argue
there's some "mathematical" basis for doing so. Mathematics suggests the exact
opposite.
> I guess if you want to insist on sets being usable as keys you might come up
> with a pair of set-like types just like we have lists/tuples.
That would seem more complicated than it needs. I would prefer to say intrinsic
sets are immutable and there's a library function for a mutable version, ala
String.
Alternatively, implement a useful library, let everybody use it for a while and
see how far it gets us. Maybe nobody want's to use sets as array indicies.
> In my mind, that's like saying that you add integers to a language but you
> can't
> do arithmetic with them ;)
I beg to differ. ;o)
Fact of the matter, integers, strings and longs presently ARE immutable and you
still CAN do arbitrary arithmetic with them. E.g.,
x = 1L << 100000
x += 1
s = string.zfill( "1", 10000 )
s += ".0"
Being immutable in the context of Python does NOT restrict in any fashion the
types of "arithmetic" you can do on objects. It just means the result is a new
object. The runtime system can even implement whatever optimization is required
to economize object space or storage or whatever, if performance is a concern.
Regards
Huaiyu Zhu
>"James J. Besemer" wrote:
>
>> Python has clear precedent for doing so, in that strings, tuples
>> and long integers all are immutable.
>
>Why is that a precedent? Lists aren't immutable, and you're as likely
>to want to add and remove objects from a set as you are to modify a
>list.
Maybe Python needs a keyword "const".
I've been toying with this idea for quite some time. It is my observation
that a substantial proportion of the discussions about Python design touches
on the issue of mutability:
- Is this thing hashable?
- Should I compare with contents or with object id?
- What does += do? Why is it different for list and numbers?
- Can I use string as a buffer?
- Some of the great uses of __getattr__ and __setattr__.
- Some security discussions.
- Why don't Python have a machine code compiler?
- How do I codify the idea that this thing will not change here?
- Speed and garbage collection for tuples (on python-dev).
There are more but I can only remember these right now.
Python provides immutable types for some objects (numbers, strings) and
mutable types for others (dictionaries, functions, classes, modules) and
both versions for some (tuples and lists).
In real life we have to deal with some versions of objects that cannot
change, and some versions that can, for any kind of objects. It might be
better to separate out the mutability aspect of objects from other aspects,
and maybe even allow objects to change the mutability under some rules.
There are at least two kinds of possible meaning of 'const' in Python: const
reference and const object.
To illustrate the idea, I'll give some examples, assuming that all things
are mutable a priori without the 'const' keyword, which is not true today.
Suppose we use prefix 'const' to refer to names and postfix 'const' to refer
to objects, we could say
# const reference to mutable object
const a = "abc"
# forbids a = "xyz"
# allows b = a; a += "uvw"; which would set b to "abcuvw".
# mutable reference to const object
a = "abcd" const
# forbids a[2] = 'g'
# allows a = 42
# const reference to const object
const a = "abc" const
# forbids both rebinding a to another object and changing the current
# object.
# more examples
a = [1, 2, 3] const # equivalent to today's a = (1, 2, 3)
a = "abc" const # equivalent to today's a = "abc"
a = {1, 2, 3} const # a set that can be hashed by content
const a = {1, 2, 3} # a set that should be hashed by id (like a container)
def f(x const) # will not modify x object inside f.
class A:
def meth1(self, x) # may modify self and x
def meth2(self const, x) # may not modify an members, but may modify x
def meth3(self, x const) # may modify members of self.
These ideas are not a concrete proposal at the moment. What I'm hoping for
is that perhaps by seeing a connection among these issues a more coherent
proposal might emerge that is better than incremental changes. The issue of
implementation and compatibility is not on my radar screen yet.
Fire up your ideas.
Huaiyu
Mark McEahern
> # const reference to mutable object
> const a = "abc"
> # forbids a = "xyz"
> # allows b = a; a += "uvw"; which would set b to "abcuvw".
Presumably, you mean:
> # allows b = a; b += "uvw"; which would set b to "abcuvw".
// mark
Erik Max Francis
> I wonder if you are perhaps too deeply attached to a particular
> implementation?
I'm going by what seems to me the most straightforward implementation,
which is also what is described in the PEP itself (with the caveat that
the PEP allows sets to contain sets through a tweak). It seems the most
sensible tradeoff between idealization and practicality.
> I hadn't considered the implication of mutable objects as set members. > If
> you allow an arbitrary list/tree structure to be members, how do you
> decide
> if it's in the set or not? You only consider the list object itself
> or do
> you look at its overall value?
Presumably by an equality test (which can be reflected in the immutable
case by having hashes of equal objects, such as 1 and 1.0, be themselves
equal).
That's not the half of it. Mutable objects can dynamically change
state, completely outside the control of the container. So the hard
question is: What happens when a mutable object changes its value, such
that it effects the arrangement of the set? How does the container get
notified of this change (which as far as I know there is no standard way
to test in Python), and what happens when a value collision occurs
within the set? Does one object get disposed? If so, which one?
These are precisely the same kind of issues that lead one to conclude
that you're much better off with immutable dictionary keys.
Roman Suzi
> Fernando PИrez wrote:
>
> > I beg to differ. Mathematically, there's nothing in the idea of a set that
> > makes it immutable. I know that Python is not a mathematics-only language,
> > but much of the cleanliness of its design does come from following abstract
> > ideas as much as is reasonable. And enforcing immutability on a set is one
> > hell of a breakage for an object as basic to many mathematical ideas as a set
> > is.
>
> I beg to differ. Mathematically, there's no notion of assignment like we have in
> programming. From a traditional mathematics view " x = x + 1" is a nonsensical
> statement. At best it's a contradiction in terms. In Mathematics, you don't
> have assignment that can be done over and over. You can only make statements
> about equality or inequality. At bottom all mathematics is defined in terms of
> sets and predicates about sets.
It is right. But if you look into applied math journals, people
communicate algorithms in a pseudolanguage where sets are
widely used. It could be nice if Python supported such things closer.
> In the context of mathematics I would argue that ALL objects are
> immutable. When you say "2 + 3 = 5", the 2 and the 3 don't cease to
> exist. Numbers are immutable. Similarly, when you say B union C you
> are defining a third, new set, composed of the union of the first two.
> The first two don't go away. They continue to exist (necessarily) to
> maintain the definition of the result. You don't destroy or reuse the
> previous ones.
Sincerely yours, Roman A.Suzi
Fernando Pérez
>> I beg to differ. Mathematically, there's nothing in the idea of a set that
>> makes it immutable. I know that Python is not a mathematics-only language,
>> but much of the cleanliness of its design does come from following abstract
>> ideas as much as is reasonable. And enforcing immutability on a set is one
>> hell of a breakage for an object as basic to many mathematical ideas as a
>> set is.
>
> I beg to differ. Mathematically, there's no notion of assignment like we
> have in
> programming. From a traditional mathematics view " x = x + 1" is a
> nonsensical
> statement. At best it's a contradiction in terms. In Mathematics, you
> don't
> have assignment that can be done over and over. You can only make
> statements
> about equality or inequality. At bottom all mathematics is defined in terms
> of sets and predicates about sets.
> In the context of mathematics I would argue that ALL objects are immutable.
Ok, I should have expressed myself more carefully. I'm not a mathematician by
training, but thanks to your post I did brush up at least on the starters of
ZFC set theory. My only formal contact with the subject had been in long ago
history of mathematics courses I took for fun.
Your points about immutability in mathematics are perfectly valid in the sense
that time is not a mathematical concept, therefore objects have the value
given at the time of their definition. When you say
A = {X | X is not a member of X}
A has been defined and you are done. Any later additions to the set will
involve a redefinition.
What I had in mind is that in the context of an evolving problem (such as is a
computer program which executes in time), the elements which satisfy the
definition of a given set can increase. What I had in mind was the difference
between saying 'x=5', which fairly well 'fixes' x and saying
's={f | f is a file in '.' with size > 10k} '
which can change if new files are added to the directory as the program
evolves (assuming it checks periodically). So while I agree with your strict
mathematical definition of immutability, I hope what I had in mind is clearer
now. Shame on me for the lack of precision, I'll be more careful next time.
>> In my mind, that's like saying that you add integers to a language but you
>> can't
>> do arithmetic with them ;)
>
> I beg to differ. ;o)
>
> Fact of the matter, integers, strings and longs presently ARE immutable and
> you
> still CAN do arbitrary arithmetic with them. E.g.,
Here you completely misunderstood me. I'm perfectly aware of how strings and
ints work in Python, I was simply using my sentence as an analogy of a
_hypothetical_ situation of 'useless integers' to express why I consider
immutable sets to be of limited usability. Read it again, I said 'add
integers to _a_ language', I was not talking about Python at all. For the
record yes, I have tried adding two numbers in python and seen it work.
Cheers,
f.
James J. Besemer
Roman Suzi wrote:
> On Fri, 17 May 2002, James J. Besemer wrote:
>
> > I beg to differ. Mathematically, there's no notion of assignment like we have in
> > programming. From a traditional mathematics view " x = x + 1" is a nonsensical
> > statement. At best it's a contradiction in terms. In Mathematics, you don't
> > have assignment that can be done over and over. You can only make statements
> > about equality or inequality. At bottom all mathematics is defined in terms of
> > sets and predicates about sets.
>
> It is right. But if you look into applied math journals, people
> communicate algorithms in a pseudolanguage where sets are
> widely used. It could be nice if Python supported such things closer.
Python certain can support sets and set arithmetic INDEPENDENTLY of whether sets are
intrinsic or not.
James J. Besemer
Fernando Pérez wrote:
> Ok, I should have expressed myself more carefully. I'm not a mathematician by
> training,[...].
Me neither.
> My only formal contact with the subject had been in long ago
> history of mathematics courses I took for fun.
Same here.
Fascinating stuff, no?
> What I had in mind is that in the context of an evolving problem (such as is a
> computer program which executes in time), the elements which satisfy the
> definition of a given set can increase. What I had in mind was the difference
> between saying 'x=5', which fairly well 'fixes' x and saying
>
> 's={f | f is a file in '.' with size > 10k} '
>
> which can change if new files are added to the directory as the program
> evolves (assuming it checks periodically). So while I agree with your strict
> mathematical definition of immutability, I hope what I had in mind is clearer
> now.
I understood you perfectly and I (re)submit that your needs as stated can be met
equally well by a set implementation that happen to be immutable. E.g., in your
above example, the syntax in the {} is a constructor. Each time it is evaluated
it would create a NEW set object and assign it to s. The object itself could be
immutable and yet you could express the computations you desire. What you really
need is to be able to change the set valued object assigned to s, and you can do
that by changing the existing object or by assigning a new one. Creating a new
one each time SOUNDS like a lot more work but in practice I bet it won't be. The
set operations themselves are fairly expensive and duping the object probably
won't take significantly longer.
A better example might be something like
s = { some set }
...
while 1:
s += { file.getname() }
Here you presumably have an existing set assigned to s and you're maybe adding a
new element by reading a name out of a file. By += we want to union the new
element into the set. Again, there is NO problem if the set is immutable. Set
objects would define a "+" operator and a "+=". The fact that a new set object
gets created doesn't matter, same as if a new string is created by its "+="
operator.
> Shame on me for the lack of precision, I'll be more careful next time.
Ha! Don't worry. *I* have made much bigger mistakes here.
Anyway, I objected to your rationale. As we discuss this further, my position is
softening on the ultimate outcome.
> Here you completely misunderstood me.
I don't think I misunderstood. Rather I simply disagree. Everything you want can
be provided by a set implementation that is immutable or mutable. Doesn't matter.
Implementation details aside, "immutable" means a few specific things in Python:
(a) if objects a and b are of the same immutable type, then a == b <=> a is b.
(b) immutable objects export a __hash__() function such that
a == b <=> __hash__( a ) == __hash__( b )
(c) Operation ons immutable objects always produce new objects, rather than
changing the state of an existing one. A chief way this comes into play is in
function calls:
def f( s ):
s.modification()
s = { some set }
f( s )
At the end of this sequence, if s is immutable then the side-effect in f() is NOT
propigated to the variable s passed in.
To propigate the side effect, f() needs to expressly return a result, e.g.,
def f( s ):
s.modify()
return s
s = { some set }
s = f( s )
Thus if sets were immutable then functions that modify sets would have to be true
functions. You would not be able to write functions that alter arguments in place
via side effects.
Chief benefit of immutability is that sets could be used as keys to dictionaries.
One voice from the frontier says most ops do NOT mutate sets. Another says he'd
do it all the time if he could. There is not a lot of clamor for needing set
indicies in dictionaries.
Downside, is functions (a) and (b) above are non-trivial to implement and if you
give up immutability then there's no reason to. The copying implied at each
operation could be unnecessarily expensive for very large sets. Some would argue
the loss of functional side effects is a bad thing. The present prototype
implementation is mutable.
All things considered, I withdraw my guilty plea and change my own vote to
mutable.
Fernando Pérez
> I understood you perfectly and I (re)submit that your needs as stated can be
> met equally well by a set implementation that happen to be immutable.
Well, I think you misunderstood me simply because I'm perfectly aware of the
idea you're stating here and I thought I had made that much clear (I'm
obviously not having much success with clarity today). In fact, another post
of mine on this same thread included:
> Maybe for implementation reasons it will be practical to have them be
> _internally_ immutable and have them 'simulate' mutability like strings do
> (s = 'hi'; s+='ho' works 'in place' even though it doesn't ;)
So I know perfectly well that immutable objects can simulate in-place
operations. The question is whether the performance hit you take is
significant or not. Since it _can_ be (try a large loop on a string with +=
and watch your machine hit a wall), I tend to be of the opinion that unless
there's a compelling reason to make the objects immutable, one is better off
by not forcing the performance penalty. Simply because it makes the language
more scalable and worry-free.
I personally would rather have mutable sets which can't be used as dict keys,
but I'm sure someone else might prefer the exact opposite.
So just to make sure I'm clear: yes, I know that mutability can be simulated
to death with immutable objects, and I've known all along how strings work.
The point is that there is a non-negligible penalty to be paid by doing
things that way for large objects. So the issue is not whether it can be done
or not, but whether the existence of that penalty tilts the decision in favor
of making them mutable and thus paying the price of losing hashability.
And by the way, when you say 'Creating a new one each time SOUNDS like a lot
more work but in practice I bet it won't be', I hope you don't really mean
that. If you deal routinely with sets with 2**N (N>>30) elements, a copy
operation for simulating += can be prohibitive. Why do you think that
Numeric's arrays implement [a:b] slicing as a reference and not a copy
operation (which bites most newbies _hard_)?
If Numeric arrays behaved like Python lists (where [a:b] is a copy operation)
they would be perfectly useless for numerical computing. Imagine writing the
standard relaxation solution for the Laplace equation --a handful of lines of
Numeric code-- with your 'I bet in practice it's not more work' and guess
what will happen ;) That is the crux I'm trying to point you to, not whether
you can _simulate_ in-place operations with immutable objects. We've known
that all along.
Cheers,
f.
PS. In case you are curious, for the 2d case the meat of the Laplace code is
as simple as:
# The actual iteration
u[1:-1, 1:-1] = ((u[0:-2, 1:-1] + u[2:, 1:-1])*dy2 +
(u[1:-1,0:-2] + u[1:-1, 2:])*dx2)*dnr_inv
You can see a complete, detailed discussion at
http://www.scipy.org/site_content/weave/python_performance.html
Bernhard Herzog
> That's not the half of it. Mutable objects can dynamically change
> state, completely outside the control of the container. So the hard
> question is: What happens when a mutable object changes its value, such
> that it effects the arrangement of the set? How does the container get
> notified of this change (which as far as I know there is no standard way
> to test in Python), and what happens when a value collision occurs
> within the set? Does one object get disposed? If so, which one?
It seems to me that the most sensible solution would be to deal with it
like a dictionary deals with mutable keys: By not caring about whether
an object is mutable or not (there is no way to determine this anyway)
but relying on a certain behavior regarding hash values instead.
If an object is stored in a dict as a key, the only things that matter
are that
1. its hash value doesn't change as long as the object is used as a key.
2. equal objects have equal hash values
There may be some more subtle requirements. I'm not sure what happens
when two objects that have the same hash value but do not compare eqal
at first later become equal, for instance.
Bernhard
--
Intevation GmbH http://intevation.de/
Sketch http://sketch.sourceforge.net/
MapIt! http://www.mapit.de/
Gonçalo Rodrigues
>Erik Max Francis <m...@alcyone.com> writes:
>
>> That's not the half of it. Mutable objects can dynamically change
>> state, completely outside the control of the container. So the hard
>> question is: What happens when a mutable object changes its value, such
>> that it effects the arrangement of the set? How does the container get
>> notified of this change (which as far as I know there is no standard way
>> to test in Python), and what happens when a value collision occurs
>> within the set? Does one object get disposed? If so, which one?
>
>It seems to me that the most sensible solution would be to deal with it
>like a dictionary deals with mutable keys: By not caring about whether
>an object is mutable or not (there is no way to determine this anyway)
>but relying on a certain behavior regarding hash values instead.
>
>If an object is stored in a dict as a key, the only things that matter
>are that
>
>1. its hash value doesn't change as long as the object is used as a key.
Doesn't this mean, in practice, that it is immutable? To me, this
requirement is just shifting responsabilities from one place to the
other and not really solving the problem.
>
>2. equal objects have equal hash values
>
>There may be some more subtle requirements. I'm not sure what happens
>when two objects that have the same hash value but do not compare eqal
>at first later become equal, for instance.
I believe 2. is more stringent:
equal objects iff equal hash values
>
> Bernhard
Best regards,
Gonçalo Rodrigues
Bengt Richter
>Erik Max Francis <m...@alcyone.com> writes:
>
>> That's not the half of it. Mutable objects can dynamically change
>> state, completely outside the control of the container. So the hard
>> question is: What happens when a mutable object changes its value, such
>> that it effects the arrangement of the set? How does the container get
>> notified of this change (which as far as I know there is no standard way
>> to test in Python), and what happens when a value collision occurs
>> within the set? Does one object get disposed? If so, which one?
>
Perhaps there could be a const-on-hash (mark as immutable if ref counts==1,
copy and mark otherwise), and then copy-on-write (copy if const, un-const the copy,
and proceed with mutating operation on the copy), so sets could play both
roles. This would just be an optimization for some kinds of sets, but probably
wouldn't be worth it for e.g., small sets of bits that could be implemented as
packed into 32-bit integers. In any case, it w/shouldn't change the set semantics.
>It seems to me that the most sensible solution would be to deal with it
>like a dictionary deals with mutable keys: By not caring about whether
>an object is mutable or not (there is no way to determine this anyway)
>but relying on a certain behavior regarding hash values instead.
>>> d={}
>>> l=range(5)
>>> d[l]='list5'
Traceback (most recent call last):
File "<stdin>", line 1, in ?
TypeError: list objects are unhashable
>>> l2=tuple([[x] for x in xrange(5)])
>>> l2
([0], [1], [2], [3], [4])
>>> d[l2] = 'tuplist5'
Traceback (most recent call last):
File "<stdin>", line 1, in ?
TypeError: list objects are unhashable
It seems to care "about whether an object is mutable or not" and doesn't
seem to believe that "(there is no way to determine this anyway)".
You must have meant something else?
>
>If an object is stored in a dict as a key, the only things that matter
>are that
>
>1. its hash value doesn't change as long as the object is used as a key.
>
>2. equal objects have equal hash values
>
for some definition of hashing an object equality...
>There may be some more subtle requirements. I'm not sure what happens
>when two objects that have the same hash value but do not compare eqal
>at first later become equal, for instance.
>
You're not confusing names and values, are you?
Regards,
Bengt Richter
Bernhard Herzog
> On 18 May 2002 17:15:29 +0200, Bernhard Herzog <b...@intevation.de> wrote:
>
> >It seems to me that the most sensible solution would be to deal with it
> >like a dictionary deals with mutable keys: By not caring about whether
> >an object is mutable or not (there is no way to determine this anyway)
> >but relying on a certain behavior regarding hash values instead.
>
> >>> d={}
> >>> l=range(5)
> >>> d[l]='list5'
> Traceback (most recent call last):
> File "<stdin>", line 1, in ?
> TypeError: list objects are unhashable
> >>> l2=tuple([[x] for x in xrange(5)])
> >>> l2
> ([0], [1], [2], [3], [4])
> >>> d[l2] = 'tuplist5'
> Traceback (most recent call last):
> File "<stdin>", line 1, in ?
> TypeError: list objects are unhashable
The messages don't say "list objects are mutable" they say they're
unhashable. This actually demonstrates what I was trying to say. The
objects used as keys have to be hashable and their hashvalues have to
follow certain rules but the objects may well be mutable.
You can easily create a sub-class of list that can be used a key in a
dict, for instance (similar things work in older versions of python as
well):
Python 2.2 (#1, Jan 17 2002, 21:04:07)
[GCC 2.95.4 20011006 (Debian prerelease)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> class mylist(list):
... def __eq__(self, other):
... return self is other
... def __hash__(self):
... return id(self)
...
>>> m = mylist()
>>> d = {m: "abc"}
>>> d
{[]: 'abc'}
>>> m.append(1)
>>> d
{[1]: 'abc'}
>>>
> It seems to care "about whether an object is mutable or not" and doesn't
> seem to believe that "(there is no way to determine this anyway)".
There is now way in python to tell whether any given object is mutable
or not for all objects. Whether an object is immutable depends solely on
its implementation. There is no flag in the object or type structures
that define whether an object is mutable or not or any other standard
way to detect this.
> You must have meant something else?
No, I meant what I said.
> >If an object is stored in a dict as a key, the only things that matter
> >are that
> >
> >1. its hash value doesn't change as long as the object is used as a key.
> >
> >2. equal objects have equal hash values
> >
> for some definition of hashing an object equality...
Not sure what you mean by that, but 2. above means that a == b implies
hash(a) == hash(b)
> >There may be some more subtle requirements. I'm not sure what happens
> >when two objects that have the same hash value but do not compare eqal
> >at first later become equal, for instance.
> >
> You're not confusing names and values, are you?
No. I was talking about objects being used as keys in dicts.
James J. Besemer
Fernando Pérez wrote:
> So the issue is not whether it can be done
> or not, but whether the existence of that penalty tilts the decision in favor
> of making them mutable and thus paying the price of losing hashability.
As I acknowledged in my previous post.
Furthermore, I previously recanted and agreed a mutable implementation probably is
better because of performance reasons.
> And by the way, when you say 'Creating a new one each time SOUNDS like a lot
> more work but in practice I bet it won't be', I hope you don't really mean
> that.
I meant that, like with strings, the majority of users won't have a problem. I
don't mean that nobody will. Exactly like with Numerics -- some applications
require much greater numeric performance than Python offers out of the box.
Say La Vee.
> If you deal routinely with sets with 2**N (N>>30) elements, a copy
> operation for simulating += can be prohibitive. Why do you think that
> Numeric's arrays implement [a:b] slicing as a reference and not a copy
> operation (which bites most newbies _hard_)?
One could similarly imagine a special Set implementation for huge numbers of
elements.
E.g., some applications might use large sets of a subrange of integers, say
0..64K. For them a bitmap implementation (ala Pascal) might be way more efficient
than any kind of dictionary lookup. Even if you need sets of arbitrary values, a
special high-performance version might be appropriate as a library alternative
instead of loading extra complexity into the base language.
If you're pushing the envelope, you're pushing the envelope and you may run into
problems.
> That is the crux I'm trying to point you to, not whether
> you can _simulate_ in-place operations with immutable objects. We've known
> that all along.
Then you should have SAID that sooner. ;o)
Most of my objections have been with the faulty reasons you used in your argument.
> In case you are curious, for the 2d case the meat of the Laplace code is
> as simple as:
Can you think of a practical example that requires efficient, large SETs?
Roman Suzi
If I understand correctly, our discussion rotates around
two axes:
hashable/unhashable items:
-------------------------
- Set must support any objects found in Python system,
otherwise people could just use dicts to the same results.
mutable/immutable set:
---------------------
- mutable sets are more practical. If one needs to use set as a dict key,
let him convert it to sorted tuple and do so. I think, it's a rare case.
Much more rare than need to append element to the set.
My idea is that sets should be as lists, but with special
set of operations and not allowing doubles.
I even thought, sets could be based purely as unordered, without
duplicates collection of "pointers" to objects but due to the following:
>>> a = "ab"
>>> b = "a" +"b"
>>> id(a)
135509000
>>> id(b)
135171664
it is not so appealing idea...
So, my understanding is: if sets are into Python, they need
to be as powerful, as possible. Otherwise dictionary keys
will be preferred by people.
My votes:
unhashable (general) items +1
mutable sets +1
Sincerely yours, Roman Suzi
--
\_ Russia \_ Karelia \_ Petrozavodsk \_ r...@onego.ru \_
\_ Sunday, May 19, 2002 \_ Powered by Linux RedHat 7.2 \_
\_ "It's not the principle of the thing, it's the money" \_
Steve Holden
> James J. Besemer wrote:
>
> > Actually Denis seemed to be suggesting that sets themselves should be
> > immutable so they could Serve as dictionary keys. I think it's very
> > plausable that sets would be used in this manner..
>
> I beg to differ. Mathematically, there's nothing in the idea of a set that
> makes it immutable. I know that Python is not a mathematics-only language,
> but much of the cleanliness of its design does come from following
abstract
> ideas as much as is reasonable. And enforcing immutability on a set is one
> hell of a breakage for an object as basic to many mathematical ideas as a
set
> is.
>
mutability, but we have lists and tuple because it is convenient to have two
similar sequence types, one of which is mutable and the other of which is
not. So it probably isn't useful to argue from mathematics when what you are
taking about is the pragmatics of programming.
> I guess if you want to insist on sets being usable as keys you might come
up
> with a pair of set-like types just like we have lists/tuples. But if sets
are
> ever going to be part of the language, _please_ don't make them immutable.
In
> my mind, that's like saying that you add integers to a language but you
can't
> do arithmetic with them ;)
>
Bearing in mind that Python does indeed allow you to do arithmetic with
integers which are immutable, I'm wondering if you might not need to look
for a rather better analogy.
I believe (without any worked-out justification) that Python could actually
perform exactly the same comutations as it does now even if lists were
removed: it would simply be more awkward and less efficient to compute with
tuples, which are immutable.
If sets were to become a Python type I would expect that it would be useful
to have both mutable and immutable variants, in just the same way as the
sequences do. The strings are a degenerate example (IMHO), because they are
the only sequence type in Python where type(s[n]) == type(s) for any valid n
(I know I've not expressed that well: what I'm trying to say is that it's a
little bizarre for strings to be sequences of strings of length one. It
works, but it's a little bizarre).
regards
Steve
--
-----------------------------------------------------------------------
Steve Holden http://www.holdenweb.com/
Python Web Programming http://pydish.holdenweb.com/pwp/
-----------------------------------------------------------------------
Steve Holden
>
> > Language design and implementation is always a balancing act: you want
> > abstract, flexible and general features but you want them to be
> > realistically
> > implementable by normal humans in a finite amount of time. Where to
> > draw the
> > line is always a decision that involves as much gut and intuition as
> > it does
> > 'science'. So far I think the python team has done an admirable job of
> > finding a great balance. IMHO for sets, making them immutable would
> > fall too
> > far in the direction of 'practicality' and lose too much in the
> > 'flexibility
> > and power of abstraction' department. But again, that's my opinion.
>
> Of course; we're just disagreeing on where that line should be drawn in
> this case.
>
> What would, then, be a reasonable implementation of a set (with mutable
> objects) in Python? The immutable keys in Python dictionaries already
> sets a precedent for this effort being on the far side of practicality.
>
Well, in my case I'm disagreeing that there ought to be a line at all. If we
can have lists and tuples, I don't see any reason why we couldn't have two
flavours of set as well.
regards
Erik Max Francis
> Well, in my case I'm disagreeing that there ought to be a line at all.
> If we
> can have lists and tuples, I don't see any reason why we couldn't have
> two
> flavours of set as well.
But we _don't_ have two flavors of dictionaries. That's the most direct
analogue in terms of implementation.
Huaiyu Zhu
>Steve Holden wrote:
>
>> Well, in my case I'm disagreeing that there ought to be a line at all.
>> If we
>> can have lists and tuples, I don't see any reason why we couldn't have
>> two
>> flavours of set as well.
>
>But we _don't_ have two flavors of dictionaries. That's the most direct
>analogue in terms of implementation.
What prevents us from having both of them in the future?
Huaiyu
Huaiyu Zhu
>state, completely outside the control of the container. So the hard
>question is: What happens when a mutable object changes its value, such
>that it effects the arrangement of the set? How does the container get
>notified of this change (which as far as I know there is no standard way
>to test in Python), and what happens when a value collision occurs
>within the set? Does one object get disposed? If so, which one?
Conclusion: Mutable objects cannot be consistently hashed by contents.
There is no escape the fact that mutable and immutable objects are
fundamentally different. Mathematically a mutable set is a sequence of sets
indexed by time.
The solution appears to be:
- Allow mutable and immutable flavors of objects.
- Mutable objects are hashed by identity.
- Immutable objectas are hashed by content.
No change would then hanve the undesirable effect you described.
Huaiyu
Huaiyu Zhu
>I believe (without any worked-out justification) that Python could actually
>perform exactly the same comutations as it does now even if lists were
>removed: it would simply be more awkward and less efficient to compute with
>tuples, which are immutable.
a = [1, 2, 3]
b = a
b += [4, 5, 6]
print a
To achieve this with tuples you need to wrap them up in some other objects,
which is effectively another implementation of lists.
>If sets were to become a Python type I would expect that it would be useful
>to have both mutable and immutable variants, in just the same way as the
>sequences do.
That is indeed the most sensible solution. I'd even argue for two flavors
of dicts and two flavors of strings, too.
When two related things have different advantages over each other under
different circumstances, it is fruitless to argue which should be the ONE.
Better to have both.
It might even be easier to implement two flavors of everything if *every
kind* of object has a mutability flag.
Huaiyu
Erik Max Francis
> The solution appears to be:
> - Allow mutable and immutable flavors of objects.
> - Mutable objects are hashed by identity.
> - Immutable objectas are hashed by content.
>
> No change would then hanve the undesirable effect you described.
But then you can easily have collisions by value between the mutable and
immutable objects. That doesn't seem like a very good implementation of
a set.
Huaiyu Zhu
>
>> The solution appears to be:
>> - Allow mutable and immutable flavors of objects.
>> - Mutable objects are hashed by identity.
>> - Immutable objectas are hashed by content.
>>
>> No change would then hanve the undesirable effect you described.
>
>But then you can easily have collisions by value between the mutable and
>immutable objects. That doesn't seem like a very good implementation of
>a set.
There need to be a different equal operator === (read as "always equal")
that is used to compare keys. For example, the following
a = {1, 2}
b = a
c = {1, 2} const
d = {1, 2} const
implies a == b == c == d, a === b, c === d, but not a === c. Therefore "a
in setA" does not imply "c in setA", nor vice versa, even though a==c. The
following semantical restrictions should apply
id(a) === id(b) implies a === b
a === b implies a==b
a === b implies hash(a) === hash(b)
a == b, a is const, b is const implies a === b
Yes, I know this solution is complicated, but all the proposed solutions
discussed so far map to some subset of this solution. All the disagreements
were about which subset should be chosen. I think that every part of this
solution has been proposed by someone.
It is fairly obvious that with mutable objects, equality at an instant in
time is different from equality for all times. There will never be
concensus about which should be uniquely blessed, because both are useful.
Huaiyu
Delaney, Timothy
>
> - mutable sets are more practical. If one needs to use set as
> a dict key,
> let him convert it to sorted tuple and do so. I think, it's a
> rare case.
> Much more rare than need to append element to the set.
This is exactly what I was going to say, but Roman beat me to it.
s = {-}
d = {}
s |= 1
s |= 2
t = tuple(s)
d[t] = s
For this to work, the following things would need to be true.
1. For the sets s1 and s2, if s1 == s2, tuple(s1) == tuple(s2) must be true.
2. For this to work, set.__iter__ must return an iterator which returns
items in a guaranteed order. It would not be sufficient to return the items
of a sorted list - then you have the problem of instances of two different
classes that compare equal but are sorted in arbitrary order. However, in
order for s1 to equal s2, we must already have a guaranteed order for the
comparison, so this should be trivial.
Tim Delaney
Ian Bicking
> id(a) === id(b) implies a === b
> a === b implies a==b
> a === b implies hash(a) === hash(b)
> a == b, a is const, b is const implies a === b
This is kind of like in Scheme, which has four equal functions -- eq?,
eqv?, equal? and =. eq? is the same as "is". equal? and = are like
"==" (= in Scheme is just for numbers). You are proposing the middle
ground of eqv? (stands for equivalent)
R5RS probably clarifies the semantics for eqv? in Scheme, it might be
useful to consider.
Ian
Kragen Sitaker
> I believe 2. is more stringent:
>
> equal objects iff equal hash values
That cannot be, unless your hash values are potentially very large
(e.g. longs, or strings).
Erik Max Francis
> There need to be a different equal operator === (read as "always
> equal")
> that is used to compare keys.
No doubt such a proposal immediately would doom a revised PEP to
failure.
But that isn't the real issue. The problem with hash/identity
collisions within a set is not that defining some metaequality is
problematic (which it is), it's that after the set has been created, a
mutable object can have its value changed, potentially even to something
that clashes with another object (mutable or not) in the same set.
Python, as far as I know, does not have any facilities for some kind of
implicit callback to containers that happens whenever an object changes
state, and so this means that once you've already placed mutable objects
in a set, they can change value willy nilly and completely break the
invariant of the set (namely that no two contained objects are
identical), essentially defeating the whole purpose for the set in the
first place.
This issue exists regardless of whether you come up with some concept of
metaequality or not; it will be present as long as the set can contain
mutable objects.
Kragen Sitaker
> So I know perfectly well that immutable objects can simulate in-place
> operations. The question is whether the performance hit you take is
> significant or not. Since it _can_ be (try a large loop on a string with +=
> and watch your machine hit a wall), I tend to be of the opinion that unless
> there's a compelling reason to make the objects immutable, one is better off
> by not forcing the performance penalty. Simply because it makes the language
> more scalable and worry-free.
Immutable objects need to be copied to effect small changes; mutable
objects can't be safely shared between code written by people who
don't communicate, and must therefore be copied at every library
boundary. Which one is a larger performance penalty depends on your
application. Most applications benefit from a mixture of some mutable
and some immutable objects, although as jb points out, the semantics
of immutable objects can be implemented efficiently with
behind-the-scenes mutation at the cost of some compiler complexity.
Mutability tends toward surprising interactions and aliasing bugs, of
course. Saying it makes the language more "worry-free" is the
farthest thing from the truth.
Fernando Pérez
>> by not forcing the performance penalty. Simply because it makes the
>> language more scalable and worry-free.
>
> Immutable objects need to be copied to effect small changes; mutable
> objects can't be safely shared between code written by people who
> don't communicate, and must therefore be copied at every library
> boundary. Which one is a larger performance penalty depends on your
> application. Most applications benefit from a mixture of some mutable
> and some immutable objects, although as jb points out, the semantics
> of immutable objects can be implemented efficiently with
> behind-the-scenes mutation at the cost of some compiler complexity.
>
> Mutability tends toward surprising interactions and aliasing bugs, of
> course. Saying it makes the language more "worry-free" is the
> farthest thing from the truth.
Good point. It makes it 'worry-free' in the direction of performance scaling
when you can deal with the in-place issues (the kind of issues I'm used to
dealing with in scientific computing) at the cost of introducing worries in
terms of potentially subtle bugs. A great example of the contrast is the
difference in slicing behavior of python lists (a copy operation) versus
numeric arrays (an in-place reference). For me, numeric arrays behave the way
I want them (fast) but I'm always aware of not stepping on the mine which
in-place referencing can be: it buys me speed, but I must be careful.
As always, it's a tradeoff. When I said worry-free I was only considering my
perspective: scientific computing where performance matters a lot. I'm
already so happy to have python's forgiveness and easiness that I don't mind
a few places where care must be exterted. It's already allowing me to forgo
raw C for many things! But you are right in pointing a different direction
for the problem.
Cheers,
f.
Bernhard Herzog
> >If an object is stored in a dict as a key, the only things that matter
> >are that
> >
> >1. its hash value doesn't change as long as the object is used as a key.
>
> Doesn't this mean, in practice, that it is immutable?
Not necessarily. If the hash value can change if the state of the object
changes, you have to make sure that you don't change the object in such
a way as long as it's used as a key in a dict.
The easiest way to achieve this is of course to have the hash value
constant for the life-time of the object.
> To me, this requirement is just shifting responsabilities from one
> place to the other and not really solving the problem.
It may, yes. It's certainly not the best solution for objects in a set.
> >2. equal objects have equal hash values
> >
> >There may be some more subtle requirements. I'm not sure what happens
> >when two objects that have the same hash value but do not compare eqal
> >at first later become equal, for instance.
>
> I believe 2. is more stringent:
>
> equal objects iff equal hash values
That can't work. Hash values are ints which today means that it's a C
long and therefore either 32bit or 64 bit on most machines. Obviously
there are far fewer possible hash values than strings for instance, so
there must be at least two strings which are unequal but have the same
hash value.
An easy example for hashes of ints:
Python 2.2 (#1, Jan 17 2002, 21:04:07)
[GCC 2.95.4 20011006 (Debian prerelease)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> -1 == -2
0
>>> hash(-1) == hash(-2)
1
>>>
Most of the time, i == hash(i) for any python int except -1, because -1
is indicates an error in the C-level equivalent of __hash__.
Roman Suzi
>
> Maybe we try to use quantitative arguments? Are there any suggestions for
> small benchmarks: we can use set-0.2 to see real efficiency (or lack of),
> etc.
>
> Any nice/classic set-using problems around?
My input:
-----------------------------------------------------
#!/usr/bin/env python2.2
from set import set
"""Making graph from adjency matrix"""
adjency = [
[0, 0, 1, 1, 0, 0, 1],
[1, 0, 0, 1, 0, 0, 1],
[0, 1, 1, 0, 0, 0, 1],
[1, 0, 1, 1, 0, 0, 0],
[0, 0, 1, 1, 1, 0, 1],
[0, 0, 1, 1, 0, 1, 1],
[0, 1, 1, 1, 0, 0, 0],
]
V = set(range(len(adjency)))
E = set([(i, j) for i in V for j in V if adjency[i][j]])
G = (V, E)
print G
---------------------------------------------------------
Sincerely yours, Roman A.Suzi
--
- Petrozavodsk - Karelia - Russia - mailto:r...@onego.ru -
Roman Suzi
Maybe we try to use quantitative arguments? Are there any suggestions for
small benchmarks: we can use set-0.2 to see real efficiency (or lack of),
etc.
Any nice/classic set-using problems around?
Sincerely yours, Roman A.Suzi
Gonçalo Rodrigues
Ah, thanks for the clarification. Since nowadays I only program in
Python, when I see int i see integer-arbitrarily-big.
>An easy example for hashes of ints:
>
>Python 2.2 (#1, Jan 17 2002, 21:04:07)
>[GCC 2.95.4 20011006 (Debian prerelease)] on linux2
>Type "help", "copyright", "credits" or "license" for more information.
>>>> -1 == -2
>0
>>>> hash(-1) == hash(-2)
>1
>>>>
>
>Most of the time, i == hash(i) for any python int except -1, because -1
>is indicates an error in the C-level equivalent of __hash__.
>
> Bernhard
Best regards,
Gonçalo Rodrigues
Huaiyu Zhu
>
>> There need to be a different equal operator === (read as "always
>> equal")
>> that is used to compare keys.
>
>No doubt such a proposal immediately would doom a revised PEP to
>failure.
That's the main reason I've been thinking about this for two years without
saying much about it. It is necessary. It will not be accepted. What a
pity.
>
>But that isn't the real issue. The problem with hash/identity
>collisions within a set is not that defining some metaequality is
>problematic (which it is), it's that after the set has been created, a
>mutable object can have its value changed, potentially even to something
>that clashes with another object (mutable or not) in the same set.
As I said several times before (perhaps in a diverging thread), mutable
objects should only be compared by identity, not by value. Therefore if
a===b, then their contents are guaranteed to be alwasy equal. Mutable and
immutable objects are never "always equal":
a = {1,2}
b = {1,2} const
a === b # false
a == b # true
a.add(3)
print a # {1,2,3}
a === b # false
a == b # false
That is, "==" only cares about an instant, but "===" cares for eternity.
>Python, as far as I know, does not have any facilities for some kind of
>implicit callback to containers that happens whenever an object changes
>state, and so this means that once you've already placed mutable objects
>in a set, they can change value willy nilly and completely break the
>invariant of the set (namely that no two contained objects are
>identical), essentially defeating the whole purpose for the set in the
>first place.
Does not matter. If (a===b), they are refering to the same object.
Whatever their contents are change to, they are changed together. If
not(a===b), then changing values of a and b will not result in (a===b), even
at times when (a==b).
This operator is very similar to "is", except that it is semantics-oriented
instead of implementation-oriented. That is, there would not be "1 is 1"
but "101 is not 101" kind of stuff.
The main mental gymnastic needed is regarding "===" as the identity
operator, "==" only as the equality operator. Two things can be equal at a
time but still not identical. Thus in the the above example a and b are
indeed *not* identical, even at the time when their values are equal.
Another mental gymnastic needed is realizing that mutable sets, however
useful they are, are not mathematical sets. The main difference being that
their identities are not defined by their contents. The mathematical model
would be a time sequence of sets, which does not have much practical use
here, except to show that "{1,2} const" and "{1,2}" are two entirely
different beasts.
>This issue exists regardless of whether you come up with some concept of
>metaequality or not; it will be present as long as the set can contain
>mutable objects.
It does not depend on mutability per se, but rather on whether mutations
disturb identity. The identity operator "===" is so defined that it is not
changed by mutations.
Huaiyu