Why We Start Indexing from 0 in Computer Science(cs.utexas.edu)
cs.utexas.edu
Why We Start Indexing from 0 in Computer Science
http://www.cs.utexas.edu/users/EWD/ewd08xx/EWD831.PDF
15 comments
Right, it makes sense when dealing with machine code and when making the compiler do extra work for you (converting one-based to zero-based indexing) would be too much work for the compiler implementer or is too slow (like on machines back in the 70s and 80s) or it would abstract too far from what is happening underneath the hood, possibly leading to errors.
But like many features of programming languages and operating systems (case-sensitivity, global menu bar, python's colon...), zero-based indexing is something that made perfect sense in the context and time in which it was originally designed and implemented, but it's really no longer necessary in most cases today, and only survives because of tradition and blind cargo cult-like copying of what others did before.
But like many features of programming languages and operating systems (case-sensitivity, global menu bar, python's colon...), zero-based indexing is something that made perfect sense in the context and time in which it was originally designed and implemented, but it's really no longer necessary in most cases today, and only survives because of tradition and blind cargo cult-like copying of what others did before.
You're vastly oversimplifying. In physics and finance, the "initial time" has always been t_0, not t_1. This has absolutely nothing to do with machine code, or with "blind cargo-cult copying". There are intrinsic reasons for doing it this way, which I'll leave for you to ponder yourself, ideally in a quiet room in a lotus position.
Traditions are not always arbitrary. Don't dismiss them until you're damned sure why they've survived, especially when you know for a fact that quantitative fields filled with high-order geniuses haven't bothered to scrap them. "Cargo-cult" thinking is a pernicious influence, but it's exceptionally rare that it's the complete explanation of anything.
Traditions are not always arbitrary. Don't dismiss them until you're damned sure why they've survived, especially when you know for a fact that quantitative fields filled with high-order geniuses haven't bothered to scrap them. "Cargo-cult" thinking is a pernicious influence, but it's exceptionally rare that it's the complete explanation of anything.
I'm addressing the topic of the post: the use of indexes in programming, not names used for variables that store an initial time.
myarray[2] doesn't mean 'myarray at time 2'
myarray[2] doesn't mean 'myarray at time 2'
One advantage I think the parent is alluding to, is that zero-based indexing makes it a bit easier and more natural to generalise between continuous (functions on R) and discontinuous (functions on N) situations.
Since the latter are often used to approximate the former, this is quite handy.
Since the latter are often used to approximate the former, this is quite handy.
Python's colon-before-indented-block resulted from usability tests of people learning how to program. I don't see why that would have different results today.
See page 7 of this presentation: http://mvdirona.com/jrh/TalksAndPapers/GuidoVanRossum_21_yea...
See page 7 of this presentation: http://mvdirona.com/jrh/TalksAndPapers/GuidoVanRossum_21_yea...
Care to explain why Dijkstra arguments for zero-indexing hold any less true today than in 1982? His arguments make a great deal of sense to me so I take exception to the assertion of cargo cultism.
Can't resist this classic quote by Stan Kelly-Bootle: "Should array indices start at 0 or 1? My compromise of 0.5 was rejected without, I thought, proper consideration."
A helpful way to think about this, especially when working in languages that have an array slice syntax, is that arrays are like rulers for measurement.
Like a ruler, the array has markers (ticks) going from 0 to N, and the array elements are stored between ticks. So the index numbers simply refer to points, while the array elements have a "one-dimensional" extent.
With that mental model, starting at 0 falls into place very naturally.
Like a ruler, the array has markers (ticks) going from 0 to N, and the array elements are stored between ticks. So the index numbers simply refer to points, while the array elements have a "one-dimensional" extent.
With that mental model, starting at 0 falls into place very naturally.
"an element's ordinal (subscript) equals the number of elements preceding it in the sequence."
That is going to make the "the 2nd item is number 1" thing SO much easier to explain when teaching. Thanks! (And it's good to have the rest of the reasoning there to answer the particularly curious students...)
Definitely falls into the "wish I'd thought of that" and "wish I'd heard someone say it that way 5 years ago" camps.
That is going to make the "the 2nd item is number 1" thing SO much easier to explain when teaching. Thanks! (And it's good to have the rest of the reasoning there to answer the particularly curious students...)
Definitely falls into the "wish I'd thought of that" and "wish I'd heard someone say it that way 5 years ago" camps.
I'll repeat my comment from a different thread:
"I've never really agreed that numbering should start at zero (or at one), I think people use indices way too much and it gets in the way of clarity. I much prefer whole array or list operations with no fiddling with indices and off by one errors. I like Haskell's array API, for example. You can index by whatever is natural in each case and you can always get the whole list of valid indices for an array x by using "indices x". I think that's much nicer, and it's also what D is doing: instead of having a(n implicitly paired) starting and ending iterator to indicate a range of positions like the C++ library does, D's library uses a range object. Basically I'm saying you can represent a range of indices as a pair of indices, one pointing to the first valid position and the other pointing past the last valid one, but that's an implementation detail you don't need to expose, make a range abstraction and you'll be happier."
"I should also point out that mathematicians don't number at zero unless there is some advantage (the default is to start at one), but more importantly, the preferred style in mathematical arguments is to avoiding fiddling with indices as much as possible (since it's so easy to mess something up working at such a low level of abstraction)."
"I've never really agreed that numbering should start at zero (or at one), I think people use indices way too much and it gets in the way of clarity. I much prefer whole array or list operations with no fiddling with indices and off by one errors. I like Haskell's array API, for example. You can index by whatever is natural in each case and you can always get the whole list of valid indices for an array x by using "indices x". I think that's much nicer, and it's also what D is doing: instead of having a(n implicitly paired) starting and ending iterator to indicate a range of positions like the C++ library does, D's library uses a range object. Basically I'm saying you can represent a range of indices as a pair of indices, one pointing to the first valid position and the other pointing past the last valid one, but that's an implementation detail you don't need to expose, make a range abstraction and you'll be happier."
"I should also point out that mathematicians don't number at zero unless there is some advantage (the default is to start at one), but more importantly, the preferred style in mathematical arguments is to avoiding fiddling with indices as much as possible (since it's so easy to mess something up working at such a low level of abstraction)."
> I should also point out that mathematicians don't number at zero unless there is some advantage (the default is to start at one)
I disagree. While this may depend a little on which areas of mathematics you study, I've found that in situations where there is a reasonably clear / natural / non-arbtirary preference, it tends to be for zero-based natural numbers.
On the other hand, situations in which 1-based numbers are used, tend to look more like arbitrary aesthetic preferences. They tend to be situations where no particular `origin' is any better than any other, and one could (despite the ugliness) use 2- or 3-based numbering without adding any additional corner-cases.
My personal favourite `reason' that the set of natural numbers should include zero (and that numbering should start at zero) comes from set theory, where cardinal numbers are equivalence classes of sets of the same size. 0 is the smallest such number corresponding to the empty set. (For numbering sequences, 0 is also naturally the smallest ordinal number).
These kinds of reasons tend to crop up in category theory and other foundational topics too, which are some of the areas of mathematics closest to theoretical computer science.
Interested in counter-examples though; I'm sure at least some exist.
I disagree. While this may depend a little on which areas of mathematics you study, I've found that in situations where there is a reasonably clear / natural / non-arbtirary preference, it tends to be for zero-based natural numbers.
On the other hand, situations in which 1-based numbers are used, tend to look more like arbitrary aesthetic preferences. They tend to be situations where no particular `origin' is any better than any other, and one could (despite the ugliness) use 2- or 3-based numbering without adding any additional corner-cases.
My personal favourite `reason' that the set of natural numbers should include zero (and that numbering should start at zero) comes from set theory, where cardinal numbers are equivalence classes of sets of the same size. 0 is the smallest such number corresponding to the empty set. (For numbering sequences, 0 is also naturally the smallest ordinal number).
These kinds of reasons tend to crop up in category theory and other foundational topics too, which are some of the areas of mathematics closest to theoretical computer science.
Interested in counter-examples though; I'm sure at least some exist.
Well, whole numbers come up in mathematics in different ways. Of course if you're talking about cardinality you should include zero: it simply is the cardinality of some set, you can't avoid that.
I was talking about a completely different use of numbers: numbering, that is assigning numbers as labels to things. There I think mathematicians on the whole prefer to number starting at 1 (or not to number at all and work with abstract indexing sets). Sometimes it is convenient to number starting at zero if it simplifies some formulas, but usually it doesn't matter.
I was talking about a completely different use of numbers: numbering, that is assigning numbers as labels to things. There I think mathematicians on the whole prefer to number starting at 1 (or not to number at all and work with abstract indexing sets). Sometimes it is convenient to number starting at zero if it simplifies some formulas, but usually it doesn't matter.
To continue with your example, take cases where a (finite) collection of discrete objects is summed over (unioned over, whatever).
You'd let N be the number of such objects, and then twenty following pages of text would contain summations from 1 to N. This is more compact than summations from 0 to N-1. And in a certain sense, there's one less "token" to remember (i.e., if you start at 1, you have 1 and N to remember, but when you start at 0, you have N, 0, and N-1 to remember).
The one that's more compact tends to be discipline-specific.
You'd let N be the number of such objects, and then twenty following pages of text would contain summations from 1 to N. This is more compact than summations from 0 to N-1. And in a certain sense, there's one less "token" to remember (i.e., if you start at 1, you have 1 and N to remember, but when you start at 0, you have N, 0, and N-1 to remember).
The one that's more compact tends to be discipline-specific.
The note is really about the best way to specify a range/sequence of integers, not why we start from 0 as an index.
But it is an excellent example of thoughtful reasoning to choose between multiple (seemingly arbitrary) design options. I think we all benefit when language (and API) designers are as thoughtful as this.
But it is an excellent example of thoughtful reasoning to choose between multiple (seemingly arbitrary) design options. I think we all benefit when language (and API) designers are as thoughtful as this.
> The note is really about the best way to specify a range/sequence of integers, not why we start from 0 as an index.
Dijkstra deals with what index start with as well, but it comes out as a consequence of which bounds to choose for a range, so it's rather short.
From the article:
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.
Dijkstra deals with what index start with as well, but it comes out as a consequence of which bounds to choose for a range, so it's rather short.
From the article:
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.
My main issue with the start-from-0 convention is that while it makes sense if you consider an array as a pointer with more pointers coming after it, it doesn't make as much sense when it is simply a list of objects.
When I have a five-page document, I number the pages as one, two, three, four, five, and say that the length of the document is five pages. If I have an "empty" document (assuming such a thing makes sense in the real world), it would have length zero, and since there are no elements to assign indices to, I would not assign them numbers.
I have to admit that I much prefer the Lua convention: in a sequence of N items, they are numbered 1, 2...N-1, N. The length of the sequence is equal to the index of the last item in the sequence. "Negative" indices are treated as if one was counting backwards from the end of the sequence, such that the items are numbered -N, (-N)+1, (-N)+2...-2, -1, i.e. the spoken forms "last," "second-to-last," "third-to-last..." This means that 1 to -1 encompasses the whole sequence. This does have the unfortunate side effect that 0 refers to no item, but even when describing an array implemented as a pointer we refer not to the "zeroth" element, but to the first and the last.
This also has an added benefit that the range notation used by Lua's numeric for loops makes perfect sense when compared to the notation used by Python's range statement. In Lua,
When I have a five-page document, I number the pages as one, two, three, four, five, and say that the length of the document is five pages. If I have an "empty" document (assuming such a thing makes sense in the real world), it would have length zero, and since there are no elements to assign indices to, I would not assign them numbers.
I have to admit that I much prefer the Lua convention: in a sequence of N items, they are numbered 1, 2...N-1, N. The length of the sequence is equal to the index of the last item in the sequence. "Negative" indices are treated as if one was counting backwards from the end of the sequence, such that the items are numbered -N, (-N)+1, (-N)+2...-2, -1, i.e. the spoken forms "last," "second-to-last," "third-to-last..." This means that 1 to -1 encompasses the whole sequence. This does have the unfortunate side effect that 0 refers to no item, but even when describing an array implemented as a pointer we refer not to the "zeroth" element, but to the first and the last.
This also has an added benefit that the range notation used by Lua's numeric for loops makes perfect sense when compared to the notation used by Python's range statement. In Lua,
for n = 1, #tbl
for n in range(len(ls))
for n = 1, 6
So... you prefer Lua because half-open ranges confuse you?
If we're going for half-open ranges, range(n) ≝ 0<i≤n would make more sense than 0≤i<n. But then again, sign(0) is still a point of disagreement today.
Dijkstra argued against this by noting that that makes adding 0 to the range impractical, but then he was considering natural numbers, not the half-open ranges we're talking about and using notation for here.
Me, I prefer integers and the a..b style, despite the off-by-one error.
Dijkstra argued against this by noting that that makes adding 0 to the range impractical, but then he was considering natural numbers, not the half-open ranges we're talking about and using notation for here.
Me, I prefer integers and the a..b style, despite the off-by-one error.
Easier to read: http://www.cs.utexas.edu/users/EWD/transcriptions/EWD08xx/EW...
Although this is indeed much easier to read, the handwriting in the original is beautiful. Love the 'f'.
You are not the only person to think so, it has been turned into a font multiple times (for example, here: http://www.fonts101.com/fonts/view/Uncategorized/34398/Dijks...).
Just to pile on: 0-based indexing is also more convenient when you want to build a multi-dimensional array from a one-dimensional array primitive using the integer division and modulo operators to map between 1D and nD indices. E.g., a matrix with M rows and N columns can be mapped to the range 0 <= i < (NxM) by letting i = (row * N) + col, and the backward mapping is row = i / N, col = i % N.
If instead you use 1 <= i <= (NxM), 1 <= row <= M, 1 <= col <= N, then the mappings aren't nearly as clean. Sure, you could hide all this behind some kind of API, eg. Image.getPixel(x,y), but if you work with multidimensional arrays very often, eventually you'll need to marshal arrays back and forth between different containers that use different access APIs, and the simplest common representation to use for this kind of data is as a 1D array, so being able to work with nD data that is stored in a 1D array comes up fairly often.
If instead you use 1 <= i <= (NxM), 1 <= row <= M, 1 <= col <= N, then the mappings aren't nearly as clean. Sure, you could hide all this behind some kind of API, eg. Image.getPixel(x,y), but if you work with multidimensional arrays very often, eventually you'll need to marshal arrays back and forth between different containers that use different access APIs, and the simplest common representation to use for this kind of data is as a 1D array, so being able to work with nD data that is stored in a 1D array comes up fairly often.
We index from zero because it requires the least translation to machine code. One idea in this note, however, is pernicious: 2 <= i < n. In the for statement - for (int i = 0; i < n; i++) a[i] = i - i must take on a value that is not in the range of indices of the array, 0..n-1, to terminate the loop. This doesn't help reasoning about the loop. The problem is worse when pointer arithmetic is involved - e.g. for (p = start; p < end; p++) *p = 0 - as the final value of p may not even be a valid address. We would be better off with closed intervals and index types that restrict the range of values to those intervals.
Matlab, which is commonly used for numerical computing, uses one-based indexes. Just one of the little gotchas when switching between Matlab and "real" programming languages.
In mathematics and physics the usage varies. Zero is used when it is really the beginning of something, like t0 for the start time of an experiment. In most other cases lists count from one and up. Matrix elements too are generally denoted from (1,1) to (n,m).
In mathematics and physics the usage varies. Zero is used when it is really the beginning of something, like t0 for the start time of an experiment. In most other cases lists count from one and up. Matrix elements too are generally denoted from (1,1) to (n,m).
> Except deadlocks have nothing to do with sharing memory, and everything to do with sharing state.
Other languages using 1-indexed arrays: Fortran, Cobol, Smalltalk, XPath, Erlang[0] and Lua (and a bunch of other very old languages like PL/1 or Algol).
All Wirthian languages (Pascal, Oberon, Ada, etc...) use configured index ranges (and provide primitives to query the array for its bounds), but I believe the convention is to use 1-index arrays when there are no special index semantics due to their strings being 1-indexed.
VB has configurable index ranges as well, but defaults to 0-indexed arrays.
You can also "configure" initial array index in Perl by setting `$[` I believe. Doing this will lead to you being beaten to death with ethernet cables by your colleagues. And if it does not, it should.
[0] though direct indexation is rarely used in erlang
Other languages using 1-indexed arrays: Fortran, Cobol, Smalltalk, XPath, Erlang[0] and Lua (and a bunch of other very old languages like PL/1 or Algol).
All Wirthian languages (Pascal, Oberon, Ada, etc...) use configured index ranges (and provide primitives to query the array for its bounds), but I believe the convention is to use 1-index arrays when there are no special index semantics due to their strings being 1-indexed.
VB has configurable index ranges as well, but defaults to 0-indexed arrays.
You can also "configure" initial array index in Perl by setting `$[` I believe. Doing this will lead to you being beaten to death with ethernet cables by your colleagues. And if it does not, it should.
[0] though direct indexation is rarely used in erlang
[deleted](1)
Lua, the oh so nice "rebel" among languages, uses 1 as the first element in its indices :)
Nasty. But it's the same for substring text offsets, array indices etc in Postgres.
Nasty? In a language without pointers it makes total sense. An index is no longer an offset from an array (or string) pointer, so the first element being 1, the second being 2, just makes more sense.
Sure, it's a departure from mainstream languages, but in my opinion it's a perfectly sensible one.
Sure, it's a departure from mainstream languages, but in my opinion it's a perfectly sensible one.
> Nasty? In a language without pointers it makes total sense. An index is no longer an offset from an array (or string) pointer, so the first element being 1, the second being 2, just makes more sense.
Not necessarily. The reasoning in e.g. Python is that the index is not to an element, it's to one of the intervals around an element. The "first interval" (right before the first element) is 0, which naturally leads to -1 being right before the last element, thus arr[-1] being an array's last element, and arr[:-1] being everything but the last element.
Not necessarily. The reasoning in e.g. Python is that the index is not to an element, it's to one of the intervals around an element. The "first interval" (right before the first element) is 0, which naturally leads to -1 being right before the last element, thus arr[-1] being an array's last element, and arr[:-1] being everything but the last element.
[deleted]
Seems pretty well reasoned to me.
2..13 2:13 2->13
Again we fall in the trap of endless discussions about bitheads, numheads and charheads.
The bithead will always think in zeros and ones, he is a hardcore c or c++ programmer, and his brain is damaged beyond repair. Avoid all discussions with that kind of specimen.
The numhead accepts both conventions, he is a python or ruby programmer, practical and gets the job done, he may ask why that weird convention but still goes on using it since it solves all his problems as it is.
The charhead is a vb or js programmer by luck, not by choice, he will never understand why we start from zero and will curse everytime he writes a for loop.
I've been in the three camps luckily escaping without any brain damage (I believe) and after 20 years programming I still prefer to count starting by one, like any human being.
Again we fall in the trap of endless discussions about bitheads, numheads and charheads.
The bithead will always think in zeros and ones, he is a hardcore c or c++ programmer, and his brain is damaged beyond repair. Avoid all discussions with that kind of specimen.
The numhead accepts both conventions, he is a python or ruby programmer, practical and gets the job done, he may ask why that weird convention but still goes on using it since it solves all his problems as it is.
The charhead is a vb or js programmer by luck, not by choice, he will never understand why we start from zero and will curse everytime he writes a for loop.
I've been in the three camps luckily escaping without any brain damage (I believe) and after 20 years programming I still prefer to count starting by one, like any human being.
> I've been in the three camps luckily escaping without any
I'm not convinced that people count starting at one.
Count the number of elephants in your bedroom. Assuming that there weren't any, how can you say that you started counting at 1 when the result of said counting was 0?
I'm not convinced that people count starting at one.
Count the number of elephants in your bedroom. Assuming that there weren't any, how can you say that you started counting at 1 when the result of said counting was 0?
But do I call the first elephant I get into my room elephant 0 or elephant 1?
It's extremely common to want to refer to some dynamic offset of a fixed location in memory, like if you have an array of equal-length items stored consecutively. If you have two literal addresses called Start and Index, you'd like to be able to say something like "Start[Index]" and have it mean "Read from Index, and whatever number is there, move that many spaces forward from Start, and give me that". It's handy that if Index is a cleared region of memory, you can say "Start[Index]" and have it mean the same thing as just "Start". More importantly, if "Start[Index]" only meant "Start" when Index was 1, that would imply that if Index were 0 that Start[Index] would refer to the spot right before Start, which is not only useless but outright dangerous.