Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Indices Point Between Elements

blog.nelhage.com

Post reply on HN
Print view View original

31–40 of 66 posts

Re: Indices Point Between Elements

#31

Post by rcthompson »

Retra wrote: post #29
amelius wrote: post #18

Ugh. Please no. This only adds to the confusion, as now there are 2 ways in which indices can be interpreted.

Specifically, this: >"Indexing between elements, instead of indexing elements, helps avoid a large class of off-by-one errors." It only replaces them with indexing-method errors. Instead of remembering if my ranges are open or closed, I have to remember if they are using between-element indices or on-element indices. It's still going to cause the same kinds of problems.

You always have to remember what kind of indexing you are using in order to avoid making errors. But using this mental model will help people avoid making off-by-one errors because they don't even understand the indexing in the first place.

Re: Indices Point Between Elements

#32

Post by nfoz »

ajanuary wrote: post #26
LoSboccacc wrote: post #20

Earlier quoted context omitted.

_It used to be popular, and still is in some circles, to debate whether programming languages ought start array indexing at 0 or 1_ this is an exemplary case of citation needed if I ever saw one. maybe it's a valid debate for programming languages that doesn't allow people to do pointer arithmetic, which already restrict the field a lot, but even then that's sound as part of the 4GL bullshit that never really took of…

> sound as part of the 4GL bullshit Actually it's primarily early languages plus Lua. [0] https://en.m.wikipedia.org/wiki/Comparison_of_programming_la...

The Math-DSL's like Matlab, Julia, and Mathematica would like to chime in and say 1-based indexing translates better with math research/lit.

Re: Indices Point Between Elements

#33

Post by beagle3 »

LoSboccacc wrote: post #20
thwarted wrote: post #2

The visuals are definitely valuable in explaining this. It used to be popular, and still is in some circles, to debate whether programming languages ought start array indexing at 0 or 1. When talking about this with other programmers, I've discovered that a lot of the issues/confusion could be avoided by consistent use of terminology: Offsets/offsetting always being zero-based and indexes/indexing always being one-ba…

_It used to be popular, and still is in some circles, to debate whether programming languages ought start array indexing at 0 or 1_ this is an exemplary case of citation needed if I ever saw one. maybe it's a valid debate for programming languages that doesn't allow people to do pointer arithmetic, which already restrict the field a lot, but even then that's sound as part of the 4GL bullshit that never really took of…

I don't know what kind of citation would satisfy you. These debates still come up in e.g. the Lua (1-based) mailing list, and used to be everywhere.

Visual Basic had the "OPTION BASE" statement to select.[0] (Many other versions of basic did too)

APL also has the ⎕IO Index Origin setting [1]

If you want to see a lively debate, there's c2[2], and there's also Dijkstra[3]

[0] https://msdn.microsoft.com/en-us/library/aa266179%28v=vs.60%...

[1] https://en.wikipedia.org/wiki/APL_syntax_and_symbols

[2] http://c2.com/cgi/wiki?ZeroAndOneBasedIndexes

[3] http://www.cs.utexas.edu/users/EWD/ewd08xx/EWD831.PDF

Re: Indices Point Between Elements

#34

Post by arielby »

matchu wrote: post #23
LoSboccacc wrote: post #19

Earlier quoted context omitted.

also this works only in this special case of array being one sized. an index is an offset to a pointer in memory, shifted by the size of the structure it points to. there is no other way around, no magic tricks about index being between elements. of course people never exposed from c miss out all of this, and then are left to made up bullshit about how stuff actually works array index are offset to a memory location,…

Memory addresses are exactly analogous to array indices, and suffer from exactly the same semantics issues. After all, low-level memory is just an array of bytes. We do have a convention that dereferencing a memory address returns the 8 bits to the right of that address. We've even optimized our hardware for that convention. But that's just a convention of the dereference operation; it's not fundamental to the addres…

A pointer points to the start of its pointee - i.e. the point "just before" its pointee. That's how derived-to-base casts work. That's also how you can have "one-past-the-end" pointers, which are actually "just after" the relevant array.

for example, if you have the following structs

    typedef struct { void *key; } base;
    typedef struct { base b; int misc; int data[2]; } derived;
