A frozendict type is a common request from users and there are various implementations.
ISTM, this request is never from someone who has a use case.
One of my colleagues implemented recently its own frozendict class (which the "frozendict" name ;-)). He tries to implement something like the PEP 351, not a generic freeze() function but a specialized function for his use case (only support list/tuple and dict/frozendict if I remember correctly). It remembers me the question: why does Python not provide a frozendict type? Even if it is not possible to write a perfect freeze() function, it looks like some developers need sort of this function and I hope that frozendict would be a first step in the good direction. Ruby has a freeze method. On a dict, it provides the same behaviour than frozendict: the mapping cannot be modified anymore, but values are still mutable. http://ruby-doc.org/core-1.9.3/Object.html#method-i-freeze
Many experienced Python users simply forget that we have a frozenset type. We don't get bug reports or feature requests about the type.
I used it in my previous work to declare the access control list (ACL) on services provided by XML-RPC object. To be honest, set could also be used, but I chose frozenset to ensure that my colleagues don't try to modify it without understanding the consequences of such change. It was not a protecting against evil hackers from the Internet, but from my colleagues :-) Sorry, I didn't find any bug in frozenset :-) My usage was just to declare a frozendict and then check if an item is in the set, and it works pretty well!
P.S. The one advantage I can see for frozensets and frozendicts is that we have an opportunity to optimize them once they are built (optimizing insertion order to minimize collisions, increasing or decreasing density, eliminating dummy entries, etc). That being said, the same could be accomplished for regular sets and dicts by the addition of an optimize() method.
You can also implement more optimizations in Python peephole or PyPy JIT because the mapping is constant and so you can do the lookup at compilation, instead of doing it at runtime. Dummy example: --- config = frozendict(debug=False) if config['debug']: enable_debug() --- config['debug'] is always False and so you can just drop the call to enable_debug() while compiling this code. It would avoid the need of a preprocessor in some cases (especially conditional code, like the C #ifdef). Victor