Again on 0-based vs. 1-based indexing
hisham.hm
hisham.hm
You can use the same mechanism (minutes:seconds) to explain the half-open ranges: does a range(0,30) mean from 0:00 to 30:00 or from 0:00 to 30:59? If the second half of the match starts at 30:00, does the first half really end at 30:00 or is it really 29:59:99...9?
For most basic concepts, there's always real-world examples to use so that the teaching doesn't have to be abstract.
I once developed a shortcut notation to simplify reasoning about ranges differentiating between "point cero" and "interval between 0 to 1", to make off-by-one errors less likely, but in the end it was functionally equivalent to the popular open/closed interval notations.
Ultimately, it relies on conventions, but I guess now you can see how this one relies on something which has some consistent pattern.
English in general makes this distinction: "He is fewer than 6 years old" is simply a mistake, while "less than 6 years old" is fine. (I think some dialects use "fewer" less often, in general, but would be pretty surprised if any prefer it here.)
those are the same number.
I think we are on the track to create a perfect programmers factory.
Once someone understands (2), pointers are incredibly simple and obvious.
you can just show them a ruler and ask them where does the first centimeter starts
Also trampolines. Kids love trampolines. From there it's a simple jump (pun intended) to something like the Y-combinator!
Unfortunately teaching languages that are good for learning, like Scheme or Pascal, went out of fashion a long time ago. For years now universities have been teaching marketable languages. Ten years ago that was Java. Now it's Python.
The unintuitive step is apparently identifying the index with the cardinality of the collection from before the item arrives, not after it arrives – i.e. ‘the n-th element is the one that arrived after I had n elements’, not ‘the n-th element is the one such that I had n elements after it arrived’. The former identification results in 0-based ordinals, the latter leads to 1-based ordinals – and to some misconceptions about infinity, such as imagining an element ‘at index infinity’ in an infinite list, where no such need to exist.
If anything, it is an artificial choice, because in programming it is derived from a property of most, probably of all, human languages that have ordinal numerals.
In most, probably in all, human languages the ordinal numerals are derived from the cardinal numerals through the intermediate of the counting sequence 1, 2, 3, ...
When cardinal numbers appeared, their initial use was only to communicate how many elements are in a set, which was established by counting 1, 2, 3, ...
Later people realized that they can refer to an element of a sequence by using the number reached at that element when counting the elements of the sequence, so the ordinal numerals appeared, being derived from the cardinals by applying some modifier.
So any discussion about whether 1 is more natural than 0 as the starting index goes back to whether 1 is more natural as the starting point of the counting sequence.
All human languages have words for expressing zero as the number of elements of a set, but the speakers of ancient languages did not consider 0 as a number, mainly because it was not obtained by counting.
There was no need to count the elements of an empty set, you just looked at it and it was obvious that the number was 0.
Counting with the traditional sequence can be interpreted as looking at the sequence in front of you, pointing at the right of an element and saying how many elements are at the left of your hand, then moving your hand one position to the right.
It is equally possible to count by looking at the sequence in front of you, pointing at the left of an element and saying how many elements are at the left of your hand, then moving your hand one position to the right.
In the second variant, the counting sequence becomes 0, 1, 2, 3, ...
The human languages do not use the second variant for 2 reasons, one reason is that zero was not perceived as having the same nature as the other cardinal numbers and the other reason is that the second variant has 1 extra step, which is not needed, because when looking at a set with 1 element, it is obvious that the number of elements is 1, without counting.
So neither 0 or 1 is a more "natural" choice for starting counting, but 1 is more economical when the counting is done by humans.
When the counting is done by machines, 0 as the starting point is slightly more economical, because it can be simpler to initialize all the bits or digits of an electronic or mechanical counter to the same value for 0, than initializing them to different values, for 1.
While 1 was a more economical choice for humans counting sheep, 0 is a choice that is always slightly simpler, both for hardware and software implementations and for programmers, who are less likely to do "off by one" errors when using 0-based indices, because many index-computing formulas, especially in multi-dimensional arrays, become a little simpler.
In conclusion, the choice between 0 and 1 never has anything to do with "naturalness", but it should always be based on efficiency and simplicity.
I prefer 0, even if I have programmed for many years in 1-based languages, like Fortran & Basic, before first using the 0-based C and the other languages influenced by it.
Well, 0-based is not what we use in everyday life, and even arriving at the invention of 0 took us several millenia, so I'd say its non-intuitiveness is pretty much established...
The ancient Greeks didn't think 1 was a number; as late as ~1500CE Isidore of Seville was saying "one is the seed of number but not number". After all, if there's only one thing you don't need to think of it as a set of things, so there's no counting to do.
(I think in some quarters it was even argued that two isn't a number, but I forget the details. Compare the fact that some languages treat pairs of things differently in their syntax from larger groups.)
But it turns out that mathematically it's a really good idea to count 1 as a number and allow sets of size 1, and these days everyone does it and no one is very confused by it. (Well, maybe by the "sets of size 1" thing. Exhibit A: Perl. Exhibit B: Matlab.) And because we're now all used to thinking of 1 as a number, it's hard even to understand how anyone might have found it unintuitive.
If we all started counting from zero and taught our children to do likewise, intuitions 50 years from now might be somewhat different from what they are now.
That's what it represents in indexing, the distance you have to travel to get to the element you want.
That's an offset. It's already covered in detail in TFA.
We don't deal with such offsets in programming, except in C pointer arithmetic (which infested this upon us).
People never said and still dont' say "this baby is 0 years old". They start at the first complete item of the lower level time units and progress from there...
So they may say one hour old, five days old, six months old, etc. a fifty year old typically doesn’t say they are a half centenarian either. Now decades are used to express an age range like so and so is a nonagenarian to avoid being specific.
How many more things can I fit in that box? How many comments are in that HN page?
I'd write more, but I'm running on empty and my pen is out of ink.
In some ways I think it's similar to the endianness debate: big endian looks natural at first glance, but when you see the expression for the total value, having the place value increase with the address just makes far more sense since it eliminates the extra length-dependent term and subtraction.
Closed and right-open intervals in Ruby:
(1..12).to_a
#=> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
(1...13).to_a
#=> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]I am doing my best in teaching my kids this way but the world around has the wrong idea. We'll see how it goes...
for x from 0 to 10 ;; closed, [0,10]
for y from 0 below 10 ;; (half-open, [0,10)
"Until" I'd think of as being the strict "to", except something about it feels off like it couldn't just be dropped in every place to/through can be used.
If I grab JS/Java/Python/PHP, an array/list is a magic sequence of values with opaque under-the-hood operations, and my only interface to it is the item index. In that context, promoting idioms because they make mechanical sense in a language I'm not using doesn't seem compelling.
I learned programming by myself when I was a teenager, and 0-indexed never was an issue.
We learn very early on as kids at school that there are 10 digit numbers, not 9. You learn to write 0 before any other characters. On every digit pad, such as phone dial, there is a "0".
If I ask you the list of digit numbers, 0 is the first element.
There is nothing counter-intuitive about that in my opinion, even for a kid.
Then Scheme, once they feel straightjacketed with BASIC; it will teach them what abstraction is and how to break code into chunks. It should be a bit of a lightbulb moment. They also get a type system.
Finally, Julia, once they get sick of the parentheses and difficulty of building "real" programs (you'll do a lot of DIY FFI to use standard libraries in Scheme). From this they will also learn array programming and the idea of a type hierarchy.
The only trouble with this curriculum is the student will be completely ruined for ever programming in C or Java. They will not have learned to tolerate the requisite level of tedium, or even programming without a REPL.
Maybe kids don't use rulers now? Just tell them that arrays are like rulers.
This has two nice properties. One is that two slices are adjacent if the beginning and ends match, and the other, far more important, is that the length of the slice is end - start.
That's the one that really gets us something. It means you can do relatively complex offset math, without having to think about when you need to add or subtract an additional 1 to get your result.
I use Lua every day, and work with abstract syntax trees. I mess this up all. the. time.
Of course you can use closed intervals and stick with 1-based indexing. But for why you shouldn't, I'm going to Appeal To Authority: read Djikstra, and follow up with these.
https://wiki.c2.com/?WhyNumberingShouldStartAtZero https://wiki.c2.com/?WhyNumberingShouldStartAtOne https://wiki.c2.com/?ZeroAndOneBasedIndexes
base is irrelevant to this, and you want (and show!) half-open, not closed, intervals.
> This has two nice properties. One is that two slices are adjacent if the beginning and ends match, and the other, far more important, is that the length of the slice is end - start.
Yeah, those are all properties of half-open intervals, irrespective of indexing base. It would be as true of π-based indexing as it is of 0-based.
This is why 1-based index languages normally use closed-closed intervals, so that they can use `1:N`.
I'm a die hard Julian (Julia is 1-based), but I do a lot of pointer arithmetic in my packages internally. I've come to prefer 0-based indexing, as it really is more natural there. 0-based plus close-open intervals are also nicer for partitioning an iteration space/tiling loops, thanks to the fact the parent commented pointed out on the end of one iteration being the start of the next. This is a nice pattern for partitioning `N` into roughly block_size-sized blocks:
iters, rem = divrem(N, block_size)
start = 0
for i in [0,iters)
end = start + block_size + i < rem
# operate on [start, end)
start = end
end
# operate on [start+1, end]
1- vs 0-based indexing is bike-shedding. A simple question we can all have opinions on that's easy to argue about, when it really doesn't matter much.
Julia uses 1-based indexing, but its pointer arithmetic is (obviously) 0-based, because pointer arithmetic != indexing. Adding 0 still adds 0, and adding 1 and `unsafe_load`ing will give me a different value than if I didn't add anything at all. (This is just reemphasizing the final point made by the blog post.)
Half-open because of the slicing properties, as noted in your posting and the grandparent posting.
0-based because of the simplification for converting between relative coordinate systems. Suppose you have one interval A represented as offsets within a larger interval B, and you'd like to know what A's coordinates are in the global coordinate system that B uses. This is much easier to compute when everything uses 0-based coordinates.
Here is a slightly longer discussion of that in a genomics context: https://github.com/ga4gh/ga4gh-schemas/issues/121#issuecomme... and a draft of a document I wrote up (again, in a genomics context) so as never to have to have this discussion ever again: https://github.com/jmarshall/ga4gh-schemablocks.github.io/bl...
To the second point, as I said: Djikstra's argument for using 0 instead of 1 with half-open intervals is, to my taste, perfect. As I have nothing to add to it, I will simply defer.
I think this is the clincher in your argument (rather than Djikstra). I only use languages with 0-based indexing, and it seems natural to me, but I could almost be convinced that if only I used 1-based indexing regularly then I'd be fine with it too. But here you are with actual experience of using 1-based indexing regularly and you don't feel that way, which blows that idea out of the water.
Leads me to the old joke:
There are only 2 difficult things in computing. Naming things, cache invalidation and off by one errors.
I mess it up as well, both in Lua and C. The key to success is to not calculate values by adding or subtracting them, but to use meaningful names instead. E.g. dist(a, b), holen(a, b), endidx(start, len) and so on. Forget about ever writing “1” in your code, point your finger and call operations out loud. It doesn’t eradicate errors, but at least elevates them to the problem domain level. Off by one is not exclusive to 1-based or 0-based, it is exclusive to thinking you’re smart enough to correctly shorten math expressions in your head every damn time.
(But sometimes I also feel too clever and after some thinking I’m just writing (i+l2+b+2) because it’s obvious if b already comes negative and means “from behind” in “0-based -1 is last” terms.)
Or the predecessor of the last element: array[array.length - 2] makes you think, whereas array[array.length - 1] is more obvious.
Doesn't work for tables, though, because you can actually put something at foo[-1], which can be useful.
I find that foo[#foo+1] is more common than foo[#foo] in my code, that is to say I add to an array more often than I access the last slot. Although I typically use the idiomatic table.insert(foo, bar) instead— but that's mostly because it's slightly awkward to add the +1 all the time.
Or how about a closed range in uint64_t that ends at 0xffffffffffffffff
Or a range from roughly a = -9223372036854775808 to b = 9223372036854775807 in int64_t. b - a will overflow.
The fact of the matter is, for a type that can hold N distinct values, there are N + 1 different possible interval lengths. You can not represent intervals over a fixed-width type in that same type.
And yes, I think any typed language with a less expressive range syntax than Ada has some work to do. That still leaves open the question of the default, and I maintain that 0 <= .. < n is the correct one.
Given how confused and inconsistent Python slicing syntax is, it obviously isn't.
It has none of the properties I want in a slice, and that a slice of literally any other length will have. In fact, it means every slice I use needs error-handling, because I might get... something that's functionally not a slice, but is still called one. If that doesn't scream "type error" at you, I don't know what would. In fact, that's precisely why 0 is a comparatively recent invention. Most list-based problems were solved just fine before then.
All these arguments are poor rationalisation for the field's inability to move on from the 8-bit era, where the loss of 1/256 of your address space mattered and compilers had bigger problems to solve than translating indices to offsets.
Instead, I'm dealing with that case at literally every one of thousands of places where I might receive it*! That's not clean.
0 comes up if you're doing any arithmetic at all. It's a natural and useful concept for almost anything. As long as you always can take something aways where there is something, you'll need 0. It wouldn't be very useful to make something such as a non-empty list type, to then be able to take away all elements except the last one, which must remain.
In more mathematical terms, 0 is called a neutral element (relative to the addition operation), and almost anything you might want to do (for example subtraction) requires as a consequence a neutral element.
So that's why you might want an empty String. If you have an optional element in a syntax, it can be convenient to match it with a rule using a Kleene star, and that gives you an empty Node, which would return an empty String if you request its value. And so on.
With open intervals, you have to represent that as, say, (3, 2). Which sucks.
It may make more sense to think of intervals in the real numbers. "[1,2)" doesn't have a maximum to the right - it has 1.9999....... but not 2. Thus it's "open" to the right. Whereas "[1,2]" includes its maximum (2), so its sealed.
The terms open and closed apply to any set of numbers (not just intervals), where "closed" means that the set includes the limit of any series of numbers in the set, and open means "not closed".
It sucks and is Stockholm syndrome.
The subscript on the coefficient then matches the power of x, letting you write the general term as ai x^i, which works out great when using capital sigma notation.
One the other hand, matrix rows and columns usually start from 1, so the elements on the top row are usually a11, a12, a13, ..., and the next row is a21, a22, a23, ..., and so on.
In an attempt to bring some unity to the two sides on this issue in programming, let me offer something that I'm sure everybody will be able to agree on.
Once upon a time I was implementing some mathematical code in C++. It was a mix of things from places where mathematicians would number from 0 and where they would number from 1.
I decided that the code would be clearer if the code looked like the formulas in the math papers they came from, which meant I wanted to use 0-based arrays in some places and 1-based in others.
Solution: I overloaded the () operator so that array(i) was a reference to array[i-1]. Then I could use 0-based or 1-based, depending on whether I was using a formula that came from a 0-based or 1-based area of mathematics.
Everybody agree that this was not a good idea?
julia> using Polynomials
julia> p = Polynomial([1, 0, 2])
Polynomial(1 + 2*x^2)
julia> p[0]
1
The remaining cases are by definition edge cases and warrant enough attention that bugs caused by 1- vs 0-based indexing doesn't seem to be a big problem in practice.
It's like with goto and structured programming - people stopped using goto for loops and ifs, so the remaining cases where goto is used as last resort aren't much of a problem. People think hard before doing this.
It is for all the more advanced uses of arrays and indexing where the base starts to actually matter, and those are not covered by foreach.
I find that the only hardcoded number I often need to slice or index is indeed the start, and most languages do offer something for that such as `slice[..i]` to slice from the start.
Generally, I agree with what someone else here stated, 1 or 0 based indexing is less important than open or closed interval. The discussion around these two is typically mixed because 1-indexing uses right-open interval while 0-based indexing uses right-closed.
Plus, the last bit is just "imagining a guy and getting angry at that guy", the absolutely dumbest form of argumentation.
Finally, someone who has never followed electoral politics or current affairs.
1. In this discussion, people often overlook that these numbers are applied to two different concepts: offsets and numbering.
2. If C had been designed with 0-based pointers (for offset calculation) and 1-based indices (for numbering the array elements) people would probably find this a strength, to have the most appropriate base for each case. It's an interesting what-if idea that I hadn't seen before.
I'm not sure about "multiply and add"... Aren't these instructions for computing with floating point numbers rather than offsets?
I don't think having pointers and indices behave differently is a good idea for the record.
They are languages primarily used for math and simulations and are pretty specialized so the indexing and representation of the vectors matches closer to how you would consider things if you were doing linear algebra by hand.
Julia, Matlab, and Fortran are also all column major for multi dimensional arrays too.
For numeric work ill take 1 index any day of the week, but for general programming or other CS work (like non vector/matrix data structures) i much prefer 0 indexing.
1. It is faster. Due to how memory works, 1-based languages need to subtract 1 internally every time you access an array[1].
2. It works mathematically better with some of the most common operations on array offsets, like modulo and division into round/ceil/floor. You'll be peppering your code with +1 or -1 around those a lot if you use 1-based indexing.
[1]: This is lua, for instance: https://github.com/lua/lua/blob/master/ltable.c#L702
I am not sure (1) is a very convincing argument. The subtraction of 1 internally is not necessarily gonna be there once the code gets compiled.
I will personally concede with you on (2), but it's still not very convincing considering that Fortran (a 1-index language) is still (arguably) the most popular language for linear algebra.
Personally, I feel "The Index Wars" are the same as the "Text Editor Wars": a matter for personal opinion.
Theoretically one can optimize it - though only when one can statically infer the index and the compiler decides to inline the array access function. If you can't do that, the best you can hope for is a fast CPU instruction like LEA or something.
In theory one could make a lot of things fast, in practice they rarely are, and it's always better to avoid problems now than to pray later.
The problem is that for every formula or calculation best suited for 1-based indexing, there is another which is better implemented using 0-based indexing. Regardless of which indexing mode you are using, peppering your code with +1 or -1 is eventually inevitable. It's why I think the choice is a matter of preference and has little to do with technical reasons.
Overall I still prefer 0-based indexing - a few bytes of RAM is cheap nowadays, when the calculation can be simplified using 1-based indexing, deliberately not using [0] and pretending that the array begins at [1] is often an acceptable option (the trick was originally invented for porting Fortran code...)
I can think of a lot of cases where I would do it for 1-based indexing, but very few for 0-based indexing. If you want to make the claim that there similarly many, you're going to have to come up with some substantial examples.
Your (2) I don't fully understand. Why would you need to use "modulo and division into round/ceil/floor" on array offsets? How often you do it?
For what it's worth, I've written a _ton_ of code in an obscure language called Omnimark, which is 1-based. Much of that code involved using arrays. I've just grepped through a large Omnimark codebase I helped to write, and no, it is _not_ peppered with "+1" or "-1".
No, it mostly affects execution time. Whether the effect is meaningful, however, depends on various factors.
> [...] and even this is assuming a particular implementation of arrays (which is not a given).
Eventually, all arrays boil down to pointer+offset memory accesses. Well, if your programming language internally implements "arrays" as hashmaps, then you've already lost performance-wise, of course.
> Why would you need to use "modulo and division into round/ceil/floor" on array offsets?
Whenever you're working with 2D/3D data in manually managed memory.
> How often you do it?
When you're writing web services? Probably not so much. When you're doing image manipulation or 3D graphics? All the time.
Circular buffers?
Every =single= hash map worth its salt should be power of 2 length backed array. And the hashing function (for the idx of the array) is not the division (that's slow and cannot be parallelized in the cpu) but a simple bitwise AND.
In short offset 1 doesn't map well to hardware.
1) It also affects runtime, when addresses need to have a subtraction, and maybe a multiplication, in the offset calculation.
2) You may need this often in certain network or protocol code, for example.Regarding performance: some mentioned that the 1 offset can often be optimized away by the compiler. But even when this is not possible, common CPU architectures include instructions that can apply the offset at no extra cost, see https://stackoverflow.com/questions/28032685/is-there-a-perf... , so 1-based indexing is just as fast.
It can be phrased mathematically like this:
Consider the equivalence relation a ≡ b (mod n). It has n equivalence classes. Use 1..n as the canonical elements for the classes.
mod1 takes a number, finds its equivalence class and returns the canonical element.
It really shows how conditioned the mankind is that they call the "0th" ordinal number by the name "first". We have never moved past the phase where the concept of "zero" was heretic.
Here + offset makes SO much sense. I think we should move to use it in other contexts too. "0 steps from the start of an ordered list" "1 step from the start of an ordered list" etc.
At the moment we are using two different "scales" for measuring things and labeling orders. We could as well use the letters "A", "B", "C" for the latter, and it wouldn't change a thing. Hindsight is 20/20, but it's just a confusing mishap that we are using "numbers" and "numbers + 1" for the two purposes, where the second one could be expressed just as another "measurement", and we could get rid of the confusing "numbers + 1" scale.
This is a left-over from mathematics where indices are distinct from the abelian group of integers.
So the index "1" as used to refer to vector element for example, is different from the number "1" on the number line. That is, one is an element of an index set comprised of ordinal numbers, while the other is an element of the integers.
The confusing part is, that both use the same symbol when in actuality they represent different concepts. The integer "1" is just a number like √2 or -7. The ordinal "1", however, is the representation of the concept "first".
The ordinal "0" would, if used as an index, always yield the empty set as a result (see von Neumann ordinals), which wouldn't be particularly useful in a programming language.
The mapping that selects elements given an index is arbitrary and can be defined as necessary. This allows for constructs like "x[-1]" mapping to the last element of an array. Here, "1" still means the "first" element, but the sign indicates the negative direction, i.e. start from last element.
In short: there's an argument to be made for having two distinct versions. One (1-based indexing) is consistent with mathematics, while the other (0-based indexing) is consistent with low-level low-level data representation and makes no distinction between ordinals and integers.
Even in maths it's pretty bad, because the Natural numbers still sometimes don't include 0, so that the 0th Natural number is 1, the 1th natural number is 2 etc. (using 1th instead of 1st to avoid the confusing nature of "first" in this discussion).
Well, every component of mankind was born. At birth your "first" year of life is the "0th" year. Right now, everyone is living its "n+1"th year of life (n >= 0).
I think the influence is strong, other than natural.
It really isn't. How many elements does a collection have, if it only has a 0th element? Is it 0? What about the size of a collection [0th, 1st, 2nd]? Or [0th .. 100th]? In language, we use 1-based indices for collections because we enumerate the elements based on counting them. A zeroth element doesn't exist, because if we had 0 elements, the collection would be empty.
Indexing of natural collections is based on cardinality, not ordinality.
You are exactly right. But does it make sense? I'm not sure. "if it only has a 0th element" isn't in my mind, a relevant question in the context of cardinality, since the answer is the same if it only has the "1th" or "2th" or "3th" element. (Sorry, picked up the habit of "misusing" "th" from another post in this thread.) The base case of indexing is "the start of the list" whereas the base case of cardinality is "empty collection". But should you define the concept of indexing by making an equivalence between cardinality and indexing by "cardinality of collection of elements from the start of a list to the current element (inclusive)" is, in my mind, something that doesn't _necessarily_ make sense.
I admit that it's awfully lot about choices and habits, but at least I find "unpacking" the arguments this way interesting and educational.
To put it this way: maths is the legacy codebase from hell; but it's what we have.
Joking, but I think there's always be a mismatch somewhere.
"...nowadays, all arguments that say that indexes should be 0-based are actually arguments that offsets are 0-based, indexes are offsets, therefore indexes should be 0-based. That’s a circular argument..."
Yes, that is a circular argument. It's not the one I would use. C made the decision that indexes and pointers are the same thing. It's a logical argument and one that's not circular. If they're separate things, then yes, you end up in a circle.
For languages that are not C-like, you could argue "pick an idiom and stick with it across multiple languages" or "make programming languages easier for humans to understand" Both of those arguments are preferential arguments. Perhaps there could be a study comparing the merits of each, but I haven't seen one yet.
I like chocolate ice cream. I like making pointers and arrays as similar as possible. I like being able to collapse pointer arithmetic down. I like doing huge mallocs and then playing around with large, empty hunks of memory. Some folks don't. I get it. Code should look like the way we think about the problem. That's an ideal state we'll never reach, but it's worthy of continued discussion.
You might dispute the premises, but I don’t see the circle. Isn’t this just “men are mortal, Socrates is a man, therefore Socrates is mortal”?
Edit: if I would make this argument, I'd say the assumption that indexes are offsets is baseless. This is easily proven since there are languages where this isn't true. However I would argue the problem based on practical merits: the reason there no 1-based index op-code exists is because no dominant programming language has 1-based indexing. Which is a self-fulfilling prophesy.
In general, I try to find the most general point and rebuttal as possible. These discussions tend to dive into pedantry and semantics. I'm just trying to do my part to engage the author where they are. ymmv
Seriously, the exact value of the lower bound for indexing doesn't matter here (some algorithms are best described with the lower bound other than 0 or 1, for example). The fixed or preferred lower bound is the real problem. Any argument for/against 0-based and 1-based indexing tends to gloss over the real problem because those arguments only exist to make some languages look better than other languages. As we move away from forced explicit indexing (e.g. arr.first() or foreach instead of arr[$LBOUND] or `for (i=$LBOUND; ...)`), it becomes clear that there is no such thing like the preferred lower bound for sequences at all.
This reminds me of my last company where the answer to the 2 vs 4 space debate was 3 spaces.
— Stan Kelly-Bootle
0-based indexing is here. 1-based has no benefit. New languages should use 0-based indexing.
Lisp or Algol are more or less contemporary to Fortran. The former uses 0-based indexing, the latter can use arbitrary bounds. As does Fortran at least since the seventies, by the way.
I do prefer 0-based indexing, of course, but often using indices can and should be avoided anyway.
Another thing to the add to the list of good ideas in Ada everyone ought to copy.
Fortran was using 1-based indexing 15 years before C existed if I understand correctly?
It seems clearly the motivation was to be in line with other mathematical languages. But then time and again I see people say Julia is supposed to replace Python in the future. Well, you've just set yourself up for a little fight there because I'd say the vast majority of programmers are used to 0-based by default, and they're not going to dick around and install packages and crap to change that default behaviour, least of all when trying to be convinced that some new language is superior.
Async vs threads matters more. Cargo vs NPM vs pip matters more. Practically speaking programming lua, do/end instead of {} took me longer to get used to than 1-based indexing.
I disagree, I had to slice bitfields in Ethernet packets in Lua and I hated 1-based indexing very much!
IMHO languages should either have 0-based indexing or any-index (as Ada does) unless you really wants to be a "mathematic only language" which is why I think that it's OK for Julia to be 1-based but not OK for Lua.
I don’t. I refer to Dijkstra’s opinion because it happens to coincide with my opinion, it’s already written down, and it would be silly to spend effort explaining it over and over again.
But if you do anything more advanced with arrays, then you will start to notice the difference.
For example, if you need to iterate backwards then it is nicer if the interval is closed on both ends (as is the case with 1 based indexing). This way, iterating backwards is as clean as iterating forwards.
Every language has its own design decisions based on some requirement or opinion, and while I have rather strong preferences about languages, these kind of design decisions doesn't strike any nerves.
As long as it's usable, that's fine by me.
My 2 cents: it isn't really that important. As long as the developer is aware of whether the language they are currently using 0 or 1 based indexing.
For a domain specific language focused around simulating physical things, or a specific application, 1-based indexing may be the more appropriate option. In this case, abstracting the problem domain is likely more important than adhering to the limitations of hardware.
He says that expressions A ≤ x ≤ B, A < x ≤ B, and A < x < B are confusing and a source of errors, but A ≤ x < B is not. I really cannot understand what's the difference, and why one would be more mentally taxing than another.
(From that he concludes that iterating over 0-based array is more intuitive. This kinda/sorta makes sense, if you believe the initial premise).
I'd like someone to shed light on this, if possible.
On the other hand, I’ve made an observation about timelines in music production software, where bars are counted starting from 1. As you zoom out, only every 4th bar tends to be labeled, which creates this strange sequence: 1, 5, 9, 13, 17… I always found that incredibly hard to reason about, and perhaps it would have been a better idea to label the first bar as 0.
For instance, suppose you're doing a lot of date arithmetic, and you might include times. If I have a range:
[2005-05-05, 2007-07-07)
[2005-05-05, 2007-07-07) [2007-07-07, 2008-08-08)
[2005-05-15, 2007-07-17) [2007-07-17, 2008-08-18)
That's because you can find the beginning and end of a range without knowing how to subtract by one. If you later decide to add times, it will just work because, conceptually, you already handle every possible value in the range.
If you want to construct a series of ranges of floats, it's a bad idea to do [3.457, 6.799999], [6.8, 12.47699999]. If you use half-open intervals, it just works, without mucking with the end of the range.
This is the reason that "indices are offsets" is powerful: it's not circular reasoning, but a simplification because we're removing an unnecessary primitive (subtracct 1) that only reliably works with integers.
And to bring this back to integer offsets, even when you're working strictly with integers, you may want to conceptually work with rational numbers.
When you're working out your math for buffered IO, you need to map byte indices to chunk indices. You need to assign every byte written to a chunk.
In a 0-based world, your chunk offset is simply your byte offset / chunk length. Because there is no distinction between indices and offsets, it's a clean mapping between one offset scheme and the other.
It means you can work out on paper when a new chunk should be started, and then translate that into integer arithmetic. And your code directly reflects the math, rather than having to stick "- 1" and "+ 1" in here and there.
It's not unnatural, but it's not natural either. It's just that 1-based indexing aligns with natural language conventions better. It also matches with some math conventions for matrices and vectors, but those don't have to use 1-based indexing either to work. I learned linear algebra with abstract "index sets" (I), where I can be {1, 2, 3, .., n}, {x,y,z}, {0,1,2}, whatever.
Programming in 0-based indexing means way less +-1 adjustments on boundaries. Division/modulus also works way better with 0-based indexing, so flattening multi-dimensional arrays is more easily expressed too.
In the end it's just a convention, it shouldn't matter too much. My money is still on 0-based indexing, as it lends itself to less errors and cognitive load when you get used to it. I used both extensively.
Tangential: conventions that are more "natural" are usually not actually natural, but just align themselves to other conventions better. Of course it's always good if conventions align, but sometimes it's inconsequential. Also there are situations where we can't make all conventions align.
An other little pet-peeve of mine is people calling big-endian more natural than little-endian, where there are actually different competing conventions:
1. Usual way of printing memory content from lower address to higher address from left to right (think hexdump).
2. Usual way of writing down numbers from left to right from most significant digit to least significant digit.
3. Expressing the value of the number from the byte array elements (\sum_0^(width-1) byte[n] 256^n for little-endian, \sum_0^(width-1) byte[n] 256^(width-n-1) for big-endian)
Big-endian aligns better with the combination of 1 and 2. Little-endian aligns better with 3.
What about how Europeans index their building floors from 0?
Fun fact: the numbers are imported from Arabic in which they are originally meant to be read from right to left => little-endian
Another minor issue is that you can access one less element with a fixed size integer than when you do 0-based indexing. So for u8 you can only access 255 elements instead of 256 for instance.
I have seen some difficult to debug issues caused by this when I used to work on game scripts.
Clojure
(range 1 10)
;=> (1 2 3 4 5 6 7 8 9)
C#
Enumerable.Range(1, 10).PrintAll();
1 2 3 4 5 6 7 8 9 10
Ruby
(1..10).each { |n| puts n }
#=> 1 2 3 4 5 6 7 8 9 10
Python
for i in range(1, 10):
print(i, end=', ')
=> 1 2 3 4 5 6 7 8 90-based indexing is inherently better for machines.
1-based indexing is inherently more natural for humans.
**
For a short stint I was running a (small) datacenter, and despite being an apologist for 1-indexed programming languages, I zero indexed EVERYTHING in the datacenter.
Let me just say, that was a huge mistake. Physical items are not offsets. Even though I was then working in a 0-indexed PL, The amount of contortion I had to do to remember zero indexing made the likelihood of errors higher (I did not make any that weren't quickly recoverable, but still).
Depends on what you are indexing. Time, for example, is very commonly represented as being 0-based by humans.
The number of times either of these properties has mattered for me also cannot be represented in the domain of 1-based indexes.
Of course, there are problems with this in a professional setting, such as how do you enforce uniformity across modules, and what happens if you copy code from one module that's Base 0 to one that's Base 1 and vice versa. But when I was first learning how to program, it was helpful to me to have a language that allowed for some choice.
In the meantime, 23 years of programming have led me to believe that index base 0 makes sense. For many applications it's moot, because we should be using higher level functions (like map and reduce) for processing lists. In every other application (such as working with data on a grid), dealing with offsets does make things easier.
Perhaps the convention is arbitrary. But, lots of industries have arbitrary conventions that we all agree on just to aid communication, and I disagree with the original author that the term "groupthink" applies in this situation.
When counting apples (i.e. only +) then 1 based. but when (* % ^ √ ÷) then 0 based
- pointer offsets - the article seems to dismiss these, but they're used loads in systems/network/driver programming, which is a reasonable chunk of the most important programming
- conceptual offsets - e.g. time of day starts at zero, not one. We think in this way a lot, and it's useful.
To save yourself from headaches, I believe 0-based indexes are preferred in almost every modern language for the simple reason of optimization. I have no evidence to back this. NULL=Nothing=0 is a thing though.
In fact, much of the vehemence in favor of it seem to be more about programmer shibboleths, to make some people feel they are in a special 'in-the-know' club (certainly if the r/programmerhumour reddit is anything to go by).
All I can do for scientists is tell them the advantage of learning a programming language outweighs the weirdness.
It is pretty intuitive when thinking about natural numbers as steps along a path. Then, zero is the number that means "you are already there".
0 based array (python) : screen_pos = x + y * width
1 based (lua) : screen_pos = 1 + x + y * width
shrug
So 0 based seems to work a little better for arithmetic based array references. But really you'll never resolve this to perfection. Assembly language programmers are very unlikely appreciative of 1-based.
Its all about what you're comfortable with.
Those wanting pointers can imagine a base address added to each calculation. 1-based then needs a -1... which is then a strange thing to advocate for.
The problem is within the phrasing and its premise: Are you using an index or an offset? 99% of the time I think of an offset, so "first" makes sense as "0". If you go by indexing "1" suddenly makes sense as an index. When people say index in the context of arrays or data structures usually they mean an offset. To me it's simply wrong phrasing.
> I’ll brush aside quickly the fact that this is not true — 1-based indexing has a long history, all the way from Fortran, COBOL, Pascal, Ada, Smalltalk, etc. — and I’ll grant that the vast majority of popular languages in the industry nowadays are 0-based. So, let’s avoid the popularity contest and address the claim that 0-based indexing is “inherently better”, or worse, “more natural”.
Maybe I missed the comments about 1-indexing being "unnatural" but if the author is referring to the discussion I took part in, then this is a strawman. It wasn't about what was "natural" or "unnatural" but about people switching from their primary language to secondary languages and gotchas like 1-indexing being error prone.
We had a platform team at my last company looking to adopt Lua for client customization. The primary authors became familiar with Lua in writing the code logic but everyone else would be touching their part, or contributing back to the core, not as people familiar with Lua but as C++ developers who would be blindly making changes in another language. It felt similar to maintenance of our Perl scripts. You don't brush up and become an expert on a language you interact with on a yearly cadence. It is important in these cases to have few gotchas to make casual contributions easier and safer.
This says nothing about using 1-indexing when your target audience isn't 0-indexed programmers (speaking of those who choose to use Lua and not to Lua's creators).
Unfortunately, for me, even with my complaints (this and language compatibility), I'll probably still use Lua for some projects of mine. I've looked at others and I'm mainly concerned about the community size.
And if the API provides `second`, `third`, `antepenultimate`, `penultimate`, and `last` methods it covers a large part of what one most often use.
Past third rank, then I will feel better served with a `slice` method, whose documentation provides explicitly it’s index convention, whether it makes a modulo on out of bounds, etc.
If you use 1-based indexing, you can't iterate over a list of maximum length with a simple loop. The normal loop condition is `while i < len` (0 based) or `while i <= len` (1 based). If len is maximal, the second one probably has an overflow bug in the loop body that turns it into an infinite loop or a crash.
And lest you think that counting down is unnatural—there are quite a few advantages in comparing to zero on every iteration instead of a computed upper bound, like that you can often roll the condition check in with the decrement instead of having to do a separate comparison.
The fact that a weird situation you set up intentionally needs special-purpose handling doesn't seem odd or unreasonable to me.
Furthermore, mathematical notation is almost universally terrible. It's inconsistent, ambiguous, and has many undeclared dialects. Oh, and many people use 0-based index to boot, because, you know, whether that's conventional or convenient (largely orthogonal qualities alas in math) depends on the context.
I mean, I can sort of buy his argument that it's arbitrary, but then he also points out that there's at least one advantage to 0-based indexing, namely that works well in offset based scenarios (not just for pointers). So in which case is 1-based indexing convenient? Based on this blog post, never.
Also, the irony of complaining about HN holy wars becoming just another trigger to continue! I'll do my part - whichever side you are on - you are wrong.
For instance, even in slicing, [start:end) eliminates this issue. Though there is something to be said for verbosity.
I think this becomes an argument for 0 based indexing, but a case could be made to the opposite.
That said, consistency is what is valuable, so the only truly wrong answer would be the one we use in real life.
And then you have Japan which sometimes starts at 2F. Hey, maybe we should use 2-based indexing.
The worst is really when you switch between the languages, but after a while you get used to it.
You just need to watch out like a hawk, when calculating the index of the last element ;)
Numbers in programming start at 0, even in the languages with 1 indexing. Period. When I initialize an integer, unless I explicitly set a value, it’s 0.
From a purely pragmatic standpoint, making the first number an invalid location in a list just adds unnecessary complexity and increases the odds of off-by-one errors. On the same token, there’s nearly no benefit to starting at one.
I agree that BASIC is inconsistent, but there are many languages beyond Basic and its descendants...
I'm afraid your argument still sounds like "C does it, so it is right" mentality.
https://docs.microsoft.com/en-us/previous-versions/visualstu...
Personally, I am not so much interested in which way is more right, but which way is less likely to result in off-by-one and related errors, though I do not know how you could gather data on that, other for people beginning programming, and any difference might go away or even flip as programmers gain experience and move on to more difficult problems. (Of course, the most effective solution is to not use indexing at all, except where absolutely necessary.)
That's it, I'm switching to saying number 0 reason from now on. If you are talking about your number 1 reason, I will forever be wondering what your number 0 reason would be. I'll tell my wife tonight she is my number 0!
kernel: array[-3..3,-3..3] of real;
x := kernel[-3,-3];
Sometimes you want negative indices, e.g. when performing a convolution on an image with a kernel.
In English we do. For example, if you are nine years old, you are in your tenth year. If an array has ten elements, the last element is the tenth element, it is nine elements away from the beginning. We could do "int array[10]; array[10th] = x;" if we wanted to mirror that.
We could imagine a language that does the distinction, but I don't know what good it would do.
[0]: https://wyborcza.pl/AkcjeSpecjalne/7,160474,24501452,zaczyna...
When you start calculating offsets and transformations of coordinates, starting at 1 forces you to carry around extra additive constants everywhere.
It has been enough of an issue for me to seriously reconsider my stance on indexing
With one-based indexes zero would be a very natural invalid value as an index similar to a null pointer.
Pretty much any language I can think of inits primitives with all bits set to 0. So either, you accidentally forget to set your index vars to 1 and out-of-range it there, or accidentally forget to take away 1 when accessing the end of the array. Pick your poison
Also, ⎕IO can be set as a local variable of a function to limit the scope of the indexing origin, which made it convenient to simplify the code to implement certain algorithms.
https://lasvegassun.com/news/2016/nov/07/the-human-calculato...
For example why is the 1st of January the first day of the month/year, but your first birthday is when you turn one year old, i.e. when your first year of life finishes.
Or let me rephrase that in the interest of avoiding natural language bias.
The starting element being at index 0 feels as natural as 0 being the starting natural number.
0 1 2 3 4 5
v v v v v v
|---|---|---|---|---|---...
^ ^ ^ ^ ^ ^
1 2 3 4 5 6...Our time counting is 1-based. There is no zeroth second, zeroth minute, hour, day, month, year, or century. This actually makes it slightly harder in 0-based languages to work with time and dates.
Also, it might be an indication that 1-based system is somewhat more intuitive to non-programmers.
My clocks all start at 00:00:00 every day, and that seems entirely logical to me. It's also how all programming languages that I've worked with represent time.
No there isn't, but we still use 0 to denote the first minute of an hour, just as we use 0 to denote the first element of an array.
But then recently I was doing some 'munging' to get some data structured correctly to display in a chart over months, with a variable start month that depended on the data. Well, let's just say that involved a fair amount of +/- 1 ing, and is hopefully the last time I think 'hm, it'd actually be quite nice if you could choose which to use on access' (or per function?).
If there weren't a zeroth second, minute, hour, day, month, year, or century when was 12:00 AM of Jan 1, 2000?
This is why a zero _offset_ is the initial _value_ for many implementations.
Not in every part in the world. Here in France, we use 24h time, and midnight is 00:00. Very convenient.
Midnight is not 01:01 AM.
Similar to the indexing question, this is only true for some cultures:
"East Asian age reckoning originated in China and continues in limited use there along with Japan and Vietnam, and is still common in Korea. People are born at the age of one..."
JavaScript will allow arr[-1] as an "individual" element, but it's internally an object and so iterating and hoping that -1 comes in order doesn't work.
Zero indexing might look weird at first but I think it helps in most cases.
arr[i]
*arr + (i + 1)This means that the 21st century started in the year 2001. Likewise, the current decade started under a month ago, not over a year ago. If you think the 21st century started in the year 2000, as do most people, then that implies that the first century either started in the year 1 B.C. (ugly) or was only 99 years long (not a century). People naturally (and incorrectly) default to zero-based indexing in this case!
I would go farther and make centuries zero-indexed too. It's far more natural to say that the Nth century is everything in the form Nxx than to say it's (N-1)xx. Every time I run across a numbered century I have to stop and think for a split second to calculate what years it covers. I got this wrong on several occasions in grade school and was marked down for it.
Zero-based indexing works naturally for grouping things. One-based indexing does not.
This, of course, doesn't matter much.