How Python works: What do you know about support for negative indices?

Discussion in 'Python' started by Raymond Hettinger, Sep 10, 2010.

  1. Hello Folks.

    It doesn't seem to be common knowledge when and how a[x] gets
    translated to a[x+len(x)]. So, here's a short info post on how Python
    supports negative indices for sequences.

    I've put the answer below, but if you want to quickly test your own
    knowledge, ask yourself which of these support negative indices:

    'abcde'[-2] # builtin string class, bracket
    syntax

    'abcde'.__getitem__(-2) # builtin class, magic method

    collections.deque('abcde')[-2] # extension class, bracket syntax

    collections.deque('abcde').__getitem__[-2] # extension class, magic
    method

    class S(str):
    pass

    class T(str):
    def __getitem__(self, i):
    print(i)
    return 'd'

    class U(str):
    def __getitem__(self, i):
    print(i)
    return 'd'
    def __len__(self):
    return 5

    class V(str):
    'str subclass overriding key methods'
    def __getitem__(self, i):
    print(i)
    return 'd'
    def __len__(self):
    return 5
    def __iter__(self):
    return iter('abcde')
    def __contains__(self, val):
    return val in 'abcde'

    class W:
    'object subclass registered as Sequence'
    def __init__(self, data):
    self.data = data
    def __getitem__(self, i):
    print(i)
    return 'd'
    def __len__(self):
    return 5
    def __iter__(self):
    return iter('abcde')
    def __contains__(self, val):
    return val in 'abcde'
    collections.Sequence.register(V)

    class X(collections.Sequence):
    'Subclass the Sequence abstract base class'
    def __init__(self, data):
    self.data = data
    def __getitem__(self, i):
    print(i)
    return 'd'
    def __len__(self):
    return 5
    def __iter__(self):
    return iter('abcde')
    def __contains__(self, val):
    return val in 'abcde'

    Essentially, the example raise these questions:

    * Are negative indices tied to the grammar (i.e. binary subscription)?
    * Does it matter if you call a magic method instead of using
    brackets?
    * Are they tied to particular concrete classes (str, list, tuple,
    deque, dict)?
    * If so, how does subclassing affect index handling?
    * What parts of user defined classes affect handling of indices?
    * Are they part of the abstract layer (PyObject_GetItem)?
    * Are they tied to the Sequence ABC?
    * How are mapping lookups differentiated (d[-2] where d is a Mapping)?

    ------------- Answers below --------------
    |
    |
    |
    |
    |
    |
    |
    |
    |
    |
    |
    |
    |
    |
    |
    |

    The first five examples support negative indices. The builtin
    sequence types: str, deque, list and tuple, all have negative index
    support built in to their concrete implementations (such as
    str.__getitem__) and that behavior persists for subclassers as long as
    they don't override __getitem__.

    The parse of "a['x']" matches the "subscription" rule in Grammar/
    Grammar. That compiles the BINARY_SUBSCR opcode which pops off the
    evaluated expressions for "a" and "x" and calls the abstract layer,
    PyObject_GetItem() which routes most calls to the concrete
    implementation (i.e. myobj.__getitem__).

    The exception to concrete dispatch is a fast path for builtin classes
    or their subclasses that
    1) are recognized as sequences (i.e. not a dictionary and have not
    overridden __getitem__)
    2) where "x" is an index (i.e. not a float)
    If so, it is passed to an intermediate abstract layer,
    PySequence_SetItem() which will apply negative index handling iff the
    sequence defines a __len__ method.

    In other words, the handling of negative indices is always up to the
    concrete class.
    It is not part of the grammar, or the definition of subscriptions, or
    the dispatch sequence.

    The docs guarantee that Python's builtin sequences implement support
    for negative indices ( http://docs.python.org/dev/reference/expressions.html#subscriptions
    ) and they all do so through their individual __getitem__
    implementations. Builtin Python sequences also have a fast path that
    make negative index handling automatic, but this is just an invisible
    optimization and can be bypassed by calling myobj.__getitem__
    directly.

    Note on slicing: slices are handled the same way (at least in 3.x),
    so it is the responsibility of concrete classes to add support if they
    choose to do so. Some, like lists tuples and string do support
    slicing and some objects like deque do not. Interestingly, the grammar
    has rules for slicing, but that is implemented as making a slice
    instance as the argument to the lookup. The actual lookup work is
    dispatched to the concrete class and there is no fast path along the
    way.

    Hope you all found this to be informative,


    Raymond
     
    Raymond Hettinger, Sep 10, 2010
    #1
    1. Advertising

  2. Raymond Hettinger

    Mark Tolonen Guest

    Re: How Python works: What do you know about support fornegativeindices?

    "Ben Finney" <> wrote in message
    news:...
    > Raymond Hettinger <> writes:
    >
    >> It doesn't seem to be common knowledge when and how a[x] gets
    >> translated to a[x+len(x)]. So, here's a short info post on how Python
    >> supports negative indices for sequences.

    >
    > Thanks for this. Could you post your messages using a channel that
    > doesn't arbitrarily split your paragraphs into long-short-long-short
    > lines? It makes paragraphs burdensome to read, and I skipped most of the
    > message because of that.
    >
    > I encourage anyone whose messages are munged like that to seek
    > correction from their mail service provider, and switch to a different
    > one until it's fixed.
    >
    > --
    > \ “Oh, I realize it's a penny here and a penny there, but look at |
    > `\ me: I've worked myself up from nothing to a state of extreme |
    > _o__) poverty.†—Groucho Marx |
    > Ben Finney
    > --
    > http://mail.python.org/mailman/listinfo/python-list


    It came across fine for me (on much maligned Outlook Express, no less).

    -Mark
     
    Mark Tolonen, Sep 10, 2010
    #2
    1. Advertising

  3. Raymond Hettinger

    Neil Hodgson Guest

    Re: How Python works: What do you know about support for negativeindices?

    Mark Tolonen:

    > It came across fine for me (on much maligned Outlook Express, no less).


    Yes, looks fine to me both in Thunderbird (news, not mailing list)
    and at Google Groups. There is a single text part with all lines except
    an URL easily within 80 columns. Perhaps there is a problem in Ben's
    reader or in the mailing list gateway.

    Neil
     
    Neil Hodgson, Sep 10, 2010
    #3
  4. Raymond Hettinger wrote:
    > collections.deque('abcde').__getitem__[-2] # extension class, magic
    > method


    Small nit: You don't mean [square] brackets here, right?

    Otherwise, good posting, thank you!

    Uli

    --
    Sator Laser GmbH
    Geschäftsführer: Thorsten Föcking, Amtsgericht Hamburg HR B62 932
     
    Ulrich Eckhardt, Sep 10, 2010
    #4
  5. Ben Finney <> writes:

    > Raymond Hettinger <> writes:
    >
    >> It doesn't seem to be common knowledge when and how a[x] gets
    >> translated to a[x+len(x)]. So, here's a short info post on how Python
    >> supports negative indices for sequences.

    >
    > Thanks for this. Could you post your messages using a channel that
    > doesn't arbitrarily split your paragraphs into long-short-long-short
    > lines?


    hi Ben, i see that you uses gnus... well, it's gnus that does the
    unwanted formatting

    try C-u g, as dettailed below, ciao

    g runs `gnus-summary-show-article'

    `gnus-summary-show-article' is an interactive compiled Lisp function
    -- loaded from "gnus-sum"
    (gnus-summary-show-article &optional ARG)

    Documentation:
    Force redisplaying of the current article.
    If ARG (the prefix) is a number, show the article with the charset
    defined in `gnus-summary-show-article-charset-alist', or the charset
    input.
    If ARG (the prefix) is non-nil and not a number, show the raw article
    without any article massaging functions being run. Normally, the key
    strokes are `C-u g'.
    --
    la lenza penzola
    -- PMF, in IHC
     
    Giacomo Boffi, Sep 10, 2010
    #5
  6. Re: How Python works: What do you know about support for negativeindices?

    On Thu, 09 Sep 2010 18:37:49 -0700, Raymond Hettinger wrote:

    > Hello Folks.
    >
    > It doesn't seem to be common knowledge when and how a[x] gets translated
    > to a[x+len(x)]. So, here's a short info post on how Python supports
    > negative indices for sequences.

    [...]
    > Hope you all found this to be informative,



    Thanks Raymond!


    --
    Steven
     
    Steven D'Aprano, Sep 10, 2010
    #6
  7. Re: How Python works: What do you know about support for negativeindices?

    > Raymond Hettinger <> writes:
    >
    >> It doesn't seem to be common knowledge when and how a[x] gets
    >> translated to a[x+len(x)]. So, here's a short info post on how Python
    >> supports negative indices for sequences.

    >
    > Thanks for this. Could you post your messages using a channel that
    > doesn't arbitrarily split your paragraphs into long-short-long-short
    > lines?


    It came across fine for me as well (gmail with basic html interface).

    > It makes paragraphs burdensome to read, and I skipped most of the
    > message because of that.


    You might want to switch to a client where you do not have this problem.

    > I encourage anyone whose messages are munged like that to seek
    > correction from their mail service provider, and switch to a different
    > one until it's fixed.


    I encourage anyone who has problems with reading various emails,
    newsgroup postings, forums and what not, to start using modern tools
    that work with the vast majority of other tools.

    Cheers,
    Daniel


    --
    Psss, psss, put it down! - http://www.cafepress.com/putitdown
     
    Daniel Fetchinson, Sep 10, 2010
    #7
  8. Raymond Hettinger

    Terry Reedy Guest

    Re: How Python works: What do you know about support for negativeindices?

    On 9/9/2010 9:37 PM, Raymond Hettinger wrote:

    > The docs guarantee that Python's builtin sequences implement support
    > for negative indices (


    http://docs.python.org/dev/reference/expressions.html#subscriptions

    The relevant paragraphs are
    "
    For built-in objects, there are two types of objects that support
    subscription:

    If the primary is a mapping, the expression list must evaluate to an
    object whose value is one of the keys of the mapping, and the
    subscription selects the value in the mapping that corresponds to that
    key. (The expression list is a tuple except if it has exactly one item.)

    If the primary is a sequence, the expression (list) must evaluate to an
    integer. If this value is negative, the length of the sequence is added
    to it (so that, e.g., x[-1] selects the last item of x.) The resulting
    value must be a nonnegative integer less than the number of items in the
    sequence, and the subscription selects the item whose index is that
    value (counting from zero).
    "

    Reading the third paragraph out of context, one can miss the restriction
    to built-in objects. I had assumed that the conversion using len(), when
    available, happened prior to the __getitem__ call. I believe I need to
    add the restriction in my discussion of negative indexing in my book. I
    would like the above rewritten something like the following:
    "
    Two types of built-in objects support subscription as primaries:
    mappings and sequences.

    For built-in mappings, the....

    For built-in sequences, the ...
    "

    The second paragraph was written before defaultdict and does not apply
    to them. I presume that it is an extension rather than built-in class
    for the purpose of the Reference.

    > Hope you all found this to be informative,


    Definitely. I save a copy for future reference.

    --
    Terry Jan Reedy
     
    Terry Reedy, Sep 10, 2010
    #8
  9. Raymond Hettinger

    Aahz Guest

    Re: How Python works: What do you know about support for negativeindices?

    In article <>,
    Daniel Fetchinson <> wrote:
    >Attribution missing:
    >>
    >> I encourage anyone whose messages are munged like that to seek
    >> correction from their mail service provider, and switch to a different
    >> one until it's fixed.

    >
    >I encourage anyone who has problems with reading various emails,
    >newsgroup postings, forums and what not, to start using modern tools
    >that work with the vast majority of other tools.


    Why? Raymond's post worked fine for me with trn3.6....
    --
    Aahz () <*> http://www.pythoncraft.com/

    [on old computer technologies and programmers] "Fancy tail fins on a
    brand new '59 Cadillac didn't mean throwing out a whole generation of
    mechanics who started with model As." --Andrew Dalke
     
    Aahz, Sep 10, 2010
    #9
  10. Raymond Hettinger

    Aahz Guest

    In article <>,
    Ben Finney <> wrote:
    >Ben Finney <> writes:
    >> Raymond Hettinger <> writes:
    >>>
    >>> It doesn't seem to be common knowledge when and how a[x] gets
    >>> translated to a[x+len(x)]. So, here's a short info post on how
    >>> Python supports negative indices for sequences.

    >>
    >> Thanks for this. Could you post your messages using a channel that
    >> doesn't arbitrarily split your paragraphs into long-short-long-short
    >> lines? It makes paragraphs burdensome to read, and I skipped most of
    >> the message because of that.

    >
    >For those who think the problem may be with the recipient's software, I
    >see the same annoying line-wrapping problems in the archived message
    ><URL:http://mail.python.org/pipermail/python-list/2010-September/1255167.html>.


    Still looks like *your* problem to me; except for exactly one paragraph,
    I don't see comb-style formatting in Lynx at that URL.
    --
    Aahz () <*> http://www.pythoncraft.com/

    [on old computer technologies and programmers] "Fancy tail fins on a
    brand new '59 Cadillac didn't mean throwing out a whole generation of
    mechanics who started with model As." --Andrew Dalke
     
    Aahz, Sep 11, 2010
    #10
  11. Raymond Hettinger

    Neil Hodgson Guest

    Re: How Python works: What do you know about support for negativeindices?

    Ben Finney:

    > For those who think the problem may be with the recipient's software, I
    > see the same annoying line-wrapping problems in the archived message
    > <URL:http://mail.python.org/pipermail/python-list/2010-September/1255167.html>.


    That looks well-formatted to me and just the same as I see in a news
    reader. There appear to be deliberate wraps at sentence end or automatic
    wraps to fit <80 columns. Which lines are wrong and why are they wrong?

    Neil
     
    Neil Hodgson, Sep 11, 2010
    #11
  12. Raymond Hettinger

    Aahz Guest

    In article <>,
    Ben Finney <> wrote:
    >Neil Hodgson <> writes:
    >>
    >> There appear to be deliberate wraps at sentence end or automatic wraps
    >> to fit <80 columns.

    >
    >The automatic wraps in the code presented in the message are wrong. The
    >automatic wraps in the bullet point list are, if not wrong, at least
    >presumably unintended.


    That is considerably different from your original claim that the post
    contained formatting that was "long-short-long-short", aka comb
    formatting.

    >I hope that clears up what I meant in this case. The effort devoted to
    >explaining this issue far outweighs the burden it caused initially. I'll
    >try to be more explicit when presenting it in future, to forestall this.


    s/explicit/accurate/

    Had you noted that some lines of code were wrapped short, I would have
    agreed with you, but I also would have noted that it's not a big deal.
    --
    Aahz () <*> http://www.pythoncraft.com/

    [on old computer technologies and programmers] "Fancy tail fins on a
    brand new '59 Cadillac didn't mean throwing out a whole generation of
    mechanics who started with model As." --Andrew Dalke
     
    Aahz, Sep 12, 2010
    #12
  13. Re: How Python works: What do you know about support for negative indices?

    [Ben Finney]
    > I encourage anyone whose messages are munged like that to seek
    > correction from their mail service provider, and switch to a different
    > one until it's fixed.


    The post was typed on a mobile device into the text window on Google
    Groups.

    It's too bad that inane concerns with newline placement overwhelmed
    the substance of the post.


    Raymond
     
    Raymond Hettinger, Sep 13, 2010
    #13
  14. Re: How Python works: What do you know about support for negative indices?

    On Sep 10, 2:13 pm, Terry Reedy <> wrote:

    > Reading the third paragraph out of context, one can miss the restriction
    > to built-in objects. I had assumed that the conversion using len(), when
    > available, happened prior to the __getitem__ call.


    Yes, that's a common misconception. It is probably based on
    the current wording of the docs and on the PySequence_GetItem()
    optimized fast-path for builtin and extension sequences.

    From the users point-of-view, the important thing is that it
    (effectively) occurs in the __getitem__() code, that builtin
    sequences and extensions support it, and that else where it is
    optional.

    Another way of saying it is: if you are ever writing a __getitem__()
    method in Python (even for a subclass of a builtin sequence), then it
    is up to you to decide whether to add support for negative indices
    and slicing.


    Raymond
     
    Raymond Hettinger, Sep 13, 2010
    #14
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. prem_eda
    Replies:
    5
    Views:
    7,888
    Pieter Hulshoff
    Oct 11, 2004
  2. dan
    Replies:
    13
    Views:
    541
    Jacek Generowicz
    Sep 17, 2003
  3. Replies:
    11
    Views:
    509
    Antoon Pardon
    Jun 26, 2006
  4. Joakim Hove

    Negative indices to a vector: Valid?

    Joakim Hove, Dec 22, 2005, in forum: C Programming
    Replies:
    8
    Views:
    296
    EventHelix.com
    Dec 24, 2005
  5. Andries

    I know, I know, I don't know

    Andries, Apr 23, 2004, in forum: Perl Misc
    Replies:
    3
    Views:
    242
    Gregory Toomey
    Apr 23, 2004
Loading...

Share This Page