Slices time complexity

[Steven D'Aprano]

On Tue, 19 May 2015 09:00 pm, Gregory Ewing wrote:

> Chris Angelico wrote:
>> 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".
>> 2) In fact, dereferencing as a whole isn't really a 'thing' either. At
>> best, it happens automatically.
>> 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.
>> 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.
>> 5) Furthermore, since a pointer is a value, you can have pointers to
>> pointers, etc. Doesn't make any sense in Python.
> 
> FWIW, most of those things are peculiar to C, and are not
> necessarily shared even with other languages that have
> explicit pointers. In Pascal, for example, there is no
> pointer arithmetic, 

That's true in theory, but I don't think that's right in practice. All the
Pascal compilers that I know of which are still in common use support
pointer arithmetic: Turbo Pascal, GNU Pascal, Free Pascal and Delphi. Some
compilers support an "inc" [increment] function to advance the pointer
safely. For those compilers that don't provide either, there's the
possibility of typecasting the pointer to a longint and back. Back in the
1990s, I used Lightspeed Pascal, and it supported typecasting pointers. For
those which don't even support that, you can usually abuse variant records
to get around the type system.

(Niklaus Wirth hated this, and made sure that this hack didn't work in his
later language Oberon.)

And finally, if all else fails, many Pascal compilers support embedding
assembly language, which obviously lets you do arithmetic on pointers.

The larger point is, the failure to allow pointer arithmetic in standard
Pascal is a design choice of the designer, not a fundamental restriction on
the pointer concept. Wirth didn't include pointer arithmetic in standard
Pascal because *he thought it was a bad idea*, not because Pascal pointers
are incapable of having arithmetic done to them. They're just an
abstraction over *numeric* memory addresses, just like in C, and there's
nothing more fundamental to numbers than arithmetic. You can't do
arithmetic on pointers in standard Pascal because the compiler stops you,
not because the operation makes no sense.

Bringing this back to Python, references in Python are *not* abstractions
over memory addresses. There is nothing in the Python model of computation
that requires values to even have such a thing as a memory address, let
alone pointers. The "references are pointers" explanation only gets you so
far, and not very far at that.


> and (at least not without nonstandard 
> extension) you can't make a pointer point into the middle
> of a stack frame or array or record, etc. (You *can* have
> a pointer to a pointer, but only by heap-allocating a
> memory block containing a single pointer, which is not
> useful very often).

Pascal programming on classic Macintosh used pointers-to-pointers
extensively, so much so that they had a name, "handle". Technically though
handles were managed by the Macintosh Toolbox routines, so slightly
different from what you are talking about. But in standard Pascal, you
certainly could create pointers to pointers.



-- 
Steven