Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #90807 > unrolled thread

Slices time complexity

Back to article view | Back to comp.lang.python

Contents

  Slices time complexity Mario Figueiredo <marfig@gmail.com> - 2015-05-18 20:23 +0100
    Re: Slices time complexity Chris Angelico <rosuav@gmail.com> - 2015-05-19 05:36 +1000
      Re: Slices time complexity Mario Figueiredo <marfig@gmail.com> - 2015-05-18 20:49 +0100
        Re: Slices time complexity Chris Angelico <rosuav@gmail.com> - 2015-05-19 06:04 +1000
    Re: Slices time complexity Todd <toddrjen@gmail.com> - 2015-05-18 21:42 +0200
    Re: Slices time complexity Ian Kelly <ian.g.kelly@gmail.com> - 2015-05-18 13:49 -0600
      Re: Slices time complexity Fabien <fabien.maussion@gmail.com> - 2015-05-18 21:54 +0200
        Re: Slices time complexity Todd <toddrjen@gmail.com> - 2015-05-18 22:23 +0200
      Re: Slices time complexity Mario Figueiredo <marfig@gmail.com> - 2015-05-18 22:04 +0100
        Re: Slices time complexity Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-05-18 22:38 +0100
        Re: Slices time complexity Terry Reedy <tjreedy@udel.edu> - 2015-05-18 19:04 -0400
      Re: Slices time complexity Rustom Mody <rustompmody@gmail.com> - 2015-05-18 19:20 -0700
        Re: Slices time complexity Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-05-19 15:13 +1000
          Re: Slices time complexity Rustom Mody <rustompmody@gmail.com> - 2015-05-18 22:33 -0700
            Re: Slices time complexity Marko Rauhamaa <marko@pacujo.net> - 2015-05-19 10:12 +0300
              Re: Slices time complexity Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-05-19 18:16 +1000
                Re: Slices time complexity Marko Rauhamaa <marko@pacujo.net> - 2015-05-19 11:39 +0300
                  Re: Slices time complexity Chris Angelico <rosuav@gmail.com> - 2015-05-19 18:50 +1000
                    Re: Slices time complexity Marko Rauhamaa <marko@pacujo.net> - 2015-05-19 12:35 +0300
                      Re: Slices time complexity Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-05-19 23:44 +1000
                        Re: Slices time complexity Christian Gollwitzer <auriocus@gmx.de> - 2015-05-20 23:54 +0200
                    Re: Slices time complexity Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2015-05-19 23:00 +1200
                      Re: Slices time complexity Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-05-20 11:47 +1000
                        Re: Slices time complexity Dennis Lee Bieber <wlfraed@ix.netcom.com> - 2015-05-20 08:07 -0400
                    Re: Slices time complexity Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-05-19 22:42 +1000
                      Re: Slices time complexity Chris Angelico <rosuav@gmail.com> - 2015-05-19 23:24 +1000
                      Re: Slices time complexity Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2015-05-20 12:31 +1200
                        Re: Slices time complexity Ben Finney <ben+python@benfinney.id.au> - 2015-05-20 10:42 +1000
                          Re: Slices time complexity Marko Rauhamaa <marko@pacujo.net> - 2015-05-20 07:24 +0300
                            Re: Slices time complexity Rustom Mody <rustompmody@gmail.com> - 2015-05-19 21:30 -0700
                              Re: Slices time complexity Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-05-20 06:06 +0100
                              Re: Slices time complexity Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-05-20 15:57 +1000
                                Re: Slices time complexity Marko Rauhamaa <marko@pacujo.net> - 2015-05-20 09:17 +0300
                                Re: Slices time complexity Rustom Mody <rustompmody@gmail.com> - 2015-05-19 23:23 -0700
                                  Re: Slices time complexity Marko Rauhamaa <marko@pacujo.net> - 2015-05-20 09:46 +0300
                                    Re: Slices time complexity Rustom Mody <rustompmody@gmail.com> - 2015-05-20 00:03 -0700
                                      Re: Slices time complexity Marko Rauhamaa <marko@pacujo.net> - 2015-05-20 10:45 +0300
                                  List semantics [was Re: Slices time complexity] Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-05-20 17:23 +1000
                                    Re: List semantics [was Re: Slices time complexity] Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2015-05-20 20:54 +1200
                                      Re: List semantics [was Re: Slices time complexity] Ned Batchelder <ned@nedbatchelder.com> - 2015-05-20 04:08 -0700
                                      Re: List semantics [was Re: Slices time complexity] Terry Reedy <tjreedy@udel.edu> - 2015-05-20 14:42 -0400
                                        Re: List semantics [was Re: Slices time complexity] Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2015-05-21 11:06 +1200
                                      Re: List semantics [was Re: Slices time complexity] Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-05-21 12:10 +1000
                                Re: Slices time complexity "Bartc" <bartc@freeuk.com> - 2015-05-20 10:56 +0100
                                  Re: Slices time complexity Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2015-05-20 10:16 +0100
                                  Re: Slices time complexity Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-05-21 15:19 +1000
                                    Re: Slices time complexity Marko Rauhamaa <marko@pacujo.net> - 2015-05-21 09:20 +0300
                                    Re: Slices time complexity bartc <bart4858@gmail.com> - 2015-05-21 06:34 -0700
                                      Re: Slices time complexity MRAB <python@mrabarnett.plus.com> - 2015-05-21 17:50 +0100
                                      Re: Slices time complexity Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-05-22 03:16 +1000
                                        Re: Slices time complexity bart4858@gmail.com - 2015-05-21 12:48 -0700
                        Re: Slices time complexity Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-05-20 12:26 +1000
                          Re: Slices time complexity Chris Angelico <rosuav@gmail.com> - 2015-05-20 12:36 +1000
                          Re: Slices time complexity Rustom Mody <rustompmody@gmail.com> - 2015-05-19 20:02 -0700
                  Re: Slices time complexity Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-05-19 21:43 +1000
                    Re: Slices time complexity Marko Rauhamaa <marko@pacujo.net> - 2015-05-19 18:59 +0300
                      Re: Slices time complexity Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-05-20 03:46 +1000
                        Re: Slices time complexity Chris Angelico <rosuav@gmail.com> - 2015-05-20 04:12 +1000
                        Re: Slices time complexity Marko Rauhamaa <marko@pacujo.net> - 2015-05-19 21:19 +0300
                          Re: Slices time complexity Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-05-20 10:43 +1000
                            Re: Slices time complexity Marko Rauhamaa <marko@pacujo.net> - 2015-05-20 07:30 +0300
                              Re: Slices time complexity Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-05-20 15:33 +1000
                                Re: Slices time complexity Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-05-20 15:58 +1000
                  Re: Slices time complexity Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2015-05-19 15:18 +0100
              Re: Slices time complexity Rustom Mody <rustompmody@gmail.com> - 2015-05-19 04:46 -0700
                Re: Slices time complexity Rustom Mody <rustompmody@gmail.com> - 2015-05-19 05:14 -0700
            Re: Slices time complexity Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-05-19 18:19 +1000
              Re: Slices time complexity Rustom Mody <rustompmody@gmail.com> - 2015-05-19 04:41 -0700
    Re: Slices time complexity Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-05-19 19:45 +1000
      Re: Slices time complexity Serhiy Storchaka <storchaka@gmail.com> - 2015-05-19 13:15 +0300
      Re: Slices time complexity Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2015-05-19 12:09 +0100
      Re: Slices time complexity "Bartc" <bartc@freeuk.com> - 2015-05-19 15:52 +0100
        Re: Slices time complexity Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-05-20 03:07 +1000
          Re: Slices time complexity Chris Angelico <rosuav@gmail.com> - 2015-05-20 03:19 +1000
          Re: Slices time complexity Mario Figueiredo <marfig@gmail.com> - 2015-05-20 20:51 +0100
            Re: Slices time complexity Ian Kelly <ian.g.kelly@gmail.com> - 2015-05-20 14:33 -0600
            Re: Slices time complexity Chris Angelico <rosuav@gmail.com> - 2015-05-21 06:35 +1000
            Re: Slices time complexity Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-05-20 21:47 +0100
              Re: Slices time complexity Mario Figueiredo <marfig@gmail.com> - 2015-05-20 22:23 +0100
            Re: Slices time complexity Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-05-21 17:35 +1000
              Re: Slices time complexity Chris Angelico <rosuav@gmail.com> - 2015-05-21 18:25 +1000
      Re: Slices time complexity Ian Kelly <ian.g.kelly@gmail.com> - 2015-05-19 09:15 -0600
      Re: Slices time complexity Serhiy Storchaka <storchaka@gmail.com> - 2015-05-19 22:51 +0300

