Dijkstra: Why numbering should start at zero | Hacker News Reader

Dijkstra: Why numbering should start at zero

cs.utexas.edu

48 pointsthunk71 comments

For my MSc thesis I'm programming some stuff for the Cell B.E. processor. It provides AltiVec vector instructions which allow quick parallel computation. It's great for getting nice speed ups, but it requires a lot of thought and bit twiddling from time to time.

It has two C "intrinsics" called vec_mule() and vec_mulo(). These take in two vectors of integer datatypes (char, short) for multiplication and produces one vector with items that are twice as big. char becomes short, short becomes long. To make room for these larger datatypes it only multiplies the even (vec_mule) or the odd (vec_mulo) items.

It's a nice construction, until you start to wonder which elements are even. Is "element 0" even, or is the "first element" odd? Should I really have to wonder about that?

I have never questioned the utter coolness of starting at index 0, until I encountered this. I do not know why we start at 0 if the rest of the world starts at 1, but it seems silly and without reason.

Well, the rest of the world also starts at 0:

1 sheep -> the number of sheep present when there is one

0 sheep -> the number of sheep present when there are none

Because you normally only enumerate things that are there it seems like you are starting at '1', but really you start relative to the situation where there are 'none'.

You can't have 'negative' presence of anything so it took a while longer to realize that there might be negative numbers too.

As for element 0 being odd or even, it's even.

So, it isn't silly and it has a reason.

0 is one of the biggest inventions in the history of mankind, programmers have given it it's natural place because we could not make our computers work if we didn't do that.

Imagine binary logic based on '1' and '2'....

> Well, the rest of the world also starts at 0

Yes, they do, when they have no elements. But if an array has an element 0, it actually has 1 element, not 0. Whereas if I have a sheep 1, I have 1 sheep. There is no sheep 0.

I think it would be good to note that I have nothing against 0 as a number. It's useful for many purposes including to indicate that a set actually has 0 elements, but I'm not so sure it's such a good idea to actually call the first element element 0.

You are confusing 'rank' with 'count'.

Not that I know of. Normal people and programmers do not count the same way.

        | last |
        | rank | count
  ------+------+-------
  sheep |  2   |   2
  sheep |  1   |   1
  sheep |  -   |   0
  ------+------+-------
  array |  1   |   2
  array |  0   |   1
  array |  -   |   0

Programmers are pretty normal people :)

When counting sheep in a field I'll count 1 sheep, 2 sheep etc.

When counting variables I'll say one variable, two variables and so on.

No difference there.

When placing items in an array I say this value goes in to slot '0', this will go into slot '1'. The slots are labelled with their index. And I will say there are now two values stored in the array, one at 'position' 0 and one at 'position' 1.

I think the whole problem disappears when you think of 'rank' as labels and count as the actual number of elements.

The first sheep is just a label you stick on a sheep to identify it, that makes it different from the other sheep.

Er, that's all worng. The question isn't number of, but index of. The index of the first element in a collection is 0. The index of the first sheep in a flock is (conventionally) 1. The total elements up to index n (inclusive) is n+1 -- the opposite parity -- which can be initially confusing.

An index is a label, a convenient way of finding something when you remember where you left it. You can start your indexing at any offset, you don't even need to use numbers (you could for instance look at an associative array where you store stuff based on a hash of some value).

index = position, label

The count is the number of occupied slots and is totally independent of the positions or labels.

Otherwise how would you count the number of elements in a sparse matrix ?

In this particular case though, where you have operations depending on evenness/oddness of some attribute related to position in a set (either position by index, or count) and the index starts with 0, there is absolutely confusion to be had over which implementation would be used.

Your logic is sound, but it's counter-intuitive to think of Obj[2] as a member of 'mulo', an odd number, "because 2 is really the 3rd element". A person implementing the system could be logical by your ideal (making 2 odd) or logical by the ideal of common sense and readability (making 2 even). Either could validly hold in a person's mind.

