A question on modification of a list via a function invocation

[Rustom Mody]

On Thursday, September 7, 2017 at 6:52:04 PM UTC+5:30, Gregory Ewing wrote:
> Rustom Mody wrote:
> 
> > I said: In that case please restate the definition of 'is' from the manual which 
> > invokes the notion of 'memory' without bringing in memory.
> 
> I don't know whether it's in the manual, but at least for
> mutable objects, there is a way to define the notion of
> "same object" that doesn't require talking about "memory":
> 
> Two names refer to the same object if and only if mutations
> made through one are visible through the other.

Seems a sensible comment!

[Aside from the fact that 'visible' is likely ill or circularly defined — my 
other comment to Stefan. But lets just ignore that for now and assume that 
'visible' has no grey/dispute areas]

> 
> Python has definite rules concerning when mutable objects
> will be the same or not, and every correct implementation
> must conform to them. In that sense it's a fundamental
> concept that doesn't depend on implementation.

I'd like to know what these rules are

> 
> There is more leeway when it comes to immutable objects;
> implementations are free to cache and re-use them, so
> well-written code avoids depending on the result of
> "is" for immutable objects.

Which sounds like saying that 'isness' of immutables is ill/un-defined
Not that I object if this is said
My objection is to the claim that the isness of python's is and the isness of
'conceptually-same' are the same.

I believe that your definition of same and the one I earlier gave are similar 
(same?? Not sure)

Repeating here for ease: (with some clarifications)

We say equivalence relation R is coarser than S is
xSy ⇒ xRy

So x is y  ⇒ x == y but not (necessarily) vice versa

However there are not 2 but 3 equivalence relations:
1. == — mathematical, too coarse to understand nuances of python semantics
2. is — machine representation, too fine to be useful
3. graph (or topological) equality which experienced pythonistas have internalized
in understanding when two data structures are same or different
[Roughly Anton's diagrams that are beyond my drawing capability!]


And yet pythonistas need 3 to understand python data structures
ie 3 captures pythonistas intuition of same better than 1 or 2

>>> a = [1,2]
>>> b = [a,a]
>>> c = [[1,2],[1,2]]
>>> b == c
True
>>> b is c
False
>>> p = [1,2]
>>> q = [p,p]
>>> r = [[1,2],[1,2]]
>>> q == r
True
>>> q is r
False
>>> b == q
True
>>> b == r
True
>>> b is q
False
>>> b is r
False

Now the pythonista understands that b and c may be math-= but have different structure
Whereas b is graph-equal to q
And c is graph-equal to r

However there is no available operation to show/see that distinction

The trouble is that graph-isomorphism is NP-complete so the crucial operation
cannot be reasonably implemented

To make it more clear
≡ is graph-equal, ie 2. The pythonista understands that
b ≢ c ## ≡ is finer than ==
Whereas
b ≡ r
ie ≡ is coarser than is

And b and r are python-equivalent without any memory relation in the sense
that no sequence of valid operations applied to b and to r will tell them apart

— sometimes called 'trace-equivalence'