Page 1 of 5  [1] 2 3 4 5  Next page →

#90807 — Slices time complexity

I'd like to understand what I'm being told about slices in
https://wiki.python.org/moin/TimeComplexity

Particularly, what's a 'del slice' and a 'set slice' and whether this
information pertains to both CPython 2.7 and 3.4.

From the above link it seems slices work in linear time on all cases.
And this really has a big impact on certain operations. For instance,
the code below may surprise some people when they realize it doesn't
run in linear time on 3.4:

    def minimum(values):
        if len(values) == 1:
            return values[0]
        else:
            m = minimum(values[1:])
            return m if m < values[0] else values[0]

Other languages implement slices. I'm currently being faced with a Go
snippet that mirrors the exact code above and it does run in linear
time.

Is there any reason why Python 3.4 implementation of slices cannot be
a near constant operation?

[toc] | [next] | [standalone]

#90808

On Tue, May 19, 2015 at 5:23 AM, Mario Figueiredo <marfig@gmail.com> wrote:
> From the above link it seems slices work in linear time on all cases.
> And this really has a big impact on certain operations. For instance,
> the code below may surprise some people when they realize it doesn't
> run in linear time on 3.4:
>
>     def minimum(values):
>         if len(values) == 1:
>             return values[0]
>         else:
>             m = minimum(values[1:])
>             return m if m < values[0] else values[0]