Given the ambiguity, I think it just shows that you shouldn't base operations on oddness/evenness, or should rigidly and obviously define them if you must use them.

I'm happy to see this. I should have submitted it when I found it. The version I found appears to be handwritten by Dijkstra and I like it better that way.

http://www.cs.utexas.edu/~EWD/ewd08xx/EWD831.PDF

Absolutely. His penmanship is as thoughtful as his bearing. I just hate pdf links.

It's fairly straightforward if you're a C programmer and think of arrays as contiguous blocks of memory.

int * a = (int * )malloc(5);

a is a pointer to the beginning of an integer (default 4 byte) array. a[i] == a + i == ((uint8_t * )a)+i*sizeof(int). Therefore, a[0] == a + 0 == the first element in a contiguous block of memory.

which would also illustrate what K&R said about array indices just being syntactic sugar for pointer arithmetic.

My mind has been blown.

If that blows your mind, you might want to avoid looking at the following: "foo"[2] == ("foo"+2) == (2+"foo") == 2["foo"]. And yes, you really can do that: in general a[b] and b[a] are exactly the same thing in C.

More C array pointer fun:

  *("abcdefg" + 3) == 'd'

sure as long as you don't care about stuff like unicode..

not quite. "foo"[2] is a char, ("foo"+2) is a string.

oh, bother, I forgot what HN does to asterisks. In what I wrote above, look for the bit in italics and mentally insert asterisks on each side of it. It was right when I typed it in, I promise...

I am starting to think Dijkstra is about the worst thing ever happening to software development.

He arguments that option A is the least ugly one, but forgets that computers have maximum numbers.

According to Dijkstra, you should test if a variable is a valid integer like: 0 <= var < MaxInt + 1. The best possible outcome of such a test would be a compiler error.

His argument that sequences defined as min <= i < (max + 1) because (max + 1) - min = total number of items is just silly. Maybe true for maths, not so for programmers. When reading code, you want to know if the code is valid, not how many items there are in a list. And reading i <= Max instead of i < (max + 1) is simpler.

Secondly, his article is about 0 or 1 based arrays, not random selections. And in case of 1 based arrays, the max = total number of elements.

So option C is best.

About whether 0 or 1 based arrays are better. They both have their uses. 0 based for spatial coordinates, 1 based for lists and character positions.

1) The memo has nothing to do with testing for MAXINT. Just test it inclusively.

2) You frequently want to know the length of a subseq, and you frequently want successive subseq ranges to dovetail.

3) What in the world does rand() have to do with this?

1) He is using real world math arguments why computer arrays should be 0 or 1 based. His example seems valid, but once you use Maxint it fails, proving his argument wrong.

2) Yes, but that has nothing to do with anything I wrote. Also calculating the length of a subset out of a 0 or 1 based array is the same, making your point completely irrelevant.

3) Where in the world do you read anything about rand()?

1) MAXINT is already a special case, so testing inclusively doesn't introduce extra accidental complexity.

2) If you test the upper bound inclusively, then the upper bound of the previous subseq is not the lower bound of the next subseq.

3) I misinterpreted GP. Scratch that :)

1) I think you are missing the point. According to Dijkstra you need to test if a var is within a range with i < last + 1. If last = maxint your computer will explode.

2) Sorry, I don't have a clue what you mean. What's the difference between tests on subseqs from 0 or 1 based arrays?

1) I get it. If your array is that big you already have code dealing with array indices approaching MAXINT. Since it's already a special case it's not introducing extra complexity to change your test in that one place.

Edit: When I say "test it inclusively" I mean when last==MAXINT you test i<=last rather than i<last+1. It's a special case.

2) I was assuming the upper bound in your 1-indexed array was inclusive, since it's necessary for your previous point. If that's the case, then when iterating over subseqs you can't just assign the previous upper bound to the next lower bound. That situation occurs frequently, and Dijkstra mentions it in the memo.

