Slices time complexity

[Steven D'Aprano]

On Tue, 19 May 2015 07:35 pm, Marko Rauhamaa wrote:

> Chris Angelico <rosuav at gmail.com>:
> 
>> Sorta-kinda-maybe, but if a C programmer's idea of pointers is invoked
>> to explain Python's object references, the differences will start to
>> be problematic:
>>
>> 1) Pointer arithmetic simply doesn't exist in Python. Arrays/lists are
>> not just pointers to their first elements, and subscripting is most
>> definitely NOT "add to pointer and dereference".
> 
> Barely an issue.
> 
>> 2) In fact, dereferencing as a whole isn't really a 'thing' either. At
>> best, it happens automatically.
> 
> Yes, you could say to a C programmer: "Python's . corresponds to C's ->"
> and be done with it.


You could say that, but you would be wrong. The amount of stuff that happens
with a dot in Python is far more than a pointer dereference. I can't think
of *any* part of Python's actual behaviour relating to attribute lookup
which it models correctly.

Among other issues, it fails to explain common behaviour like inheritance,
dynamic attribute access (__getattr__ and friends), and descriptors
(properties, methods, etc), never mind about *complicated* stuff like
metaclasses.


>> 3) References actually mean something. Copying a pointer doesn't.
>> Whether the Python you're using is refcounted (CPython) or
>> mark-and-sweep (uPy, I think) or some other model, an additional
>> reference to the same object will prevent it from being disposed of,
>> which isn't the case in C.
> 
> "Disposing of" shouldn't concern a beginning Python programmer. Note
> that Scheme does not address the whole topic in its standard. The memory
> model is infinite if you will.

Beginning Python programmers are not necessarily newbies to programming. If
Susan is a guru-level programmer with thirty years experience in C, C#,
Javascript, Lisp and Forth, but today is her first day using Python, are
you going to try to tell her that Python has infinite memory when she asks
what sort of memory management Python uses?

Even beginners to programming may be capable of intuiting for themselves
that disposal is an issue to be considered. "I know my computer has 4GB of
RAM, and I've just created a list of two billion strings. My computer is
running a bit slow. Maybe this has something to do with memory? How do I
dispose of those strings so they aren't using up memory?"


>> 4) A pointer is itself a value. You can pass a
>> pointer-to-local-variable to another function and have that function
>> change a local variable.
> 
> Correct, variables are not first-class objects in Python. In C, they
> are. Functions are not first-class objects in C. In Python, they are.

Variables are not first class values in C. (I assume you meant *values*
rather than "objects", on account of C not being an OOP language.) There is
no way, for example, to set x to *the variable y* in either C or Python. If
you could, that would imply something like this:

y = 42  # regular assignment
x ::= y  # set x to be the variable y, not the value of y
assert x == y  # naturally, since x and y are now two different 
               # names for the same variable
x = 23  # regular assignment
assert y == 23  # since y is just another name for x

You should note carefully that my example doesn't involve calling setter
functions, explicitly manipulating a namespace, pointer dereferences or any
other form of indirect assignment. It just uses name binding: a name on the
left, a value on the right.

You cannot do that in C or Python.

I'm not aware of any language which treats variables as first class values.


> Still, that doesn't make the pointer semantics any less applicable to
> Python.
> 
>> 5) Furthermore, since a pointer is a value, you can have pointers to
>> pointers, etc. Doesn't make any sense in Python.
> 
> What you are saying is that references in general are not first-class
> objects in Python. In C, they are.

References in Python are not values at all, so they are not first-class
values.

Pointers in C are values, and first-class values at that.

Arrays, on the other hand, are values but not first-class values in C: you
cannot do array assignment, pass an entire array by value, or return an
array from a function.



-- 
Steven