https://xkcd.com/1270/

Is there really a reason to code this in such a bizarrely inefficient
way? Linear or not, it's bound to be less efficient than the more
obvious form:

def minimum(values):
    values = iter(values)
    min = next(values)
    for value in values:
        if value < min: min = value
    return min

And if you know your value domain (maybe you're working with floats,
or positive integers, or something) and can put a hard-coded base
value in, it becomes even simpler:

def minimum(values):
    min = 0 # or float("-inf") etc
    for value in values:
        if value < min: min = value
    return min

It's obvious that this code will complete in linear time. It's also
pretty obvious how it's working: it steps through the collection,
comparing each value against the current smallest. With your recursive
version, it effectively steps backward through the list, comparing
each value against the current smallest, all while unwinding the
stack. It can't even be tail-call-optimized in its current state.

What's the point of optimizing slicing to allow you to use a poor
algorithm, instead of fixing your algorithm?

ChrisA

[toc] | [prev] | [next] | [standalone]

#90809

On Tue, 19 May 2015 05:36:44 +1000, Chris Angelico <rosuav@gmail.com>
wrote:

>What's the point of optimizing slicing to allow you to use a poor
>algorithm, instead of fixing your algorithm?
>

Chris, thank you for your input. But the code isn't really the
question, is it?

It's just an example. It was being used earlier to demonstrate Time
Complexity calculations in another forum. It's not real live code.
Never will be. Besides we already have a min() function in Python.

[toc] | [prev] | [next] | [standalone]

#90813

On Tue, May 19, 2015 at 5:49 AM, Mario Figueiredo <marfig@gmail.com> wrote:
> On Tue, 19 May 2015 05:36:44 +1000, Chris Angelico <rosuav@gmail.com>
> wrote:
>
>>What's the point of optimizing slicing to allow you to use a poor
>>algorithm, instead of fixing your algorithm?
>>
>
> Chris, thank you for your input. But the code isn't really the
> question, is it?
>
> It's just an example. It was being used earlier to demonstrate Time
> Complexity calculations in another forum. It's not real live code.
> Never will be. Besides we already have a min() function in Python.

