Again on 0-based vs. 1-based indexing
hisham.hm
hisham.hm
If anything, it is an artificial choice, because in programming it is derived from a property of most, probably of all, human languages that have ordinal numerals.
In most, probably in all, human languages the ordinal numerals are derived from the cardinal numerals through the intermediate of the counting sequence 1, 2, 3, ...
When cardinal numbers appeared, their initial use was only to communicate how many elements are in a set, which was established by counting 1, 2, 3, ...
Later people realized that they can refer to an element of a sequence by using the number reached at that element when counting the elements of the sequence, so the ordinal numerals appeared, being derived from the cardinals by applying some modifier.
So any discussion about whether 1 is more natural than 0 as the starting index goes back to whether 1 is more natural as the starting point of the counting sequence.
All human languages have words for expressing zero as the number of elements of a set, but the speakers of ancient languages did not consider 0 as a number, mainly because it was not obtained by counting.
There was no need to count the elements of an empty set, you just looked at it and it was obvious that the number was 0.
Counting with the traditional sequence can be interpreted as looking at the sequence in front of you, pointing at the right of an element and saying how many elements are at the left of your hand, then moving your hand one position to the right.
It is equally possible to count by looking at the sequence in front of you, pointing at the left of an element and saying how many elements are at the left of your hand, then moving your hand one position to the right.
In the second variant, the counting sequence becomes 0, 1, 2, 3, ...
The human languages do not use the second variant for 2 reasons, one reason is that zero was not perceived as having the same nature as the other cardinal numbers and the other reason is that the second variant has 1 extra step, which is not needed, because when looking at a set with 1 element, it is obvious that the number of elements is 1, without counting.
So neither 0 or 1 is a more "natural" choice for starting counting, but 1 is more economical when the counting is done by humans.
When the counting is done by machines, 0 as the starting point is slightly more economical, because it can be simpler to initialize all the bits or digits of an electronic or mechanical counter to the same value for 0, than initializing them to different values, for 1.
While 1 was a more economical choice for humans counting sheep, 0 is a choice that is always slightly simpler, both for hardware and software implementations and for programmers, who are less likely to do "off by one" errors when using 0-based indices, because many index-computing formulas, especially in multi-dimensional arrays, become a little simpler.
In conclusion, the choice between 0 and 1 never has anything to do with "naturalness", but it should always be based on efficiency and simplicity.
I prefer 0, even if I have programmed for many years in 1-based languages, like Fortran & Basic, before first using the 0-based C and the other languages influenced by it.
Seriously?
- "Hey Timmy, how many pens do you have on your desk?"
- "Let's count them! Zero, One, Two."
- "So how many is that?"
- "Well since I ended my counting sequence with 'two', it totally makes sense to announce that I have three pens."
So your Timmy has a bug in his loop code, which caused a premature exit :-)
He should have counted 0, 1, 2, 3. Like I have said, humans do not count like this, because there are 4 steps instead of 3 steps.
For humans, it is easier to have an "if" before the loop, selecting between the special case of an empty set and a non-empty set, whose elements must be counted.
Nonetheless, an electronic counter would have really counted 0, 1, 2, 3, unlike you.
> He should have counted 0, 1, 2, 3
Is that how _you_ count? You imagine some pointer going _between_ items, start at zero, and stop once you have nothing at the right of your pointer?
Or, little Timmy could also skip the "zero" part (because you know, he's not dumb nor blind, and sees that he has several pens on his desk), start at 1 while pointing _at_ the first pen, and count up to 3.
People who are interrupted while they are counting and who have to restart the counting later, frequently forget whether they have already counted the pointed object, or not.
Pointing between the objects avoids these errors.
When I was young, I also had the impression that counting from 1 is natural. When I first encountered 0-based languages, I was annoyed by them, especially because I knew how Fortran compilers are implemented and I was familiar with all the tricks that are used by compilers to minimize the extra operations that are required to work with 1-based arrays.
So my initial naive thought was that maybe the implementers of C were not competent enough. However, after many extra years of experience, I believe that all the tricks for the efficient implementation of 1-based arrays are not worthwhile, because even for programmers it is more efficient to think using 0-based indices.
So now I really consider 0, 1, 2, 3 ... as a more "natural" counting sequence, unlike when I was a child.
With memory slots is the pointer in between or at a slot?
Should pages in books also start at 0? If you are saying show me page 4 should you look between 3 and 4?
What if there is no leftmost item? Because you skipped the first step, essentially assuming that there was at least one item and including it in your initial condition, that process fails when the set of objects to be counted is empty. Humans are good at dealing with special cases like this; they'll notice the discrepancy and report "zero" instead of following through with the predetermined process. Computers, not so much. So instead we start with a count of zero and all items in the as-yet-uncounted set as our initial condition, and increment the count by one as we move each item from the "uncounted" set to the "counted" set, which correctly handles the case of the empty set.
Anyway, to handle the exception, you could start the algorithm with a "check for the empty collection" base case; that would make it a natural definition for a computational recursive definition as well.
The brain is very good at finding patterns for special cases and very bad at following repetitive orders.
Here are two processes Timmy could use to count the pens on his desk. (I have numbered them starting with 1, because I considerately adapt to the needs of my audience :-).)
1. Say "0". Then increment for each object. So he goes: zero, (points to pen) one, (points to pen) two, (points to pen) three.
The advantage of this is that you don't need a special case when the number of pens turns out to be zero. Hey, Timmy, how many unicorns on your desk? Timmy starts by saying "zero", looks around, no unicorns, finished: it's the same process as for pens, it just stopped earlier.
2. Number the objects from 0, and then the count is the next number after the ones you listed. So he goes: (points to pen) zero, (points to pen) one, (points to pen) two, so the number is three.
This corresponds more closely to how indexing works in computers, and matches up nicely with the so-called von Neumann construction in mathematics, but in other ways I find it less natural than #1. But I am confident that you could teach it to children, and they would find it natural, and think it weird to mix up "the number of objects" with "the number of the last object". In this case, the only thing that changes from your dialogue is that Timmy says "Well, since the next number is three, it totally makes sense to announce that I have three pens." You count the pens, then you say how many there are. Zero, one, two, three. Not zero, one, two, two as you would prefer. What are you, some kind of weirdo or something? :-)
Answer: none
As far as efficiency, this should be the task of the compiler. We shouldn't have to start counting with the "zeroth" just to save the compiler a few cycles (or a few mental cycles to whomever writes the compiler/interpreter). That's why we don't program in assembly after all.
But I agree with GP, we shouldn't start counting from 1 either, but from "1st". Keeping ordinal separate from cardinals would be closest to how natural language works and I bet it would eliminate all kind of errors and gotchas.
The unintuitive step is apparently identifying the index with the cardinality of the collection from before the item arrives, not after it arrives – i.e. ‘the n-th element is the one that arrived after I had n elements’, not ‘the n-th element is the one such that I had n elements after it arrived’. The former identification results in 0-based ordinals, the latter leads to 1-based ordinals – and to some misconceptions about infinity, such as imagining an element ‘at index infinity’ in an infinite list, where no such need to exist.
Closed and right-open intervals in Ruby:
(1..12).to_a
#=> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
(1...13).to_a
#=> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12] |-1..12-|.to_a ## e.g. months in a year
#=> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
/1..\13.to_a ## e.g. hours from 1h (1AM) to 13h (1PM)
#=> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
for i in range(len) # 0, 1, ..., len - 1which is why switching between rust and nim is a real pain in the buttox
1..12 = [1,12]
And I think that last example demonstrates why the closed range notation makes a lot of sense over half-open (at least for languages that permit describing ranges of arbitrary discrete types). When talking about numbers a half-open range notation is clear and useful because numbers exist in an obvious sequence (so long as we're sticking to some subset of the real numbers, complex numbers don't have as obvious an ordering). But when talking about other ranges, like characters, how would you use a half-open range (in a clear way) to describe the characters a-z? 'a'..'{'? Is that actually clear?
What about describing the range when you want to include the last valid value? How do I describe, using the byte type itself, a range 0 through 255:
type Byte is mod 256;
subtype Full_Range is Byte range 0..255; -- valid Ada, closed range notation
subtype Full_Range is Byte range 0..256; -- invalid Ada, half-open notation
subtype Characters_After_And_Including_Lower_A is Character range 'a'..???;
-- presumably we'd have a better name in a real application
subtype Characters_After_And_Including_Lower_A is Character range 'a'..;
Character range 'a' ...; -- perhaps?Any language that makes use of mutation for primitive constructs (not saying that's the case here specifically) needs an understanding of "observing/causing change" pretty early on.
One counter-example is Mathematica. I can mutate any object any time I like, and doing so is extremely common. Yet under "pointer" its help tells me about some unicode symbols, and some GUI stuff about mouse pointers.
In reality, some of its lists are dense memory like C, some contain arbitrary objects (such as expressions, or high-precision numbers), but these implementation details aren't part of the language, and most users never know them.
In Mathematica's case (and most other languages, sadly), presumably the concept of 'variable' is overloaded with the semantics of a pointer/reference. Meaning, you cause and observe changes to locations via a variable.
0-based arrays are based on hardware implementations; 1-based arrays are based on abstract collections; you could make the argument that 0-based arrays are a leaky abstraction, but the question then becomes: what abstraction? C explicitly tried not to abstract away the underlying hardware.
Surely the point of any language at all is to abstract away some details of the underlying hardware. Both for portability and to make things easier for human brains. How much you should abstract away obviously varies, based on what you're trying to do, and on how varied the hardware is.
And it depends on how much computation & memory you can give your compiler. One reason new languages can have nicer abstractions is that they don't have to compile on 1970s hardware.
Growing up with BASIC, I didn't have any understanding of pointers or how memory worked. PEEK and POKE, which I only saw used in other people's programs and examples, were black magic as far as I could tell. It wasn't until I learned C that I actually understood them but I still managed to write a whole lot of programs without ever using them.
To be a professional programmer I'd agree though. If you don't understand how pointers work, regardless of the language you're using, you're probably not good at your job.
It just makes a point opposite to the author's intent.
Thank you for pointing out my error.
You may not need to understand molecular differences, but knowing hows fats, proteins, and carbs work, along with how to substitute ingredients, and different theories of cooking all help to actually understand why you can cook until mysteriously things don't work the same as yesterday.
Of course, following a recipe in specific ideal circumstances works, as long as nothing changes.
And when beginners won't be beginners anymore they'l have to learn how the underlying abstractions work anyway. A programmer that doesn't at least superficially understand how operating systems work is not going to be able to write performant or secure software, let alome combine those qualities.
You don’t have to understand the low level details to be productive at the higher levels, you just have to understand the interfaces.
I've worked with programmers like that. They can glue a lot of things together, but when the slightest of problems appears, they are absolutely lost with how to debug. They usually resort to making pseudorandom changes until it "appears to work", and are also unable to appreciate just how fast computers are supposed to be.
The kind of understanding you're rooting for relies on formal logic, not electronics.
We're all dealing with abstractions over abstractions at this point, so it's really about finding what model of understanding works for the learner and then going from there.
I think we are on the track to create a perfect programmers factory.
Once someone understands (2), pointers are incredibly simple and obvious.
Math, as commonly encountered, is a collection of facts and relations. Their notion of variable is very different than in CS and programming.
To a mather (one who uses/does math), this makes sense:
x = 7 * y
y = 6
therefore x = 42
It makes sense to the mather because each statement exists at the same time. To the coder, each statement is realized over a period of time. To the coder "y = 6" hasn't happened yet when "x = 7 * y". This is the part that has to be communicated to the novice with a mathematical background.
If the OP was teaching people a language like Prolog then there wouldn't have been the same confusion.
x <= y;
y <= y * 20;
x' = y
y' = y * 20
x_n = y_{n-1}
y_n = y_{n-1} * 20
x, y = y, y * 20
(psetf x y
y (* y 20))
Spreadsheets, expression-rewriting languages or any other functional programming language don't necessarily have this limitation, and declarations can be made in any order if the compiler supports it.
Mutability is really a result of the fact that computers are physical machines. So I think if you're going to teach software development, you should really start at the machine architecture and build up (ala NAND to Tetris) or start with an immutable-by-default language and only dip into mutation as an "advanced" concept, only to be used by experts and definitely not by beginners.
I endorse the second way, as I've seen it work very well, whereas I've seen more than one ship crash on the shore of understanding pointers...
Of course, my N is small.
x = f0()
x = f1(x)
All he needed was to be informed that this could be equivalently represented as
x = f0()
y = f1(x)
x = f1(f0())you can just show them a ruler and ask them where does the first centimeter starts
The first centimeter starts at 0.
The first array element starts at 0.
(Also please note that both this and my previous reply are tongue-in-cheek).
"First" is an abbreviated form of "foremost". So if you start counting at 0, "first" corresponds to index 0. There's no real clash here yet; "first" and "one" are entirely separate terms.
"Second" is from Latin "secundus" meaning "following"; the second thing follows the first. So "second" corresponds to index 1. Again, no clash yet; "second" and "two" are basically unrelated.
"Third", though, actually derives from "three". So "third" has to correspond to index 3.
This leaves a gap, which might perhaps be filled by a new word "twifth", corresponding to index 2.
So now we have the cardinal numbers: zero, one, two, three. And the corresponding ordinals: first, second, twifth, third.
> you can just show them a ruler and > ask them where does the first centimeter start(s)
The question involves a nuance of the english language, the distinction between a measure of wholeness and the contents of that unit.
Length is a count of the completeness of a measure. The length of an interval must inherently include 0 as a unit to describe taking no units.
A 0 starting index is likewise also required to indicate skipping no storage cells.
Therefore an absolute index start must be zero based, and the Addition of duration must also include the option of zero as a means of describing a point at which to begin, but having not yet used any length.
The subtle trick is that is a point, an array of zero size; this is why the length, or alternately absolute stop point, for an array storing anything is one higher. It isn't actually zero indexed, it's a different property of measure (the size or stopping address).
A centimeter is also a wonderful example since it should graphically contain eight additional ticks for millimeter marks, and naught else, among it's inner span. This aligns wonderfully with explaining that there are targets spots for 8 bits of an octet within that single byte of indexed storage.
Though i do appreciate Fahrenheit for how it scales with humans. 0 is really damn cold, 100 is really damn hot, while in Celcius 0 is kinda chilly and 100 is instant death.
It's actually supposed to be the body temperature. Due to imprecise measurements, it's actually having a light fever. Flip note: C scales the same - 0 is the water freezing point, and then you have the same scaling as F but in 5s instead of 10s. [and you gotta remember: (f-2pow5)*5/9].
That's an old debate, yet if you are born/used to C, F is pretty horrific.
FWIW I started with K&R, but times have changed and I definitely don't think it's a pedagogically sound way of teaching programming.
It never worked very well in practice. I expect that when you're fortunate enough to have unusually able teachers teaching unusually able pupils it might do OK -- but then, in that situation, anything will do OK.
(Tom Lehrer fans will know about this from his song "New Math", with "It's so simple, so very simple, that only a child can do it" in the refrain.)
I certainly had unusually able teachers.
Incidentally, that book has been praised for making computation easy to understand for non-programmers, which I would consider to be evidence for starting out low-level.
but times have changed
Not for the better, if you look at the average state of software today --- and I think a lot of it can be explained by the general lack of low-level knowledge.
Instead of just graduating 50 people who "get the trade", we're now diluting them with another 350 that "made the grade". Then tech firms need wild, crazy interview processes to sort them back out. Everybody suffers, including the 350 who may have been productive and happy in another, more suitable profession.
It's less about gatekeeping, and more about sustaining a healthy industry that is quickly headed for a disastrous race to the bottom. Google and friends are spending billions under the magnanimous "bringing coding to everyone" when they really just want to lower developer salaries. Not everyone needs to learn how to code, just like not everyone needs to be a doctor, or learn how to be a carpenter. I constantly wonder when will be the right time to "get out" before salaries start their inevitable side downwards. Could be a couple decades though.
The idea is that if the hard stuff comes too late, people might not find out that they aren't really suited to that field as a career until it is too late to change majors without having to take an extra year or two of college.
The intro class is too early for that, though, because CS is useful enough for other fields that many people (perhaps even a majority of people) taking intro CS don't intended to actually go into CS. Better is to put it in the first class in a field that will mostly only be taken by people who are intending to go into that field.
Just like DRM, make it a little harder to skate on by and you actually filter a lot of casual/non-serious people.
Unfortunately teaching languages that are good for learning, like Scheme or Pascal, went out of fashion a long time ago. For years now universities have been teaching marketable languages. Ten years ago that was Java. Now it's Python.
All of them.
Also trampolines. Kids love trampolines. From there it's a simple jump (pun intended) to something like the Y-combinator!
I am doing my best in teaching my kids this way but the world around has the wrong idea. We'll see how it goes...
We should be careful not let such easily observed facts inhibit our efforts to dumb down curriculum.
You can use the same mechanism (minutes:seconds) to explain the half-open ranges: does a range(0,30) mean from 0:00 to 30:00 or from 0:00 to 30:59? If the second half of the match starts at 30:00, does the first half really end at 30:00 or is it really 29:59:99...9?
For most basic concepts, there's always real-world examples to use so that the teaching doesn't have to be abstract.
English in general makes this distinction: "He is fewer than 6 years old" is simply a mistake, while "less than 6 years old" is fine. (I think some dialects use "fewer" less often, in general, but would be pretty surprised if any prefer it here.)
I know there are studies on how birth date affects future success in school (though IIRC I read in Gladwell, and I'm wary of accurate his read on things are), I wonder if that effect is compounded with this system?
Americans do this a lot too, except at a (pseudo) decade level, e.g. "are you a '90s kid?"
This brings up other ambiguities. A "90's kid" might have been born in the 80's.
You could say that the American school year is 0-based. Except instead of naming it zeroth grade, it is named kindergarten.
Other languages use a less confusing term for it: anniversaire (French) is just anniversary, verjaardag (Dutch) roughly means year-rollover-day, and cumpleaños (Spanish) signifies completion of another year.
late 14c., from Old English byrddæg, "anniversary or celebration of one's birth" (at first usually a king or saint); see birth (n.) + day. Meaning "day on which one is born" is from 1570s. Birthnight is attested from 1620s. https://www.etymonline.com/word/birthday#etymonline_v_27158
I once developed a shortcut notation to simplify reasoning about ranges differentiating between "point cero" and "interval between 0 to 1", to make off-by-one errors less likely, but in the end it was functionally equivalent to the popular open/closed interval notations.
/9..10\ : "short" interval : size 1 (hour) == half-open interval [9..10)
-|20..21|- : "long" interval : size 2 (days) == closed interval [20..21]Ultimately, it relies on conventions, but I guess now you can see how this one relies on something which has some consistent pattern.
those are the same number.
Well, 0-based is not what we use in everyday life, and even arriving at the invention of 0 took us several millenia, so I'd say its non-intuitiveness is pretty much established...
So they may say one hour old, five days old, six months old, etc. a fifty year old typically doesn’t say they are a half centenarian either. Now decades are used to express an age range like so and so is a nonagenarian to avoid being specific.
People never said and still dont' say "this baby is 0 years old". They start at the first complete item of the lower level time units and progress from there...
The ancient Greeks didn't think 1 was a number; as late as ~1500CE Isidore of Seville was saying "one is the seed of number but not number". After all, if there's only one thing you don't need to think of it as a set of things, so there's no counting to do.
(I think in some quarters it was even argued that two isn't a number, but I forget the details. Compare the fact that some languages treat pairs of things differently in their syntax from larger groups.)
But it turns out that mathematically it's a really good idea to count 1 as a number and allow sets of size 1, and these days everyone does it and no one is very confused by it. (Well, maybe by the "sets of size 1" thing. Exhibit A: Perl. Exhibit B: Matlab.) And because we're now all used to thinking of 1 as a number, it's hard even to understand how anyone might have found it unintuitive.
If we all started counting from zero and taught our children to do likewise, intuitions 50 years from now might be somewhat different from what they are now.
That's what it represents in indexing, the distance you have to travel to get to the element you want.
That's an offset. It's already covered in detail in TFA.
We don't deal with such offsets in programming, except in C pointer arithmetic (which infested this upon us).
How many more things can I fit in that box? How many comments are in that HN page?
I'd write more, but I'm running on empty and my pen is out of ink.
In some ways I think it's similar to the endianness debate: big endian looks natural at first glance, but when you see the expression for the total value, having the place value increase with the address just makes far more sense since it eliminates the extra length-dependent term and subtraction.
"Until" I'd think of as being the strict "to", except something about it feels off like it couldn't just be dropped in every place to/through can be used.
for x from 0 to 10 ;; closed, [0,10]
for y from 0 below 10 ;; (half-open, [0,10)
Then Scheme, once they feel straightjacketed with BASIC; it will teach them what abstraction is and how to break code into chunks. It should be a bit of a lightbulb moment. They also get a type system.
Finally, Julia, once they get sick of the parentheses and difficulty of building "real" programs (you'll do a lot of DIY FFI to use standard libraries in Scheme). From this they will also learn array programming and the idea of a type hierarchy.
The only trouble with this curriculum is the student will be completely ruined for ever programming in C or Java. They will not have learned to tolerate the requisite level of tedium, or even programming without a REPL.
I learned programming by myself when I was a teenager, and 0-indexed never was an issue.
We learn very early on as kids at school that there are 10 digit numbers, not 9. You learn to write 0 before any other characters. On every digit pad, such as phone dial, there is a "0".
If I ask you the list of digit numbers, 0 is the first element.
There is nothing counter-intuitive about that in my opinion, even for a kid.
If I grab JS/Java/Python/PHP, an array/list is a magic sequence of values with opaque under-the-hood operations, and my only interface to it is the item index. In that context, promoting idioms because they make mechanical sense in a language I'm not using doesn't seem compelling.
Maybe kids don't use rulers now? Just tell them that arrays are like rulers.
This has two nice properties. One is that two slices are adjacent if the beginning and ends match, and the other, far more important, is that the length of the slice is end - start.
That's the one that really gets us something. It means you can do relatively complex offset math, without having to think about when you need to add or subtract an additional 1 to get your result.
I use Lua every day, and work with abstract syntax trees. I mess this up all. the. time.
Of course you can use closed intervals and stick with 1-based indexing. But for why you shouldn't, I'm going to Appeal To Authority: read Djikstra, and follow up with these.
https://wiki.c2.com/?WhyNumberingShouldStartAtZero https://wiki.c2.com/?WhyNumberingShouldStartAtOne https://wiki.c2.com/?ZeroAndOneBasedIndexes
base is irrelevant to this, and you want (and show!) half-open, not closed, intervals.
> This has two nice properties. One is that two slices are adjacent if the beginning and ends match, and the other, far more important, is that the length of the slice is end - start.
Yeah, those are all properties of half-open intervals, irrespective of indexing base. It would be as true of π-based indexing as it is of 0-based.
for (i=lower;i<upper;i++) {}
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:
iters, rem = divrem(N, block_size)
start = 0
for i in [0,iters)
end = start + block_size + i < rem
# operate on [start, end)
start = end
end
# operate on [start+1, end]
1- vs 0-based indexing is bike-shedding. A simple question we can all have opinions on that's easy to argue about, when it really doesn't matter much.
Julia uses 1-based indexing, but its pointer arithmetic is (obviously) 0-based, because pointer arithmetic != indexing. Adding 0 still adds 0, and adding 1 and `unsafe_load`ing will give me a different value than if I didn't add anything at all. (This is just reemphasizing the final point made by the blog post.)
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.
The subscript on the coefficient then matches the power of x, letting you write the general term as ai x^i, which works out great when using capital sigma notation.
One the other hand, matrix rows and columns usually start from 1, so the elements on the top row are usually a11, a12, a13, ..., and the next row is a21, a22, a23, ..., and so on.
In an attempt to bring some unity to the two sides on this issue in programming, let me offer something that I'm sure everybody will be able to agree on.
Once upon a time I was implementing some mathematical code in C++. It was a mix of things from places where mathematicians would number from 0 and where they would number from 1.
I decided that the code would be clearer if the code looked like the formulas in the math papers they came from, which meant I wanted to use 0-based arrays in some places and 1-based in others.
Solution: I overloaded the () operator so that array(i) was a reference to array[i-1]. Then I could use 0-based or 1-based, depending on whether I was using a formula that came from a 0-based or 1-based area of mathematics.
Everybody agree that this was not a good idea?
julia> using Polynomials
julia> p = Polynomial([1, 0, 2])
Polynomial(1 + 2*x^2)
julia> p[0]
1
The remaining cases are by definition edge cases and warrant enough attention that bugs caused by 1- vs 0-based indexing doesn't seem to be a big problem in practice.
It's like with goto and structured programming - people stopped using goto for loops and ifs, so the remaining cases where goto is used as last resort aren't much of a problem. People think hard before doing this.
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.
Plus, the last bit is just "imagining a guy and getting angry at that guy", the absolutely dumbest form of argumentation.
Finally, someone who has never followed electoral politics or current affairs.
1. In this discussion, people often overlook that these numbers are applied to two different concepts: offsets and numbering.
2. If C had been designed with 0-based pointers (for offset calculation) and 1-based indices (for numbering the array elements) people would probably find this a strength, to have the most appropriate base for each case. It's an interesting what-if idea that I hadn't seen before.
I'm not sure about "multiply and add"... Aren't these instructions for computing with floating point numbers rather than offsets?
I don't think having pointers and indices behave differently is a good idea for the record.
They are languages primarily used for math and simulations and are pretty specialized so the indexing and representation of the vectors matches closer to how you would consider things if you were doing linear algebra by hand.
Julia, Matlab, and Fortran are also all column major for multi dimensional arrays too.
For numeric work ill take 1 index any day of the week, but for general programming or other CS work (like non vector/matrix data structures) i much prefer 0 indexing.
1. It is faster. Due to how memory works, 1-based languages need to subtract 1 internally every time you access an array[1].
2. It works mathematically better with some of the most common operations on array offsets, like modulo and division into round/ceil/floor. You'll be peppering your code with +1 or -1 around those a lot if you use 1-based indexing.
[1]: This is lua, for instance: https://github.com/lua/lua/blob/master/ltable.c#L702
I am not sure (1) is a very convincing argument. The subtraction of 1 internally is not necessarily gonna be there once the code gets compiled.
I will personally concede with you on (2), but it's still not very convincing considering that Fortran (a 1-index language) is still (arguably) the most popular language for linear algebra.
Personally, I feel "The Index Wars" are the same as the "Text Editor Wars": a matter for personal opinion.
Theoretically one can optimize it - though only when one can statically infer the index and the compiler decides to inline the array access function. If you can't do that, the best you can hope for is a fast CPU instruction like LEA or something.
In theory one could make a lot of things fast, in practice they rarely are, and it's always better to avoid problems now than to pray later.
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:
L64:
vaddpd ymm0, ymm0, ymmword ptr [rcx + 8*rsi]
vaddpd ymm1, ymm1, ymmword ptr [rcx + 8*rsi + 32]
vaddpd ymm2, ymm2, ymmword ptr [rcx + 8*rsi + 64]
vaddpd ymm3, ymm3, ymmword ptr [rcx + 8*rsi + 96]
add rsi, 16
cmp rdx, rsi
jne L64
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:
** 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).
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.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.
addLast(e)
elements[tail++] = e;
tail &= elements.length - 1;
if (tail == head) doubleCapacity();
} 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
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:
[ null, null, null, null, null, null,
null, X, 0, X, null, null,
null, null, O, X, X, null,
null, null, null, X, 0, 0 ]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]
(arr - 1) + x
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.
It really shows how conditioned the mankind is that they call the "0th" ordinal number by the name "first". We have never moved past the phase where the concept of "zero" was heretic.
Here + offset makes SO much sense. I think we should move to use it in other contexts too. "0 steps from the start of an ordered list" "1 step from the start of an ordered list" etc.
At the moment we are using two different "scales" for measuring things and labeling orders. We could as well use the letters "A", "B", "C" for the latter, and it wouldn't change a thing. Hindsight is 20/20, but it's just a confusing mishap that we are using "numbers" and "numbers + 1" for the two purposes, where the second one could be expressed just as another "measurement", and we could get rid of the confusing "numbers + 1" scale.
Even in maths it's pretty bad, because the Natural numbers still sometimes don't include 0, so that the 0th Natural number is 1, the 1th natural number is 2 etc. (using 1th instead of 1st to avoid the confusing nature of "first" in this discussion).
Well, every component of mankind was born. At birth your "first" year of life is the "0th" year. Right now, everyone is living its "n+1"th year of life (n >= 0).
I think the influence is strong, other than natural.
This is a left-over from mathematics where indices are distinct from the abelian group of integers.
So the index "1" as used to refer to vector element for example, is different from the number "1" on the number line. That is, one is an element of an index set comprised of ordinal numbers, while the other is an element of the integers.
The confusing part is, that both use the same symbol when in actuality they represent different concepts. The integer "1" is just a number like √2 or -7. The ordinal "1", however, is the representation of the concept "first".
The ordinal "0" would, if used as an index, always yield the empty set as a result (see von Neumann ordinals), which wouldn't be particularly useful in a programming language.
The mapping that selects elements given an index is arbitrary and can be defined as necessary. This allows for constructs like "x[-1]" mapping to the last element of an array. Here, "1" still means the "first" element, but the sign indicates the negative direction, i.e. start from last element.
In short: there's an argument to be made for having two distinct versions. One (1-based indexing) is consistent with mathematics, while the other (0-based indexing) is consistent with low-level low-level data representation and makes no distinction between ordinals and integers.
To put it this way: maths is the legacy codebase from hell; but it's what we have.
Joking, but I think there's always be a mismatch somewhere.
It really isn't. How many elements does a collection have, if it only has a 0th element? Is it 0? What about the size of a collection [0th, 1st, 2nd]? Or [0th .. 100th]? In language, we use 1-based indices for collections because we enumerate the elements based on counting them. A zeroth element doesn't exist, because if we had 0 elements, the collection would be empty.
Indexing of natural collections is based on cardinality, not ordinality.
You are exactly right. But does it make sense? I'm not sure. "if it only has a 0th element" isn't in my mind, a relevant question in the context of cardinality, since the answer is the same if it only has the "1th" or "2th" or "3th" element. (Sorry, picked up the habit of "misusing" "th" from another post in this thread.) The base case of indexing is "the start of the list" whereas the base case of cardinality is "empty collection". But should you define the concept of indexing by making an equivalence between cardinality and indexing by "cardinality of collection of elements from the start of a list to the current element (inclusive)" is, in my mind, something that doesn't _necessarily_ make sense.
I admit that it's awfully lot about choices and habits, but at least I find "unpacking" the arguments this way interesting and educational.
"...nowadays, all arguments that say that indexes should be 0-based are actually arguments that offsets are 0-based, indexes are offsets, therefore indexes should be 0-based. That’s a circular argument..."
Yes, that is a circular argument. It's not the one I would use. C made the decision that indexes and pointers are the same thing. It's a logical argument and one that's not circular. If they're separate things, then yes, you end up in a circle.
For languages that are not C-like, you could argue "pick an idiom and stick with it across multiple languages" or "make programming languages easier for humans to understand" Both of those arguments are preferential arguments. Perhaps there could be a study comparing the merits of each, but I haven't seen one yet.
I like chocolate ice cream. I like making pointers and arrays as similar as possible. I like being able to collapse pointer arithmetic down. I like doing huge mallocs and then playing around with large, empty hunks of memory. Some folks don't. I get it. Code should look like the way we think about the problem. That's an ideal state we'll never reach, but it's worthy of continued discussion.
You might dispute the premises, but I don’t see the circle. Isn’t this just “men are mortal, Socrates is a man, therefore Socrates is mortal”?
Edit: if I would make this argument, I'd say the assumption that indexes are offsets is baseless. This is easily proven since there are languages where this isn't true. However I would argue the problem based on practical merits: the reason there no 1-based index op-code exists is because no dominant programming language has 1-based indexing. Which is a self-fulfilling prophesy.
In general, I try to find the most general point and rebuttal as possible. These discussions tend to dive into pedantry and semantics. I'm just trying to do my part to engage the author where they are. ymmv
Seriously, the exact value of the lower bound for indexing doesn't matter here (some algorithms are best described with the lower bound other than 0 or 1, for example). The fixed or preferred lower bound is the real problem. Any argument for/against 0-based and 1-based indexing tends to gloss over the real problem because those arguments only exist to make some languages look better than other languages. As we move away from forced explicit indexing (e.g. arr.first() or foreach instead of arr[$LBOUND] or `for (i=$LBOUND; ...)`), it becomes clear that there is no such thing like the preferred lower bound for sequences at all.
This reminds me of my last company where the answer to the 2 vs 4 space debate was 3 spaces.
— Stan Kelly-Bootle
0-based indexing is here. 1-based has no benefit. New languages should use 0-based indexing.
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.
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.
Every language has its own design decisions based on some requirement or opinion, and while I have rather strong preferences about languages, these kind of design decisions doesn't strike any nerves.
As long as it's usable, that's fine by me.
My 2 cents: it isn't really that important. As long as the developer is aware of whether the language they are currently using 0 or 1 based indexing.
For a domain specific language focused around simulating physical things, or a specific application, 1-based indexing may be the more appropriate option. In this case, abstracting the problem domain is likely more important than adhering to the limitations of hardware.
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:
[1]
[2] [3]
[4][5] [6][7]
Under 0 based, it's not as nice:
[0]
[1] [2]
[3][4] [5][6]
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.
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.
On the other hand, I’ve made an observation about timelines in music production software, where bars are counted starting from 1. As you zoom out, only every 4th bar tends to be labeled, which creates this strange sequence: 1, 5, 9, 13, 17… I always found that incredibly hard to reason about, and perhaps it would have been a better idea to label the first bar as 0.
For instance, suppose you're doing a lot of date arithmetic, and you might include times. If I have a range:
[2005-05-05, 2007-07-07)
[2005-05-05, 2007-07-07) [2007-07-07, 2008-08-08)
[2005-05-15, 2007-07-17) [2007-07-17, 2008-08-18)
That's because you can find the beginning and end of a range without knowing how to subtract by one. If you later decide to add times, it will just work because, conceptually, you already handle every possible value in the range.
If you want to construct a series of ranges of floats, it's a bad idea to do [3.457, 6.799999], [6.8, 12.47699999]. If you use half-open intervals, it just works, without mucking with the end of the range.
This is the reason that "indices are offsets" is powerful: it's not circular reasoning, but a simplification because we're removing an unnecessary primitive (subtracct 1) that only reliably works with integers.
And to bring this back to integer offsets, even when you're working strictly with integers, you may want to conceptually work with rational numbers.
When you're working out your math for buffered IO, you need to map byte indices to chunk indices. You need to assign every byte written to a chunk.
In a 0-based world, your chunk offset is simply your byte offset / chunk length. Because there is no distinction between indices and offsets, it's a clean mapping between one offset scheme and the other.
It means you can work out on paper when a new chunk should be started, and then translate that into integer arithmetic. And your code directly reflects the math, rather than having to stick "- 1" and "+ 1" in here and there.
It's not unnatural, but it's not natural either. It's just that 1-based indexing aligns with natural language conventions better. It also matches with some math conventions for matrices and vectors, but those don't have to use 1-based indexing either to work. I learned linear algebra with abstract "index sets" (I), where I can be {1, 2, 3, .., n}, {x,y,z}, {0,1,2}, whatever.
Programming in 0-based indexing means way less +-1 adjustments on boundaries. Division/modulus also works way better with 0-based indexing, so flattening multi-dimensional arrays is more easily expressed too.
In the end it's just a convention, it shouldn't matter too much. My money is still on 0-based indexing, as it lends itself to less errors and cognitive load when you get used to it. I used both extensively.
Tangential: conventions that are more "natural" are usually not actually natural, but just align themselves to other conventions better. Of course it's always good if conventions align, but sometimes it's inconsequential. Also there are situations where we can't make all conventions align.
An other little pet-peeve of mine is people calling big-endian more natural than little-endian, where there are actually different competing conventions:
1. Usual way of printing memory content from lower address to higher address from left to right (think hexdump).
2. Usual way of writing down numbers from left to right from most significant digit to least significant digit.
3. Expressing the value of the number from the byte array elements (\sum_0^(width-1) byte[n] 256^n for little-endian, \sum_0^(width-1) byte[n] 256^(width-n-1) for big-endian)
Big-endian aligns better with the combination of 1 and 2. Little-endian aligns better with 3.
What about how Europeans index their building floors from 0?
I vaguely remember that the original minesweeper started counting time from 1, which is certainly odd. I could be wrong here though.
It's more complicated anyway, since there are many structures with intermediate floors below or slightly below the ground, and those are usually nominated specifically ("mezzanine", "demisol" , etc.).
Fun fact: the numbers are imported from Arabic in which they are originally meant to be read from right to left => little-endian
Another minor issue is that you can access one less element with a fixed size integer than when you do 0-based indexing. So for u8 you can only access 255 elements instead of 256 for instance.
The sign of the index can be determined without a comparison, usually simultaneously with one of the previous operations.
I have seen some difficult to debug issues caused by this when I used to work on game scripts.
Here are some examples: http://www.lua.org/pil/2.5.html and http://www.lua.org/pil/11.1.html
Packed Array[0..255] of Char
http://docwiki.embarcadero.com/RADStudio/Sydney/en/Structure...
Examples:
- var MyArray: array [1..100] of Char;
- packed array[Boolean, 1..10, TShoeSize] of Integer;
Dynamic arrays are indexed from zero.
Clojure
(range 1 10)
;=> (1 2 3 4 5 6 7 8 9)
C#
Enumerable.Range(1, 10).PrintAll();
1 2 3 4 5 6 7 8 9 10
Ruby
(1..10).each { |n| puts n }
#=> 1 2 3 4 5 6 7 8 9 10
Python
for i in range(1, 10):
print(i, end=', ')
=> 1 2 3 4 5 6 7 8 90-based indexing is inherently better for machines.
1-based indexing is inherently more natural for humans.
**
For a short stint I was running a (small) datacenter, and despite being an apologist for 1-indexed programming languages, I zero indexed EVERYTHING in the datacenter.
Let me just say, that was a huge mistake. Physical items are not offsets. Even though I was then working in a 0-indexed PL, The amount of contortion I had to do to remember zero indexing made the likelihood of errors higher (I did not make any that weren't quickly recoverable, but still).
Depends on what you are indexing. Time, for example, is very commonly represented as being 0-based by humans.
The number of times either of these properties has mattered for me also cannot be represented in the domain of 1-based indexes.
Of course, there are problems with this in a professional setting, such as how do you enforce uniformity across modules, and what happens if you copy code from one module that's Base 0 to one that's Base 1 and vice versa. But when I was first learning how to program, it was helpful to me to have a language that allowed for some choice.
In the meantime, 23 years of programming have led me to believe that index base 0 makes sense. For many applications it's moot, because we should be using higher level functions (like map and reduce) for processing lists. In every other application (such as working with data on a grid), dealing with offsets does make things easier.
Perhaps the convention is arbitrary. But, lots of industries have arbitrary conventions that we all agree on just to aid communication, and I disagree with the original author that the term "groupthink" applies in this situation.
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?
When counting apples (i.e. only +) then 1 based. but when (* % ^ √ ÷) then 0 based
- pointer offsets - the article seems to dismiss these, but they're used loads in systems/network/driver programming, which is a reasonable chunk of the most important programming
- conceptual offsets - e.g. time of day starts at zero, not one. We think in this way a lot, and it's useful.
To save yourself from headaches, I believe 0-based indexes are preferred in almost every modern language for the simple reason of optimization. I have no evidence to back this. NULL=Nothing=0 is a thing though.
In fact, much of the vehemence in favor of it seem to be more about programmer shibboleths, to make some people feel they are in a special 'in-the-know' club (certainly if the r/programmerhumour reddit is anything to go by).
All I can do for scientists is tell them the advantage of learning a programming language outweighs the weirdness.
It is pretty intuitive when thinking about natural numbers as steps along a path. Then, zero is the number that means "you are already there".
There is a reason that Fortran, which was designed for science and engineering, uses 1 based indexing: because it makes sense when counting things, as opposed to dealing with some internal arcana of a computer's memory model.
0 based array (python) : screen_pos = x + y * width
1 based (lua) : screen_pos = 1 + x + y * width
shrug
So 0 based seems to work a little better for arithmetic based array references. But really you'll never resolve this to perfection. Assembly language programmers are very unlikely appreciative of 1-based.
Its all about what you're comfortable with.
Those wanting pointers can imagine a base address added to each calculation. 1-based then needs a -1... which is then a strange thing to advocate for.
The problem is within the phrasing and its premise: Are you using an index or an offset? 99% of the time I think of an offset, so "first" makes sense as "0". If you go by indexing "1" suddenly makes sense as an index. When people say index in the context of arrays or data structures usually they mean an offset. To me it's simply wrong phrasing.
> I’ll brush aside quickly the fact that this is not true — 1-based indexing has a long history, all the way from Fortran, COBOL, Pascal, Ada, Smalltalk, etc. — and I’ll grant that the vast majority of popular languages in the industry nowadays are 0-based. So, let’s avoid the popularity contest and address the claim that 0-based indexing is “inherently better”, or worse, “more natural”.
Maybe I missed the comments about 1-indexing being "unnatural" but if the author is referring to the discussion I took part in, then this is a strawman. It wasn't about what was "natural" or "unnatural" but about people switching from their primary language to secondary languages and gotchas like 1-indexing being error prone.
We had a platform team at my last company looking to adopt Lua for client customization. The primary authors became familiar with Lua in writing the code logic but everyone else would be touching their part, or contributing back to the core, not as people familiar with Lua but as C++ developers who would be blindly making changes in another language. It felt similar to maintenance of our Perl scripts. You don't brush up and become an expert on a language you interact with on a yearly cadence. It is important in these cases to have few gotchas to make casual contributions easier and safer.
This says nothing about using 1-indexing when your target audience isn't 0-indexed programmers (speaking of those who choose to use Lua and not to Lua's creators).
Unfortunately, for me, even with my complaints (this and language compatibility), I'll probably still use Lua for some projects of mine. I've looked at others and I'm mainly concerned about the community size.
And if the API provides `second`, `third`, `antepenultimate`, `penultimate`, and `last` methods it covers a large part of what one most often use.
Past third rank, then I will feel better served with a `slice` method, whose documentation provides explicitly it’s index convention, whether it makes a modulo on out of bounds, etc.
If you use 1-based indexing, you can't iterate over a list of maximum length with a simple loop. The normal loop condition is `while i < len` (0 based) or `while i <= len` (1 based). If len is maximal, the second one probably has an overflow bug in the loop body that turns it into an infinite loop or a crash.
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.
Furthermore, mathematical notation is almost universally terrible. It's inconsistent, ambiguous, and has many undeclared dialects. Oh, and many people use 0-based index to boot, because, you know, whether that's conventional or convenient (largely orthogonal qualities alas in math) depends on the context.
I mean, I can sort of buy his argument that it's arbitrary, but then he also points out that there's at least one advantage to 0-based indexing, namely that works well in offset based scenarios (not just for pointers). So in which case is 1-based indexing convenient? Based on this blog post, never.
Also, the irony of complaining about HN holy wars becoming just another trigger to continue! I'll do my part - whichever side you are on - you are wrong.
For instance, even in slicing, [start:end) eliminates this issue. Though there is something to be said for verbosity.
I think this becomes an argument for 0 based indexing, but a case could be made to the opposite.
That said, consistency is what is valuable, so the only truly wrong answer would be the one we use in real life.
And then you have Japan which sometimes starts at 2F. Hey, maybe we should use 2-based indexing.
The worst is really when you switch between the languages, but after a while you get used to it.
You just need to watch out like a hawk, when calculating the index of the last element ;)
Numbers in programming start at 0, even in the languages with 1 indexing. Period. When I initialize an integer, unless I explicitly set a value, it’s 0.
From a purely pragmatic standpoint, making the first number an invalid location in a list just adds unnecessary complexity and increases the odds of off-by-one errors. On the same token, there’s nearly no benefit to starting at one.
I agree that BASIC is inconsistent, but there are many languages beyond Basic and its descendants...
I'm afraid your argument still sounds like "C does it, so it is right" mentality.
https://docs.microsoft.com/en-us/previous-versions/visualstu...
Personally, I am not so much interested in which way is more right, but which way is less likely to result in off-by-one and related errors, though I do not know how you could gather data on that, other for people beginning programming, and any difference might go away or even flip as programmers gain experience and move on to more difficult problems. (Of course, the most effective solution is to not use indexing at all, except where absolutely necessary.)
That's it, I'm switching to saying number 0 reason from now on. If you are talking about your number 1 reason, I will forever be wondering what your number 0 reason would be. I'll tell my wife tonight she is my number 0!
kernel: array[-3..3,-3..3] of real;
x := kernel[-3,-3];
Sometimes you want negative indices, e.g. when performing a convolution on an image with a kernel.
In English we do. For example, if you are nine years old, you are in your tenth year. If an array has ten elements, the last element is the tenth element, it is nine elements away from the beginning. We could do "int array[10]; array[10th] = x;" if we wanted to mirror that.
We could imagine a language that does the distinction, but I don't know what good it would do.
[0]: https://wyborcza.pl/AkcjeSpecjalne/7,160474,24501452,zaczyna...
When you start calculating offsets and transformations of coordinates, starting at 1 forces you to carry around extra additive constants everywhere.
It has been enough of an issue for me to seriously reconsider my stance on indexing
With one-based indexes zero would be a very natural invalid value as an index similar to a null pointer.
Pretty much any language I can think of inits primitives with all bits set to 0. So either, you accidentally forget to set your index vars to 1 and out-of-range it there, or accidentally forget to take away 1 when accessing the end of the array. Pick your poison
Also, ⎕IO can be set as a local variable of a function to limit the scope of the indexing origin, which made it convenient to simplify the code to implement certain algorithms.
https://lasvegassun.com/news/2016/nov/07/the-human-calculato...
For example why is the 1st of January the first day of the month/year, but your first birthday is when you turn one year old, i.e. when your first year of life finishes.
Or let me rephrase that in the interest of avoiding natural language bias.
The starting element being at index 0 feels as natural as 0 being the starting natural number.
0 1 2 3 4 5
v v v v v v
|---|---|---|---|---|---...
^ ^ ^ ^ ^ ^
1 2 3 4 5 6...Our time counting is 1-based. There is no zeroth second, zeroth minute, hour, day, month, year, or century. This actually makes it slightly harder in 0-based languages to work with time and dates.
Also, it might be an indication that 1-based system is somewhat more intuitive to non-programmers.
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?).
Midnight is not 01:01 AM.
Similar to the indexing question, this is only true for some cultures:
"East Asian age reckoning originated in China and continues in limited use there along with Japan and Vietnam, and is still common in Korea. People are born at the age of one..."
JavaScript will allow arr[-1] as an "individual" element, but it's internally an object and so iterating and hoping that -1 comes in order doesn't work.
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:
void *malloc_r(int size, int count) {
void *m = malloc(size, count+1;
m[count] = count;
return m+count;
}
void free_r(void *m) {
free(m - m[0]);
}
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.
arr[i]
*arr + (i + 1)This means that the 21st century started in the year 2001. Likewise, the current decade started under a month ago, not over a year ago. If you think the 21st century started in the year 2000, as do most people, then that implies that the first century either started in the year 1 B.C. (ugly) or was only 99 years long (not a century). People naturally (and incorrectly) default to zero-based indexing in this case!
I would go farther and make centuries zero-indexed too. It's far more natural to say that the Nth century is everything in the form Nxx than to say it's (N-1)xx. Every time I run across a numbered century I have to stop and think for a split second to calculate what years it covers. I got this wrong on several occasions in grade school and was marked down for it.
Zero-based indexing works naturally for grouping things. One-based indexing does not.
This, of course, doesn't matter much.