I see that Dijkstra text posted a thousand times whenever this comes up, as it often does, and the more I reread it, the more wack I find it.
To the extent that Dijkstra’s essay can be read as implying that ordinal numbering should start at 0, that is messed up.
His text reads as “this is element number zero, this is element number one, this is element number two, this is element number three”. Creating a mismatch between cardinal and ordinal. That is not OK. I don’t have 3 apples when I have four.
There are good reasons to prefer 0-based indexing for arrays as I wrote in another subthread to this post: “Think of it as how many rooms do I need to go to to get to the kitchen? Zero if you already are in the kitchen. One if you are in the second room. Two if you are in the third room.” That makes sense to me.
But “numbering” should not and does not start at zero. Dijkstra isn’t clear, so I’m only arguing against this particular reading of his text (which might be the reading he intended, which would be an indictment of his reasoning, but I don’t presume it is).
Edit: I mean, he literally says it:
So let us let our ordinals start at zero: an element’s ordinal (subscript) equals the number of elements preceding it in the sequence.
That is quite wack. I’m not onboard with that. Instead, recognize that it’s not the element’s subscript, it’s the offset’s subscript.
The cardinal/ordinal mismatch can be seen as an interplay between sets and numerals. Using Von Neumann’s ordinals, the zeroth cardinal is the cardinality of the empty set, which is the zeroth Von Neumann ordinal. The first cardinal is the cardinality of the set with one element, which is (isomorphic to) the first ordinal, etc.
I am the “someone” in “someone linked me a story.” I consider myself corrected on the history of the zero-based index convention. I shall endeavor not to take advantage of @hwayne’s good nature by trolling them into doing any additional research for free.
I disagree that zero-based indexing is “the right choice” and the others are, as Dijkstra put it, “ugly.” Those are aesthetic judgements with which I happen to disagree. But our debate was really much more about where the convention came from, rather than what the convention ought to be. On the subject of origins, bravo.
Think of it as how many rooms do I need to go to to get to the kitchen? Zero if you already are in the kitchen. One if you are in the second room. Two if you are in the third room.
The key is to not think of e[0] as “this is the zeroeth element in e”. The number 0 doesn’t belong to the element, it belongs to the array subscript operator. How many steps do you need to tell it to go to find the element you want? If zero steps, then e[0]. If five steps, then e[5]. Don’t think of e[5] as some kind of Leeloo Dallas Multipass fictional “fifth element”. That’s watching way too much Captain Planet. Instead, think of it as asking the array subscript operator to go five steps to get you an element.
Like on your hand, the elements are the fingers and the steps are the spaces between your fingers.
Understand this and you’re on the way to making waaay fewer, if any, off-by-one errors. Good luck my friends♥
But I’m not in the kitchen! I am outside looking at the house. This has smells of C where int* is “an array”. In that case you really are in the kitchen as an array is the same thing as the pointer to the first element. For languages where an array is more encapsulated it is very clear that std::vector<int> is not equivalent to the first element.
The “offset” explanation I give is a way to remember and understand the indexing in a way that makes sense. If you are on the outside looking in to a house, you can see the first, second, and third room. It’s not the zeroeth, first, and second room.
Between the rooms, however, you can see the first and the second door.
Another example is Lisp where we have first, second, third as synonyms for (car), (cadr), (caddr) etc. You start at the first cell and work your way through increasing dereferences. That’s a linked list rather than a pointer to a linear allocation but you’re still in the kitchen.
I’m not arguing for or against a particular notation—some contexts call for 1-indexing, others for 0-indexing—but I’m arguing against Dijkstra’s reasoning in the essay.
The observation that conventions a) and b) have the advantage that the difference between the bounds as mentioned equals the length of the subsequence is valid.
That’s great. But if I ask you to bring me volumes three to five of a book series, or read pages 17–20 for homework, don’t skip the last one.
Books also don’t start at page 0.
The way Dijkstra explains it is so unnatural and wrong that it’s a recipe for off-by-one errors. When I started thinking of it this way instead (that it’s the stairs that are numbered, not the floors), I stopped making those errors.
Dijkstra’s text is always trotted out as a be-all, end-all, debate ender even though it doesn’t really have any arguments (he prefers conventions a and b so that the bounds delta is the cardinality—and that is fine, dates and times often use the same convention (“I work nine to five” is commonly understood as nine hours) while pages, issues, volumes, house numbers do not) and he prefers conventions A and D even though they make the maximal ordinal mismatch the cardinal.
This is just arbitrary. You could make a programming language where the order as 8, 6, 7, 5, 3, 0, 9 for all I care. An elegant language is consistent and designed to match up as you combine its parts, which is why C (correctly) uses 0-based, offset-based indexing while CSS (which is also good) uses 1-based element indexing.
Saying “programmers should start counting at 0” is a common joke but not as funny when people start taking it literally.
Having the ordinal match the cardinal is just good practice and in languages where there are practical reasons to index on zero (like C, for the array offsets) it’s good to have a mental model of seeing the indices as counting something else not the element. It’s just a super good and healthy mnemonic to see
apple[0], the first apple, apple number one, as “this apple”
apple[1] as one apple over, the next apple, the second apple.
apple[2], the third apple, two apples away, two apples over
See the [] dereference operator as how far you must reach. It’s just a better way to make sense of the cruft of languages and practices and not get tangled up.
(“I work nine to five” is commonly understood as nine hours)
Where is that? Here in .fi I think everyone would think of that as coming in at nine, leaving at seventeen, making eight hours.
We also say “half five” when we mean 16:30 (or 4:30), as I think the Germans do, but there are others who parse that as “half (past) five”, ie 17:30 (or 5:30).
I don’t know if this and the way we number our floors affects our thinking of indexes, but it doesn’t seem to hurt.
It’s been a while since homework, but in that case I do seem to recall the last page was included, though ending times are not, so there may be other exceptions I can’t think of now.
Coming in at nine leaving at seventeen is what I meant! Which is convention a or b (I got that part right) which is eight hours, not nine (I got that part wrong). So as I said, times and dates often do use Dijkstra’s convention a or b but books don’t. 🤷🏻♀️
I was taught it is so that when you have a 2D array, packed linearly into memory of course, and you want to know what row you’re in, modular division works so nicely.
Having cited Hoye’s original a couple of times, I felt obliged to post Hoye’s rebuttal to @hwayne. Doing so does not mean that I rescind my earlier concession on the topic.
This is a long take, but the answer is well known: “Who are you? How did you get into my house?”
Source: https://xkcd.com/163/
Seriously, Donald Knuth did write about reasons for this outside of simple computational convenience.
As did Dijkstra https://www.cs.utexas.edu/users/EWD/transcriptions/EWD08xx/EWD831.html
I see that Dijkstra text posted a thousand times whenever this comes up, as it often does, and the more I reread it, the more wack I find it.
To the extent that Dijkstra’s essay can be read as implying that ordinal numbering should start at 0, that is messed up.
His text reads as “this is element number zero, this is element number one, this is element number two, this is element number three”. Creating a mismatch between cardinal and ordinal. That is not OK. I don’t have 3 apples when I have four.
There are good reasons to prefer 0-based indexing for arrays as I wrote in another subthread to this post: “Think of it as how many rooms do I need to go to to get to the kitchen? Zero if you already are in the kitchen. One if you are in the second room. Two if you are in the third room.” That makes sense to me.
But “numbering” should not and does not start at zero. Dijkstra isn’t clear, so I’m only arguing against this particular reading of his text (which might be the reading he intended, which would be an indictment of his reasoning, but I don’t presume it is).
Edit: I mean, he literally says it:
That is quite wack. I’m not onboard with that. Instead, recognize that it’s not the element’s subscript, it’s the offset’s subscript.
The cardinal/ordinal mismatch can be seen as an interplay between sets and numerals. Using Von Neumann’s ordinals, the zeroth cardinal is the cardinality of the empty set, which is the zeroth Von Neumann ordinal. The first cardinal is the cardinality of the set with one element, which is (isomorphic to) the first ordinal, etc.
Which is closer to what I’ve been saying about offset indexing as opposed to Dijkstra’s talk of “an element’s ordinal”.
“I’m a locksmith, and I’m a locksmith.”
so does your life: What age are you on birth?
That depends on what country you were born in.
Really? What are the options?
In Japan you are 1 the day you’re born, or so I’m told. The same is true in the US of racehorses.
Just today I heard something similar but slightly different about Korea.
Found this relevant Wikipedia article: https://en.m.wikipedia.org/wiki/East_Asian_age_reckoning#Korea
That page also includes info about the age systems for other East Asian countries.
That was, roughly, how it worked in pre-modern Japan.
One.
I am in my first year of life.
Suggested tag: rant
I am the “someone” in “someone linked me a story.” I consider myself corrected on the history of the zero-based index convention. I shall endeavor not to take advantage of @hwayne’s good nature by trolling them into doing any additional research for free.
I disagree that zero-based indexing is “the right choice” and the others are, as Dijkstra put it, “ugly.” Those are aesthetic judgements with which I happen to disagree. But our debate was really much more about where the convention came from, rather than what the convention ought to be. On the subject of origins, bravo.
https://idiomdrottning.org/offset-indexing
But I’m not in the kitchen! I am outside looking at the house. This has smells of C where
int*is “an array”. In that case you really are in the kitchen as an array is the same thing as the pointer to the first element. For languages where an array is more encapsulated it is very clear thatstd::vector<int>is not equivalent to the first element.Making sense of C’s crazy is the point, yeah.
The “offset” explanation I give is a way to remember and understand the indexing in a way that makes sense. If you are on the outside looking in to a house, you can see the first, second, and third room. It’s not the zeroeth, first, and second room.
Between the rooms, however, you can see the first and the second door. Another example is Lisp where we have
first,second,thirdas synonyms for(car),(cadr),(caddr)etc. You start at the first cell and work your way through increasing dereferences. That’s a linked list rather than a pointer to a linear allocation but you’re still in the kitchen.I’m not arguing for or against a particular notation—some contexts call for 1-indexing, others for 0-indexing—but I’m arguing against Dijkstra’s reasoning in the essay.
That’s great. But if I ask you to bring me volumes three to five of a book series, or read pages 17–20 for homework, don’t skip the last one.
Books also don’t start at page 0.
The way Dijkstra explains it is so unnatural and wrong that it’s a recipe for off-by-one errors. When I started thinking of it this way instead (that it’s the stairs that are numbered, not the floors), I stopped making those errors.
Dijkstra’s text is always trotted out as a be-all, end-all, debate ender even though it doesn’t really have any arguments (he prefers conventions a and b so that the bounds delta is the cardinality—and that is fine, dates and times often use the same convention (“I work nine to five” is commonly understood as nine hours) while pages, issues, volumes, house numbers do not) and he prefers conventions A and D even though they make the maximal ordinal mismatch the cardinal.
This is just arbitrary. You could make a programming language where the order as 8, 6, 7, 5, 3, 0, 9 for all I care. An elegant language is consistent and designed to match up as you combine its parts, which is why C (correctly) uses 0-based, offset-based indexing while CSS (which is also good) uses 1-based element indexing.
Saying “programmers should start counting at 0” is a common joke but not as funny when people start taking it literally.
Having the ordinal match the cardinal is just good practice and in languages where there are practical reasons to index on zero (like C, for the array offsets) it’s good to have a mental model of seeing the indices as counting something else not the element. It’s just a super good and healthy mnemonic to see
See the [] dereference operator as how far you must reach. It’s just a better way to make sense of the cruft of languages and practices and not get tangled up.
Where is that? Here in .fi I think everyone would think of that as coming in at nine, leaving at seventeen, making eight hours.
We also say “half five” when we mean 16:30 (or 4:30), as I think the Germans do, but there are others who parse that as “half (past) five”, ie 17:30 (or 5:30).
I don’t know if this and the way we number our floors affects our thinking of indexes, but it doesn’t seem to hurt.
It’s been a while since homework, but in that case I do seem to recall the last page was included, though ending times are not, so there may be other exceptions I can’t think of now.
Coming in at nine leaving at seventeen is what I meant! Which is convention a or b (I got that part right) which is eight hours, not nine (I got that part wrong). So as I said, times and dates often do use Dijkstra’s convention a or b but books don’t. 🤷🏻♀️
I was taught it is so that when you have a 2D array, packed linearly into memory of course, and you want to know what row you’re in, modular division works so nicely.
I always thought that: array-addr + index = item
If the memory model was prefixed with the array length, maybe using 1 would make sense, otherwise it makes pointer arithmetic a total pain.
I think the real question here is whether there’s still a reason to do this in languages that don’t have pointer arithmetic, right?
Or linked lists.
This is the best way to remember it and think of it. And it matches with what the OP says: “it matches machine semantics more”. Which is true.
Having cited Hoye’s original a couple of times, I felt obliged to post Hoye’s rebuttal to @hwayne. Doing so does not mean that I rescind my earlier concession on the topic.