then derived is laid out as follows

    -----+------+---------+---------+---------+-----
     ... | base | derived | data[0] | data[1] | ...
    -----+------+---------+---------+---------+-----
         ^                ^                   ^
         |                |                   |
        base         derived.data      &derived.data[2]

Re: Indices Point Between Elements

#35

Post by matchu »

arielby wrote: post #34
matchu wrote: post #23

Earlier quoted context omitted.

Memory addresses are exactly analogous to array indices, and suffer from exactly the same semantics issues. After all, low-level memory is just an array of bytes. We do have a convention that dereferencing a memory address returns the 8 bits to the right of that address. We've even optimized our hardware for that convention. But that's just a convention of the dereference operation; it's not fundamental to the addres…

A pointer points to the start of its pointee - i.e. the point "just before" its pointee. That's how derived-to-base casts work. That's also how you can have "one-past-the-end" pointers, which are actually "just after" the relevant array. for example, if you have the following structs typedef struct { void *key; } base; typedef struct { base b; int misc; int data[2]; } derived; then derived is laid out as follows ----…

Yep. A pointer is a memory range, but it supports a cast operation that allows you to change the pointer type, and therefore the end address. I think we agree, right? :)

Re: Indices Point Between Elements

#36

Post by arielby »

matchu wrote: post #35
arielby wrote: post #34

Earlier quoted context omitted.

A pointer points to the start of its pointee - i.e. the point "just before" its pointee. That's how derived-to-base casts work. That's also how you can have "one-past-the-end" pointers, which are actually "just after" the relevant array. for example, if you have the following structs typedef struct { void *key; } base; typedef struct { base b; int misc; int data[2]; } derived; then derived is laid out as follows ----…

Yep. A pointer is a memory range, but it supports a cast operation that allows you to change the pointer type, and therefore the end address. I think we agree, right? :)

Except you can have a void* that does not have an end address.

Re: Indices Point Between Elements

#37

Post by duaneb »

thwarted wrote: post #2

The visuals are definitely valuable in explaining this. It used to be popular, and still is in some circles, to debate whether programming languages ought start array indexing at 0 or 1. When talking about this with other programmers, I've discovered that a lot of the issues/confusion could be avoided by consistent use of terminology: Offsets/offsetting always being zero-based and indexes/indexing always being one-ba…

I would argue an index, in the sense that it might be an integer, is indistinguishable from an offset. I would refer to one-based indexing as positional—1st, 2nd, 3rd, ..., ith.

Of course, it's the offset from the first element, so it's kind of a circular definition.

Re: Indices Point Between Elements

#38

Post by thwarted »

pavlov wrote: post #10
thwarted wrote: post #2

The visuals are definitely valuable in explaining this. It used to be popular, and still is in some circles, to debate whether programming languages ought start array indexing at 0 or 1. When talking about this with other programmers, I've discovered that a lot of the issues/confusion could be avoided by consistent use of terminology: Offsets/offsetting always being zero-based and indexes/indexing always being one-ba…

I remember something about the ground floor in the UK buildings not being "Floor 1" like it is in the United States. Actually, that's perfectly explained with your offset vs. index terminology. In some countries, the floor number is an index within the array of floors. In others, it's an offset from the ground.

Oh, I know it's perfectly explained by that, but using an example of building floors has cultural idioms. Ruler measurements and birthdays seem to be more universal.

Re: Indices Point Between Elements

#39

Post by orclev »

He undermines his own argument right out of the gate. When he shows the part about which number should be used for the last element in the range there's still two valid choices, you could choose to stop at 3 with the understanding that the element to the right of that is the last element to be selected, or to stop at 4 with the understanding that in this context your indexing is "special" and you're actually selecting the element to the left of the index.

Re: Indices Point Between Elements

#40

Post by marijn »

And this is why JavaScript's `lastIndexOf` method gets it wrong, wrong, wrong. (`"foo".lastIndexOf("o", 2)` yields 2, whereas I, and probably a lot of other people, would expect it to be 1, with the search starting at the space between element 1 and 2)
Post reply on HN