Slices time complexity

[Steven D'Aprano]

On Tuesday 19 May 2015 18:39, Marko Rauhamaa wrote:

> What I'm saying is that it doesn't matter what semantic description you
> give Python constructs as long as the observed behavior is correct.

You really think that it doesn't matter which of the following two 
explanations I give for this behaviour?

x = 2
y = 3
print x+y  # prints 5

Explanation #1:

"Python adds 2 and 3 together and prints 5."

Explanation #2:

"Python takes the 2nd decimal place of pi (4), and the 3rd decimal place of 
e (8), multiplies them (32), then prints the sum of the digits (5)."

The first explanation has the advantage that it actually describes Python's 
semantic model for the + operator, and consequently it is far more likely to 
allow the user to predict the output of (say) 5+2. The second explanation 
explains the observed behaviour, but doesn't have any predictive power:

Explanation #2 continued:

"Of course Python only does that when the arguments are 2 and 3. With 
arguments 5 and 2, it takes the tenth decimal place of pi (5), the 9th 
decimal place of e**2 (8), and subtracts them from 20 (7)."

Explanations shouldn't just explain the observed behaviour. Any semi-
arbitrary collection of special cases can do that. 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.

Explanation #3, assuming that Python follows the same rules as C, might 
predict overflow to -32768, saturation (32767 + 1 = 32767), or "undefined 
behaviour" up to and including erasing your hard drive.

Only one of these models for Python allows you to make correct predictions, 
even though all three explain the observations given.

Having a good, consistent model for the programming language allows one to 
predict not just *what* it will do, but (in a rough and ready fashion) *how* 
it will do it. Having the *right* model allows you to predict *correctly*.


> 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.

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.



-- 
Steve