1) The maxint was just an example and these tests are not limited to arrays. For the same I was talking about bytes. And comparing a byte value against 255 + 1 is still wrong.

So yes, test inclusively, but not only the special cases, but always. It will prevent bugs, make code more readable and give faster code,

Only it's not what Dijkstra advocates.

2) When iterating 20 <= i < 30 or 20 <= i <= 29 the result is the same. At the end of the loop i will be 30, so in both cases the next lower bound = previous upper bound + 1.

While typing I thought of a case where inclusive might be more confusing, When iterating to first + n. Then < would be better than <= first + n - 1.

But I think this has little to do with if 0 or 1 based arrays are better. Only the start is different, after that it's all the same.

1) I'm going to leave this one here, because I think we might be having a semantic disconnect.

2) ... the result is the same.

Ahh, but it's not. When looping over consecutive subseqs, i's scope is the inner loop, and you lose i's value on exit, which means you can't use it as the next outer loop's lower bound. The previous upper bound in your example is 29, but we want 30, which means we're back to index-jockeying. This is the common situation Dijkstra was referring to.

Regardless, I've enjoyed the back and forth with you. You may come back with a devastating rebuttal, but I've got to keep working. Until next time! :)

For fixed size ints, no rule for mapping pairs of ints to a range of consecutive ints can allow both the empty range and the range of maximal size, e.g. you can't have both "", the empty range, and "0,...,Maxint".

You really need to give up one of the possibilities, or use an extra bit.

Admirably put.

The upperbound = maxint

The total number of items = maxint + 1

"I am starting to think Dijkstra is about the worst thing ever happening to software development."

"0 based for spatial coordinates, 1 based for lists and character positions."

Sums up my thoughts pretty well.

The real reason we do zero-based counting in computers is because of bits, speed and laziness.

And, of course, it provides an easy way to separate REAL PROGRAMMERS (TM) from everybody else.

In the same snarky tone, I'd say it helps to easily identify masochists in a herd of brilliant programmers.

Did you read Dijkstra's article? He's making the case for 0, though he's doing it a little abstractly. Simply put, if you start numbering at 1, you are setting yourself up for more boundary problems and off-by-one errors than if you start at 0 (and by extension, inclusive lower bounds and exclusive upper bounds). That's not to say that some algorithms are not in fact easier expressed by numbering things from 1, just that they're not the majority.

Oh, and obviously 0 is even. Why? Because 0 mod 2 = 0, 0 is evenly divided by 2, and that's what "even" means. If you need more intuition, though: 1 is indisputably odd, and even and odd numbers alternate, so 0 is even. The rest is philosophy -- you can probably find definitions for "odd" and "even" where 0 is a problem. That's fine, but those don't help. Ignore them. Mathematically there's no problem whatsoever.

The trickiness only comes if you insist in thinking in terms of "the first element", rather than "element number 0". Some people use "zeroth", but this seems to invite more confusion because it induces two meanings for all the other ordinal forms -- if there's a zeroth element, does that mean the "first" element is in fact the second element? Best to avoid ordinals altogether -- you usually don't need any more than "first" and "last" anyway.

"obviously 0 is even"

Sounds like a bit of an odd statement to me.

> Did you read Dijkstra's article?

Yes, I did. Does it hurt to offer a different perspective? I feel it doesn't. Approaching a subject with an open mind or from a different angle tends to be good for discussion. Offering a contradicting opinion or observation helps everyone to understand an issue better.

> Oh, and obviously 0 is even.

I might counter this with a similar question you asked me: "did you read my post?" I didn't make a case that 0 was odd, I asked how I should look at it: as element 0, or as the first element. If you look at it as element 0, the first element of the vector is an even element. If, on the other hand, you look at it as the first element, you will think it is an odd element. This is the case I made, not that 0 is even.

> Yes, I did. Does it hurt to offer a different perspective?