General rule of optimization: Do the simplest thing first, and make it
more complicated only if the speed benefit is worth it. In this case,
slicing a list is done in the obvious and simple way: construct a new
list of the appropriate length, and assign all its elements. (The
details may be optimized some at the C level, but it still constructs
a new list.) You're asking why Python doesn't have a much more
complicated system (Todd suggests views and COW; another way is to do
a LISP-style linked list, which has similar consequences to views, but
is more efficient if you do this specific thing of processing the
first element and recursing for the rest), and the answer is: There's
always a better way to write your algorithm.

So if your code is intended to demonstrate how a poor algorithm can
turn a linear task into a quadratic one, congrats! You've succeeded.
If you're trying to showcase how terrible Python is, well, I'm sure
you could do that in more effective ways, but they'll still come down
to trying to write <insert other language name here> code using the
Python interpreter. If you write idiomatic Python code, using
iterators and loops rather than recursion, you'll find your code is
cleaner and faster than it would be if you fight against the language.

ChrisA

[toc] | [prev] | [next] | [standalone]

#90810

[Multipart message — attachments visible in raw view] — view raw

On May 18, 2015 9:26 PM, "Mario Figueiredo" <marfig@gmail.com> wrote:
>
> I'd like to understand what I'm being told about slices in
> https://wiki.python.org/moin/TimeComplexity
>
> Particularly, what's a 'del slice' and a 'set slice' and whether this
> information pertains to both CPython 2.7 and 3.4.
>
> From the above link it seems slices work in linear time on all cases.
> And this really has a big impact on certain operations. For instance,
> the code below may surprise some people when they realize it doesn't
> run in linear time on 3.4:
>
>     def minimum(values):
>         if len(values) == 1:
>             return values[0]
>         else:
>             m = minimum(values[1:])
>             return m if m < values[0] else values[0]
>
> Other languages implement slices. I'm currently being faced with a Go
> snippet that mirrors the exact code above and it does run in linear
> time.
>
> Is there any reason why Python 3.4 implementation of slices cannot be
> a near constant operation?

In this case you are copying the items (or rather pointers to the items)
from the list to a new list. This is inherently a O(k) operation.

There are other ways to implement it. I recall the was talk of a way to get
views of sequences, although this would involve keeping the original list
in memory and any changes to the new list would be passed to the original
(this is how numpy works) . It is also possible to do copy-on-write, which
avoids altering the original list but has the same memory problems while
still involving a O(k) copy operation if you want to change the list, and
it is more complex to implement (this is how MATLAB works) .

But to have a new list that can be edited independently requires coping
something, and that will be a O(k) operation, unless you use a radically
different data structure with its own limitations.

[toc] | [prev] | [next] | [standalone]

#90811

On Mon, May 18, 2015 at 1:23 PM, Mario Figueiredo <marfig@gmail.com> wrote:
> I'd like to understand what I'm being told about slices in
> https://wiki.python.org/moin/TimeComplexity
>
> Particularly, what's a 'del slice' and a 'set slice' and whether this
> information pertains to both CPython 2.7 and 3.4.

"Del Slice" is the operation where a slice of a list is deleted, and
"Set Slice" is the operation where a slice is replaced. E.g.:

>>> x = list(range(100))
>>> del x[2:98]
>>> x
[0, 1, 98, 99]
>>> x[1:3] = [7, 6, 5, 4, 3]
>>> x
[0, 7, 6, 5, 4, 3, 99]


> Other languages implement slices. I'm currently being faced with a Go
> snippet that mirrors the exact code above and it does run in linear
> time.
>
> Is there any reason why Python 3.4 implementation of slices cannot be
> a near constant operation?

The semantics are different. IIRC, a slice in Go is just a view of
some underlying array; if you change the array (or some other slice of
it), the change will be reflected in the slice. A slice of a list in
Python, OTOH, constructs a completely independent list.

It may be possible that lists in CPython could be made to share their
internal arrays with other lists on a copy-on-write basis, which could
allow slicing to be O(1) as long as neither list is modified while the
array is being shared. I expect this would be a substantial piece of
work, and I don't know if it's something that anybody has looked into.

