Just like big- vs. little endian issue, the differences matter less than everyone adopting one. When you program having two code sets with different base of indexing is several times worse than either alone.
0-based indexing is here. 1-based has no benefit. New languages should use 0-based indexing.
Yes! And it's not a coincidence Fortran was conceived to target scientists, while C was targeting kernel developers. The target audience had much to do with the choice.
Fortran predates C, so 1-based indexing has been “here” arguably longer than 0-based indexing. Most languages targeted at numerical computing use 1-based indexing because mathematics uses 1-based indexing in linear algebra. That seems like a huge benefit to me! C has 0-based indexing precisely because it doesn’t have genuine multi-dimensional arrays and has to use pointer arithmetics instead (which in my opinion makes it a very bad fit for scientific computing)
Mathematicians can, and do, use both, and would arguably be better of with 0-based. Mathematicians sometimes need to use partitioned matrices, and describing the start and end indices of those partitions goes better with 0-based indexing of matrix elements, so that the top left element is at 0,0. It's horrible if you have to work with such things in 1-index based matlab, the amount of nested +1 and -1 corrections you need to type...
0-based indexing was "here" long before C was created.
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.
This is where I land. Anyone arguing one way or the other tends to make up some arbitrary reason or impose assumptions on the implementation of the language. They are both perfectly fine and logical numbering systems, however since 95% of developers expect a 0-based numbering system, that is what we should use.
This ignores the fact that people use different languages for different purposes. More people use Excel, which is 1-based, than all other languages combined. Should Excel be 0-based because people who use C (a much smaller minority) prefer their language to be 0-based?
I like Ada's indexing range types, if you do it the right way your arrays can be 0-index or 1-index or indexed from 23 to 149. The bottomline is that in a good language it shouldn't matter and the programmer shouldn't even know how the compiler indexes the data. You iterate from array'first to array'last.
I do prefer 0-based indexing, of course, but often using indices can and should be avoided anyway.
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.
I don't have a strong position on 0-based versus 1-based, but Dijkstra's argument does not make any sense to me.
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.
One interesting case is when partitioning on integers, but wish to compare with floats... How do you get all values in say in 0..9.9999 when using 0 <= x <= 9... it makes sense to use 0 <= x < 10...
Another case is when using datetime... how do you specify the whole day without knowing the precision of your datetime (seconds, milliseconds, nanoseconds...)...
again, specifying 2021-01-10 to 2021-01-11 makes more sense than using 2021-01-10T23:59:59.999 for the upper boundary.
It's just fine for negatives. If you slide the range that 'makes sense' back by 10 (add -10 to it):
-10 <= x < 0
This excludes the end of the range, it includes the start of the range. What's changed is that the start of the range is no longer at zero and also has crossed from positive to negative.
I hope you are not iterating over floating point numbers between 0 and 9.9999 :-)
But your example is just the case for using 0 <= x < 10 in that _particular_ case.
However, if I want all numbers greater than zero and up to and including 10, I'd write 0 < x <= 10.
So I fail to see your point. Do you argue that if we had to choose just one of these expressions, 0 <= x < 10 would have more utility? I don't know how to evaluate this conjecture, but suppose it's right.
Why would you need to limit yourself to just one, though?
Why not to use one that is most suitable to the problem you are dealing with?
His argument works by exclusion; he excludes every notation that doesn't work with just the natural numbers.
Using strict inequality for the lower bound means you can't express sequences starting at 0 without expressing your lower bound as a negative number, which is ugly. So he prefers non-strict inequality for the lower bound.
Using non-strict inequality for the upper bound causes a similar problem. Consider the sequences (non-strict inequality on both sides) [0..2], [0..1], [0..0]. The first has three elements, the second two elements, the third one element. If you want to express a sequence with no elements starting at 0, that is impossible without using a negative number for the upper bound ([0..-1]). So he excludes using non-strict inequality for upper bounds.
What we're left with is non-strict inequality for the lower bound and strict inequality for the upper bound. This way we never have to leave the set of natural numbers to express natural number sequences, and as an added bonus, the difference between our bounds is equal to the length of the sequence.
Note that this part of the argument doesn't touch on 0 vs 1 yet, that is argued later in the essay.
Why would you need to "wrap around" an array?
I guess it's helpful if you use an array to represent a cyclic group, but how often this happens in practice?
And when you need the number of the last element, you need to do A[n-1], which is "less helpful", I guess.
I think both those cases happen with a certain frequency, yes, your last element is a bit trickier, though in Python it is represented by A[-1] (so that would turn into A[len-1])
Yeah, maybe there's no fundamental advantage, one would have to check the most common cases.
You still have to understand what is being abstracted if you want to do anything useful. You cannot just ignore what data structures are and how they work or you will have some very bad surprises.
Also often abstractions (and their quirkiness) make way more sense when you understand what is being abstracted.
If the language doesn't expose pointers, then that's an abstraction leak. Even if it does, why must that dictate the syntax and semantics? I'm sure our compilers and interpreters are capable of turning
I was hoping for an interesting analysis of 0 vs 1 based indexing, but instead got a 3 page rant of HN-this and appeal-to-authority-that which adds absolutely nothing of value to the discussion. It feels more like a bottom-of-the-page angry comment to an article than an actual article.
Fully agree. Got to the end of the post and was looking for the rest. The ranting could have been fine if there was more information and exploration. As it is, it’s unremarkable and not worth reading
This is probably because this whole debate is pedantic and irrelevant. 0-base wins, at this point it's not about picking a fork in the road, just swimming up stream for the sake of standing out.
LUA is over 23 years old at this point, it made a arbitrary design decision and has had to die on that hill ever since.
Yeah, this is a bunch of paragraphs complaining that arguments for 0-based aren't good enough for him, but giving no actual arguments FOR 1-based. That's not how you convince anyone. You can't just say that the other guy is wrong without giving any explanation for why you are right.
Plus, the last bit is just "imagining a guy and getting angry at that guy", the absolutely dumbest form of argumentation.
Not sure what you are trying to say here. It is a well known principle in political campaigning that presenting positive policies tends to gain you more votes than negative attacks on the policies of your opponents.
I quite disagree, I think it makes two insightful points:
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.
If C had 0-based pointers and 1-based indices, every CPU in existence would have a "subtract 1, multiply, and add" instead of an "multiply and add" instruction and everybody would think this is stupid because "multiply and add" could be used for a lot of things, but "subtract 1, multiply, and add" has only one use.
It was super frustrating to see the author dismiss Dykstra’s argument as an appeal to authority. No it isn’t, it just means that we find the arguments he outlined compelling. As someone who switches between C and FORTRAN daily, it’s incredibly clear that zero based indexing is easier.
My opinion is that languages where you work with vector representations primarily (or at least often) like Fortran, Matlab, Julia are best with a 1 index.
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.
I think it just comes down to where you want your index-out-of-range errors to occur.
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
I don't think it simplifies quite that far. There are languages that are capable of catching such errors ahead of time. Now that I think about it, there are even more that catch the initialization error - or at least do so more automatically than the end point error.
Perl initializes its scalars to "undef", not 0.
If you try to use undef as an array index, it will convert it to 0 but issue a warning.
I'd prefer it to be an error instead.
For a general purpose programming language 1-based indexing probably causes more confusion and errors than benefits. A language trying to be a general purpose computer programming language shouldn't abstract in a way that's likely to lead to confusion with those that understand the fundamentals.
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.
I don't think it's a real fundamental though - at least not for computing in general. It is true for C, and it is likely true for the many languages that implement things like C. But it's not inherently true that the 'fundamental' implementation of an array must exist as a C array does.
I don't know if it relies on C so much but what C is an abstraction over. An array in C is a set of data that exists in consecutive locations in memory. Memory addresses start at 0. Technically, a C array located at the start of addressable memory, by the nature of the way we've decided computers work in general, would start at 0. Plus as many extra zeros as your architecture can represent. This is generally the way computers are assumed to work.
Higher level general purpose programming languages exist primarily to serve as an abstraction over the fundamental architecture of computers. C is technically a higher level language than machine code and assembly code, both of which use the 'lowest address is zero' abstraction. Every other abstraction, including C exists over top of that.
My point is mostly, if you're trying to remain relatively close to abstracting over general computing keeping arrays and their index based on what they are fundamentally abstracting over makes sense.
In domain specific applications, it may make less sense.
Though it is a convention, it has demonstrable, objective benefits.
The use of 0 as the basis means that, in mathematical language, the indexing is homogeneous and that conversion between different units is a linear map.
Imagine if we have tape measure that measures both meters and centimeters. Imagine that the first tick on the tape measure, representing no displacement, is simultaneously labeled "1 cm" and "1 m" instead of 0.
Now, we no longer have a linear map to convert between cm and m. What we have is an affine map, like m = 1 + (cm - 1)/100.
An affine map is a strictly inferior alternative when we have the freedom to establish a linear map.
Homogeneous/linear is the superior default. One-based can be used in the special cases where it is nicer.
Here is one example: binary heaps. When we store a binary tree structure into a heap array, 1 based indexing makes the calculations nicer for navigating from parent to children or vice versa:
[1]
[2] [3]
[4][5] [6][7]
The children of every node [n] are [2n] and [2n + 1]. The parent of every node [n] is [n / 2] (floor-truncating division).
Under 0 based, it's not as nice:
[0]
[1] [2]
[3][4] [5][6]
The children are now [2n+1] and [2n+2]. One extra addition is required in the case of the left child. Finding the parent requires a subtraction: [(n-1)/2].
Another way to see the advantage of 1 based here is that every row of the tree starts with a power of : [1] [2] [4] ...
Because we are dealing with exponentiation, avoiding 0 helps: 0 is not a power of two, so to "boostrap" the exponentiation, we have to displace it.
Note that even though it is nice for a binary heap to use 1 based indexing, we still want to store that in an zero-based array, and just sacrifice the storage for the zero element.
If we use a zero based array, then the nice heap arithmetic we wrote in the source code will look nice in the object code, due to the map from the source code array to the object code array being a linear map, rather than an affine map.
It is almost always better to simulate a 1 based array by sacrificing a storage element, than to have the compiler uglify the beautiful indexing calculations for the sake of which we switched to 1 based in the first place.
In summary:
1. we should choose the representation which offers the most succinct indexing calculations for the given situation, and not for some emotional reasons like "children learn to count from 1 and non-programmers understand that best".
2. arrays should be zero-based to preserve the succinctness of the calculation through to the object code (linear map from source to object, not affine).
I still find this view of programming languages to be too limited. It's still very C-focused, in the sense that it seems to assume every language is trying to do the same things C is in roughly the same ways C does it.
Yet this just isn't the limit of computers or programming languages. Consider Prolog or a Lisp. What meaningful abstraction do they provide to have a deep connection with a block of contiguous memory used to store multiple same-sized elements? I'm sure you'll find such things ultimately used if you go deep enough, but it's not a meaningful part of the abstraction the languages provide.
And if we can do away with the entire concept of a set of same-sized data stuffed into a contiguous block of memory, what need can there be to adhering to considering indexes as memory offsets?
The incredible amount of (possible) separation between programming languages and the exact way in which such programs are executed provides an extremely valuable and deep freedom in how programmers can think about and address problems and their solutions. I don't see how insisting that we minimize any possible differences between language abstractions and common hardware practice gains us anything.
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.
A list of length equal to whatever maxint is is something you would have to set up on purpose. (If it were naturally occurring and unpredictable, then you would need to handle the much more common case where the length of the list is greater than maxint, too.)
The fact that a weird situation you set up intentionally needs special-purpose handling doesn't seem odd or unreasonable to me.
This is actually symmetrical. When you use 0-based indexing, you can't count down with a simple loop: you need to either extend your index type to include an invalid -1 or apply the infamous evaluate-then-decrement semantic. In practice, this means people often index with a signed integer, which is absurd.
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.
I grew up on languages that were 1 indexed - BASIC, VB, VB.Net. It took me a long time to get used to 0 indexed, primarily in college and later in working with more C inspired languages, yet I think 0 indexed is superior. Why?
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.
No, no "period". There are plenty of languages that either require you to initialize your variables, don't allow to use a variable until it's initialized, or give an uninitialized variable a special value like "undef" or "Nil".
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.
No it doesn't. That just gives you the last element, which is not a "based indexing".
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.
Sure it does. -2 gives second to last, -3 gives third to last, etc. If you only use negative indices i, the "base" of the array is the end, and arr[i] is just arr[len(arr)+i].
First, it's a "joke", second, nobody is going to force you to use non-negative indices. Sure, you can use a base index of zero and read left to right... but you can use a base index of -1 and read right to left and live a full (if lonely) life without considering the passé alternatives.
More precisely, I'm defining the "base" to be the right hand side of the array and operating on the reversed list -- it's just a change of variables. Python supports -1 based indexing, but does not support 1 based indexing. You could easily define a language which only provides the -1 based indexing but does not support 0-based. Let me demonstrate:
Here’s some fuel to the flames: < is less chars than <= , it also is more logical. 0-based indexes have the advantage of if in comparison and range. Mathematics treats 0 as special and can have all sorts of side effects if dropped into a formula, code doesn’t have this side effect (unless running formula as an algorithm, which is math).
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.
Here's two arguments arguments in favor of 0-based 'indexing' (or offsets), that aren't just "because that's how it's done":
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.
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.
>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.
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.
I mentioned it's theoretically possible and outlined the specific conditions for optimizations to happen.
But I also mentioned that in reality various things often prevent compilers (assuming it's a compiled language, and not interpreted, like that LUA implementation) from applying such optimizations:
- you're programming against an API or are compiling an API (i.e. non-static functions).
- you have time-constraints for emitting optimized code, like most JITs - you can't afford any deep analysis that would enable such optimizations, you're mostly pattern-matching for lower hanging fruits.
Since pictures say more than a thousand words, here's the actual disassembly of that lua function I linked earlier, as shipped by my Linux distribution: https://i.imgur.com/DnqVC8E.png
The green stuff is the "fast path". For 0-based indexing you would completely drop the first LEA and replace those last MOV/SHL/LEA with a (faster?) MOV r,r/SHL/ADD r,m - which is what GCC is likely to generate.
So that's Lua (one implementation at least) in practice. No compiler magic making arrays fast here.
LuaJIT (from my current reading) goes the different route of just pretending the first array element doesn't exist, meaning that in memory they have an element '0', but they simply don't use it. This trades some memory for speed.
From lj_tab.c:
** The array size is non-inclusive. E.g. asize=128 creates array slots
** for 0..127, but not for 128. If you need slots 1..128, pass asize=129
** (slot 0 is wasted in this case).
Personally I quite like this approach. A lot better than hoping compilers will magically fix everything and quite hard to argue with, considering LuaJIT's performance. Though it would be a ludicrous design for a lower-level language.
Your (1) only affects compilation time, and even this is assuming a particular implementation of arrays (which is not a given).
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".
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.
Modulus (division) is slow and the length should be pow2 and the operation "& (len-1)". If you do %len, you have far greater issues. I have pretty extensive experience writing hashmap/cyclic buffers and the like. If you have auto-grow structs (and you almost always want that), you want pow2 length arrays. e.g.
This is entirely orthogonal to whether you do "prev+1 & len-1" or "(prev & len-1) + 1". (In fact, the latter gives a more natural construction if you fill downward.)
Adding/advancing is indeed easier. What about going backwards (insert before head or remove from tail), i.e when 0, then length. One way to do it is something like that, assume 2 compliment and there is negative shift left available. Not straightforward:
int h = ( -(--head) >>> 31) ^ 1;//if head was equal to 1 (and only 1), h = 1, otherwise zero
head += h * len; //or shift left, if there is log2 len available; still, mul is a fast operation, unlike div
Of course, it can implemented via branching but that would be a major downside for 1-based idx.
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.
Citation needed. Yes, the -1 appears in the source code. It might even appear in the intermediate representation. It'll even show up in the assembly for multidimensional arrays (but it'll all get folded into a single `mov` assembly for vectors).
But I dare you to actually demonstrate a performance difference. Compared to a memory access, a `dec` is free.
At some point I would like to write up a story about this team in my University Object-Oriented Programming class who decided to use 1-based 1ndexes in Java while making a 2-D array for a board game.
I don't want to spoil it, but the following picture of a how they stored a 3x3 tic-tac-toe board is a hint:
That's what I was thinking, too, but most of the time (even if the index is not static) the -1 can be eliminated by just modifying the address at which the array is assumed to start. That is,
arr[x]
compiles into an access at address
(arr - 1) + x
Since the address of arr is statically known, arr - 1 is, too, and the address of "one before the first element" will be what's written as the base for the memory access.
> Since the address of arr is statically known [...]
No, that's almost never the case – only when accessing a static array. Typically, that restricts it to static look-up tables and very simple embedded systems.
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.
Only one reason exists these days: it prevents bugs because people mix up order, infecting, counting, arrays semantics, implementation, pointer arithmetic
For 2), in Julia, there is "mod1" function which acts as modulo, with 1 being the smallest value instead of zero. It doesn't really make sense mathematically, but is very useful for looping over circular arrays.
> It works mathematically better with some of the most common operations on array offsets
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...)
Not convinced that is the case. I do not pepper my code with +1 and -1 while using 0-based indexing.
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.
The -1 with 0-based indexing occurs very frequently when using the amount of elements in some collection to derive boundaries of the indexes, which will range from 0 up to and including n-1. Grepping for "- 1" in my code folder returns mostly expressions that look like 'length/len/size - 1'.
This can happen, but it is fairly rare, especially if you favour handling ranges as either (start, length) tuples, or as half-open intervals, with the end index being one past the highest index. This representation simplifies many things, many of them unrelated to 0- or 1-based indexing.
Notably, this requires you to use a signed index type, which is absurd.
The alternative is to use the so-called goes-to operator: for (i=N; i --> 0;). But this actually relies on the postincrement semantics, which is a huge wart.
Regarding the mathematical advantage: it depends on the subfield, but I think 1-based numbering is more common in mathematical notation and algorithms (linear algebra being a prominent 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.
This type of bikeshedding behavior is a sign of technical immaturity. The more technical experience one gains, one usually becomes a lot more disinterested about small syntactic technical details of programming languages and more interested about larger abstract concepts (e.g. discussions on Monads, type theory, "everything is an expr" etc...)
Zero- versus one-based indexing actually matters somewhat for correctness. The real trivial ‘small syntactic technical’ bikeshedding is braces versus indentation (and: which kind of indentation) or semicolons versus no semicolons.
Semicolons vs. end of line (like in Python) has a significant difference on what kinds of things you can express. End of line based syntax strongly discorages long lines, what brings problems and benefits. (And the Javascript choice is simply wrong.)
Semicolons vs. indentation structure (like in Haskell) has a huge usability difference in interactive shell. It's trivial on editor code.
The dismissal of syntax as trivial is not a good line of thinking. Syntax tends to have surprising impacts on semantics.
yeye, "HN" tends to abstract everything to the point that sometimes I do wonder how Java is not the church language of HN, also I do wonder whether people here still write code, or just became "architects".
So, there's nothing wrong with challenging common norms - remember NULL? XML oriented programming?
The biggest thing about index 0 or 1 is the inclusive and exclusive slicing. When the index is 0 and the slicing is [inclusive:exclusive], I find it a bit easier to write code with array manipulation.
While I don't have a strong preference in this "war", I can think of an interesting argument for 1-based.
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.
Our counting is 0-based as well - usually when you start by saying "one" it is implied that 1 second has elapsed. So while we don't pronounce zero we still count starting from it.
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.
But 00:00:00 does not represent the first second of your day. It represents a _point_in time, which has no duration.
The first second of your day is an interval between the moment your clock shows 00:00:00 and the moment it shows 00:00:01.
If 00:00:00 is the fist second, why it's not the first minute and not the first hour? Is the fist second is the same as the first minute and the first second?
I'm not French, but your comment just made me 'realise' that people who use 12h have the largest numbers when we on 24h have the smallest, almost like the 'start' is one o'clock. Weird.
Same :00 start happens with minutes on 12h though of course.
I think GP didn't mean to talk about time, has a point regarding months as I replied elsewhere. We represent the months numerically as 1-12, and I have recently found that annoying to work with.
Indeed, months are 1 based, but it's never been a problem to eg compute which month it will be, say 9 months later: just sum and subtract 12, no need for a real modulo computation. It's probable I've never found it annoying because I don't need to perform this computation with more than 12 months.
12:00 should actually be 0:00 on the 12 hour clock, it belongs to the next 12 hour period. 11:59 PM is yesterday, 12:00 AM is one minute later, and falls on today. Same with noon, 12:00 PM comes one minute after 11:59 AM. When I see 12:00, I automatically convert that to 0:00, otherwise AM/PM doesn't make sense.
Yeah, this is most familiar to me too. Still, I'd argue it's 1-based.
00:00 is a point in time, but the first second is between 00:00:00 and 00:00:01, and it's "00:00:01" when it has elapsed.
There absolutely is a zeroth second! It is the 60th second of the prior minute. This is actually the exact reason why midnight is 12 AM not 12 PM, and noon 12 PM not 12 AM.
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.
... And I (a non-native English speaker living in the US) always have trouble remembering what 12 AM and 12 PM means, even after all these years I have to look it up every time, and sometimes it drives me nuts.
(For a moment I hoped your explanation would at least serve as a heuristics... but alas, it does not make sense to me. Well, at least at the moment I remember the notation).
Regardless of it, "12:00 AM of Jan 1, 2000" is not a particular second. It's a point in time, it has no duration.
It does not belong to any particular calendar hour or day or year, it's a _boundary_ between two.
Of course it belongs to XX century since XXI century starts at 12:00 AM of Jan 1, 2001.
The first second of Jan 1 lasts from 12:00::00 AM to 12:00:01 AM.
First minute of that day lasts from 12:00 AM to 12:01 AM.
Etc.
Yes, this isn't usually an argument I care for, I happily use zero-based and occasionally having to pause to remember to get it right in SQL is a minor annoyance and that's that.
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?).
TBH indexing became much less important with every language adopting some sort of "for all" and map/filter/reduce constructs. If you don't care about indexes you don't need to think about them (finally!).
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.
Yes. I did write Lua for a few years and have a hard time remembering seeing any indexing cases. I probably encountered some but they were very few and far between.
Exactly. When I was a beginner I made off-by-1 errors (in Python mind you) all the time. Now that I iterate directly through arrays or use map-reduce patterns I rarely have to handle the index itself.
I disagree, this depends a lot on your problem space. I mainly do scientific programming and so have to do array/vector slicing etc. and indexing definitely plays a big role.
Do you often find a need to slice hardcoded numbers, however?
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.
Well I was replying to the statement that the OP was saying indexing is less important and I find when dealing with slices it definitely is important (as can be seen in your example).
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.
I'd say it's the exact opposite. Iterating over an array is trivial no matter if you use 0- or 1-based indexing. If that is all you do, the type of indexing really doesn't matter.
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.
In the same way that I don’t think learning sklearn is the hard part of knowing ML, I don’t think 0 or 1 -based arrays is the hard part of any particular language. There are situations where both are appropriate. The choice of either as the deal breaker for a language is extremely superficial.
I kinda take issue with his complaining about referring to Dijkstra's argument as being an argument from authority. Dijkstra makes a pretty solid case in his writing, it's not just about him being Dijkstra.
But we don't need to rely on Dijkstra's opinion at all. Plenty of us have programmed with both 1-based and 0-based languages and (most of us) will tell you that it doesn't really make much of a difference in practice. It (generally) doesn't change how you conceptualize your program or how you express it to the computer. Its like tabs and spaces - pick one, life is too short to care.
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.
> (most of us) will tell you that it doesn't really make much of a difference in practice.
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.
> But we don't need to rely on Dijkstra's opinion at all.
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 Dijkstra's opinion is not well founded, so it's definitely an appeal to authority. His opinion hinges on words like "ugly" and "preferred" without explaining what he means by this. He makes a choice of one over the other forms based on an unclear value function. His entire argument is this:
"There is a smallest natural number. Exclusion of the lower bound —as in b) and d)— forces for a subsequence starting at the smallest natural number the lower bound as mentioned into the realm of the unnatural numbers. That is ugly, so for the lower bound we prefer the ≤ as in a) and c). 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. That is ugly, so for the upper bound we prefer < as in a) and d). We conclude that convention a) is to be preferred."
I mean... that doesn't exactly settle it. Sure, your opinion might coincide with that, but this is not a logical argument. First you're going to have to explain what unnatural numbers are (because they're not a thing as far as I can tell), and then you'll have to tell me what about them makes them "ugly", and how that makes the other option "preferable".
Natural numbers have a least element X. (In fact, any subset of them does. This is called the well-ordering principle.)
Part 2:
Suppose lower bounds are exclusive. Then the lower bound L of any interval containing X must be less than X. Since X is the smallest natural number, L must be an unnatural (non-natural) number.
It is more convenient to stay in the naturals.
Therefore, it is more convenient to use inclusive lower bounds.
Part 3:
Suppose upper bounds are inclusive. Then, to represent an empty interval, the upper bound must be less than the lower bound. (If it were equal to the lower bound, we would get a singleton interval, not an empty interval).
It is already strange that we need an upper bound that is less than the lower bound. But there's more: When the lower bound is X, this would again take us out of naturals.
Therefore, it is more convenient to use exclusive upper bounds.
Conclusion:
It is more convenient to use inclusive lower bounds and exclusive upper bounds, i.e. convention (a).
I know what natural numbers are. But "unnatural" numbers is not a term people use.
"It is more convenient to stay in the naturals."
Right here, you do the same thing Dijkstra does. You declare that one way is more "convenient" than the other (he calls it ugly), without defining what "convenient" means. This makes the argument subjective. What you think is convenient, others may not think so. Or, one may agree with you on a matter of convenience, but would prefer a different choice due to some other priority e.g. learnability.
So I just don't agree this is an airtight argument. It's a subjective argument for a preference at best.
> You declare that one way is more "convenient" than the other (he calls it ugly), without defining what "convenient" means. This makes the argument subjective.
Nope.
1. Some things are objectively more convenient than others.
2. I've explained exactly what I mean. And so did Dijkstra.
Since you apparently don't want to use natural numbers for indices, what do you want to use?
Djikstra does a good job of selling the virtues of 0-based indexing, but he doesn't give the same attention to the situations where 1-based indexing is better. That's the biggest problem I see in EWD831.
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.
0-based indexing with closed intervals is better for slicing. This shouldn't be controversial. It's because you can represent a zero interval cleanly: [3,3) is an empty interval after slot 2, representing a single cell is [3,4).
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.
> 0-based indexing with closed intervals is better for slicing. This shouldn't be controversial.
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.
For </<= intervals and 1-based indexing you have to write `for(i=1; i++; i <= N)`. So you lost nice property of having `upper - lower` number of iterations.
For half-open intervals, you have upper-lower iterations regardless of base. In C for loop terms, it's:
for (i=lower;i<upper;i++) {}
If you are using 0-based indexing, lower is zero and upper is the number of elements for a full iteration over all indexes; with 1-based indexing lower is 1 and upper is one greater than the number of elements.
Now, despite the utility of half-open intervals, most people’s intuition is around ordinal index ranges, so 0-based indexing is counterintuitive with half-open intervals because slices start at 0, and 1-based indexing is counterintuitive with them because they end at N+1.
This is because, useful or not, half-open intervals are counterintuitive, but they are worth developing the intuition for because they combine nicely.
> with 1-based indexing lower is 1 and upper is one greater than the number of elements.
Do you see +1 tweak? Also consider that "for loop" can't be expressed as </* interval and always expressed as <=/* interval. So 1-based indexing have to be either 1 <= i <= N (closed interval, bad, N - 1 != number of iterations) or 1 <= i < N + 1 (half open interval, good, but +1 tweak).
It's related to 0-based indexing in that if you you want to take/iterate over the first `N` elements, `0:N` works with 0-based indexing + close-open, but if you had 1-based and close-open, you'd need the awkward `1:N+1`.
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
But that's only slightly nicer. To translate this into 1-based indexing and closed-closed intervals, you'd just substitute the `# operate` line with
# operate on [start+1, end]
the `[0,iters)` with `[1:iters]`, and `i < rem` with `i <= rem`.
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.)
I have on occasion, and when working on custom array types I've added support for being offset with optionally compile-time known offsets.
As StrideArrays.jl matures and I write more libraries making use of it, I may use 0-based indices more often. The idea of dynamic offsets when they aren't needed bothers me, even though I've benchmarked that as being pretty meaningless.
The bigger problem is just that OffetArrays are a wrapper, and there's a Julia bug where TBAA information on wrappers often gets lost, so that the compiler reloads the pointer you're loading from on every iteration of a loop. Aside from that being slow itself, it also causes the autovectorizer to fail. This causes a severe regression when it occurs. Performance should be fine in other cases.
LoopVectorization or `@simd ivdep` should also avoid the problem.
For the most part, my preference on 1 vs 0 is weak, and for coffee other people are likely to look at i do want to make it easy to understand / not full of surprises.
The natural representation of intervals for doing arithmetic on is 0-based half-open.
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.
I think this is a good write up, but I think the notation is still carrying some mental baggage. It's not necessary to have these open and closed brackets/parenthesis. They don't add anything, and if anything, they confuse the matter. An interval is just (1, 2) (or [1, 2] if preferred aesthetically). Since a base cannot be "on" either 1 or 2, it's not meaningful to have these open/closed interval notion. In other words, (1, 2) == [1, 2) == (1, 2] == [1, 2].
Open/closed intervals only come into play in continuous dimensions. DNA sequences, arrays in memory, et al are discrete.
On the first point, yep, completely misspoke, what you don't want is open intervals.
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.
True, but there are examples where 1-based indexing is easier, like returning the last element based on length. I think array[array.length] is easier to understand than array[array.length - 1].
Or the predecessor of the last element: array[array.length - 2] makes you think, whereas array[array.length - 1] is more obvious.
I think the most mathematically natural way to interpret negative indices is to threat them as numbers modulo list length. Then 0 = length, and -1 = length - 1.
Negative indices have an implied ”len(list)” in front of them. They can be seen as an application of the idea of half-open intervals (0 <= i < len(list)), so it makes sense that they’re not symmetrical.
I'm not sure on what principles you'd make a principled justification. My most common use of negative indices is for slicing the end of the list, in which context the interpretation similar to len(list) makes sense. E.g., list[:-2] does what you'd expect (the same as list[2:], except from the other end).
> implicitly taking indices mod len(list)?
Isn't this doing that (plus some bounds checking)? -1 mod 4 evaluates to 3.
imagine if you used list[index] where index would be calculated
if you misscalculated something and went on negative, then you'd have big exception/error, but when negative indices are viable, then the code will work fine
Sure. Let's take array elements in reverse, from m to m-n.
Suppose n erroneously becomes larger than m. That should
produce an error, not silently take several tailing elements.
Which Lua has also, for strings, and it's quite convenient.
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.
> I use Lua every day, and work with abstract syntax trees. I mess this up all. the. time.
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.
Why on Earth would I want a "zero interval" slice?
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.
You want a zero-slice because it’s a simpler base case in almost any even mildly complex algorithm. Without empty lists, you need many additional branches throughout a code base to handle the “no element” case, causing more potential bugs. There’s nothing “8-bit” about cleaner code, quite the opposite.
Wikipedia says that Egyptians had a 0 as early as 1770 BC - almost 4000 years ago. If that's a "relatively recent" invention, what about computers?
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.
Well, you might want a function which returns String, not Maybe(String), so that you can just concatenate, rather than handle Some(String) or None all the time.
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.
Just a friendly correction :-). You have repeatedly confused the meaning of open and closed. "Closed" means including the end element given in the range, and "open" means excluding it.
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".
Much appreciated! The terminology and notation seemed backwards to me, and I basically never use it except when discussing Djikstra on HN ;-)
Visually, it looks like ) has more "room" than ], if that makes sense, and that "closed" would mean that the element defines the 'lid' of the range, while "open" means it defines the final extent.
But you can't argue with nomenclature, and extending the definition to the reals helped make it click for me, so I'm unlikely to screw it up again. Thanks!
You could imagine the curved parentheses as "cutting the corner" of the square brackets - or imagine the curve as just gently kissing the endpoint at a single point, while the flat square solidly includes it. "Open" makes sense because it satisfies the criterion that for any number in the interval, you can find a larger (or smaller) number that is also in it - there's "no end".
A programmer “strengthens their ankle and leans forward by holding their arm out, preparing to relax the shoulder” into a bar. The bartender bursts out laughing for few sprints.
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.)
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.
Did you mean open range? I've never encountered a circumstance where closed ranges are useful, though I presume they exist.
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.
That... makes no sense? Whether you start counting a list at 0 or 1, if your language of choice supports [x,x) notation, that syntax will effect an empty interval, and [x,x+1) will effect a single cell, no matter whether your list indexes the first element as 0, or 1. The only difference is which cell [x,x+1) refers to, which is the part that keeps sparking the controversy.
521 comments
[ 7.3 ms ] story [ 345 ms ] thread0-based indexing is here. 1-based has no benefit. New languages should use 0-based indexing.
Fortran was using 1-based indexing 15 years before C existed if I understand correctly?
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.
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.
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.
Another case is when using datetime... how do you specify the whole day without knowing the precision of your datetime (seconds, milliseconds, nanoseconds...)... again, specifying 2021-01-10 to 2021-01-11 makes more sense than using 2021-01-10T23:59:59.999 for the upper boundary.
This breaks down for negatives, though. -9.9999..0 would be -10 < x <= 0.
-10 <= x < 0
This excludes the end of the range, it includes the start of the range. What's changed is that the start of the range is no longer at zero and also has crossed from positive to negative.
But your example is just the case for using 0 <= x < 10 in that _particular_ case. However, if I want all numbers greater than zero and up to and including 10, I'd write 0 < x <= 10.
So I fail to see your point. Do you argue that if we had to choose just one of these expressions, 0 <= x < 10 would have more utility? I don't know how to evaluate this conjecture, but suppose it's right. Why would you need to limit yourself to just one, though? Why not to use one that is most suitable to the problem you are dealing with?
Using strict inequality for the lower bound means you can't express sequences starting at 0 without expressing your lower bound as a negative number, which is ugly. So he prefers non-strict inequality for the lower bound.
Using non-strict inequality for the upper bound causes a similar problem. Consider the sequences (non-strict inequality on both sides) [0..2], [0..1], [0..0]. The first has three elements, the second two elements, the third one element. If you want to express a sequence with no elements starting at 0, that is impossible without using a negative number for the upper bound ([0..-1]). So he excludes using non-strict inequality for upper bounds.
What we're left with is non-strict inequality for the lower bound and strict inequality for the upper bound. This way we never have to leave the set of natural numbers to express natural number sequences, and as an added bonus, the difference between our bounds is equal to the length of the sequence.
Note that this part of the argument doesn't touch on 0 vs 1 yet, that is argued later in the essay.
- [0] https://news.ycombinator.com/item?id=25829966
Zero indexing might look weird at first but I think it helps in most cases.
Though ok, reading an array backwards requires a len-1-i
And when you need the number of the last element, you need to do A[n-1], which is "less helpful", I guess.
Yeah, maybe there's no fundamental advantage, one would have to check the most common cases.
> Why would you need to "wrap around" an array?
Ring buffers
Okay, maybe don't use that one in production :)
Though yes, adding or subtracting one is a minor thing
Also often abstractions (and their quirkiness) make way more sense when you understand what is being abstracted.
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.
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
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.
Higher level general purpose programming languages exist primarily to serve as an abstraction over the fundamental architecture of computers. C is technically a higher level language than machine code and assembly code, both of which use the 'lowest address is zero' abstraction. Every other abstraction, including C exists over top of that.
My point is mostly, if you're trying to remain relatively close to abstracting over general computing keeping arrays and their index based on what they are fundamentally abstracting over makes sense.
In domain specific applications, it may make less sense.
That's just another convention, though…
It is, but it's a widely accepted convention that underlies how computers fundamentally work.
The use of 0 as the basis means that, in mathematical language, the indexing is homogeneous and that conversion between different units is a linear map.
Imagine if we have tape measure that measures both meters and centimeters. Imagine that the first tick on the tape measure, representing no displacement, is simultaneously labeled "1 cm" and "1 m" instead of 0.
Now, we no longer have a linear map to convert between cm and m. What we have is an affine map, like m = 1 + (cm - 1)/100.
An affine map is a strictly inferior alternative when we have the freedom to establish a linear map.
Homogeneous/linear is the superior default. One-based can be used in the special cases where it is nicer.
Here is one example: binary heaps. When we store a binary tree structure into a heap array, 1 based indexing makes the calculations nicer for navigating from parent to children or vice versa:
The children of every node [n] are [2n] and [2n + 1]. The parent of every node [n] is [n / 2] (floor-truncating division).Under 0 based, it's not as nice:
The children are now [2n+1] and [2n+2]. One extra addition is required in the case of the left child. Finding the parent requires a subtraction: [(n-1)/2].Another way to see the advantage of 1 based here is that every row of the tree starts with a power of : [1] [2] [4] ...
Because we are dealing with exponentiation, avoiding 0 helps: 0 is not a power of two, so to "boostrap" the exponentiation, we have to displace it.
Note that even though it is nice for a binary heap to use 1 based indexing, we still want to store that in an zero-based array, and just sacrifice the storage for the zero element.
If we use a zero based array, then the nice heap arithmetic we wrote in the source code will look nice in the object code, due to the map from the source code array to the object code array being a linear map, rather than an affine map.
It is almost always better to simulate a 1 based array by sacrificing a storage element, than to have the compiler uglify the beautiful indexing calculations for the sake of which we switched to 1 based in the first place.
In summary:
1. we should choose the representation which offers the most succinct indexing calculations for the given situation, and not for some emotional reasons like "children learn to count from 1 and non-programmers understand that best".
2. arrays should be zero-based to preserve the succinctness of the calculation through to the object code (linear map from source to object, not affine).
Yet this just isn't the limit of computers or programming languages. Consider Prolog or a Lisp. What meaningful abstraction do they provide to have a deep connection with a block of contiguous memory used to store multiple same-sized elements? I'm sure you'll find such things ultimately used if you go deep enough, but it's not a meaningful part of the abstraction the languages provide.
And if we can do away with the entire concept of a set of same-sized data stuffed into a contiguous block of memory, what need can there be to adhering to considering indexes as memory offsets?
The incredible amount of (possible) separation between programming languages and the exact way in which such programs are executed provides an extremely valuable and deep freedom in how programmers can think about and address problems and their solutions. I don't see how insisting that we minimize any possible differences between language abstractions and common hardware practice gains us anything.
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.
The fact that a weird situation you set up intentionally needs special-purpose handling doesn't seem odd or unreasonable to me.
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.
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...
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.
I never liked that feature, it has chance to hide bugs in more complicated code where indexes are calculated...
I'd prefer a 'reverse' indexer instead.
You can't even create an array/list in python w/o a hard 0 reference.
More precisely, I'm defining the "base" to be the right hand side of the array and operating on the reversed list -- it's just a change of variables. Python supports -1 based indexing, but does not support 1 based indexing. You could easily define a language which only provides the -1 based indexing but does not support 0-based. Let me demonstrate:
Memory allocated through malloc_r is right-aligned and you should only use negative indices. Best not touch m[0]!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.
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.
Think about vectorization and loop unrolling. It _always_ does a memory load with an offset as a single CPU instruction.
As an example a 4 times unrolled sum of doubles on AVX looks like this:
The `rcx + 8*rsi + 32` stuff is offsets the compiler generates. Don't even think about worrying about -1 here...Don't be snarky.
I mentioned it's theoretically possible and outlined the specific conditions for optimizations to happen.
But I also mentioned that in reality various things often prevent compilers (assuming it's a compiled language, and not interpreted, like that LUA implementation) from applying such optimizations:
- you're programming against an API or are compiling an API (i.e. non-static functions).
- you have time-constraints for emitting optimized code, like most JITs - you can't afford any deep analysis that would enable such optimizations, you're mostly pattern-matching for lower hanging fruits.
Since pictures say more than a thousand words, here's the actual disassembly of that lua function I linked earlier, as shipped by my Linux distribution: https://i.imgur.com/DnqVC8E.png
The green stuff is the "fast path". For 0-based indexing you would completely drop the first LEA and replace those last MOV/SHL/LEA with a (faster?) MOV r,r/SHL/ADD r,m - which is what GCC is likely to generate.
So that's Lua (one implementation at least) in practice. No compiler magic making arrays fast here.
LuaJIT (from my current reading) goes the different route of just pretending the first array element doesn't exist, meaning that in memory they have an element '0', but they simply don't use it. This trades some memory for speed.
From lj_tab.c:
Personally I quite like this approach. A lot better than hoping compilers will magically fix everything and quite hard to argue with, considering LuaJIT's performance. Though it would be a ludicrous design for a lower-level language.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".
Circular buffers?
Hash tables matter more though.
Modulus (division) is slow and the length should be pow2 and the operation "& (len-1)". If you do %len, you have far greater issues. I have pretty extensive experience writing hashmap/cyclic buffers and the like. If you have auto-grow structs (and you almost always want that), you want pow2 length arrays. e.g.
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.
I bet it's done a lot as a lot of data structures are implemented vid pow2 length arrays. It's just the people who write them are unaware.
Citation needed. Yes, the -1 appears in the source code. It might even appear in the intermediate representation. It'll even show up in the assembly for multidimensional arrays (but it'll all get folded into a single `mov` assembly for vectors).
But I dare you to actually demonstrate a performance difference. Compared to a memory access, a `dec` is free.
I don't want to spoil it, but the following picture of a how they stored a 3x3 tic-tac-toe board is a hint:
That's what I was thinking, too, but most of the time (even if the index is not static) the -1 can be eliminated by just modifying the address at which the array is assumed to start. That is,
compiles into an access at address Since the address of arr is statically known, arr - 1 is, too, and the address of "one before the first element" will be what's written as the base for the memory access.No, that's almost never the case – only when accessing a static array. Typically, that restricts it to static look-up tables and very simple embedded systems.
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.
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.
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.
for(i=N-1; i>=0; i--)
The alternative is to use the so-called goes-to operator: for (i=N; i --> 0;). But this actually relies on the postincrement semantics, which is a huge wart.
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.
Semicolons vs. indentation structure (like in Haskell) has a huge usability difference in interactive shell. It's trivial on editor code.
The dismissal of syntax as trivial is not a good line of thinking. Syntax tends to have surprising impacts on semantics.
So, there's nothing wrong with challenging common norms - remember NULL? XML oriented programming?
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 ;)
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.
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.
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.
The first second of your day is an interval between the moment your clock shows 00:00:00 and the moment it shows 00:00:01.
If 00:00:00 is the fist second, why it's not the first minute and not the first hour? Is the fist second is the same as the first minute and the first second?
Not in every part in the world. Here in France, we use 24h time, and midnight is 00:00. Very convenient.
Same :00 start happens with minutes on 12h though of course.
I think GP didn't mean to talk about time, has a point regarding months as I replied elsewhere. We represent the months numerically as 1-12, and I have recently found that annoying to work with.
No?
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.
(For a moment I hoped your explanation would at least serve as a heuristics... but alas, it does not make sense to me. Well, at least at the moment I remember the notation).
Regardless of it, "12:00 AM of Jan 1, 2000" is not a particular second. It's a point in time, it has no duration.
It does not belong to any particular calendar hour or day or year, it's a _boundary_ between two.
Of course it belongs to XX century since XXI century starts at 12:00 AM of Jan 1, 2001.
The first second of Jan 1 lasts from 12:00::00 AM to 12:00:01 AM.
First minute of that day lasts from 12:00 AM to 12:01 AM. Etc.
At least this is how I parse it.
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?).
When counting apples (i.e. only +) then 1 based. but when (* % ^ √ ÷) then 0 based
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.
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.
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.
The number of times either of these properties has mattered for me also cannot be represented in the domain of 1-based indexes.
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.
But if you do anything more advanced with arrays, then you will start to notice the difference.
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.
"There is a smallest natural number. Exclusion of the lower bound —as in b) and d)— forces for a subsequence starting at the smallest natural number the lower bound as mentioned into the realm of the unnatural numbers. That is ugly, so for the lower bound we prefer the ≤ as in a) and c). 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. That is ugly, so for the upper bound we prefer < as in a) and d). We conclude that convention a) is to be preferred."
I mean... that doesn't exactly settle it. Sure, your opinion might coincide with that, but this is not a logical argument. First you're going to have to explain what unnatural numbers are (because they're not a thing as far as I can tell), and then you'll have to tell me what about them makes them "ugly", and how that makes the other option "preferable".
https://en.wikipedia.org/wiki/Natural_number
Dijkstra is saying the following.
Part 1:
Natural numbers have a least element X. (In fact, any subset of them does. This is called the well-ordering principle.)
Part 2:
Suppose lower bounds are exclusive. Then the lower bound L of any interval containing X must be less than X. Since X is the smallest natural number, L must be an unnatural (non-natural) number.
It is more convenient to stay in the naturals.
Therefore, it is more convenient to use inclusive lower bounds.
Part 3:
Suppose upper bounds are inclusive. Then, to represent an empty interval, the upper bound must be less than the lower bound. (If it were equal to the lower bound, we would get a singleton interval, not an empty interval).
It is already strange that we need an upper bound that is less than the lower bound. But there's more: When the lower bound is X, this would again take us out of naturals.
Therefore, it is more convenient to use exclusive upper bounds.
Conclusion:
It is more convenient to use inclusive lower bounds and exclusive upper bounds, i.e. convention (a).
This argument is basically airtight.
"It is more convenient to stay in the naturals."
Right here, you do the same thing Dijkstra does. You declare that one way is more "convenient" than the other (he calls it ugly), without defining what "convenient" means. This makes the argument subjective. What you think is convenient, others may not think so. Or, one may agree with you on a matter of convenience, but would prefer a different choice due to some other priority e.g. learnability.
So I just don't agree this is an airtight argument. It's a subjective argument for a preference at best.
Nope.
1. Some things are objectively more convenient than others.
2. I've explained exactly what I mean. And so did Dijkstra.
Since you apparently don't want to use natural numbers for indices, what do you want to use?
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.
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.
Now, despite the utility of half-open intervals, most people’s intuition is around ordinal index ranges, so 0-based indexing is counterintuitive with half-open intervals because slices start at 0, and 1-based indexing is counterintuitive with them because they end at N+1.
This is because, useful or not, half-open intervals are counterintuitive, but they are worth developing the intuition for because they combine nicely.
Do you see +1 tweak? Also consider that "for loop" can't be expressed as </* interval and always expressed as <=/* interval. So 1-based indexing have to be either 1 <= i <= N (closed interval, bad, N - 1 != number of iterations) or 1 <= i < N + 1 (half open interval, good, but +1 tweak).
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:
But that's only slightly nicer. To translate this into 1-based indexing and closed-closed intervals, you'd just substitute the `# operate` line with the `[0,iters)` with `[1:iters]`, and `i < rem` with `i <= rem`.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.)
For the most part, my preference on 1 vs 0 is weak, and for coffee other people are likely to look at i do want to make it easy to understand / not full of surprises.
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...
Open/closed intervals only come into play in continuous dimensions. DNA sequences, arrays in memory, et al are discrete.
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.
Or the predecessor of the last element: array[array.length - 2] makes you think, whereas array[array.length - 1] is more obvious.
Or another way: Is this more reasonable than, say, implicitly taking indices mod len(list)? How about implicitly flooring indices? If so, why?
> implicitly taking indices mod len(list)?
Isn't this doing that (plus some bounds checking)? -1 mod 4 evaluates to 3.
> implicitly flooring indices?
Not sure I understand what this means.
I'm getting this right?
if you misscalculated something and went on negative, then you'd have big exception/error, but when negative indices are viable, then the code will work fine
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.
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.
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.
If you've worked with mathematical proofs before, you'll have experience with how they make proofs shorter and more elegant.
That's why they're natural base cases.
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".
Visually, it looks like ) has more "room" than ], if that makes sense, and that "closed" would mean that the element defines the 'lid' of the range, while "open" means it defines the final extent.
But you can't argue with nomenclature, and extending the definition to the reals helped make it click for me, so I'm unlikely to screw it up again. Thanks!
It sucks and is Stockholm syndrome.
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 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.