Why numbering should start at zero (1982)
cs.utexas.edu
cs.utexas.edu
Also, the recent rise in programming with multidimensional data invites the question of why matrix integer indices should include zero, which Dijkstra's essay doesn't address.
Likewise, the increasing use of real variables in software invites asking whether an elegant syntax for specifying integer ranges applies equally well when used for real ranges, since <= operators make less sense when constraining floats. Also not addressed.
for (Object &o : iter)
for (i = begin_iter; i < end_iter; i++)I'd agree with that for lots of domains. If you're dealing with indices often you're probably working at the wrong level of abstraction. Indices are just error prone in general even if you count from zero.
Yes, explicit indices are less common than they used to be due to iterator support in languages. However they are far from being obsolete. I've been recently going through a lot of code dealing with numerical calculations and there you see hardly any iterator use.
Also, MATLAB code, which uses 1-based indices, is an absolute pain to deal with compared to Python/numpy, for example.
In my case, it is very common that i-th element in an array is somehow related to say (x0 + i*dx). This fits naturally with 0-based indices.
With 1-based indices you tend to have (i-1) or (x0-dx) everywhere. It gets extremely annoying when people get clever and rearrange this -1 in equations. Then it is no longer clear what is there as a side effect of the indexing and what is perhaps some constant in the numerical method.
Could you explain this?
It's all about each language's default semantics -- what can and should be left unsaid, and how that expresses the language's model for array access, pointer de/referencing, and loop control.
For array indexing, the most accommodating syntax is to do what Fortran does: allow the programmer to explicitly specify each array index's closed array range. That may be the most user-tolerant and unambiguous model for arrays, but it doesn't work well if you also want the same syntax to dereference pointers, whose indices must start at 0. Thus array indices of pointer-based languages (always?) start at 0. But that annoys the hell out of folks who work extensively with arrays AND real numbers, where half-open 0-based integer index ranges compel clumsy semantics when iterating over their precious arrays. (Folks like me, BTW.)
I wish I could somehow hide the fact that Lua uses 1-based indexing by concealing them completely with iterators.
And yet here I am, programming in Lua with 1-based indices in tables and dealing with the logical inconsistencies of interfacing with application bindings that necessarily expose C-native structures using 0-based indexing.
Edit: Removed asterisks for multiplications, as they got interpreted as markup.
split [a, c[ into [a, b[ and [b, c[
vs.
split [a, c] into [a, b] and [b+e, c]
This betrays the complete lack of mathematical qualification evident in the rest of your comment. IEEE numbers don't even pretend to be the reals. The most that can be said for them is that they're two copies (positive and negative) of a very small subset of the nonnegative rationals, adjoined to a couple extra symbols (+inf, -inf, NaN), with really wonky operations to work around the obvious non-closure of the rational subsets under standard mathematical operations (let alone the approximations to transcendental functions). I think it's important to be extremely clear: this is not at all like the mathematical reals, not even a tiny little bit. The use of IEEE numbers in serious applications (Bitcoin, iiuc) is truly frightening. They should be considered "useful for computer graphics" (although I can't say whether modern gpus are using IEEE numbers; they're at least useful for software rendering) and nothing more.
I agree on the numbering but many people don't. He doesn't mention how nicely it works with the modulo operator, which is I think the most compelling reason. But having L[2] be the third index in an array is horribly counterintuitive and leads to countless mistakes. CS students when they begin do not like it, it is not natural. It is beaten into them by scary red error messages and instructors over months and years until they finally accept it.
At the same time, it's not actually all that common to index elements in loops these days - most languages have some kind of a for-each construct that hides indices (and some, like Python, only have such a construct).
But slices definitely are, yes.
Frankly, I find Dijkstra's writing horribly grating and irritating. The majority of his articles seem to be just him insulting things he doesn't like, another thing I find grating (for one thing, I can't think of anything he does like off the top of my head). He also seems to have a habit of passing his opinions off as fact.
But he is really smart, and often right, so while I can be annoyed by him, I can't actually ignore what he says, because it does matter.
it's been occasionally opined that the biggest issue Dijkstra had with computer science is that it often needed to be applied to computers.
It is practically impossible to teach good programming to
students that have had a prior exposure to BASIC: as
potential programmers they are mentally mutilated beyond
hope of regeneration.
The use of COBOL cripples the mind; its teaching should,
therefore, be regarded as a criminal offence.
APL is a mistake, carried through to perfection. It is the
language of the future for the programming techniques of
the past: it creates a new generation of coding bums.
The use of anthropomorphic terminology when dealing with
computing systems is a symptom of professional immaturity.
I think of the company advertising "Thought Processors" or
the college pretending that learning BASIC suffices or at
least helps, whereas the teaching of BASIC should be rated
as a criminal offence: it mutilates the mind beyond
recovery.
But I must leave you with a quote from Sir Alan Kay that I found on the Wikiquote page while I was researching this:
You probably know that arrogance, in computer science, is measured in nanodijkstras.
I think finding fault with this kind of opinion is a symptom of the modern concept of "taking offence". Ie nobody can express an opinion without also showing that they respect others' opinions. But that's not right. We don't have to respect each others' opinions if we think they are wrong. What we must do in a free society is respect their right to have, and express, a different opinion.
Dijkstra clearly thinks that teaching BASIC is damaging people's brains so he says that loudly and clearly with a touch of humour. Should he water it down to avoid offending people that like BASIC?
Firstly, he doesn't say that understanding COBOL and BASIC is a crime: he says that teaching COBOL and BASIC should be regarded as a crime. And he lays out why: he says that exposure to those languages causes some kind of mental damage, so he is likening the teaching of them to the intentional infliction of an injury. Clearly this is tongue-in-cheek - it is highly unreasonable to infer that he literally wanted the teaching of two programming languages added to the criminal code, because this is absurd on its face.
The intended takeaway is that there are habits of thought learned by use of BASIC or COBOL that are must be unlearned to think about programming problems in that way that Dijkstra recommends.
He puts this statement in a list of very serious statements, most of which are actually true, claiming:
Nearly all computing scientists I know well will
agree without hesitation to nearly all of them.
What it is about is how arrogant and absurd it is to say that learning BASIC causes brain damage. If people couldn't re-learn and develop new ideas, we wouldn't even have computers.
https://medium.com/@acidflask/this-guys-arrogance-takes-your...
Really, that's just a confusion caused by language and historical accidents.
There is nothing that inherently links "one" to "first", or "two" to "second"--it just so happens that for some weird reason, it's common in English to abbreviate "first" as "1st", "second" as "2nd", and so on.
But just as "A" is the first letter of the alphabet (and not, say, the Ast), "0" is the first cardinal number, and "first" is the first ordinal number.
And there is a very simple reason why zero is the correct default first array index: Zero is the neutral element of addition, and (sub)array indexing is an additive operation.
$10 says you don't have any children.
The historical "accident" is that we don't start with "zeroth". That's probably what you wanted to say but the reasoning tripped me up.
How can the "empty" placeholder value represent the presence of an item? It's just even more confusing than the existing situation.
"The first year of the third millennium begins at 2001/01/01 00:00:00"
Wouldn't this make much more sense:
"The zeroth year of the second millennium begins at 2000/00/00 00:00:00"
Uhm, no, just the opposite.
Hmm, no, not really. While definitions are, indeed, by definition arbitrary, different concepts are of different usefulness, and as such, definitions that use more useful concepts can reasonably be considered better definitions of given terms.
There is no such advantage in using the binary 000 to represent the first index, though, except in so far as it results from the binary 000 representing the neutral element of addition, which corresponds to the natural number 0. The latter is the part that's actually not arbitrary.
> there never is one for naming
Well, the whole point kindof is that it's not about naming, but about arithmetic. If you only want to name stuff, you can use strings and hash tables, or letters of the alphabet, or whatever other set of symbols that you can come up with, it's really to a large degree a matter of taste. But there is a distinctive feature of arrays vs. other collection data types: You can do arithmetic on its indices. And arithmetic with a number type that doesn't have a zero is braindead.
Zero indicates the absence of a value in our numbering system. If I have a single apple, I have 1 Apple, not 0 Apples. Thus if I have 1 element in an Array I have element[1], not element[0]. It is more natural for us to use numbers not by their cardinal position in a set, but by their inferred value... because they represent quantities.
I am one of those who feels the confusion around zero bounded indexes leads to countless issues because it is counter-intuitive to how we use numbers in real life. I agree it is beaten into developers that this is how is should be, but to me we would have been further ahead to let developers accept what comes intuitively.
So, you would say that "A" is not the first element of the alphabet or that "0" is not the first cardinal number?
> Zero indicates the absence of a value in our numbering system.
You are utterly confused. If I have an account balance of zero, that indicates an absence of a value? How is zero mathematically any different then +1000 or -1000 that justifies making it a special case?
> If I have a single apple, I have 1 Apple, not 0 Apples. Thus if I have 1 element in an Array I have element[1], not element[0].
You are mixing up ordinal and cardinal numbers.
> It is more natural for us to use numbers not by their cardinal position in a set, but by their inferred value... because they represent quantities.
There is no such thing as a "cardinal position", positions are ordinal, cardinality describes sizes.
> I am one of those who feels the confusion around zero bounded indexes leads to countless issues because it is counter-intuitive to how we use numbers in real life.
Nope, what leads to problems is that people don't understand the difference between cardinal and ordinal numbers. You cannot fix that by changing the first index, all that causes is a shift to different bugs. Including stuff like equating zero with the absence of a value.
(Disclaimer: I used to hate 1-based indexing, for reasons similar to what you are saying, but I'm brainwashed by R these days and now rather like it.)
Nope, size is equivalent to quantity in this context. But ordinals describe position in an order as opposed to size/quantity. If you want to connect them mathematically, you would usually map a scale to a quantity measure, where the first unit position on the scale is the zero-position, the second unit position is the one-position, and so on--so, a quantity of size three units reaches from the position 0 on the scale to the position 3 on the scale.
> (Disclaimer: I used to hate 1-based indexing, for reasons similar to what you are saying, but I'm brainwashed by R these days and now rather like it.)
Well, it doesn't matter unless you have to to arithmetic with the indices, you might as well label them with letters from the alphabet, so if you don't need that, it's simply a matter of getting used to it. But in general-purpose programming languages, array indices are often computed, and 1-based indexing is as sensible there are having an integer type that doesn't have a zero. It's not that you cannot work with it, but it makes things unnecessarily complicated.
Zero is actually always a special case in math, specially in algebra, the only number where division by it is not defined.
> Nope, what leads to problems is that people don't understand the difference between cardinal and ordinal numbers.
Actually, by Von Neumann definition of ordinals, ordinal 0 represents an empty set, thus it's equivalent of null, not single element set. So strictly mathematically speaking for non-empty sets we should use ordinals starting at 1.
But using zero-based indices is just a matter of convention, so lets not make a big philosophy out of it...
And what does any of this have to do with division?
> Actually, by Von Neumann definition of ordinals, ordinal 0 represents an empty set, thus it's equivalent of null, not single element set. So strictly mathematically speaking for non-empty sets we should use ordinals starting at 1.
So, strictly mathematically speaking, we should use "2 apples" to describe an apple within another apple, where both of those apples also contain nothing?
I'm sorry, but this just makes no sense whatsoever. What relevance does von Neumann's construction of the natural numbers have to this question? Especially so, given that the empty set, aka "0", is the first(!) von Neumann ordinal. We should use 1-based ordinals because von Neumann constructed 0-based ordinals, maybe?
> But using zero-based indices is just a matter of convention, so lets not make a big philosophy out of it...
No, it's not. You yourself stated that the algebraic/arithmetic behaviour of 0 is quite different from that of 1, so how do you suddenly come to the conclusion that it's merely a matter of convention?
Because in programming it is, it's just a number chosen by some languages to start enumerating from because it makes things easier in some real-life cases. In pascal you could set the arbitrary start and end index and it worked just as well. It's like arguing which is a more precise way to measure temperature, in fahrenheit or celsius scale...
> What relevance does von Neumann's construction of the natural numbers have to this question? Especially so, given that the empty set, aka "0", is the first(!) von Neumann ordinal. We should use 1-based ordinals because von Neumann constructed 0-based ordinals, maybe?
You talked of ordinal numbers, so I cited one of the definitions of ordinal numbers, the one from the set theory. The similar reasoning applies for other definitions as well. Ordinal number zero is always the ordinal of an empty set. We use null for that in programming. So the next one is a single element set and it has ordinal 1. So how from this you conclude that index 0 is "the correct way" to count non-empty sets? You completely ignore the empty array that way...
Nah, bad analogy. Let me suggest a better version: It's like arguing about whether degree Fahrenheit or Kelvin is a more useful default unit to use for physics calculations. What do you think?
It's not just a number that's used to start enumerating from, it's a set of numbers used to calculate with as well, and array indexing, as I mentioned, is an additive operation, and thus using a set of indices that's not a group, for lack of an identity element, is as sensible as doing most of your physics calculations in degree Fahrenheit.
> You talked of ordinal numbers, so I cited one of the definitions of ordinal numbers, the one from the set theory. The similar reasoning applies for other definitions as well. Ordinal number zero is always the ordinal of an empty set.
Exactly. And you realize that that is the first ordinal number, right? "First" means "the one without a predecessor", and the empty set, also represented as a zero in that context, is the element without a predecessor, and as such the first ordinal number of that construction. Now, what is your point?
> We use null for that in programming.
We use null to represent the first ordinal number? What kind of weird languages are you using?!?
> So the next one is a single element set and it has ordinal 1. So how from this you conclude that index 0 is "the correct way" to count non-empty sets? You completely ignore the empty array that way...
First of all, it seems like you are utterly confused about the relevance of von Neumann's constructions of ordinal numbers to how to index arrays. There is none. It's simply an exercise in finding an isomorphism between sets and "normal" numbers.
Also, no, I don't ignore the empty array. An empty array has no positions, therefore, there is no ordinal number that could refer to a position in an empty array. If you have an index pointing into an empty array, you are doing something wrong. You cannot point to the fifth element in a four-element array, you cannot point to the second element in a one-element array, and you cannot even point to the first element in a zero-element array.
If you want to be able to have a data structure that can represent an index into an array, or alternatively the absence of an index (for whatever reason--one reason might be because the array is empty), that's your problem, not the problem of the index type. Why should we reserve perfectly useful values of data types to represent stuff that's logically separate from the type? How about we reserve the value "2" in floating point values for cases where you want to store the word "honey" as a floating point value? That's just crazy. You can possibly use such sentinel values in your software for performance reasons or whatever, but limiting sensible use by the general public because you want to mix concerns?!?
The third element of the sub-array starting at the second element of an array is which element of the base array?
With zero-based indices, that is a perfectly normal additive operation: 1 + 2 = 3 --the element is to be found at index 3.
With one-based indices, you resurrect all the crazyness of algebra and arithmetics before the zero was invented, just because you want to use the zero for something else: 2 + 3 = 5 ... and the index is 4, obviously!
What's counter-intuitive to me is that we habitually call the second floor in a building the "first floor"!
The ridiculousness of that argument should be evidence enough that the fifth item is item 4.
Consider the physical world. Let's say you've got three fenceposts (of unit width) in a line standing before you, each separated by 0.5 fencepost-widths of space.
It makes sense to say "the first fencepost." That's the post can be found in the (0.0, 1.0) region of the fence.
But "fencepost 0" or "fencepost 1" are both ambiguous to me: neither 0 nor 1 is inside the region the first fencepost occupies, physically. The mapping isn't intuitive. Both of those numbers point to where the fencepost isn't: just past its ends. Depending on your mindset, you might want to refer to the fencepost either to the left or the right in the row of that imaginary separating line: either "the fencepost that was just completed" or "the fencepost that is about to start" in your visual stream. Even worse if you're from a culture that reads right-to-left.
In physical terms, if you wanted to give "the first fencepost" an address... it'd be fencepost 0.5! Likewise, "the second fencepost" would be fencepost 2.0, and "the third fencepost" would be fencepost 3.5. These numbers refer to the centers of each fencepost. You don't have to ask the question of which "direction you head" to find the fencepost from the address: when you're at the address, you "have" a fencepost. You just need to know the origin and axes of the fence and you can "go to" the fencepost.
Now, we could get fencepost addresses of 0.0, 1.0, 2.0, and so on, by following some indexing strategy like "the position of the left edge of the Nth fencepost, measuring only fencepost-widths and not space between fenceposts." This kind of offset-based indexing is "intuitive" when talking about memory addresses, because memory addresses are like an ideal fence: every post is 1.0 units wide, with no space in-between posts. (Also, you can't actually point to the centre of an atomic unit of memory; memory addresses are quantized such that the only place the "handle" of a memory address can be attached to the memory itself is the "left edge"—the beginning—of the memory.) Great for digital logic, but we just don't have anything like that in physical space.
In reality, when we want indexes, we explicitly label things with numbers from a monotonic sequence, and then either write down mappings from the center-of-measured-interval addresses of the physical world (e.g. GPS coordinates) to those labels, or, worse, binary-search our items for one with the right address-label, hoping the labels have stayed monotonically sorted since they were issued.
There are nearly no cases where there is a natural "element zero" that exists at zero in the physical world, to create that associative intuition (perhaps, people crossing a finish line in a race: the winner is certainly "person zero" in the photo.)
Which is good, because it means that you are not confused :-)
The confusion is the idea that there is an inherent link between "1" and "first" or "0" and "first", which there isn't, because one of them is a label, while the other is an ordinal number.
You need a definition of how to map one to the other, and as long as you don't have that, the labels do indeed remain ambiguous, which you correctly recognize.
Now, there is an argument to be made for why array indexing should use a definition that maps the first element to label 0, and that is, as I wrote, that array indexing is an additive operation.
As for how that connects to your fence example: What you necessarily need in addition if you want to model your fence with an array(!) is a definition that maps your fence posts' positions to ordinal numbers, which you then can map to array indices via the definition above. That exact mapping is necessarily arbitrary to a degree, and the only really important thing is that you are consistent.
But within the implementation, you are likely to encounter problems such as "find the third fencepost of the part of the fence that starts at the second fencepost". And that would be the fourth fencepost of the overall fence, not the fifth, or in indices: 1 + 2 = 3 vs. 2 + 3 != 4.
> There are nearly no cases where there is a natural "element zero" that exists at zero in the physical world
Well, nor is there a natural "element one" that exists "at one".
Right. I'm on the "no natural mapping" side as well, here, not with the "first = 1" people.
Actually, consider for a moment, a programming language that tried to avoid both of these mappings, at least in its programmer-facing syntax (it might compile down to one or the other mapping, but that's an implementation detail.) It might not be so bad!
Of course, you wouldn't be able to index arrays by a single ordinal number at all, instead being forced to do speak in terms of intervals:
letters = char{'A', 'B', 'C'}
letters[0ch .. 1ch] # => ['A']
letters[1ch .. 2ch] # => ['B']
pairs = short{'AB', 'CD', 'EF'}
pairs.slice(0sh .. 1sh) # => ['AB']
pairs[0sh .. 1sh] # => 'AB'
pairs[0ch .. 1ch] # => ['A'] or a type error, as the language author pleases
pairs[0sh .. 2sh] # => argument error
pairs.slice(0sh .. 2sh) # => ['AB', 'CD']
This seems kind of annoying to write. But, I swear, it feels so pleasant to read. Much moreso than any language I've used. It's not hard at all to "keep the logic in my head" when I read the above back.
['AB'], no? Or the letters without []?
> This seems kind of annoying to write. But, I swear, it feels so pleasant to read. Much moreso than any language I've used. It's not hard at all to "keep the logic in my head" when I read the above back.
Well, yeah, but you conveniently left out index arithmetic :-)
If it's only about hard-coded indices, it really doesn't matter, IMO, as long as it's consistent, and you could just use any ordered set of symbols for indexing, and let the compiler figure out the mapping to binary numbers and machine code that's functionally equivalent.
The interesting case is when you, as the programmer, want to do arithmetic with indices. Of course, you could have a separate number type for array indices, say. But there really is no way around making its algebraic behaviour isomorphic to 0-based indices, because 1-based arithmetic is hell, and if you do that, it's probably a good idea to use the established names such as "0" or "1" for the established concepts such as "neutral element of addition" or "neutral element of multiplication", in order to avoid confusion.
Without. The dyadic arr[range] operator would always return one (unwrapped) element, a bit like how SQL ORMs frequently have a Query#get_one method to match Query#get_all. `letters` was a char[], `pairs` was a short[], so you're grabbing a short by its interval-address (+0 shorts from origin, +1 shorts from origin).
(Or, to clarify if you were confused by the not-quite-C pseudocode, by 'AB' I meant the short 0x4142.)
> But there really is no way around making its algebraic behaviour isomorphic to 0-based indices
Oh, sure, it's "zero-based arithmetic" because we're still fundamentally dealing with offsets (and when you slice the array, you take offsets from the beginning of the slice, etc.)
I think it's just better—in some vague human-factors sense—to be forced to mention, in each indexing operation, both where the offset (position of hyperplane separating the element from its previous) and the offset+size (position of hyperplane separating the element from its successor) will land, so that you realize explicitly what two numbers those are in your program, as you write them.
Humans—especially beginner programmers—don't intuitively realize that array indexes are offsets. They just want to talk about cardinal-numbered positions, and find themselves unable to, so they guess at a mapping and make mistakes.†
This syntax sort of short-circuits that by giving them an indexing operation that doesn't ask them to decide on any cardinal:ordinal mapping at all. It just asks for two numbers that are clearly "offsets of the positions between array elements", rather than offsets (or counts) of elements.
But even for experienced programmers who understand that indexing operations are pointer offset math, such an indexing-by-continuous-slicing scheme is potentially still a bit helpful, somewhat like being asked to write out a deductive proof for a hand-wavy argument: it makes you aware of when you've made a leap of logic that has no rule allowing you to make it. Or, in this case, it makes you aware of what element you're actually capturing with your hand-wavy math.
> The interesting case is when you, as the programmer, want to do arithmetic with indices.
I think—and this I find even weirder to say than my first thought—that it might be good to restrict this "humane" indexing operation from containing compound expressions.
Instead of this:
foo[(a * 3 + 2)ch .. (a * 3 + 5)ch]
offset = a * 3 + 2
foo[(offset)ch .. (offset+1)ch]
pos = a * 3 + 2
foo[(pos)ch : 0ch..1ch]
---
† A tangent: "pointers are hard" for beginning programmers because C tries very hard to make array access, and even plain pointer math, "act like" reference-by-cardinal-rank, but then still uses zero-based offsets, munging up the ability to deduce a coherent semantics of pointers as memory-address-valued variables.
In C, when you add an (ordinal!) integer to a pointer, it multiplies that integer by the sizeof() the pointer's referent type because it wants you to model the pointer as being an iterator-handle for a collection of things, rather than just being a memory-address-valued variable. It makes sense, for practical reasons, that you can't create a short︎＊-typed variable containing a non-short-stride-aligned memory-address... but that should be a domain error on the result of the addition, not something you're mathematically unable to express.
Well, I'm not convinced, but who knows? My guess would be that it wouldn't really reduce mistakes much. People would simply memorize the rule that for a single element, you always have to give some index and then follow that by index + 1 --and if the index is computed incorrectly, the result is just the same wrong result as before. You cannot force people to prove that the offset is correct by forcing them to write down the expressions for two values that have to always differ by exactly 1.
> In C, when you add an (ordinal!) integer to a pointer, it multiplies that integer by the sizeof() the pointer's referent type because it wants you to model the pointer as being an iterator-handle for a collection of things, rather than just being a memory-address-valued variable. It makes sense, for practical reasons
Nah, I think that's perfectly sensible, even theoretically. A pointer is a perfectly sensible memory-address-valued variable, it's just that it's not in "machine code addresses", because that is an implementation detail, but rather in "abstract address space addresses", with a separate address space per object (by which I mean an allocated memory region), and obviously, with arithmetic in that abstract space counting in elements of that respective address space's type. Why would counting in bytes make any more sense? The size of a byte (or a char, rather) is mostly an arbitrary implementation detail that abstract code shouldn't be bothered with.
BTW, what you write is kindof wrong: As per the abstract definition of the language, nothing is being multiplied by sizeof()s. That tends to be how it's often implemented on the usual platforms, but the abstract definition simply says that arithmetic with pointers works in units of elements, and that consistently: If you subtract pointers, you get the number of elements between them, not the number of bytes/chars/octets/words/whatever between them, the internal value is not really visible anywhere, and could relate to the abstract value in arbitrarily complicated ways anyway (like, you could have pointers that are implemented with tags to differentiate pointers to different machine address spaces and stuff like that).
> that you can't create a short︎＊-typed variable containing a non-short-stride-aligned memory-address...
That's actually not the goal nor the case. Whether a pointer is aligned is an implementation detail, there is nothing in C that would require short objects to be aligned to short boundaries, and what implementations do simply depends on (a) whether the platform can handle non-aligned pointers, and (b) if it can, what makes sense as a matter of weighing performance vs. memory usage. I haven't checked it, but my guess would be that the AVR GCC, for example, does not align anything, because it only needs more memory and makes no difference whatsoever for performance (I think ... maybe I am forgetting something).
So, empty water bottles don't exist? Or do you object to saying "this bottle contains 0 ml of water"? Why? Or do you think that no water bottle is the same thing as a water bottle with no water in it?
> I have 1 car, not 0.
And what about someone who has no car? Are there no people who don't have cars? Or do you object to saying "this person has zero cars"? Why? Or do you think that no garage is the same as a garage with no car in it?
> If I had a lineup of cars, the first one would be 1, not 0.
No, it wouldn't. Unless you arbitrarily decided to label it as such. It would be the first. That's an ordinal number. Also, you would have 1 car. That's a cardinal number.
They exist conceptually, because a water bottle could be empty of anything that fits inside. We say it has 0 ml of water and not coke or sand because we've designated it to be a water bottle, but nature obviously doesn't care what goes in the bottle, as long as it fits. It's just a useful idea we have to say there is zero something to designate a lack of something. But there isn't zero water in nature, anymore than there are zero unicorns, or zero Kings of France.
>> And what about someone who has no car? Are there no people who don't have cars? Or do you object to saying "this person has zero cars"? Why? Or do you think that no garage is the same as a garage with no car in it? <<
Are there no people who don't have dinosaurs or time machines? The things we have zero of are infinite. But you don't actually have zero pink elephants in your backyard.
>> No, it wouldn't. Unless you arbitrarily decided to label it as such. It would be the first. That's an ordinal number. Also, you would have 1 car. That's a cardinal number.
So if we were to label to cars in increasing numeric order from one end to the other, we would start with 0 instead of 1 at the first car? We don't do that with building levels. You enter on the first floor, go to the elevator, and you push a button for the floor level. The first floor is 1. 0 Would be the basement level.
That's just confusion on your part. All of language is just a useful idea we have to designate whatever we designate with it, and you are just confusing things for no reason at all. You obviously understand what "zero something" means, and that what it means is indeed something that can describe aspects of reality, and then you go on and claim that somehow it doesn't. When I say "there are 0 ml of water in this bottle", you understand what it means, right? And if there is indeed no water in the bottle, what is there to be confused about? It does mean that there is no water in the bottle, but it also means something else at the same time? Or there is no water in the bottle, but there is also not no water in the bottle?
> The things we have zero of are infinite. But you don't actually have zero pink elephants in your backyard.
Yes, I actually have. "having zero <whatevers>" is, as you evidently know, a synonym for "having no <whatevers>" or "not having <whatevers>", and I absolutely certainly actually do not have pink elephants in my backyard.
> So if we were to label to cars in increasing numeric order from one end to the other, we would start with 0 instead of 1 at the first car?
There is no such thing as "we would start". You can start wherever you want. That is, as derefr has already explained to you, an exercise in assigning serial numbers. You can use whatever numbering scheme you like. Obviously. Some might be more useful than others, though.
> We don't do that with building levels. You enter on the first floor, go to the elevator, and you push a button for the floor level. The first floor is 1. 0 Would be the basement level.
Except you don't enter on the first floor. The "first" thing in any order is defined to be the thing without a predecessor. Obviously, if there is a basement, the ground floor is not the first floor, because the basement precedes it. Just because the ground floor is commonly called the "first floor" for historical reasons, doesn't make it the mathematically first floor.
In some places (e.g., most of North America), that's the convention. In others, the "first floor" is the one immediately above the ground floor.
>So if we were to label to cars in increasing numeric order from one end to the other, we would start with 0 instead of 1 at the first car? We don't do that with building levels. You enter on the first floor, go to the elevator, and you push a button for the floor level. The first floor is 1. 0 Would be the basement level.
We opted for the word "Ground Floor" instead of "Zeroth Floor" likely due to the associations people make of "zero" (ie. not existing) and because it may have sounded weird but the concept is the same.
The U.K and U.S refer to different storeys as the "first floor". In the U.S, the first floor is considered the ground floor and in the U.K the first floor is considered the second storey. A source of headaches when told the place you're looking at is on the first floor and you spend ages looking for it on the ground floor.
Ordinal numbers (0, 1, 2) map to the world as amounts, and certainly it seems 'real' that there can be "one of something" in a way that it isn't that there is "zero of something" (though it isn't, really.)
Cardinal numbers (first, second, third) map to the world as rankings or positions. Positions, further, often almost always map to distances from an origin. "First" really almost always means "the item that is +0 positions away from the origin." The person who wins a competition ("first place") is zero positions down the leaderboard. The "first" book on your book shelf can be found +0cm away from the left edge of your bookshelf. Etc.
With your cars, you're talking about a third thing, though: serial numbers. "Car 1" is what you might call the first car you bought (if you were planning on buying several), because we conventionally assign serial numbers to things starting with 1. But that has nothing to do with counting or ranking; it's just a convention (as can be seen when we choose to use an alternate scheme, like UUIDs, for labelling items in a database.)
What we're talking about here is the relationship between counting and ranking: between cardinal and ordinal numbers. Since they're both abstract, and not structurally connected in any important way, there's actually no "essential, required" way to relate them to one-another, and we have to just make one up. Some people relate "first" to the natural number 0; some people relate "first" to the natural number 1.
It's a bit awkward, but once explained it is a quick way to tell the two numbering schemes apart.
L[2] == *(L + 2) == *(2 + L) == 2[L]I started with arrays with Fortran. There can pass an array as an argument to a parameter of a subroutine, and the subroutine can address the darned array any way it wants. Why? Sure, maybe want to sort the array based on a slice here omitting details. Sure, such programming would need a lot of well done documentation and still is dangerous. And such array fooling around stands to get into trouble with compiler options to check array bounds.
Then I did a lot with PL/I: There get arrays, structures, structures of arrays of structures of arrays, etc. Also get to set the lower and upper bounds of each array index to anything -- positive, negative, or zero, including during execution -- that can be represented in the usually 16 bit array indexing arithmetic. And, it turns out, all that array indexing, even for arrays of structures of arrays, etc., is just ordinary multi-dimensional array arithmetic -- nearly as useful as objects but with much simpler storage allocation and array indexing. And if look carefully at that arithmetic, then do see how to have any subscript (index) lower bounds and upper bounds with just trivial modification of the usual array indexing.
And, yes, when I wrote C code, no way did I like the high emphasis on starting an array at index 0. Besides C doesn't even really support arrays, e.g., with several subscripts, and forces a programmer to write a macro or some such that does the arithmetic. And there are problems in a subroutine that receives such an array. And compiler support for checking array bounds is in trouble because the language syntax and semantics don't even support arrays with several dimensions. So, have to write, say, a matrix package that has a C structure for the details of number of dimensions and the upper/lower bounds for each dimension -- it works but get no compiler based debugging support or I/O support, and no doubt the compiler can't do some indexing optimizations that Fortran and PL/I can do because the data being used for the indexing is, in the semantics, not subject to being changed by the user's code during the indexing arithmetic. E.g., with PL/I, in the execution logic, each structure or array, each aggregate has a little table, a dope vector that describes the aggregate, yes, within a subroutine and within runtime subroutines, e.g., for doing I/O on the whole aggregate.
PL/I was in good shape before C was developed. PL/I was used for the operating systems Multics and much of Primos. So, PL/I offers programmers much more than C and, still, is good for both applications and operating system code, especially in array indexing.
Sorry, Dijkstra.
https://learnxinyminutes.com/docs/c/ then text seach for "dimensional".
More detail: http://beginnersbook.com/2014/01/2d-arrays-in-c-example/
I didn't see that in K&R, 1988. Are such multi-dimensional arrays new since 1988?
When I needed to do a little matrix work in C, I just wrote my own little package of matrix code, maybe with more functionality than I just saw in your first link. Maybe I didn't really need to write my own?
p == &(p[0])
p[0] == *(p+0)
p[1] == *(p+1)
For 0 based indexing the punctuation is the indexes/offsets:
[ a , b , c ]
0 1 2 3
[ a , b , c ]
1 2 3
elements[0:3] - all items between offset 0 and 3
elements[1:3] - all items including 1 and 3
Where they stop making sense is when you'd mix up the inclusivity ie (for the second case).
elements[1:4] - including item 1 not including 4Keep calling it the second, then. And use 'zeroth' for L[0]. Problem solved.
Also, what is 'counterintuitive' is very often just a question of habit. I've many times seen Americans (at least those not scientifically inclined) express confusion over metric units. I have been using the metric system all my life in every its domain: I buy apples in kilograms, measure rooms in metres, water in litres, and I regard it as the most natural thing in the world. I find the American unit system batshit insane (why is 'ounce' a unit of mass, but 'fluid ounce' a unit of volume? WTF is up with all those different conversion factors?) and if I had the power to wipe the it from the face of the Earth, I'd do it in a heartbleed. I'm sure that if I asked some people from my country about this, I'd find many agreeing with me. But I realise there are people who feel just the opposite. (I still think they're wrong, but I get where they're coming from.)
Zero-based indexing is similarly just a question of what people are used to. When those students start appreciating the nicer mathematical properties of zero-based indexing (and half-open ranges that go along with it), it'll become second nature to them. (I suspect the reason why many people don't is because laymen don't often work with abstract algorithms and indexed data structures where those properties display their usefulness.)
Nice of you to speak for them. Unfortunately you are in error.
I don't know if this is still the case -- my understanding of microprocessor architecture is about 30 years old.
according to at least one attempt 0 based indexing was chosen because it was slightly faster to compile.
Why is 2 so special? Is it more important for humans to be able to calculate quantities in their head, or to be able to convert to obscure computer formats?
We do, not when they're starting out but the number line is introduced pretty early to children. Even earlier we teach them to count backwards with zero being the final element. Kids aren't strangers to the concept of zero.
[1] https://en.wikipedia.org/wiki/OpenType#Advanced_typography [2] https://en.wikipedia.org/wiki/Font#Character_variants
Nowadays I do write stuff but summarize it into the computer. I've tried various tools for automatic capture (e.g. livescribe) but they don't work that well. I realized that the probably would have worked great with my 35-years-ago handwriting.
In addition my handwriting has become terrible. If I check my notes soon after writing them (within the same day) I can often tell by making out a few words and remembering what was being discussed when I was marking that part of the page :-(. A couple of days later I can barely understand them and longer than that I might as well forget it.
I could probably get by making random marks on the paper!
It's so sad, because when I was a scientist and had to maintain a lab notebook other people could easily read my notes (and they had to be clear for IP reasons). Or maybe I should look at it the other way: it's not sad, because it doesn't matter as much any more.
(Charles Rennie Mackintosh has particularly lovely drafting letters; turned into the Hill House font.)
Edit: I can't explain how, but the first time I downloaded that PDF I received a file which looked different. Here is a similar file from the same site which clearly resembles what led me to make the comment above:
https://www.cs.utexas.edu/users/EWD/ewd00xx/EWD77.PDF
So I apologise for this unnecessary diversion from the topic.
http://stackoverflow.com/questions/37953786/why-does-postgre...
It is interesting to see the same question applied to natural numbers, and Dijkstra landing on the same [x, y) recommendation. I'd say for natural numbers the argument is even stronger, since there is a least possible value.
Try some string manipulation using the awk language, which has 1-based strings and arrays, and you'll see that programs and string expressions are generally shorter and more idiomatic.
Later languages building on awk such as Java and JavaScript (awk is almost a subset of, and the inspiration for early JavaScript) have cargo-culted 0 into the language as base offset. Though probably it may have prevented some errors to make commonly used languages behave same in this respect.
Depends very much on what you're doing. If you're doing, say, a filesystem driver, and you need to do math or reasoning on [offset, length] pairs quite frequently, you will find 0-based indexing much more natural. At least that's been my experience. I think some of this applies to strings and memory too.
In the west, we measure our age and start from 0. In China, they count their age (number of distinct years someone has been alive in) and thus start from 1. In fact, in China, if you are born on new years eve you can be 2 years old at 2 days old!
But it doesn't really apply in the natural world, where 1 is a much better starting number for probably all contexts where you have to number or reference things in an order.
Maybe this clarification is redundant, I don't know. But when I read the headline, I assumed it was talking about everywhere, which is why I found it interesting and even clicked it in the first place.
In naive set theory, starting with 1 poses some problems (specifically, you don't have numbers yet, so you start with the notion of the empty set, which you use to define 0, and then proceed from there).
Starting the naturals from 0 is also problematic in group theory, since you lose the additive identity.
I'd say that the only situation where it makes sense to count from 1 is when you are counting objects. Of course, counting objects is so important that it dominates people's perception of numbers and counting.
"pause one, pause two, ..."
So when you get to 10, you have said 10 numbers and there have been ten pauses. The "you are only counting 9 seconds" thing would only make sense if the counting period starts when you say the first number, which is not how I usually do it...
|------------|-------
t0 t1
^ ^
First SecondAnyway, if you do make a conscious pause, I would argue that you are effectively counting from 0 even if you don't pronounce 0 due to the bias against that number caused by counting objects. The first pause needs to start somewhere, the start of that pause is in your mind (even if you don't pronounce it) and it corresponds to 0.
for i in 0u8..256 { } // <-- doesn't compile, because 265 is not a valid value for a u8when you see `-1` in code it is often a failure of the expressiveness of 0-indexed lists. For example, the last item in an array:
arr[arr.length - 1]
if (arr.indexOf("thing") > -1) {
Your second example isn’t ultimately about array indices, but is caused by confusion between using 0 as both an ordinal number and as a representation of boolean false.
With 1-based indexing, you can just skip zero, and be consistent - a[1] is the first element from the left, a[-1] is the first element from the right.
With one-based indexing, you can’t have arr[-1] as the last element (that would cause huge problems!). Languages with one-based indexing write something like arr[end] or arr[arr.length] to refer to the last element, with arr[end-1] or arr[arr.length-1] referring to the second-to-last element.
Can you give some examples?
Modulo and exponents are, to me, the primary reason for using a 0 based numbering system
arr.indexOf("thing") > -1
...And when you see '+1' or '(x%ArrayLen)+1' or 'x<=arrayLen', in lua or FORTRAN it is often a failure in the expressiveness of one-indexed lists.
a[N : length(a) - N + 1]
a[N : -N]
a[N : length(a)]
a[N : -N - 1]
In fact, merely having a special syntax for reverse indexing solves it for 0-based languages. For example, suppose that we extend the slice syntax such that either index can be prefixed with ~ to indicate indexing from the end. Then ~0 is the last element, and it becomes:
a[N : ~N]
Alternatively, you can provide syntactic sugar for the length of the array within the indexer - say, `$`. Then, in 0-based end-exclusive approach, you just write:
a[N : $ - N]
However, this only works if your ranges aren't first-class (i.e. if they only appear inside []). These days, the trend seems to be to have ranges as first-class values in the language, and have the indexer accept a range as an operand. In that case, since the range can be constructed separately, it needs to be able to encode "index from start" and "index from end" inside the object itself, and special range syntax for that makes more sense.
If the language uses iterators or equivalent, then the iterator itself can encode the direction, and the range is just a pair of iterators. But you would still want some special short syntax, or at least a short convenience function, to easily create reverse iterators. C++ does just that - a pair of iterators expressing the same thing for random-access container `a` would be:
make_pair(a.begin() + N, a.rbegin() + N)
let a = <some very long expression>
in make_pair(a.begin() + N, a.rbegin() + N)Also, I don't think the parent's point is "1 is better than 0" but rather "0 is not better than 1".
C++ has arr.back() which is much nicer to read, but has the downside that behaviour is undefined when the vector is empty. Seems like interfaces always have pain points.
arr[arr.length - 1]
arr[arr.lastIndex]
arr.last
if (arr.indexOf("thing") > -1) {
if (arr.indexOf("thing") > 0) {
if (arr.member?("thing")) {
This is not commonly held belief. I am in minority but this is what makes sense and I always believed that computers should serve us, not the other way around.
Amen! The idea that we should change our way of thinking because it somehow makes more sense for computers is preposterous.
1. Naturally, the first element in a list cardinally corresponds to 1. Contrarily, even official documentation of JavaScript has explicit disclaimers that the "first element of an array is actually at index 0" - this is easily forgotten, especially by novices, and can lead to errors.
2. Mathematically, a closed interval is properly represented in code as for(i = 1; i <= items.length; i++), because it includes its endpoints. Offset notation instead is technically a left-closed right-open interval set, represented in code as for(i = 0; i < items.length; i++). This matters because code deals with integer intervals, because all elements have a fixed size - you can not access a fractional part of an element. Integer intervals are closed intervals, thus conclusively proving this importance.
3. Mathematically, matrix notation also starts with 1.
4. The last element in a list cardinally corresponds to the length of the list, thus allowing easy access with items.length rather than having frustrating (items.length - 1) arithmetic everywhere in your code.
5. Negative indices are symmetric with positive indices. Such that -1 and 1 respectively refer to the last and first element, and in the case where there is only one item in the list, it matches the same element. This convenience allows for simple left and right access that offset notation does not provide.
6. Non existence of an element can be represented by 0, which would conveniently code elegantly as if( !items.indexOf('z') ) return;. Rather, one must decide upon whether if( items.indexOf('z') == -1 ) return; is philosophically more meaningful than if( items.indexOf('z') < 0 ) return; with offset notation despite ignoring the asymmetry of the equation.
And choosing "0" to mean "absent" is as arbitary and misguided (unless you are optimizing bits and cycles on a low-powered machine) as choosing "-1" to mean "absent"
'Cardinally' is wrong; it refers to cardinality, i.e. measuring the size, not indexing. It's just a historical accident that indexing traditionally started with one, and most languages lack a word for an ordinal number corresponding to zero. That's mostly because for a long time zero hasn't even been recognised as a number at all.
But the Ancient Greeks didn't recognise 1 as a number either. We've grown past that.
> 2. [...] This matters because code deals with integer intervals, because all elements have a fixed size - you can not access a fractional part of an element. Integer intervals are closed intervals, thus conclusively proving this importance.
Half-open intervals preserve the property that [a,b) ∪ [b,c) = [a,c) whether the domain is discrete or not. Half-open intervals generalise well both to empty ranges and infinite ones. In fact, in set theory ordinal numbers can be said to be defined as half-open intervals starting with zero (according to the most popular modern definition): an ordinal is simply the set of all ordinals that precede it.
The 'fractional part of an element' is nonsense.
> 3. Mathematically, matrix notation also starts with 1.
This is just a historical accident as well.
> 4. The last element in a list cardinally corresponds to the length of the list, thus allowing easy access with items.length rather than having frustrating (items.length - 1) arithmetic everywhere in your code.
That is somewhat obtuse, but I don't believe it outweighs other concerns. And again, not 'cardinally'.
> 5. Negative indices are symmetric with positive indices. Such that -1 and 1 respectively refer to the last and first element, and in the case where there is only one item in the list, it matches the same element. This convenience allows for simple left and right access that offset notation does not provide.
Zero-based indexing together with negative indexing lets you effortlessly treat any list as a circular list. Which is related to the reason why people bring up modulo all the time, by the way.
Tangentially, Lua uses this very convention (1-based indexing, closed ranges and negative indexing) in its string functions. It annoys me every time I write something parser-like by hand.
> 6. Non existence of an element can be represented by 0, which would conveniently code elegantly as if( !items.indexOf('z') ) return; Rather, one must decide upon whether if( items.indexOf('z') == -1 ) return; is philosophically more meaningful than if( items.indexOf('z') < 0 ) return; with offset notation despite ignoring the asymmetry of the equation.
The first is obviously more sensible. Failure to find an element might just as well be represented by a null; that the value chosen to represent it is an integer smaller than any valid index is mostly an accident. In a better-designed programming language, a function equivalent to indexOf would have a return type of an option type of a valid index. The language would also have pattern-matching constructs handling it with a syntax just as snappy as a boolean negation is in JavaScript. (Why? For one, because it generalises well to maps of arbitrary type.) This remark proves little apart from pointing out the shortcomings of JavaScript's type system.
Ask ten people to implement binary search with 1-based indexing, for example. Watch the off-by-ones roll in.
In fact, from https://en.m.wikipedia.org/wiki/Zero-based_numbering With zero-based numbering, a range can be expressed as the half-open interval, [0,n), as opposed to the closed interval, [1,n]. Empty ranges, which often occur in algorithms, are tricky to express with a closed interval without resorting to obtuse conventions like [1,0]. Because of this property, zero-based indexing potentially reduces off-by-one and fencepost errors.
Edit: Lol, the Wikipedia article cites Dijkstra's article.
On its own, I think that's a reasonable contention, but it doesn't work when combing intervals: [1, 1) combined with [1, 2) is still [1, 2), but [1, 0] combined with [0, 2] isn't [1, 2].
[0..5] 0,1,2,3,4,5
(0..5) 1,2,3,4
[0..5) 0,1,2,3,4
(0..5] 1,2,3,4,5
For programming, as Dijkstra mentions, a consistent start from zero seemed to be helpful.
Let's call it $[, so a statement like '$[ = 17' causes arrays to start indexing at 17.
http://search.cpan.org/dist/perl-5.17.1/ext/arybase/arybase....
(C.S. way) 0 <= a < N
(Math way) 0 < b <= N
As he says, both ways have the property that "upper bound - lower bound = Number of elements", both can represent an empty set "lower bound = upper bound", and both make partitioning easy "(0 <= a < M)U(M <= a < N)".
However I disagree that including the lower bound way is preferable to the starting at 1, math way. Math is the older science and children are still taught to count in this way.
As many of the benefits of one way or the other are mostly just network effects (i.e. in math subscripts typically start at 1 or in C, ints and structs are pointed to by their lowest char), we should have used the notation of the older science.
What's happening here is experts arguing about minutia that feels important to them, but looks trivial from the outside.
[1-based index] Year 2016 -> Century 21 -> Millennium 3
New year on 2017-01-01 01:01:01
[0-based index] Year 2015 -> Century 20 -> Millennium 2
New year on 2016-00-00 00:00:00 :-)
Why do people make the fuss about indexing and not about column-major arrays?
Such minimalism is elegant and efficient, to be sure, and I'm a big believer that beauty often shows the path to truth. So from a computer science standpoint, I wholly agree.
From a software engineering standpoint it's really fucking stupid. People generally learn to count on their fingers and they need to grasp the concept of counting and numbers as an abstraction before they can get with the concept of a zero.
Counting on your fingers is one of those very basic things like learning the alphabet (ro its equivalent in other languages) or learning to tie shoelaces. Nobody I have ever met defaults to counting from zero, not even people who claim to do so - easily tested by buying them a drink at some later time and tricking them into counting something.
If you're a software engineer your job is to build something that works and is maintainable. This is not the same thing as doing computer science or mathematical computing, even though it may all be math from the computer's point of view - just as architects are not mathematicians despite their reliance on geometry. Array bound errors are omnipresent in software projects because counting everything from zero is directly at odds with how we count things in the real world, and when we're in a hurry or under pressure we default to learned behaviors. Even people who have been bilingual for years will burst into their default language or switch between two default languages when they're excited. Building your code to go from 1 to n+1 may not be quite as beautiful, but it is a hell of a lot easier for other people to read and (in my experience) you make fewer mistakes if you switch away from starting at zero.
Yes, this requires developing some new habits that feel really awkward at first. Since I've only ever programmed for myself rather than as part of a team I haven't had to deal with the inevitable resistance to this. But it is worth making the switch. Just as a lab and a construction site are very different environments [1], so are the practices of computer science and commercial software development. It would also make a huge difference in programming education, where many prospective students are alienated by being asked to do something highly counterintuitive very early on (typically while trying to grasp the concept of looping) and lead to errors which they are likely to keep making forever because nobody defaults to counting from zero in any other context.
If you're a computer scientist, carry on as you were. If you're an engineer, then build for the needs and instincts of your end users - some of whom will eventually be programmers - and not for the computer gods. They're not going to be around to help when your code breaks down.
I'm not very optimistic about this plea (especially not in the USA where y'all won't even adopt the damn metric system), but please at least give it a try. Technology should adapt to the needs of the people that use it, rather than the other way around. If you're working in a high level language, then use high level concepts.
1. Remember the story about the three little pigs who all built their houses out of subatomic particles formed into atoms formed into molecules and whose houses were topologically identical but had different coefficients of structural stability? Me neither.
(And for the record, I started out in the 1-origin Basic and Fortran world; my preference isn't just a matter of which one I learned first.)
Surely not the Noble kind of sciences, but if animosity leads too thoroughly read papers and found errors, maybe the dark side is just willing to work harder.