list comprehension problem

[Steven D'Aprano]

On Sat, 31 Oct 2009 14:12:40 -0400, Terry Reedy wrote:

> alex23 wrote:
>> Terry Reedy <tjre... at udel.edu> wrote:
>>> alex23 wrote:
>>>> You're completely wrong. Immutability has nothing to do with
>>>> identity,
> ...
>  > I'm honestly not getting your point here.
> 
> Let me try again, a bit differently.
> 
> I claim that the second statement, and therefor the first, can be seen
> as wrong. I also claim that (Python) programmers need to understand why.
> 
> In mathematics, we generally have immutable values whose 'identity' is
> their value. There is, for example, only one, immutable, empty set.


I think it's more than that -- I don't think pure mathematics makes any 
distinction at all between identity and equality. There are no instances 
at all, so you can't talk about individual values. It's not that the 
empty set is a singleton, because the empty set isn't a concrete object-
with-existence at all. It's an abstraction, and as such, questions of 
"how many separate empty sets are there?" are meaningless.

There are an infinite number of empty sets that differ according to their 
construction:

The set of all American Presidents called Boris Nogoodnik.
The set of all human languages with exactly one noun and one verb.
The set of all fire-breathing mammals.
The set of all real numbers equal to sqrt(-1).
The set of all even prime numbers other than 2.
The set of all integers between 0 and 1 exclusive.
The set of all integers between 1 and 2 exclusive.
The set of all positive integers between 2/5 and 4/5.
The set of all multiples of five between 26 and 29.
The set of all non-zero circles in Euclidean geometry where the radius 
equals the circumference.
...

I certainly wouldn't say all fire-breathing mammals are integers between 
0 and 1, so those sets are "different", and yet clearly they're also "the 
same" in some sense. I think this demonstrates that the question of how 
many different empty sets is meaningless -- it depends on what you mean 
by different and how many.



> In informatics, and in particular in Python, in order to have
> mutability, we have objects with value and an identity that is separate
> from their value.

I think you have this backwards. We have value and identity because of 
the hardware we use -- we store values in memory locations, which gives 
identity. Our universe imposes the distinction between value and 
identity. To simulate immutability and singletons is hard, and needs to 
be worked at.

Nevertheless, it would be possible to go the other way. Given 
hypothetical hardware which only supported mutable singletons, we could 
simulate multiple instances. It would be horribly inefficient, but it 
could be done. Imagine a singleton-mutable-set implementation, something 
like this:

class set:
    def __init__(id):
        return singleton
    def add(id, obj):
        singleton.elements.append((id, obj))
    def __contains__(id, element)
        return (id, obj) in singleton.elements


and so forth.

You might notice that this is not terribly different from how one might 
define non-singleton sets. The difference being, Python sets have 
identity implied by storage in distinct memory locations, while this 
hypothetical singleton-set has to explicitly code for identity.



> There can be, for example, multiple mutable empty
> sets. Identity is important because we must care about which empty set
> we add things to. 'Identity' is only needed because of 'mutability', so
> it is mistaken to say they have nothing to do with each other.

True, but it is not a mistake to say that identity and mutability are 
independent: there are immutable singletons, and mutable singletons, and 
immutable non-singletons, and mutable non-singletons. Clearly, knowing 
that an object is mutable doesn't tell you whether it is a singleton or 
not, and knowing it is a singleton doesn't tell you whether it is 
immutable or not.

E.g. under normal circumstances modules are singletons, but they are 
mutable; frozensets are immutable, but they are not singletons.


> Ideally, from both a conceptual and space efficiency view, an
> implementation would allow only one copy for each value of immutable
> classes. 

Ideally, from a complexity of implementation view, an implementation 
would allow an unlimited number of copies of each value of immutable 
classes.


> This is what new programmers assume when they blithely use 'is'
> instead of '==' (as would usually be correct in math).

Nah, I think you're crediting them with far more sophistication than they 
actually have. I think most people in general, including many new 
programmers, simply don't have a good grasp of the conceptual difference 
between equality and identity. In plain language, "is" and its 
grammatical forms "be", "are", "am" etc. have many meanings:

(1) Set membership testing:
Socrates is a man.
This is a hammer.

(2) Existence:
There is a computer language called Python.
There is a monster under the bed.

(3) Identity:
Iron Man is Tony Stark.
The butler is the murderer.

(4) Mathematical equality:
If x is 5, and y is 11, then y is 2x+1.

(5) Equivalence:
The winner of this race is the champion.
The diameter of a circle is twice the radius.

(6) Metaphoric equivalence:
Kali is death.
Life is like a box of chocolates.

(7) Testing of state:
My ankle is sore.
Fred is left-handed.

(8) Consequence
If George won the lottery, he would say he is happy.

(9) Cost
A cup of coffee is $3.


Only two of these usages work at all in any language I know of: equality 
and identity testing, although it would be interesting to consider a 
language that allowed type testing:

45 is an int  -> returns True
"abc" is a float -> returns False

Some languages, like Hypertalk (by memory) and related languages, make 
"is" a synonym for equals.


> However, for time efficiency reasons, there is no unique copy guarantee,
> so one must use '==' instead of 'is', except in those few cases where
> there is a unique copy guarantee, either by the language spec or by
> one's own design, when one must use 'is' and not '=='.  Here 'must'
> means 'must to be generally assured of program correctness as intended'.
> 
> We obviously agree on this guideline.


Yes. 



-- 
Steven