Semantics of ==

[Axel Boldt]

Re: Semantics of ==

Erik Max Francis <max@alcyone.co m>[color=blue]
> Axel Boldt wrote:
>[color=green]
> > I couldn't find that algorithm in the language reference, only in 5.9:
> > "Tuples and lists are compared lexicographical ly using comparison of
> > corresponding elements. This means that to compare equal, each element
> > must compare equal and the two sequences must be of the same type and
> > have the same length."
> >
> > That definition doesn't seem to fully specify equality of list values:
> > ...[/color]
>
> Sure it does; the rule can be used recursively.[/color]

....and then it can run into an infinite loop. I explained that for the
example s==w in the part you deleted. The recursion does not always
have a base case; the rule does not always give a definite truth
value.
[color=blue][color=green]
> > I hope that the
> > actual result received, i.e. s==w, is not implementation dependent?[/color]
>
> They're also equal in Jython. It wouldn't surprise me if you could find
> an implementation where they might not compare equal, because this is
> such a pathological case.[/color]

.... i.e. such a fun case. If there really is an implementation
dependency hidden in something as fundamental as == for lists, that'd
better be mentioned in the language reference.
[color=blue][color=green]
> > Is there a string
> > function analogous to pickle.dumps or repr which only takes values
> > into account, not internal structure?[/color]
>
> How can you define the value of an arbitrary object without reference to
> its internal structure?[/color]

Well, you claim that s and w have the same value yet different
internal structure, so you must work with some definition of "value"
that's different from internal structure. I don't know what it is, and
the language reference doesn't fully specify it.

I.e., I'm interesting in a function val : lists -> strings with the
property val(l1) == val(l2) iff l1 == l2. That would also considerably
clarify the semantics of == for lists, which I still don't understand.

Axel

[Erik Max Francis]

Re: Semantics of ==

Axel Boldt wrote:
[color=blue]
> ...and then it can run into an infinite loop. I explained that for the
> example s==w in the part you deleted. The recursion does not always
> have a base case; the rule does not always give a definite truth
> value.[/color]

But the == operator doesn't run into an infinite loop, so this is much
ado about nothing.
[color=blue]
> ... i.e. such a fun case. If there really is an implementation
> dependency hidden in something as fundamental as == for lists, that'd
> better be mentioned in the language reference.[/color]

I don't know what you're talking about here. The behavior you saw with
your s == w example is completely consistent with Python's definition of
equality and Python's definition of equal sequences. You have some
additional equivalence in your mind that simply does not apply to
Python.
[color=blue][color=green]
> > How can you define the value of an arbitrary object without
> > reference to
> > its internal structure?[/color]
>
> Well, you claim that s and w have the same value yet different
> internal structure, so you must work with some definition of "value"
> that's different from internal structure. I don't know what it is, and
> the language reference doesn't fully specify it.[/color]

1 and 1.0 have different internal structure, but they're equal. This is
an obvious existence proof that Python simply does not follow the
equivalence that you're thinking of.

Equality does _not_ indicate equivalence in internal structure in
Python. This is especially true in Python where users can define their
own equality behavior, so you can make it whatever you want -- you can
make your own instance that compares equal (or unequal) with absolutely
everything. If 1 == 1.0 didn't convince you, surely this will convince
you that equality and equivalence in internal structure are not related
in Python.
[color=blue]
> I.e., I'm interesting in a function val : lists -> strings with the
> property val(l1) == val(l2) iff l1 == l2. That would also considerably
> clarify the semantics of == for lists, which I still don't understand.[/color]

Why are you interested in such a function?

--
__ Erik Max Francis && max@alcyone.com && http://www.alcyone.com/max/
/ \ San Jose, CA, USA && 37 20 N 121 53 W && &tSftDotIotE
\__/ I do not promise to consider race or religion in my appointments.
I promise only that I will not consider them. -- John F. Kennedy

[Erik Max Francis]

Re: Semantics of ==

