Slices time complexity

[Steven D'Aprano]

On Thu, 21 May 2015 11:34 pm, bartc wrote:

> On Thursday, 21 May 2015 06:19:39 UTC+1, Steven D'Aprano  wrote:
>> On Wednesday 20 May 2015 19:56, Bartc wrote:
> 
>> What you *shouldn't* do is implement your own argument convention,
> 
> (That's exactly what I did for my static language compiler which
> generates x64 code. The Win64 calling convention was far too
> complicated, and required 16-byte stack alignment which was another
> headache. My private calling convention works fine! But I have to use the
> official one for calling foreign (eg. C) functions.

You deleted the rest of my sentence, where I said and then call it by a
standard name that it is not. If you really need your own invented calling
conventions, then I suppose you can do so, but there's really only so many
ways you can do it.


> This is at a lower level than the logical or language view of parameter
> passing, but still, you don't always have to do what everyone else does.)
> 
>> Don't do what the Lua community does, which is invent a stupid
>> distinction between "reference types" and "value types" so they too can
>> misuse terminology:
> 
> But in the mind of the user, such a distinction can be intuitive.

But it's *wrong*. When your intuition gives you the wrong answer, you need
to stop relying on "gut feelings" and *learn some facts*.

Lua has a much smaller set of types than Python, and I'm not an expert on
it, so it may be that there are so few types that you can pass around in
Lua that (wrong or not) it doesn't matter. But I doubt it.


> If 
> I'm passing a 32-bit integer, it is easy to think of the value being
> passed. With a 100 million element array, it harder to think of it being
> passed by value than by reference.

Huh? This doesn't make any sense. The value either *is* or *isn't* passed by
value. That's a property of the language, it doesn't depend on what you
think of it.

If the value is passed by value, then regardless of whether it is a 32-bit
integer or an 1GB array, the value *will be copied*. If it is not copied,
then it isn't pass by value.


>> This calling convention has been known as pass by sharing (or variations
>> of that, like "pass by object sharing") since it was named by Barbara
>> Liskov in the 1970s, for the language CLU, but the convention itself goes
>> back to Lisp in the 1950s.
> 
> I looked it up expecting a new convention to solve all my problems.
> But it's just a re-statement of how Python works anyway!

Exactly.


> So a mutable object passed to a function can be changed by that function,
> so that the caller sees the change. An immutable object can't be
> changed in the same way, but only because Python doesn't allow it to
> be modified. (But it does allow assignment to the version in the
> function.)

I don't understand what your last sentence there means. What do you
mean "the version in the function"? What do you mean by "allow assignment"?

There are three common calling conventions: by value, reference and sharing.
If you have a function with a parameter:

function func(arg)

and then call it with a named variable as argument:

x := something
result := func(x)


*all three conventions* allow assignment to arg inside func. It would be a
pretty strange language which didn't! But the *effect* of such assignment
may vary, depending on the calling convention.

In call-by-value and call-by-sharing, the parameter "arg" is local to func,
so any assignment to arg changes only the local scope, *not* the outer
scope; consequently, the global variable x does not get assigned. arg and x
merely have the same value, they aren't the same variable.

(The difference between the two is that call-by-value *copies* the value, so
in-place modifications to arg don't affect the original x; call-by-sharing
doesn't copy the value, so in-place modifications to arg does affect the
original x.)

In call-by-reference, the compiler treats the parameter "arg" as just
another way of saying "x". So assigning to arg is the same as assigning to
x: for the duration of the function call, arg and x are two names for the
same variable.

(The usual implementation of this is for the compiler to pass a pointer to
x, and then automatically dereference that pointer whenever it refers to
arg, regardless of whether arg is on the left or right of an assignment. C
does not have call-by-reference, but you can fake it by manually doing the
pointer dereferencing yourself.)

Call-by-name is a fourth technique, not common but nevertheless historically
significant. "Call by name" is a bit of misnomer, because it's really more
of call by expression, where the expression is sometimes a single name.

In call-by-name, when you call func(some expression), "some expression" is
recorded in a lightweight anonymous function (called a thunk). Then, inside
the body of func, every time you refer so the parameter name arg, that
expression is re-evaluated.



> Using what is really pass-by-reference for everything is fine, 

I'm really sure it isn't fine. You could use pass-by-reference for
everything, but if you do, you will surprise a lot of people:

def func(arg):
   arg = 1

x = 23
func(x)
assert x == 23  # this will fail

Pass-by-reference does NOT just mean "pass a reference". There's more to it
than that. This is what people don't get.



> but 
> I'm having some trouble with making it efficient for small integer
> values (I think this is a weak area of Python). 

I can imagine that pass-by-reference would be a bit tricky to implement in a
dict-based namespace language, but that has nothing to do with the size of
the value.


> Even with my clunky system 
> of passing descriptors, the equivalent of BINARY_ADD for two small
> integers can be reduced to perhaps 10 or 12 machine instructions,
> byte-code dispatch *and* double type-dispatch overheads included (using
> ASM that is; and technically the type-dispatching is by-passed).
> 
> If small integers need to be heap-allocated and managed, then it might
> need a few more. (And then Python will auto-range these to arbitrary
> precision as needed, another difference.)

Are you talking about Python or your custom language?


> 

-- 
Steven