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.
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.
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.
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.
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.
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.
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.
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.
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) 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()?
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.
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! :)
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.
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 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 :-))
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.
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.
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'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"!
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.
"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"?
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).
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.
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.
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.
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.
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.
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.)
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.
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.