No, I was questioning whether you had considered his arguments at all, given the "why do we start counting at 0" question which he tried to answer.

> I didn't make a case that 0 was odd, I asked how I should look at it: as element 0, or as the first element.

You can look at it either way, as both are correct.

> If you look at it as element 0, the first element of the vector is an even element. If, on the other hand, you look at it as the first element, you will think it is an odd element.

Ah, I see your point now. To me this wouldn't be a question because everyone knows programmers start counting at 0 -- a machine instruction would operate on indexes, not ordinals. "The first element" is the element with index 0. It is not "element number one", or if you do want to see it that way, "number one" is the ordinal you use when you start counting on your fingers, which is something we deliberately ignore.

> No, I was questioning whether you had considered his arguments at all

Ah, yes. No, I wasn't trying to disprove him. I just gave a different approach to the issue. My mind is not made up on this subject. I've been a programmer for too long: 0 is burned in my fingers and my mind.

> a machine instruction would operate on indexes, not ordinals

The interesting aspect isn't the difference between indexes and ordinals, but the difference between indexes and cardinals. The cardinals match the ordinals for normal people. For normal people, indexes have no meaning.

But the difference between indexes and cardinals aren't that easy for programmers either. In an example presented by Dijkstra a young programmer used 0 in everyday language as a cardinal replacing 1. Indexes have little meaning in real life, but cardinals do.

Good response, BTW. Thanks. It's interesting to link the concepts of ordinals and cardinals to the discussion.

> I didn't make a case that 0 was odd, I asked how I should look at it: as element 0, or as the first element.

element 0, aka the 0th element..

I often wonder if Dijkstra's arguments still hold sway, since algorithms written in modern languages differ greatly from those written when Dijkstra wrote this. Rather than writing hash functions or shortest route algorithms, a majority of my algorithms are centered around lists and or dictionary manipulations. There are still many situations where it makes more sense to start indexing at 0, but I wonder if it is still the majority of cases.

Well, I think that there is a very important human reason to keep sticking to 0 as the start: convention. It has always been this way. Changing it would cause a whole lot of weird bugs.

To be honest, I think one reason why this grew is probably the way C handles array indexing. a[0] = *(a + 0) and this symmetry is a nice property to have in many cases. I think I use that symmetry in my MSc project a lot more than I use vec_mule/vec_mulo.

(Yeah, I'm not of a fixed mind in this matter :-))

http://en.wikipedia.org/wiki/Evenness_of_zero

Learning that such article could exist (it DOES exist), and reading it was a shocking experience to me.

Relevant quote from the article:

'A second-year was "quite convinced" that zero was odd, on the basis that "it is the first number you count"'

> you usually don't need any more than "first" and "last" anyway.

Apart from FP people - they need "the first" and "the rest" ;)

I write in primarily in 3 languages, 2 start indexes at 0 and the third starts at 1.

Not withstanding Dijkstra's logical arguments, I have adopted starting at 1 for 2 reasons:

1. I don't have to think about "shifting" data in order to look at it in the third language.

2. I don't have to "think" at all. It's intuitive that the first element is "1".

I just insert a null in the first position of any array in a 0-starting language.

I'm a actionscript developer at my day job and I would totally take up this approach if I didn't have to deal with screen/stage coordinates all the time.

You see, the backend of our project is in Coldfusion which has 1 based indexes for Array's and it has led to head-butting screen confusion when requesting the current index from the server. Then the visual side is always 1 based when showing data to the end-user, I'm always thinking I'm the problem in the middle.

There have been numerous occasions where QA have called me to ask why the first slide in a slideshow is called "Slide 0"!

If you ever have to pack multidimentional data in a flat array, I wish you luck, then. In this case, starting at 1 messes up lookup and insertion. You have to insert "-1" or "+1" pretty often. Too hard to get right in my opinion, I prefer the easier way: to start at 0.

