Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A “frozen” dictionary for Python

lwn.net

Post reply on HN
Print view View original

91–100 of 172 posts

Re: A “frozen” dictionary for Python

#91

Post by zahlman »

vanviegen wrote: post #86
zahlman wrote: post #62

Earlier quoted context omitted.

> Ordering, like stability in sorting, is an incredibly useful property. I can't say I've noticed any good reasons to rely on it. Didn't reach for `OrderedDict` often back in the day either. I've had more use for actual sorting than for preserving the insertion order.

Indeed! I don't understand why it isn't more common for stdlibs to include key-ordered maps and sets. Way more useful than insertion ordering.

Presumably because it involves different performance characteristics.

Re: A “frozen” dictionary for Python

#93

Post by LtWorf »

jonathaneunice wrote: post #58
zahlman wrote: post #40

Earlier quoted context omitted.

> Also worth noting that understanding changes over time. Remember when GvR and the rest of the core developers argued adamantly against ordered dictionaries? Haha! Good times! The new implementation has saved space, but there are opportunities to save more space (specifically after deleting keys) that they've now denied themselves by offering the ordering guarantee.

Ordering, like stability in sorting, is an incredibly useful property. If it costs a little, then so be it. This is optimizing for the common case, where memory is generally plentiful and dicts grow more than they shrink. Python has so many memory inefficiencies that occasional tombstones in the dict internal structure is unlikely to be a major effect. If you're really concerned, do `d = dict(d)` after aggressive del…

Does your code actually rely on that? I've never once needed it.

Re: A “frozen” dictionary for Python

#94

Post by zelphirkalt »

Someone wrote: post #69
sesm wrote: post #61

Earlier quoted context omitted.

Since that time HAMT was invented and successfully used in Scala and Clojure, so this talk didn't age well.

Wikipedia ( https://en.wikipedia.org/wiki/Hash_array_mapped_trie ) links to the paper describing HAMT ( https://infoscience.epfl.ch/server/api/core/bitstreams/f66a3... ) and claims that is from 2000. That talk is from 2016.

Do you know of any implementation, that is well annotated/commented, so that it is easy to understand?

Re: A “frozen” dictionary for Python

#95

Post by chriswarbo »

tremon wrote: post #63
chriswarbo wrote: post #57

Earlier quoted context omitted.

> Theoretically, could `set` be a subclass of `frozenset` (and `dict` of `frozendict`)? At one extreme: sure, anything can be made a subclass of anything else, if we wanted to. At the other extreme: no, since Liskov substitution is an impossibly-high bar to reach; especially in a language that's as dynamic/loose as Python. For example, consider an expression like '"pop" in dir(mySet)'

> consider an expression like '"pop" in dir(mySet)' class frozenset: pass class set(frozenset): def pop(self, key): pass I don't see why hasattr(mySet, 'pop') should be a problem here?

> I don't see why hasattr(mySet, 'pop') should be a problem here?

I never said it's a problem (and I never said it's not!). I was specifically addressing two things:

- The "theoretical" nature of the question I quoted (i.e. ignoring other aspects like subjectivity, practicality, convention, etc.)

- The reasoning about "Liskov violation", which was quoted further up this thread.

For context, here's Liskov's definition of their principle (from https://en.wikipedia.org/wiki/Liskov_substitution_principle ):

> Barbara Liskov and Jeannette Wing described the principle succinctly in a 1994 paper as follows:[1]

> > Subtype Requirement: Let ϕ(x) be a property provable about objects x of type T. Then ϕ(y) should be true for objects y of type S where S is a subtype of T.

My expression `"pop" in dir(mySet)` gives an explicit example of how `set` and `frozenset` are not subtypes of each other (regardless of how they're encoded in the language, with "subclasses" or whatever). In this case `ϕ(x)` would be a property like `'"pop" in dir(x)' = 'False'`, which holds for objects x of type frozenset. Yet it does not hold for objects y of type set.

Your example of `hasattr(mySet, 'pop')` gives another property that would be violated.

My point is that avoiding "Liskov violations" is ("theoretically") impossible, especially in Python (which allows programs to introspect/reflect on values, using facilities like 'dir', 'hasattr', etc.).

(FYI I became rather jaded on the Liskov substitution principle after reading https://okmij.org/ftp/Computation/Subtyping )

Re: A “frozen” dictionary for Python

#96

Post by seanhunter »

jonathaneunice wrote: post #58
zahlman wrote: post #40

Earlier quoted context omitted.

> Also worth noting that understanding changes over time. Remember when GvR and the rest of the core developers argued adamantly against ordered dictionaries? Haha! Good times! The new implementation has saved space, but there are opportunities to save more space (specifically after deleting keys) that they've now denied themselves by offering the ordering guarantee.

Ordering, like stability in sorting, is an incredibly useful property. If it costs a little, then so be it. This is optimizing for the common case, where memory is generally plentiful and dicts grow more than they shrink. Python has so many memory inefficiencies that occasional tombstones in the dict internal structure is unlikely to be a major effect. If you're really concerned, do `d = dict(d)` after aggressive del…

Ordering is specifically a property (useful or not) that a set doesn't have. You need a poset for it to be ordered.

I would expect to use a different data structure if I needed an ordered set.

Re: A “frozen” dictionary for Python

#97

Post by tremon »

chriswarbo wrote: post #95
tremon wrote: post #63

Earlier quoted context omitted.

> consider an expression like '"pop" in dir(mySet)' class frozenset: pass class set(frozenset): def pop(self, key): pass I don't see why hasattr(mySet, 'pop') should be a problem here?

> I don't see why hasattr(mySet, 'pop') should be a problem here? I never said it's a problem (and I never said it's not!). I was specifically addressing two things: - The "theoretical" nature of the question I quoted (i.e. ignoring other aspects like subjectivity, practicality, convention, etc.) - The reasoning about "Liskov violation", which was quoted further up this thread. For context, here's Liskov's definition…

> > Subtype Requirement: Let ϕ(x) be a property provable about objects x of type T. Then ϕ(y) should be true for objects y of type S where S is a subtype of T.

This says "if hasattr(parent, 'pop') == True then hasattr(child, 'pop') must be True". This is not violated in this case, since hasattr(parent, 'pop') is False. If you want to extend the above definition so that negative proofs concerning the parent should also hold true for the child, then subtyping becomes impossible since all parent and child types must be identical, by definition.

Re: A “frozen” dictionary for Python

#98

Post by rurban »

> so having a safe way to share dictionaries between threads will be a boon

Since only the keys are const, the values not, frozendict is not thread-safe per se. There needs to be a small lock around the value getter and setter.

Re: A “frozen” dictionary for Python

#99

Post by varelaz »

rurban wrote: post #98

> so having a safe way to share dictionaries between threads will be a boon Since only the keys are const, the values not, frozendict is not thread-safe per se. There needs to be a small lock around the value getter and setter.

it's thread safe on operations on the dict but not on the values. Same relates to other immutable structures like tuples. Lock will not help here cause unsafety comes from operation on value after value is obtained.
Post reply on HN