[toc] | [prev] | [next] | [standalone]

#90812

On 05/18/2015 09:49 PM, Ian Kelly wrote:
> It may be possible that lists in CPython could be made to share their
> internal arrays with other lists on a copy-on-write basis, which could
> allow slicing to be O(1) as long as neither list is modified while the
> array is being shared. I expect this would be a substantial piece of
> work, and I don't know if it's something that anybody has looked into.

Isn't Numpy doing this (not sure, not a python nor a numpy expert):

 >>> import numpy as np
 >>> a = np.array([1,2,3,4])
 >>> b = a[1:]
 >>> b[0] = 9
 >>> a
array([1, 9, 3, 4])


Fabien

[toc] | [prev] | [next] | [standalone]

#90814

[Multipart message — attachments visible in raw view] — view raw

On May 18, 2015 9:56 PM, "Fabien" <fabien.maussion@gmail.com> wrote:
>
> On 05/18/2015 09:49 PM, Ian Kelly wrote:
>>
>> It may be possible that lists in CPython could be made to share their
>> internal arrays with other lists on a copy-on-write basis, which could
>> allow slicing to be O(1) as long as neither list is modified while the
>> array is being shared. I expect this would be a substantial piece of
>> work, and I don't know if it's something that anybody has looked into.
>
>
> Isn't Numpy doing this (not sure, not a python nor a numpy expert):
>
> >>> import numpy as np
> >>> a = np.array([1,2,3,4])
> >>> b = a[1:]
> >>> b[0] = 9
> >>> a
> array([1, 9, 3, 4])
>
>
> Fabien

Numpy arrays use views. Matlab arrays use copy-on-write.  But as discussed
in the recent thread about string views, these approaches have a memory
penalty since they require keeping the original array in memory. And the
copy-on-write approach still has a O(k) complexity if you try to make any
changes.

[toc] | [prev] | [next] | [standalone]

#90816

On Mon, 18 May 2015 13:49:45 -0600, Ian Kelly <ian.g.kelly@gmail.com>
wrote:

>> Other languages implement slices. I'm currently being faced with a Go
>> snippet that mirrors the exact code above and it does run in linear
>> time.
>>
>> Is there any reason why Python 3.4 implementation of slices cannot be
>> a near constant operation?
>
>The semantics are different. IIRC, a slice in Go is just a view of
>some underlying array; if you change the array (or some other slice of
>it), the change will be reflected in the slice. A slice of a list in
>Python, OTOH, constructs a completely independent list.
>
>It may be possible that lists in CPython could be made to share their
>internal arrays with other lists on a copy-on-write basis, which could
>allow slicing to be O(1) as long as neither list is modified while the
>array is being shared. I expect this would be a substantial piece of
>work, and I don't know if it's something that anybody has looked into.

This is what I was after. Thank you Ian.

So we basically don't have a view of a list. Makes sense now, since
slice does create a new list. I should have seen that. Thank you once
again.

It would a good addition though. Even if only on specialized
implementations like pypy. Inspecting and not changing lists is a good
chunk of our code. But that's besides the point. I was more interested
in understanding the behavior. Thank you once again.

[toc] | [prev] | [next] | [standalone]

#90817

On 18/05/2015 22:04, Mario Figueiredo wrote:
> On Mon, 18 May 2015 13:49:45 -0600, Ian Kelly <ian.g.kelly@gmail.com>
> wrote:
>
>>> Other languages implement slices. I'm currently being faced with a Go
>>> snippet that mirrors the exact code above and it does run in linear
>>> time.
>>>
>>> Is there any reason why Python 3.4 implementation of slices cannot be
>>> a near constant operation?
>>
>> The semantics are different. IIRC, a slice in Go is just a view of
>> some underlying array; if you change the array (or some other slice of
>> it), the change will be reflected in the slice. A slice of a list in
>> Python, OTOH, constructs a completely independent list.
>>
>> It may be possible that lists in CPython could be made to share their
>> internal arrays with other lists on a copy-on-write basis, which could
>> allow slicing to be O(1) as long as neither list is modified while the
>> array is being shared. I expect this would be a substantial piece of
>> work, and I don't know if it's something that anybody has looked into.
>
> This is what I was after. Thank you Ian.
>
> So we basically don't have a view of a list. Makes sense now, since
> slice does create a new list. I should have seen that. Thank you once
> again.
>
> It would a good addition though. Even if only on specialized
> implementations like pypy. Inspecting and not changing lists is a good
> chunk of our code. But that's besides the point. I was more interested
> in understanding the behavior. Thank you once again.
>

