Python sets, frozensets, and literals

A Python "frozenset" is simply a set object that is immutable—the objects it contains are determined at initialization time and cannot be changed thereafter. Like sets, frozensets are built into the language, but unlike most of the other standard Python types, there is no way to create a literal frozenset object. Changing that, by providing a mechanism to do so, was the topic of a recent discussion on the python-ideas mailing list.

Dictionaries, lists, tuples, and sets, which are called collections in Python, can all be created "on the fly" in the language using a variety of brackets:

    >>> a_dict = { 'a' : 42 }
    >>> a_set = { 'a', 42 }
    >>> a_list = [ 'a', 42 ]
    >>> a_tuple = ( 'a', 42 )

    >>> print(a_dict, a_set, a_list, a_tuple)
    {'a': 42} {42, 'a'} ['a', 42] ('a', 42)

As with mathematical sets, Python sets only contain a single element of a given value; adding the same value multiple times does not change the set. Continuing on from the example above:

    >>> a_set.add('b')
    >>> a_set.add('a')
    >>> a_set
    {'b', 42, 'a'}

    >>> an_fset = frozenset(a_set)
    >>> an_fset
    frozenset({'b', 42, 'a'})
    >>> an_fset.add('c')
    Traceback (most recent call last):
      File "<stdin>", line 1, in <module>
    AttributeError: 'frozenset' object has no attribute 'add'

    >>> new_set = { a_set }
    Traceback (most recent call last):
      File "<stdin>", line 1, in <module>
    TypeError: unhashable type: 'set'
    >>> new_set = { an_fset }
    >>> new_set
    {frozenset({'b', 42, 'a'})}

    >>> fset2 = frozenset(a_set)
    >>> new_set = { fset2, an_fset }
    >>> new_set
    {frozenset({'b', 42, 'a'})}

Literal frozensets?

It is against that backdrop that Steven D'Aprano posted a query about adding a way to create frozensets on the fly in some fashion, like with the other built-in collection types. His jumping off point was an enhancement request that noted the most recent Python compiler already takes a shortcut when building literal sets of constant values; it creates them as frozensets, rather than as mutable sets. D'Aprano used the dis module to disassemble and display the bytecode for a simple Python statement:

CPython already has some neat optimizations in place to use frozensets instead of sets, for example:

>>> import dis
>>> dis.dis("x in {1, 2, 3}")
  1           0 LOAD_NAME                0 (x)
              2 LOAD_CONST               0 (frozenset({1, 2, 3}))
              4 CONTAINS_OP              0
              6 RETURN_VALUE

and the compiler can build frozensets of literals as a constant.

The set literal "{1, 2, 3}" is built as a constant frozenset (since it cannot be changed) by the compiler and the bytecode loads it directly. But, as he demonstrated with another example, when the programmer wants a frozenset of constant values themselves, the compiler creates a frozenset constant, turns it into a set, and calls frozenset() at run time to create the frozenset it already had: "So to get the frozenset we want, we start with the frozenset we want, and make an unnecessary copy the long way o_O".

It should be noted that his second example, and the one shown in the enhancement request, only occur in the under-development Python 3.11 version of the language. The example shown above, though, works in Python 3.8 (and likely earlier versions), so the compiler clearly has the ability needed to create frozenset constants. But all sets obviously cannot just be switched to frozensets. Beyond that, since the frozenset() call is made at run time, there is the possibility that the function has been shadowed or monkey-patched to do something subtly (or not-so-subtly) different. D'Aprano had a suggestion:

It seems to me that all of the machinery to make this work already exists. The compiler already knows how to create frozensets at compile-time, avoiding the need to lookup and call the frozenset() builtin. All we need is syntax for a frozenset display.

How does this work for you?

    f{1, 2, 3}

As might be guessed, the "spelling" of the syntax was not pleasing to some. Chris Angelico objected that it would look too much like other constructs that have a different interpretation:

While it's tempting, it does create an awkward distinction.

