Live data from Hacker News

Indices Point Between Elements

blog.nelhage.com

61–66 of 66 posts

Re: Indices Point Between Elements

#61
post #37
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.

Generally, it's useful to distinguish offset from name sometimes. For instance, gravitational potential energy has numbers associated with different amounts, but once you choose an origin you can compute energy differences.

Another example is screen space versus screen displacement. This is the difference between affine space and a vector space. Whether the upper corner is (0,0) or (222,22) shouldn't matter as long as you are doing everything relative to some point.

In C, I argue we always use offsets. Each element of an array A is at a particular memory location, the name of the array being the first memory location, and then A[i] means take the thing at A+i. Notice that the difference p-q between two memory locations p and q is exactly the offset you put into an index expression: q[p-q] == *p.

That said, it is convenient to confuse the offset with the memory location since 1. the memory location is likely not known when writing the program 2. if it were known, it would be almost impossible to use.

Now, an anecdote: I was helping implement a QR factoring algorithm from a textbook which uses 1-based indexing in a language which uses 0-based offsets. We tried changing the bounds of the nested loops to account for the difference, but it was basically impossible to avoid off-by-one errors. So, we left the loop bounds as the textbook had them and instead indexed like A[i-1], since this i-1 is the offset from A[0], the array element labeled 1.

Re: Indices Point Between Elements

#62
post #52

Earlier quoted context omitted.

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.

Ah, ok. In that case, wouldn't the floors actually be a good real-world example to students? It's a case where the index vs. offset convention seems to be split roughly 50%/50% around the world. If people can't agree about which way is better for numbering floors, it's no surprise that number-crazy programmers can't agree about numbering a whole lot of other things :)

In that case, wouldn't the floors actually be a good real-world example to students? It's a case where the index vs. offset convention seems to be split roughly 50%/50% around the world.

I suppose it would be a good real world example of the contrast, but I was saying I don't think it's a good, universal example to explain indexing or offsetting specifically. "You start your fourth year alive on your third birthday" has nearly universal understanding, "You exit the building on the floor numbered 1" is highly idiomatic.

Re: Indices Point Between Elements

#63

Once at a party I accidentally started an argument about which way toilet paper should hang from the roll (front or back) by mentioning how silly it was that people would argue about such a trivial matter.

Also at which and do you start pealing a banana?

Re: Indices Point Between Elements

#66
I have sometimes wondered whether it would be useful to have two different types for indices, depending on if we are indexing the elements themselves or the "gaps" between them. Let's say I'm thinking about some language like Haskell, where types are already a big deal.

That way the compiler would be able to tell if I accidentally mixed the two. Every conversion would have to explicit: for example, there might be two functions, "before" and "after", that take a gap index, and return an element index.

I think I might actually enjoy programming this way, but perhaps others would find it needlessly bureaucratic.

Post reply on HN