Not directly affecting slices but the idea of views has come into Python 
3, please see:-

https://www.python.org/dev/peps/pep-3118/

https://docs.python.org/3/whatsnew/3.3.html#pep-3118-new-memoryview-implementation-and-buffer-protocol-documentation

https://docs.python.org/3/library/stdtypes.html#typememoryview

-- 
My fellow Pythonistas, ask not what our language can do for you, ask
what you can do for our language.

Mark Lawrence

[toc] | [prev] | [next] | [standalone]

#90819

On 5/18/2015 5:04 PM, Mario Figueiredo wrote:

>>> Other languages implement slices. I'm currently being faced with a Go
>>> snippet that mirrors the exact code above and it does run in linear
>>> time.

>>> Is there any reason why Python 3.4 implementation of slices cannot be
>>> a near constant operation?
>>
>> The semantics are different. IIRC, a slice in Go is just a view of
>> some underlying array; if you change the array (or some other slice of
>> it), the change will be reflected in the slice. A slice of a list in
>> Python, OTOH, constructs a completely independent list.
>>
>> It may be possible that lists in CPython could be made to share their
>> internal arrays with other lists on a copy-on-write basis, which could
>> allow slicing to be O(1) as long as neither list is modified while the
>> array is being shared. I expect this would be a substantial piece of
>> work, and I don't know if it's something that anybody has looked into.
>
> This is what I was after. Thank you Ian.
>
> So we basically don't have a view of a list.

Actually we do if you think about things the right way.  An index can be 
viewed as representing the slice of a list from the indexed item to the 
end.  In this view, "for i in range(len(seq)):" works with progressively 
shrinking slices, the same as with the recursive version of the algorithm.

The analogy is better with iterators.  iter(seq) returns a seq_iterator 
that initially represent a tail slice consisting of the entire sequence. 
  Each next(seq_iter) call return the head of the sequence and mutates 
seq_iter to represent a reduced tail-slice.  The effect is the same as 
repeatedly stripping the head from a linked list. For statements 
automate the next calls and StopIteration checks.

-- 
Terry Jan Reedy

[toc] | [prev] | [next] | [standalone]

#90822

On Tuesday, May 19, 2015 at 1:20:55 AM UTC+5:30, Ian wrote:
> It may be possible that lists in CPython could be made to share their
> internal arrays with other lists on a copy-on-write basis, which could
> allow slicing to be O(1) as long as neither list is modified while the
> array is being shared. I expect this would be a substantial piece of
> work, and I don't know if it's something that anybody has looked into.

One fundamental difference/choice in language semantics is copy vs reference
C#/.Net call it value-type and reference-type. [The names may be a bit odd...]

Functional languages OTOH tend to the philosophy:
- maximise sharing internally
- mutability taboo
which has its own costs -- eg 'obvious' data structures like arrays become hard/impossible

Its quite likely that your proposal - slices as COW-views -- will have 
significant penalties in other usage scenarios.  Imagine plastering more and 
more complex slice-views on an array inter-mixed with updates.

I must say I am impressed by C#/.Net for making the value/object distinction
first-class all the way from language to VM.

[toc] | [prev] | [next] | [standalone]

#90825

On Tuesday 19 May 2015 12:20, Rustom Mody wrote:

> I must say I am impressed by C#/.Net for making the value/object
> distinction first-class all the way from language to VM.

I'm not sure what you mean by that. Are you referring to something similar 
to Java's distinction between native/unboxed types versus objects and boxed 
values?