Shouldn't the "index start value" just be a compilation directive?

i couldn't bring myself to stick null pointers here and there for the convenience of syntax :P

i see a lot about code being written for humans, but i'm not onboard with it. elegance in how it executes is #1, and elegance of maintenance is #2.

For 98% of all software, 'elegance of maintenance' is vastly more important than your #1. Most software doesn't need the absolute fastest hand tuned implementation, it needs an implementation that the poor schlub who inherits it in 15 years can understand.

Now I'm not agreeing about the particular indexing argument put forth by edw519, I think zero indexes lead to cleaner code whenever you have to do math with them, but unless you can make an honest case for maximum performance, I have to disagree with your assertion about elegance.

I am doubtful about the value of reason 2. "Intuitive", very often, just means "familiar", and I think that's the case here. It's not too difficult to get used to starting at 0, at which point there's no loss in "intuitiveness" from doing so.

Reason 1 has more force. I don't run into it very often when transferring data from one language to another -- I don't do very much of that -- but I do when, e.g., translating between code and standard mathematical notation.

People sometimes complain about Lua's tables, which use 1 as their first index when treated like arrays. I suppose it could make some algorithms more complicated but in my day to day programming it's never made any difference to me so far.

I wish I was shown this in my "introduction to programming course".

All they told us was "because that's how things are. [MEMORIZE IT!]"

Perhaps I should read more of Dijkstra's writings.

Edit: I love when directory indexing is NOT forbidden. http://www.cs.utexas.edu/~EWD/ewd08xx/

"Consider now the subsequences starting at the smallest natural number: inclusion of the upper bound would then force the latter to be unnatural by the time the sequence has shrunk to the empty one."

Maybe it is too late, but I don't understand this sentence.

A sequence starting at the smallest natural number would be: 0, 1, 2. The variant Dijkstra is arguing about is: 0 <= i <= 2. How can the latter be unnatural? And what does he mean with "shrunk"?

    [0,1) = (0)
    [0,0) = ()
    [0,0] = (0)
    [0,x] = ()

Probably you'd say x=-1 but if you're using unsigned indices, then you can't distinguish the biggest possible sequence from the empty one (this is true of all schemes, actually, but at least the other don't require negative numbers).

I don't care if computers think in 0s and 1s or if arrays should start at 0 because it is the way computers think.

Computers were made to serve us and as such they should translate all their inner thoughts to more human consumable data.

Five is 5, not 101.

So no, numbering should start at ONE, even if most programmers have already been hardwired to start counting from zero.

But he was making the point that there are valid human reasons for zero-based indexing - e.g. keeping the lower bound within the natural numbers; having the upper bound be the number of elements in the preceding sequence, etc. The "way computers think" doesn't enter the discussion.

"keeping the lower bound within the natural numbers; having the upper bound be the number of elements in the preceding sequence, etc."

Read your post and understand the same can be said of using one-based indexing.

That's false. You'd be forced to sacrifice the exclusive upper bound, which would then force you to sacrifice the difference between the upper and lower bounds being the number of elts in the collection. Unless the lower bound was exclusive, in which case it could be an unnatural number.

No, the only way there's no lump in the carpet is his way.

We have this convention for the benefit of humans. Indexing starting at 0 has the convenient property that when we modulus an arbitrary number by the size of a range, the result is a valid index into that range. This comes up when implementing things that map a larger set onto a smaller set, such as buffers or hash tables.

We could still achieve the same effect if we started indexing at 1, but it would require more code, and it would be less clear.

"We could still achieve the same effect if we started indexing at 1, but it would require more code, and it would be less clear."

Really?

How about dealing with strings?

"123456789" how many chars we have? 9

char[1] = 1

char[2] = 2

char[9] = 9

Now, let's try the C approach:

"123456789"

char[0] = 1

char[1] = 2

char[8] = 9

where is char "1"? at zero index!

how many elements we have?

