Slices time complexity

[Steven D'Aprano]

On Wed, 20 May 2015 01:59 am, Marko Rauhamaa wrote:

> Steven D'Aprano <steve+comp.lang.python at pearwood.info>:
> 
>> To be useful, explanations ought to give the user *predictive power*
>> -- if I calculate 32767 + 1, what will Python do?
>>
>> Explanation #1 predicts that Python will return 32768.
>> Explanation #2 makes no prediction at all.
> 
> Any semantic ruleset that correctly predicts the behavior of any given
> Python program is equally valid.

This is a more reasonable position to take than your earlier stance that the
only thing that matters is whether it explains observed behaviour. It's
still wrong, but at least it is defensible in the sense that sometimes a
ruleset which is objectively wrong but still gives the right answer might
be *preferred* over one which is objectively correct but hard to
understand.

But some rulesets may have perfect predictive power, and still be rejected:

http://star.psy.ohio-state.edu/coglab/Pictures/miracle.gif

Unlike scientific theories about the universe, where we have to hypothesise
what the rules are, we can actually look at the source code for the Python
interpreter and see exactly what the rules are. We don't have to guess how
list.sort() works, we have the documentation, we have the source code, we
can ask the author, and if all else fails, we can run the interpreter in a
debugger and watch what it does.

A ruleset which corresponds to the facts of how list.sort() works is more
valid than a counter-factual ruleset which does not. "Python uses timsort"
is usually to be preferred over "Python uses bubblesort" because at least
two interpreters (CPython and Jython) use timsort, while no interpreter
uses bubblesort. (Here, "Python" is to be understood as referring to a
specific interpreter, not the language itself.)



>> Only one of these models for Python allows you to make correct
>> predictions, even though all three explain the observations given.
> 
> You're slaying straw men.

"I was wrong, but I don't want to admit it" is not spelled "straw man".

You made a claim that was not defensible, and I tore that claim to shreds.
Have the good grace to admit that your earlier position:

    "it doesn't matter what semantic description you give Python 
    constructs as long as the observed behavior is correct"

doesn't stand up to scrutiny. If you can't do that, at least let it pass in
silence without trying to pretend that you never made that argument and
falsely accusing me of misrepresenting you.



>>> For example, you could explain Python's object references as pointers
>>> (memory addresses) if you considered that helpful. (That's how Lisp
>>> textbooks often explain cons cells.)
>>
>> Well, you could do that, but it would fail to explain the behaviour of
>> Jython and IronPython.
> 
> Jython, CPython and IronPython are supposed to be semantically
> equivalent. So any valid CPython model is also a valid model for Jython
> and IronPython.

They are only supposed to equivalent in regards to behaviour specified by
the language specifications, and that gives plenty of opportunity for
implementation-dependent behaviour. And of course performance and memory
use is a measure of quality of implementation.

One such implementation-dependent behaviour is whether Python objects have a
fixed location or not. CPython objects currently do. Jython and IronPython
objects do not, they can move in memory, so references in those two
implementations cannot be implemented as pointers or memory addresses.

PyPy objects don't even have a fixed existence, there are circumstances
where objects in PyPy can disappear, only to be recreated (possibly in a
new location).


>> Mixing descriptions of a specific implementation with descriptions of
>> the high level semantics is sometimes useful but often misleading, and
>> one needs to be careful how and when one does it.
> 
> Nobody has proposed doing that.

You did. Pointers are the CPython implementation, they are not the high
level semantics.




-- 
Steven