Apart from the possible efficiency gains, what benefit do you see from 
distinguishing between "values which are objects" versus "values which are 
not objects"?


-- 
Steve

[toc] | [prev] | [next] | [standalone]

#90826

On Tuesday, May 19, 2015 at 10:44:10 AM UTC+5:30, Steven D'Aprano wrote:
> On Tuesday 19 May 2015 12:20, Rustom Mody wrote:
> 
> > I must say I am impressed by C#/.Net for making the value/object
> > distinction first-class all the way from language to VM.
> 
> I'm not sure what you mean by that. 

Neither am I <wink> 
[Dont know too much about that environment]

> Are you referring to something similar 
> to Java's distinction between native/unboxed types versus objects and boxed 
> values?

Yes except that it seems to be more core to C# than to Java (or python):
https://msdn.microsoft.com/en-us/library/s1ax56ch.aspx
And then this distinction goes all the way down to the CLR
[in ways that I am not very clear about]
eg http://www.informit.com/articles/article.aspx?p=30608&seqNum=3

> Apart from the possible efficiency gains, what benefit do you see from 
> distinguishing between "values which are objects" versus "values which are 
> not objects"?

As I said, in the context of a low level language its probably a bit of a misnomer
However conceptually/pedagogically making a fundamenal distinction of
timeless | time
value | object
immutable | mutable
expression | statement
function | procedure

is key to getting programming [and is something that Pascal got better than most
of its successors].

The FPers want to squeeze the whole world into column 1
The OOPers want to do the opposite and are embarrassed by the existence of
column-1 [status of int in java etc]
Unless one is committed to some philosophical extreme position --
Only One True Way -- I believe accepting two fundamentals is the most sane choice 
 

[toc] | [prev] | [next] | [standalone]

#90828

Rustom Mody <rustompmody@gmail.com>:

> However conceptually/pedagogically making a fundamenal distinction of
> timeless | time
> value | object
> immutable | mutable
> expression | statement
> function | procedure
>
> is key to getting programming [and is something that Pascal got better
> than most of its successors].
>
> The FPers want to squeeze the whole world into column 1
> The OOPers want to do the opposite and are embarrassed by the existence of
> column-1 [status of int in java etc]
> Unless one is committed to some philosophical extreme position --
> Only One True Way -- I believe accepting two fundamentals is the most
> sane choice

I sympathize. Can you get Python without getting a language like C
first? Can a baby be born without an umbilical cord? Can you skip Newton
and go straight to quantum mechanics and relativity? I have noticed some
experienced Java programmers are a bit lost in the woods because they
don't have an idea of what is going on under the hood.

Scheme almost gets away with the dilemma but must face it with pairs:

    A pair (sometimes called a dotted pair) is a record structure with
    two fields called the car and cdr fields (for historical reasons).
    Pairs are created by the procedure cons. The car and cdr fields are
    accessed by the procedures car and cdr. The car and cdr fields are
    assigned by the procedures set-car! and set-cdr!.

    Pairs are used primarily to represent lists.

    <URL: http://www.schemers.org/Documents/Standards/R5RS/HTM
    L/r5rs-Z-H-9.html#%_sec_6.3.2>

What is a "record structure?" What is a "field?" What is "creation?"

Still, I don't like the dichotomy of boxed/unboxed values. Is a Python
integer an "object" or a "value?" The Faithful have a surefire answer,
but I think the key is: who cares? What matters is the effect of a
program. If two metaphysical formulations of language semantics produce
the same outcome, neither is objectively better than the other.

Pedagogically, I think you could introduce topics with half-truths and
simplifications, and revisit them later with corrections when the
students are better equipped to handle the abstractions.


Marko

[toc] | [prev] | [next] | [standalone]

#90829

On Tuesday 19 May 2015 17:12, Marko Rauhamaa wrote:

> Can you get Python without getting a language like C first? 

Yes.

There are a few senses in which C is very important to Python. Python was 
designed to be a glue language for interoperability with C libraries, so 
that's a very important sense, but in another way it is a trivial sense. You 
could replace C by any other language, or no language at all, and Python 
would still be more or less the same.