Axel Boldt wrote:
[color=blue]
> Like I said, it would clarify the semantics of == for lists. Another
> use would be to hash on values of lists.[/color]

What part of the semantics are you unclear about? Two sequences are
equal if they are element-wise equal. That is the definition that
people rely on, that's the definition that the interpreter uses, and
that definition is even consistent with the behavior you saw with the
self-referencing lists which for some reason surprised you.

--
__ Erik Max Francis && max@alcyone.com && http://www.alcyone.com/max/
/ \ San Jose, CA, USA && 37 20 N 121 53 W && &tSftDotIotE
\__/ Whoever named it necking was a poor judge of anatomy.
-- Groucho Marx

[Raymond Hettinger]

Re: Semantics of ==

[Axel Boldt][color=blue][color=green][color=darkred]
> > >>> l=[1]
> > >>> s=l
> > >>> l.append(s)
> > >>> w=[1]
> > >>> r=[1,w]
> > >>> w.append(r)
> > >>> s[/color][/color]
> [1, [...]][color=green][color=darkred]
> > >>> w[/color][/color]
> [1, [1, [...]]][color=green][color=darkred]
> > >>> s==w[/color]
> > True
> >
> > Note that they're equal, yet are printed differently.
> >[color=darkred]
> > >>> s[0]=2
> > >>> w[0]=2
> > >>> s==w[/color]
> > False
> >
> > All of a sudden they have become unequal.[/color][/color]

[John Roth][color=blue]
> You've got a recursive structure! I originally thought
> that the [...] was something you'd done to the printout,
> but it isn't.
>
> I think the original True is a bug. It's getting confused
> by the recursion.[/color]

Armin Rigo found and fixed this for Py2.4:

