Why numbering should start at zero (1982)(cs.utexas.edu)
cs.utexas.edu
Why numbering should start at zero (1982)
http://www.cs.utexas.edu/users/EWD/transcriptions/EWD08xx/EWD831.html
11 comments
Those are great insights, thanks for laying it out like that.
This is also why rulers start with 0 (even if you can't see the 0) - because a ruler isn't about counting the marks, it's about measuring the space between the marks.
There's an excellent discussion and illustration of this in the original Inside Macintosh - a few us us were kicking it around a couple of years ago here:
https://news.ycombinator.com/item?id=6601515
This is also why rulers start with 0 (even if you can't see the 0) - because a ruler isn't about counting the marks, it's about measuring the space between the marks.
There's an excellent discussion and illustration of this in the original Inside Macintosh - a few us us were kicking it around a couple of years ago here:
https://news.ycombinator.com/item?id=6601515
I would argue for one-based counting [a] and zero-based indexing.
Illustrated example of an array- indexes along the top (where the data can be found), and counting along the bottom (how many values have been read):
Illustrated example of an array- indexes along the top (where the data can be found), and counting along the bottom (how many values have been read):
0 1 2 3
| A | B | C | D |
^ ^ ^ ^
"1" "2" "3" "4"
You made me realize that we use 0-indexing because we confused the torsor[1] for the group. What I mean is that we may take differences between labels (numbers on the posts) to see how many posts to the left or the right a post is relative to another, and then we do this all relative to the first post. It is convenient in, say, C to do 0-based indexing because then you can add the index (the difference) to the pointer to the first element to move over that many posts, but that is different from the concept of which ordinal the post is labeled with.
[1] Quickly stated, a torsor over a group is a collection of things which support taking differences, and the differences are elements of the group. One example is pointers vs integers, since the difference between two pointers (to things in the same array in C) is an integer, and the sum of a pointer and an integer is another pointer. Another example is energy vs work, or Euclidean space vs vectors.
[1] Quickly stated, a torsor over a group is a collection of things which support taking differences, and the differences are elements of the group. One example is pointers vs integers, since the difference between two pointers (to things in the same array in C) is an integer, and the sum of a pointer and an integer is another pointer. Another example is energy vs work, or Euclidean space vs vectors.
Regarding the initial argument, I'd opt for C or D; since here we're being consistent with our signs and therefore the statement's more readable. To me this is more apparent than the number of elements being the upper bound minus the lower, or natural numbers shrinking to unnatural (which I confess I don't understand given here i is by definition an integer and thus natural).
Of these two I'd likely opt for C since this lends itself to natural language (e.g. if I ask someone to choose a number between 1 and 10 I mean the choice is inclusive of 1 and 10), so again is likely more readable.
Also "pernicious: having a harmful effect, especially in a gradual or subtle way". I don't understand this statement either. A language not mentioned, PowerShell, uses two dots to great effect (ellipses vs two dots is another debate; but I can't see how one would be considered harmful and the other not). `1..10 | %{"we're at number {0}" -f $_}`; simple, clear and obvious.
The whole article reads as if someone's trying to show off their intellect, rather than present an honest analysis of the benefits of the merits of the different indexing/numbering systems. @TOGoS's comment on this thread, on the other hand gives a compelling and well reasoned argument of when to use each system.
Also "pernicious: having a harmful effect, especially in a gradual or subtle way". I don't understand this statement either. A language not mentioned, PowerShell, uses two dots to great effect (ellipses vs two dots is another debate; but I can't see how one would be considered harmful and the other not). `1..10 | %{"we're at number {0}" -f $_}`; simple, clear and obvious.
The whole article reads as if someone's trying to show off their intellect, rather than present an honest analysis of the benefits of the merits of the different indexing/numbering systems. @TOGoS's comment on this thread, on the other hand gives a compelling and well reasoned argument of when to use each system.
I've always been charmed by EWD's handwriting: http://www.cs.utexas.edu/users/EWD/ewd08xx/EWD831.PDF
That literally looks like it was typed in a hand drawn font -- remarkable.
One big advantage of zero-based indexing is that it's consistent with division with remainder. This is especially nice when working with multidimensional arrays.
I'd argue that in the presence of one-based indexing, remainders being defined as 1..n, inclusive, makes more sense anyways.
So 8 divided by 4 is 1 with a remainder of 4?
No. Two with a "remainder" of 4. Ideally I'd call it by another name to avoid confusion (and the implication that x == x//y * y + x % y - although this is often incorrect in the case of negative values anyways), but I do not know what other "better" name to call it.
Think about it. If you have a series of bins with 4 items each, and you ask someone to grab the 8th item, where do they go? To the 4th item of the second bin.
Think about it. If you have a series of bins with 4 items each, and you ask someone to grab the 8th item, where do they go? To the 4th item of the second bin.
Looking at division and mod as a pair finding group and subgroup indices is interesting. For zero based indexing, we want division to round down and the usual zero-based mod. So Group(8,4) = 8/4 = 2, Index(8,4) = 8 % 4 = 0. The invariant is x == x/y * y + x % y. With one based indexing, we want division to round up and want the modulo operator you're describing. So Group(8,4) = 8/'4 = 2, Index(8,4) = 8 %' 4 = 4. The invariant is x == (x/'y - 1) * y + x %' y.
Although it might make sense to define the modulus operator in that way, it doesn't really make sense to define remainders that way: what is the remainder of n/n?
As I said in another comment:
It ideally shouldn't be called a remainder. I just don't know what else to call it.
In this system, n % n is n. (Although note that I'm not even going to try to get into negative values here. "Standard" modulus is bad enough for this - this operator has the same potential choices as "standard" modulo w.r.t. negative values / mods) If you have 1 bin with n items, the nth item is the nth item within the bin within which it is contained. (I hope that's parsable.)
It ideally shouldn't be called a remainder. I just don't know what else to call it.
In this system, n % n is n. (Although note that I'm not even going to try to get into negative values here. "Standard" modulus is bad enough for this - this operator has the same potential choices as "standard" modulo w.r.t. negative values / mods) If you have 1 bin with n items, the nth item is the nth item within the bin within which it is contained. (I hope that's parsable.)
That's still a remainder, it's just the remainder of the zeroth bin.
No. One-based indexing everywhere.
So 8 / 4 is 2 with a "remainder" of 4.
Think about it. If you have a series of bins with 4 items each, and you ask someone to grab the 8th item, where do they go? To the 4th item of the second bin.
So 8 / 4 is 2 with a "remainder" of 4.
Think about it. If you have a series of bins with 4 items each, and you ask someone to grab the 8th item, where do they go? To the 4th item of the second bin.
The fourth item of the second bin is the fourth item of the remaining items after you've looked at one bin.
But it is contained in the second bin.
I get that. I'm not completely stupid. I'm saying that it is still a remainder. It can be a remainder and in the second bin at the same time.
I've long been a zero-based-index-loving geek, but I'm now coming around to preferring one-based indices in programming. Hopefully in the near future I'll write a blog post detailing why.
Regarding the article itself... sorry, Dijkstra, but I think conventions C and D are more beautiful, as I prefer discrete ranges where the signs on both ends are the same. Convention C is my favorite, as it only makes mention of members of the range, not numbers that lie outside of it.
Regarding the article itself... sorry, Dijkstra, but I think conventions C and D are more beautiful, as I prefer discrete ranges where the signs on both ends are the same. Convention C is my favorite, as it only makes mention of members of the range, not numbers that lie outside of it.
I have an example of a similar journey I followed.
The Lua language has a 1-based indexing scheme. Furthermore, the only thing that differentiates a hash-map from an ordered array is the existence of only keys in the range [1, ∞) (and they must be entirely contiguous starting from 1 until the last present key).
The interface for arrays and hash-map data types is uniform, called a 'table', which has your standard `mapper[key] = value` syntax (and also, equivalently, `mapper.key = value` for well-formatted string-literal keys).
This results in the very surprising and confounding fact that if a naive programmer doesn't realize that Lua has this system, they will very likely end up starting from 0 and build an unordered hash map rather than an ordered array - complete with all the resulting performance penalties and unordered traversals.
For a long time this struck me as being absolutely absurd and very damning. After working with Lua for a while, though, there began to be a certain elegance to it that I could admire. There is a SO post that goes in to some of the benefits[0][1].
I still much prefer 0-based indexing though.
0: http://stackoverflow.com/questions/2785704/why-do-lua-arrays...
1: Irony intended.
The Lua language has a 1-based indexing scheme. Furthermore, the only thing that differentiates a hash-map from an ordered array is the existence of only keys in the range [1, ∞) (and they must be entirely contiguous starting from 1 until the last present key).
The interface for arrays and hash-map data types is uniform, called a 'table', which has your standard `mapper[key] = value` syntax (and also, equivalently, `mapper.key = value` for well-formatted string-literal keys).
This results in the very surprising and confounding fact that if a naive programmer doesn't realize that Lua has this system, they will very likely end up starting from 0 and build an unordered hash map rather than an ordered array - complete with all the resulting performance penalties and unordered traversals.
For a long time this struck me as being absolutely absurd and very damning. After working with Lua for a while, though, there began to be a certain elegance to it that I could admire. There is a SO post that goes in to some of the benefits[0][1].
I still much prefer 0-based indexing though.
0: http://stackoverflow.com/questions/2785704/why-do-lua-arrays...
1: Irony intended.
Reading Dijkstra's own argument convinced me that 1-indexing is better. Convention C (consistently non-strict) is the one that we normally use to describe ranges in English.
While the article is explicitly only dealing with natural numbers, convention C is insufficiently expressive for anything more granular than the natural numbers.
"When dealing with a sequence of length N, the elements of which we wish to distinguish by subscript, the next vexing question is what subscript value to assign to its starting element. Adhering to convention a) yields, when starting with subscript 1, the subscript range 1 ≤ i < N+1; starting with 0, however, gives the nicer range 0 ≤ i < N. So let us let our ordinals start at zero: an element's ordinal (subscript) equals the number of elements preceding it in the sequence. And the moral of the story is that we had better regard —after all those centuries!— zero as a most natural number."
To put this another way; as mentioned by the fence post example another poster above mentioned.
If you label the fence posts with numbers, from 1 to N, the value at a given address along the length of the fence is the distance from the start of the fence.
In this case 0 posts from the start is the value 1. What makes this confusing is the arbitrary choice of the value of the object at location 0. Dijkstra does a reasonable job of explaining why logically beginning numbering at 0 makes sense for the index/address, but does not reasonably explain that the fault in the logic of those whom would count an item is failing to use that logically derived index/address as the identity of the object.
That is, the numeric id of the object at address 0 should also be 0, not 1, as many assume it should be based on the conventions that were instilled in basic education.
If you label the fence posts with numbers, from 1 to N, the value at a given address along the length of the fence is the distance from the start of the fence.
In this case 0 posts from the start is the value 1. What makes this confusing is the arbitrary choice of the value of the object at location 0. Dijkstra does a reasonable job of explaining why logically beginning numbering at 0 makes sense for the index/address, but does not reasonably explain that the fault in the logic of those whom would count an item is failing to use that logically derived index/address as the identity of the object.
That is, the numeric id of the object at address 0 should also be 0, not 1, as many assume it should be based on the conventions that were instilled in basic education.
When he's right, he's right.
Hard to convince my students of it, though (they are Americans; is it different elsewhere?).
Hard to convince my students of it, though (they are Americans; is it different elsewhere?).
..and why shouldn't:
if (someStr.indexOf("John") !== -1) { ... }
vs
if (someStr.indexOf("John")) { ... }
Or when _teaching_ it's kind of funny saying "So, we take the first element, that is the zeroth, then the third (I mean the real third, not the one with index three)...".
OK, but to be entirely honest, I both sides have pros and cons. And as long as a language/program/person is reasonably consistent (vide https://xkcd.com/163/), there is not a big difference.
if (someStr.indexOf("John") !== -1) { ... }
vs
if (someStr.indexOf("John")) { ... }
Or when _teaching_ it's kind of funny saying "So, we take the first element, that is the zeroth, then the third (I mean the real third, not the one with index three)...".
OK, but to be entirely honest, I both sides have pros and cons. And as long as a language/program/person is reasonably consistent (vide https://xkcd.com/163/), there is not a big difference.
Your example should really be (using a polyfill if necessary)
if(someStr.includes('John')) {...}
Zero doesn't have to be a special case. In ruby 0 is a truthy value, as well as the empty string. The only things that are falsey are false and nil.
Truthy/falsey means when used in a conditional or after a unary !. So you still get strong typing, e.g. false == nil is not a true statement.
Truthy/falsey means when used in a conditional or after a unary !. So you still get strong typing, e.g. false == nil is not a true statement.
Option #2 assumes that 0 is falsy. Its an OK assumption for a language like C but for languages that let lots of different things go into an if condition I prefer for zero to be truthy and just false / null / etc to be falsy.
Banning implicit integer conversions, such that neither 0 nor 1 can be used in a conditional, isn't unreasonable; then you have to write a boolean operator or conversion explicitly.
However, if you allow integers in conditionals, yet have 0 mean true, you will break the default expectations of far too many programmers.
However, if you allow integers in conditionals, yet have 0 mean true, you will break the default expectations of far too many programmers.
The first several languages I learned treated 0 as falsey and I can't really recall it tripping me up when I learned a language (Ruby) where that's not the case.
I suppose always thought of 0-as-false as an unfortunate consequence of C not having a native boolean type, anyhow.
I suppose always thought of 0-as-false as an unfortunate consequence of C not having a native boolean type, anyhow.
In a statically typed language, restricting if conditionals to just booleans is the approach I like the most: simple and safe.
On the other hand, in dynamic languages, where you can pass anything to conditional I think that treating 0 as falsy is very error prone. For example, its very common to use conditionals to implement default values:
On the other hand, in dynamic languages, where you can pass anything to conditional I think that treating 0 as falsy is very error prone. For example, its very common to use conditionals to implement default values:
function foo(name){
name = name || "default name";
}
If your language has something like "None" or "null", then you should be checking against that to implement a default, rather than checking a truth value. After all, what if you wanted to implement a boolean parameter with a default value?
Personally, I'm a big fan of languages with a "Maybe" type for this kind of thing.
Personally, I'm a big fan of languages with a "Maybe" type for this kind of thing.
The `||` pattern is super common in a bunch of languages though and to code it with a `== null` test you would need to expand it to a full blown ternary operator
(And I agree with you on the Maybe thing but, as I said previously, 0 in conditionals is not a problem when conditionals have to be boolean)
name != null ? name : "default name"
(And I agree with you on the Maybe thing but, as I said previously, 0 in conditionals is not a problem when conditionals have to be boolean)
"Some languages have a "null-coalescing" operator you can use in these cases but its a niche thing."
I see that not as niche, but as a fairly recent invention, or at least one that recently is becoming popular. IMO, C#'s ?? is superior to reusing binary operators.
Advantages are that it looks more like the ternary operator, and that it doesn't require adding implicit conversions to boolean to your language.
I see that not as niche, but as a fairly recent invention, or at least one that recently is becoming popular. IMO, C#'s ?? is superior to reusing binary operators.
Advantages are that it looks more like the ternary operator, and that it doesn't require adding implicit conversions to boolean to your language.
My point is, you should be checking for null or None or equivalent, rather than boolean false; once you do, 0 being false is no more or less of a problem than false being false.
[deleted]
Can someone explain this sentence to me:
"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."
The previous statement asserts that inclusion of the lower bound is preferred because the sequence then starts with a natural number (so for a set 1<=x<12 the sequence starts at 1 instead of 1.000000 .... 1 in 1<x<12). How is inclusion of the upper bound forcing the "latter" (what is he referring to by latter) to be unnatural by the time the sequence has shrunk to the empty one.
"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."
The previous statement asserts that inclusion of the lower bound is preferred because the sequence then starts with a natural number (so for a set 1<=x<12 the sequence starts at 1 instead of 1.000000 .... 1 in 1<x<12). How is inclusion of the upper bound forcing the "latter" (what is he referring to by latter) to be unnatural by the time the sequence has shrunk to the empty one.
"The latter" here refers to the upper bound. By "unnatural" he means negative, as he is discussing the natural numbers (positive integers and zero). By convention these are the numbers used to index arrays. (So, for your examples: for the set 1<=x<12, the sequence is 1,2,3,4,5,6,7,8,9,10,11; for the set 1<x<12, the sequence is 2,3,4,5,6,7,8,9,10,11.)
As for what he's saying: suppose you decide your array indexing starts at the lowest natural number, i.e., 0. And imagine an array with 1 element. And assume you've adopted the notation a<=i<=b. This array's indexes are then 0<=i<=0.
But what if you have an array of 0 elements? What then? You can't say 0<=i<=-1, because -1 is not natural and therefore not a valid array index.
But if you adopt the convention that a<=i<b, then your 1-element array's indexes would be 0<=i<1, and your empty array would be 0<=i<0. (Or, indeed, 1<=i<1, or n<=i<n for any n you choose - the first section deals with how to denote the range, so the choice of n isn't the key thing.)
As for what he's saying: suppose you decide your array indexing starts at the lowest natural number, i.e., 0. And imagine an array with 1 element. And assume you've adopted the notation a<=i<=b. This array's indexes are then 0<=i<=0.
But what if you have an array of 0 elements? What then? You can't say 0<=i<=-1, because -1 is not natural and therefore not a valid array index.
But if you adopt the convention that a<=i<b, then your 1-element array's indexes would be 0<=i<1, and your empty array would be 0<=i<0. (Or, indeed, 1<=i<1, or n<=i<n for any n you choose - the first section deals with how to denote the range, so the choice of n isn't the key thing.)
Thank you for the explanation.
I love one-based indexing. I prefer array[1..n] to array[0..n-1]. The reason is because with one-based indexing, I don't have names for things that are invalid. begin, end: these are valid places to be. Your "end" token can mean "the last element", and you don't have to think about "being behind the thing that represents the thing past your last element".
I acknowledge it's domain-specific, but I find there's something mentally relaxing about one-based indexing. And I grew up on 0-based.
I acknowledge it's domain-specific, but I find there's something mentally relaxing about one-based indexing. And I grew up on 0-based.
The Fortran (not FORTRAN) standard current when Dijkstra wrote that allowed arbitrary lower bounds in array declarations, and an array could be equivalenced to one with different bounds. The language doesn't impose the choice.
> That is ugly
This is the defining reason? Seems an awful lot like personal preference, to me.
This is the defining reason? Seems an awful lot like personal preference, to me.
Starting with one considered harmful.
I always had this feeling that with one based indexing, 70s era compilers ended up subtracting one from the index. For each and every element access made. Because memory decoding circuits don't start at one, they 'start' with 0000...000. Course it would be possible to just waste the first element, but 70's era memory... Waste a 16 bit word here, and there and suddenly you're talking real money.
Say you're counting the length of a fence, so you are numbering the posts. Of course it's preferable to number the posts starting at zero, because after having numbered N posts, you know the length of the fence is N.
On the other hand, if you are counting the posts themselves, you would want to say "one!" after the first post, as you have just counted one post. In this case, the number you assign the post is the number of posts counted after encountering it. Otherwise you end up having to +1 at the end.
Which is all to say: I've always felt that the disagreement between whether to start at one or zero is due to people not making clear what it is they're counting.
If you're numbering the points between spans (as you tend to be when giving names to dates, memory locations, and fence posts), always start at zero. If you're giving numbers to the spans themselves, it's often convenient to use a physically-based number such as the location of the center of the span (when writing graphics applications I will often refer to the pixel in the upper-left corner as 0.5,0.5, rounding down to get its address).