Another sense is that Python has borrowed some syntax and concepts from C, 
e.g. zero-based indexing, "continue" and "break" keywords, etc. But these 
are incidentals, the language would be mostly still the same if "continue" 
was spelled "next" in the Pascal tradition.

Python has been influenced by, and borrowed concepts from, a whole slew of 
languages, including Pascal, Algol, Modula 3, Icon, CLU, Lisp, Haskell, TCL, 
Smalltalk, ML, and especially ABC.

[...]
> Still, I don't like the dichotomy of boxed/unboxed values.

Distinguishing the two is important for mere reasons of implementation 
efficiency, but it makes the language semantics messy.


> Is a Python integer an "object" or a "value?" 

Why should that be a dichotomy?

Ints are values. Floats are values. Lists are values. Strings are values. 
Structs and records and union types and even functions are values. Why 
should objects not also be values?


> The Faithful have a surefire answer,
> but I think the key is: who cares? What matters is the effect of a
> program. If two metaphysical formulations of language semantics produce
> the same outcome, neither is objectively better than the other.

By outcome, do you mean the program's output? But the metaphysical 
formulation of the language is irrelevant to the program output. You can get 
the same output in Forth, Haskell, Prolog, C, Applescript or a Turing 
Machine, despite having radically different paradigms.

The outcome which matters is *usability*. Some paradigms are better suited 
to human understanding than others. Complexity and inconsistency is hard. A 
language where the rules for dealing with lists is different from those for 
floats will be harder to use than a language where they are both treated in 
the same way.

I'm not talking about the functionality available to each type -- obviously 
lists and floats use different syntax and different functionality. But if 
you wrote `$spam = alist` to assign a list, and `spam := $afloat` to assign 
a float, that would be bad. A consistent language paradigm is better than an 
inconsistent one. Think of Perl with its complicated rules that you have to 
memorize before you know whether to prefix a variable with a $ or a @ or 
whatever the sigils are.

-- 
Steve

[toc] | [prev] | [next] | [standalone]

#90831

Steven D'Aprano <steve+comp.lang.python@pearwood.info>:

>> What matters is the effect of a program. If two metaphysical
>> formulations of language semantics produce the same outcome, neither
>> is objectively better than the other.
>
> By outcome, do you mean the program's output?

Yes, the program's output, but also the interactions between program
parts.

> But the metaphysical formulation of the language is irrelevant to the
> program output. You can get the same output in Forth, Haskell, Prolog,
> C, Applescript or a Turing Machine, despite having radically different
> paradigms.

You misunderstood my point. A valid Python program would not produce the
same output when given to a Prolog interpreter (it would likely produce
a syntax error).

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.

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


Marko

[toc] | [prev] | [next] | [standalone]

#90832

On Tue, May 19, 2015 at 6:39 PM, Marko Rauhamaa <marko@pacujo.net> wrote:
> 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.)

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

A closer comparison is the C++ "reference", which works kinda like
pass-by-reference, kinda like a pointer, and kinda not like anything
at all, really. But that's still not the same thing as HLL object
semantics (the same semantics used by Python, Pike, ECMAScript, and a
bunch of other languages). As long as you are aware that analogies are
always limited, you can certainly use them as part of an explanation;
but you do have to take care.

ChrisA

[toc] | [prev] | [next] | [standalone]

#90835

Chris Angelico <rosuav@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.

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

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

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.

So in Python, we have these memory locations (variables, references)
that are accessible through special syntax only. Ok. Again, that in no
way invalidates pointer semantics. (And Guido could approve a perfectly
backwards-compatible PEP tomorrow that elevates references to the
first-class status.)

> As long as you are aware that analogies are always limited, you can
> certainly use them as part of an explanation; but you do have to take
> care.

I'm talking about a model, not a mere analogy.


Marko

[toc] | [prev] | [next] | [standalone]

#90853

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

> Chris Angelico <rosuav@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

[toc] | [prev] | [next] | [standalone]

Page 1 of 5  [1] 2 3 4 5  Next page →

Back to top | Article view | comp.lang.python

csiph-web