Python 2.4a0 (#46, Mar 23 2004, 01:55:44) [MSC v.1200 32 bit (Intel)] on win32
<snipped>[color=blue][color=green][color=darkred]
>>> s[/color][/color][/color]
[1, [...]][color=blue][color=green][color=darkred]
>>> w[/color][/color][/color]
[1, [1, [...]]][color=blue][color=green][color=darkred]
>>> s==w[/color][/color][/color]


Traceback (most recent call last):
File "<pyshell#9 >", line 1, in -toplevel-
s==w
RuntimeError: maximum recursion depth exceeded in cmp


Raymond Hettinger

[Isaac To]

Re: Semantics of ==

>>>>> "Raymond" == Raymond Hettinger <python@rcn.com > writes:

Raymond> [Axel Boldt][color=blue][color=green][color=darkred]
>> > >>> l=[1] > >>> s=l > >>> l.append(s) > >>> w=[1] > >>> r=[1,w] >
>> >>> w.append(r) > >>> s [1, [...]] > >>> w [1, [1, [...]]] > >>>[/color]
>> s==w > True[color=darkred]
>> >
>> > Note that they're equal, yet are printed differently.
>> >
>> > >>> s[0]=2 > >>> w[0]=2 > >>> s==w > False
>> >
>> > All of a sudden they have become unequal.[/color][/color][/color]

Raymond> [John Roth][color=blue][color=green]
>> You've got a recursive structure! I originally thought that the [...]
>> was something you'd done to the printout, but it isn't.
>>
>> I think the original True is a bug. It's getting confused by the
>> recursion.[/color][/color]

Raymond> Armin Rigo found and fixed this for Py2.4:

Raymond> Python 2.4a0 (#46, Mar 23 2004, 01:55:44) [MSC v.1200 32 bit
Raymond> (Intel)] on win32 <snipped>[color=blue][color=green][color=darkred]
>>>> s[/color][/color][/color]
Raymond> [1, [...]][color=blue][color=green][color=darkred]
>>>> w[/color][/color][/color]
Raymond> [1, [1, [...]]][color=blue][color=green][color=darkred]
>>>> s==w[/color][/color][/color]

Raymond> Traceback (most recent call last): File "<pyshell#9 >", line 1,
Raymond> in -toplevel- s==w RuntimeError: maximum recursion depth
Raymond> exceeded in cmp

I'm confused... what makes the new behaviour more "correct" than the original?

Regards,
Isaac.

[Axel Boldt]

Re: Semantics of ==

Erik Max Francis <max@alcyone.co m> wrote
[color=blue]
> What part of the semantics are you unclear about? Two sequences are
> equal if they are element-wise equal.[/color]

That definition is circular.
[color=blue]
> That is the definition that people rely on,[/color]

Yes.
[color=blue]
> that's the definition that the interpreter uses,[/color]

No.
[color=blue]
> and that definition is even consistent with the behavior you saw with the
> self-referencing lists which for some reason surprised you.[/color]

Yes, s==w is consistent with the definition, but s!=w would also have
been consistent with it.

Consider for instance the following definition:
* all strings and numbers are called "well-founded"
* a list is called well-founded if and only if all its elements are
well-founded.

l=[]
l.append(l)
Is l well-founded? Both answers "yes" and "no" are consistent with the
above definition. If you write a program to determine whether a given
list is well-founded, it will run into an infinite loop. Similarly, if
you try to write a program implementing the above simple-minded
definition of list-equality, it'll run into an infinite loop. Since
Python does not run into an infinite loop, it must use a different
definition.

Axel

[Isaac To]

Re: Semantics of ==

>>>>> "Axel" == Axel Boldt <axelboldt@yaho o.com> writes:

Axel> l=[] l.append(l) Is l well-founded? Both answers "yes" and "no"
Axel> are consistent with the above definition. If you write a program
Axel> to determine whether a given list is well-founded, it will run
Axel> into an infinite loop.

That depends on how you write the program. I can easily give you a program
that will tell you either this is or is not, depending on whether you like
it one way or the other---provided that I have a little bit of memory to
play with, or I'm allowed to look at my own back-trace.

Regards,
Isaac.

[Erik Max Francis]

Re: Semantics of ==

Axel Boldt wrote:
[color=blue]
> Erik Max Francis <max@alcyone.co m> wrote
>[color=green]
> > What part of the semantics are you unclear about? Two sequences are
> > equal if they are element-wise equal.[/color]
>
> That definition is circular.[/color]

No, because presumably you already understand what equality means for
two non-sequence objects.
[color=blue][color=green]
> > and that definition is even consistent with the behavior you saw
> > with the
> > self-referencing lists which for some reason surprised you.[/color]
>
> Yes, s==w is consistent with the definition, but s!=w would also have
> been consistent with it.[/color]

As I already demonstrated in your initial response, Python's behavior in
your examples was completely consistent with this definition, whether
you realize it or not. The cases that you thought shouldn't have been
equal were in fact equal, and the cases that you thought should have
been equal weren't, in fact, equal. I and several others carefully
demonstrated this to you, but you ignored us so that you could continue
ranting that Python's list equality is broken, when there is no evidence
that it is.
[color=blue]
> Consider for instance the following definition:
> * all strings and numbers are called "well-founded"
> * a list is called well-founded if and only if all its elements are
> well-founded.
>
> l=[]
> l.append(l)
> Is l well-founded? Both answers "yes" and "no" are consistent with the
> above definition.[/color]

No they aren't, since l's first element is a list, not a string or
number.

What is the point of this definition?

--
__ Erik Max Francis && max@alcyone.com && http://www.alcyone.com/max/
/ \ San Jose, CA, USA && 37 20 N 121 53 W && &tSftDotIotE
\__/ Drifting from woman-who-tries misconstrued / Shifting to
woman-wise -- Lamya

[Axel Boldt]

Re: Semantics of ==

Erik Max Francis <max@alcyone.co m> wrote[color=blue]
> Axel Boldt wrote:[color=green]
> > Erik Max Francis <max@alcyone.co m> wrote
> >[color=darkred]
> > > What part of the semantics are you unclear about? Two sequences are
> > > equal if they are element-wise equal.[/color]
> >
> > That definition is circular.[/color]
>
> No, because presumably you already understand what equality means for
> two non-sequence objects.[/color]

Yes, but a list can contain other lists, and even itself, as elements.
So in order to understand what equality for lists means, according to
the above definition, you already need to understand what equality for
lists means. That's what makes the definition circular. I thought we
had clarified that much a week ago.
[color=blue][color=green]
> > Consider for instance the following definition:
> > * all strings and numbers are called "well-founded"
> > * a list is called well-founded if and only if all its elements are
> > well-founded.
> >
> > l=[]
> > l.append(l)
> > Is l well-founded? Both answers "yes" and "no" are consistent with the
> > above definition.[/color]
>
> No they aren't, since l's first element is a list, not a string or
> number.[/color]

The above definition does not require that the first element of a
well-founded list be a string or number. It could also be a
well-founded list.
[color=blue]
> What is the point of this definition?[/color]

To show how easy it is to give circular definitions (and
non-terminating recursive functions) when dealing with lists.

Axel

[Andrew Bennetts]

Re: Semantics of ==

On Mon, Mar 29, 2004 at 04:26:34AM -0800, Axel Boldt wrote:[color=blue]
> Erik Max Francis <max@alcyone.co m> wrote[color=green]
> > Axel Boldt wrote:[color=darkred]
> > > Erik Max Francis <max@alcyone.co m> wrote
> > >
> > > > What part of the semantics are you unclear about? Two sequences are
> > > > equal if they are element-wise equal.
> > >
> > > That definition is circular.[/color]
> >
> > No, because presumably you already understand what equality means for
> > two non-sequence objects.[/color]
>
> Yes, but a list can contain other lists, and even itself, as elements.
> So in order to understand what equality for lists means, according to
> the above definition, you already need to understand what equality for
> lists means. That's what makes the definition circular. I thought we
> had clarified that much a week ago.[/color]

No, it makes the definition recursive. There's a difference.

-Andrew.

[Fred Mailhot]

Re: Semantics of ==

On 3/29/04 4:26 AM, "Axel Boldt" <axelboldt@yaho o.com> wrote:

[snip]
[color=blue][color=green][color=darkred]
>>> Consider for instance the following definition:
>>> * all strings and numbers are called "well-founded"
>>> * a list is called well-founded if and only if all its elements are
>>> well-founded.
>>>
>>> l=[]
>>> l.append(l)
>>> Is l well-founded? Both answers "yes" and "no" are consistent with the
>>> above definition.[/color]
>>
>> No they aren't, since l's first element is a list, not a string or
>> number.[/color]
>
> The above definition does not require that the first element of a
> well-founded list be a string or number. It could also be a
> well-founded list.[/color]

Seems to me that the example given makes it clear that l is not
well-founded. Look at it step by step:

(1) >>> l = []

at this stage, l is *not* well-founded, since it's a list with no elements,
and the definition explicitly states that a well-founded list is a list
containing all and only well-founded elements, and the only thing other than
lists that can be well-founded are strings and numbers.

(2) >>> l.append(l)

at this stage, l is *still* not well-founded, since all it contains is a
list that we've already seen is not well-founded (cf. the original
definition)...


Fred.

[Terry Reedy]

Re: Semantics of ==


"Fred Mailhot" <fred.mailhot@v ideotron.ca> wrote in message
news:BC8F332F.1 30C3%fred.mailh ot@videotron.ca ...
[color=blue][color=green][color=darkred]
> >>> Consider for instance the following definition:
> >>> * all strings and numbers are called "well-founded"
> >>> * a list is called well-founded if and only if all its elements are
> >>> well-founded.[/color][/color][/color]
[color=blue]
> Seems to me that the example given makes it clear that l is not
> well-founded.[/color]

No. In my experience, the standard interpretation of such definitions is
that the empty list (in this case) 'trivially satisfies' the condition
precisely because it has no elements to check for conformance.

In pure set theory, sets only have sets as members. The empty set
'trivially satifies' this condition, to use the standard catchphrase.
Authors vary on whether this sort of this is said explicitly or not.

Terry J. Reedy