last index plus one!

see? there is already confusion in place, or as you say, more code and less clear...

"0123456789"

  ch[0] = 0;
  ch[1] = 1;
  ch[2] = 2;
  :
  ch[9] = 9;

  ch[1] = 0;
  ch[2] = 1;
  ch[3] = 2;

....

Please re-read his question: "how many chars we have?" "how many elements we have?"

  ch[1] = 0;
  ch[2] = 1;
  ch[3] = 2;
  ...
  ch[10] = 9;

This is about having the Nth element of the array with the index N rather than N-1.

That's not code, that's English.

When we start indexing from 0, the only time we need to do a +/- 1 is when we need to index the last element. All other times (iterating, mapping) we don't need to.

Also, starting indices at 1 would change the idiomatic iteration to:

   for (int i = 1; i <= SIZE; ++i)

I find that the <= and >= operators add more to my cognitive load than the strict relation operators < and > because there's an or in there. I don't find the alternative to that idiom any better:

  for (int i = 1; i < SIZE + 1; ++i)

Your original argument was that we should make it easy for humans to understand, not computers. I think that starting indices from 0 is easier for humans to understand because it simplifies the code we must write and read.

No, your language limitations don't have to force the rest of the world to accept them.

As I alreay said, some languages use the simpler construct:

For i=1 to N

And C could easily use:

for(i=1;i==n;i++)

just by changing the way the loop condition works.

So as you say, it is all about the language.

No way I would trust a language design with your semantics for this syntactic construct: for(i=1;i==n;i++)

Look at your hand and start counting your fingers while naming them:

[1] thumb

[2] index

[3] middle

[4] ring

[5] pinkie

so we have a simple range [1..5]

which can be represented in so many ways in computer programs:

for i=1 to 5 print finger[i]

for(i in [1..5]) print finger[i]

my first finger[1] is my thumb

my last finger[5] is my pinkie

how many fingers we have? as many as the last index in the list: 5

now, C programmers like to count this way:

for(i=0;i<5;i++) print finger[i]

where finger[0] is thumb

and finger[4] is pinkie

how many fingers we have?

as many as the last index in the list plus one: 4+1

how human-like!

And that's why you get so messy when trying to get the string position of a substring:

if(pos>-1) exists, since pos=0 means the substring is in the starting position

again, how human-like!

But how dare I argue with C programmers without being burned at the stake?

for i=1 to 5 print finger[i]

for(i in [1..5]) print finger[i]

You're using an inclusive upper range here. Not that that's necessarily wrong, but it isn't standard for the reason Dijkstra mentioned (how many fingers do I have? 5 - 1 = 4. Oops.)

"how many fingers do I have? 5 - 1 = 4. Oops."

Upper-Lower+1, easy. Whenever the lower is 1, just the upper is enough.

In your case you go from 0 to 4, how's that different from how many fingers you have? 4-0=4 Oops.

Congratulations; you have successfully introduced a whole new way to have off-by-one errors.

People are used, due to forty years or more of tradition in the great majority of major languages, to zero-based indexing. Tossing that away Because It's Inelegant won't do much good to anyone, especially when you take into consideration the fact that an awful lot of math is more convenient with 0-based indexing.

What makes you think people who 0-index arrays and prefer half-open intervals count any differently? Is this argument directed at a four year old?

4+1=5 never enters into it. What a rubbish argument. I might as well complain that your [a,b] has (b-a+1) integers in it. (5-0)=5 so the half open interval has 5 things in it.

What's the measure of a real interval 1<=x<=5? 4. 0<=x<5? 5.

Don't try your cheap tricks on me.

We go from 1 to 5, so the math would be 5-1 +1

You go from 0 to 4, the math would be the same, 4-0 +1

Using 5 as your upper bound, then starting from 0 to 4 is the same as me using 6 as my upper bound then going from 1 to 5.

Reply on news.ycombinator.com