f(1, 2, 3) # look up f, call it with parameters
f[1, 2, 3] # look up f, subscript it with paramters
f{1, 2, 3} # construct a frozenset

And that means it's going to be a bug magnet.

He suggested using angle brackets instead (e.g. <1, 2, 3>), if the parser could be made to handle it. D'Aprano thought that the switch to the PEG parser might enable using angle brackets, but he was not in favor of doing so:

Reading this makes my eyes bleed:

    >>> <1, 2, 3> < <1, 2, 3, 4>
    True

D'Aprano said that Python's f-strings provide another example of how "f" can be used in a potentially confusing way; beyond that, "r" can be used to prefix raw strings, but be used as a function or array name too. "I don't think that f{} will be any more of a bug magnet than f"" and r"" already are." Inevitably, other suggestions were made, including Rob Cliffe's for "fs{1, 2, 3}" to avoid the possible ambiguity of simply using "f" and Greg Ewing's joke suggestion of using the Unicode snowflake ("❄{1, 2, 3}"). Matthew Barnett (MRAB) suggested double curly brackets, which would open up another possibility:

How about doubling-up the braces:

    {{1, 2, 3}}

and for frozen dicts:

    {{1: 'one', 2: 'two', 3: 'three'}}

if needed?

At least currently, there is no built-in frozendict; it was rejected when proposed back in 2012. But either of those two expressions currently raise exceptions, because sets and dictionaries are not hashable, which means that syntax could potentially be used. As Barnett pointed out, though, nested frozensets might lead to curly-brace overload.

Oscar Benjamin wondered about whether frozenset comprehensions (analogous to list comprehensions) should be supported. A set comprehension like the following:

    >>> {x**2 for x in range(10)}
    {0, 1, 64, 4, 36, 9, 16, 49, 81, 25}

Advantages

There were questions about the advantages of adding some kind of literal frozenset syntax. In his initial message, D'Aprano said that the idea had come up before, most recently in 2018, where it was suggested for consistency's sake. Inada Naoki recognized the inconsistency of not having a way to specify a literal frozenset, but was only lukewarm on adding syntax for it unless improvements to existing code could be demonstrated. Christopher Barker also thought that consistency was behind the current effort, but D'Aprano said that there were other reasons for it:

CPython already has all the machinery needed to create constant frozensets of constants at compile time. It already implicitly optimizes some expressions involving tuples and sets into frozensets, but such optimizations are fragile and refactoring your code can remove them. Ironically, that same optimization makes the explicit creation of a frozenset needlessly inefficient.

He noted some uses of frozenset in the standard library that might benefit from the new syntax, but does not think the change will be earth-shattering by any means:

The benefit is not huge. This is not list comprehensions or decorator syntax, which revolutionized the way we write Python, it is an incremental improvement. If the compiler didn't already have the machinery in place for building compile-time constant frozensets, this might not be worth the effort.

D'Aprano also described some of the problems that can arise with the current state of affairs. Creating a frozenset is dependent on the frozenset() function, unlike, say, creating a list: "[1, 2, 3] is guaranteed to return a genuine list, even if the name 'list' is deleted, shadowed or replaced". In addition, there are current optimizations that are done, but that are somewhat fragile:

If you are writing if x in ("this", "that", "another", "more") then you probably should be using a frozenset literal, since membership testing in sets is faster than linear search of a tuple.

I think that the CPython peephole optimizer actually replaces that tuple with a frozenset, which is cool, but you can defeat that optimization and go back to slow linear search by refactoring the code and giving the targets a name:

    targets = ("this", "that", "another", "more")
    if x in targets: ...

In the end, this "feature" would not be a big change, either in CPython, itself, or for the Python ecosystem, but it would remove a small wart that might be worth addressing. Consistency and avoiding needless work when creating a literal frozenset both seem like good reasons to consider making the change. Whether a Python Enhancement Proposal (PEP) emerges remains to be seen. If it does, no major opposition arises, and the inevitable bikeshed-o-rama over its spelling ever converges, it just might appear in an upcoming Python—perhaps even Python 3.11 in October.