The origin of zero-based array indexing

http://exple.tive.org/blarg/2013/10/22/citation-needed/

by fizwhiz • 13 years ago

103 107 13 years ago

exple.tive.org

lukasm• 13 years ago

If people would use word "offset" there would a lot less confusion.

coolsunglasses• 13 years ago

This mischaracterizes what happens by leaning on an unreliable source.

adamnemecek• 13 years ago

That sure is a lot of words to say 'because indices are memory offsets'.

thepicard• 13 years ago

Because it's more than that. It wasn't originally to speed up run time, but compile time. That history is wildly fascinating to me. We tend to take compile time for granted, unless we are bitching about Scala, or compiling C++ at Google.

The author also addresses the importance of history. Voodoo knowledge _does_ pervade modern computer science, and I for one am happy to see something different.

stinos• 13 years ago

Because it's more than that

But is it really? I'm inclined towards anonymouz's and adamnemecek's idea here: Dr Richard clearly says indices are offsets, no? It's nice the author gets all sentimental about it, but that doesn't make him right.

MichaelMoser123• 13 years ago

Lambda the ultimate had an interesting discussion on this article, recently http://lambda-the-ultimate.org/node/4843#comment

anonymouz• 13 years ago

I don't get it: The quote by Dr. Richard essentially says that the reason to do it this way in BCPL is because they are offsets, and it would have been unnatural to subtract 1 of them.

I can't see anything about the computational cost of the indexing in there: Does the author have another source for that? It doesn't seem to be supported by what he quotes. The anecdotes about the IBM 7094 are nice, but I don't see much evidence for the kind of connections the author claims.

moogleii• 13 years ago

I was inclined to disagree due to the author's strong arguments and precise use of language, but after re-reading the part around Dr. Richard's comments, I do think the author made a bit of a logical leap.

It went from "I'm Dr. Richard, and BCPL supports pointer arithmetic starting from zero" to "I'm the author, and the IBM 7094 handles all the pointer arithmetic during compile time, and time is limited; therefore, Dr Richard added zero-based indexing to speed up compile time." When really, his intentions are assumed by the author. Dr. Richard sounds like a very pure computer scientist. He may have added that feature without consideration of when pointer arithmetic is calculated simply because he wanted it in his BCPL language.

Really, Dr. Richard seems to sum up the issue nicely, "I can see no sensible reason why the first element of a BCPL array should have subscript one."

Also, wasn't the original question why zero vs one, not, why we started using pointer arithmetic at all?

mattdw• 13 years ago

Related is Dijkstra explaining the pros and cons of different styles of indexing and slicing: http://www.cs.utexas.edu/users/EWD/transcriptions/EWD08xx/EW...

jimhefferon• 13 years ago

Right. The author discusses Dijkstra's argument, and dismisses it as not rising to the level of wrong. Personally, I find Dijkstra's argument unassailable. (It is, roughly, what a person would express in Python syntax as range(0,k)+range(k,n)=range(0,n).)

ronaldx5• 13 years ago

I don't find Dijkstra's argument unassailable: let's claim instead that half-open intervals are ugly (they are asymmetrical, and not typically used in mathematics) and closed intervals are preferable.

Given that, his arguments support 1-indexing better.

jerf2• 13 years ago

And the reason why I don't want to assail Dijkstra's argument is that I've programmed fairly extensively in both types of languages. 1-indexing means I have to think about every single time I want to go and slice an array. Half-open interval means it just does what I want, and I literally can not think of a case where I wrote an off-by-one bug under that regime. And, again, let me emphasize, extensive experience in both regimes, which is to say, it's not just a matter of what I was "used to". Indeed, I believe my first 2 languages (possibly 3) were 1-based. I'll take the style that produces the fewest bugs and happily call it "right"; others are free to argue that their intuition says they should use the buggier style, I guess, but I'm not going to be finding it convincing anytime soon.

I consider the idea that we should follow human intuition to itself "not rise to the level of wrong". There is nothing intuitive about programming, it is probably the second least intuitive activity known to man behind only pure mathematics. Your intuition needs to be trained from what is basically scratch, not blinding copied from much friendly, human domains. We know what that leads to, we've been doing it for decades; some people seem to argue "Oh, if only we'd try more human-friendliness it would all be better" as if we've never tried it, but we have, repeatedly. We get Applescript and COBOL and other languages that strive to be "human friendly" and produce an impenetrable morass of "human friendliness" that become incredibly hard to use as the size of the project exceeds trivial. As counter-intuitive as it may be, the track record is pretty clear at this point that the best languages are those that do not try to cloak themselves in false human skin.

(Which is of course not to say that we should all be programming assembler. Don't strawman me there. But the task of a language should be seen as a bridge between the human world and the computer world; it is not the job of the language to actually be in the human world itself.)

mtdewcmu10• 13 years ago

I don't get why zero-indexing requires so much justification. Here are two powerful reasons why it makes sense:

    * Zero is the first unsigned integer. If you start at 1, you're wasting one
    * p[0] == *p, and it makes no difference whether pointer arithmetic had been invented, because pointers are just memory addresses, and that's what the cpu works with

The best reason for one-indexing:

* Some people think it's less confusing

> Over and over again tools meant to make it easier for humans to approach big problems are discarded in favor of tools that are easier to teach to computers, and that decision is described as an inevitability.

That's exactly how it should be. What's easier for humans is subjective. What's easier for computers is objective, and going with the grain of the machine tends to yield solutions that work, whereas going against the grain tends to cause over-complicated and buggy implementations. That's the true take-home of "Worse is Better." The Unix approach to syscalls worked, and Unix is alive and well. The MIT approach was quite possibly impossible to implement, and the system they were building is extinct. If you want to use a computer well, you have to learn a little about computers and set aside your preconceived ideas. What's so unreasonable about that?

jebus9893• 13 years ago

"Some people" is understated; if you're holding one orange and I ask for your first orange then you give me that one, in your first hand. I'm over-emphasising but the point is that no zeroes are involved.

It's a trade-off, if we were bending entirely to the computer's will we'd all be programming machine code, whereas there's overhead in using more natural language. Honestly I've bought this 0-indexing is the Right Way for a long time but the more I use R the more a 1-index seems to make sense for high-level languages.

loxs• 13 years ago

Same thing with Erlang... it seemed so weird at start... now I hate all 0-indexed languages.

mtdewcmu10• 13 years ago

Well, frankly, I always thought 0-indexing made perfect sense, given the elegant symmetry with pointer arithmetic in C. It also makes sense in that variables are naturally initialized to zero, and that puts an index right at the start of an array. Everything just falls into place.

paulnechifor• 13 years ago

if you're holding one orange and I ask for your first orange then you give me that one, in your first hand. I'm over-emphasising but the point is that no zeroes are involved.

No ones are involved either. I don't have a "first" hand and when you request a first orange, you're just asking for the head of the ordered set.

dspig• 13 years ago

Well, you don't have to use the 0th index, it's better than wanting to in a language where you can't!

lucideer• 13 years ago

An index is the beginning of a unit - the point at which it is found, where it begins. The index doesn't represent the unit itself, just where it is located.

Your orange takes the zeroth index becoming the first orange: http://i.imm.io/1lWRO.png

People understand the concept of zero perfectly. They know the day doesn't begin at 1am, they know babies aren't born 1 years old. This isn't a computer-specific concept in any way.

zvrba• 13 years ago

I ask for your first orange then you give me that one, in your first hand

It's the difference between ordinals and cardinals. In human languages I see ordinals as a pure shorthand: you could just as well say "give me orange number zero", except it's more cumbersome. I honestly can't think of a context (in human languages) where ordinals would be something more than a mere convenience. I believe the existence of ordinals is a technically unnecessary historical artifact: counting was invented before zero.

PS: I doubt people number their hands. A person would say "in your left hand", not in "your first hand".

runarberg2• 13 years ago

> What's easier for humans is subjective. What's easier for computers is objective.

Just want to point out that perhaps we humans are not as subjective as our intuition indicates. The third rear brake light make car's stopping distance shorter. There are human (psychological) reasons for that. I mean you could do objective approach all you want to make traffic safer, like build better brakes, but ultimately, humans control cars, humans have biased (arguably fixed) way of thinking, and there are ways to create interfaces that makes use of that bias. 1-based indexing makes ton of sense when your tool is meant for human use, because most of us is biased towards start counting at 1, objectively at least.

VLM2• 13 years ago

"There are human (psychological) reasons for that"

Neurological in that the line detecting algorithm is more excited by seeing a triangle of three lines than a horizontal bar of just one line. We have the technology to stick a HDTV on the bumper of each car and replace "brake lights" with a giant glowing stop sign which would work even better. But its basically the same argument.

mtdewcmu10• 13 years ago

What I meant to say is that people are arbitrary and capricious and, in many cases, will never agree on what is easier. The objectivity of the practical engineering concerns offers a rational basis for making a choice.

People are certainly not consistent in preferring 1-indexing. People expect decades and millenia to start on years ending in zero (even though they actually don't, because of 1-indexing).

fsck--off• 13 years ago

The Unix approach to syscalls worked, and Unix is alive and well. The MIT approach was quite possibly impossible to implement, and the system they were building is extinct.

The "MIT approach" in Worse is Better discussed the extant PCLSRing scheme on ITS (not a theoretical one) and the different approach that Unix took. Saying that it was "impossible to implement" is just flat out wrong.

ITS is an ancient time sharing system that predates Unix. It was written in assembly, ran on PDP-6s and later on PDP-10s, and had fallen into disuse when Gabriel wrote that essay (MIT would stop using it the following year). The success of Unix had nothing to do with its solution to the PCLSRing problem.

mtdewcmu10• 13 years ago

It's interesting to consider whether PCLRing might have worked. I'll look at it in more depth.

mtdewcmu10• 13 years ago

I see. It was already in production. It's an open question whether the more complex syscall conventions would have held up over time as new features were added. It makes a lot of sense in general to push unnecessary complexity out of the kernel and into userspace, since processes in userspace are allowed to fail. The complexity of the system call interface can be hidden behind a library.

lloeki• 13 years ago

I don't get why zero-indexing requires so much justification. Here are two powerful reasons [...]

Reasons which I feel are too C-like and high level already. The article falls into the same trap and says this as a counter argument:

It’s not about * i = a + n * sizeof(x) because pointers and structs didn’t exist.

But I actually read this as an argument in favor of zero-based index origin: since pointers and structs did not exist, any form of memory addressing and data storing/retrieving had to be done at some lower level, and if you did it by hand, you will for sure align the start of your in memory handmade array-like structure at the address of it, then merely add to the register holding the address an offset maybe itself stored in a register, and certainly you would not add 1 again to those, because the idea would not even cross your mind to lose one and one byte/word of memory and one cycle, as it would just make no sense at that level.

Subsequently, C (or B or A or whatever) evolves the process and embeds into the language such arithmetics, abstracting it under monikers such as "pointer", "struct" and "array" and adding utility functions like "sizeof", so that you don't have to remember if this or that CPU/asm uses ADD or ADL, or is foo-aligned, or uses bar calling convention.

ronaldx5• 13 years ago

In my opinion, one-indexing is better:

* Ordinal and cardinal numbers both start from 1 in all major human languages

* Humans didn't use the number zero until relatively recently in mathematical history - this illustrates that it's intuitively hard for humans to grasp.

* It's important to separate the cases of 0 and null, which is easier if you use 1-indexing. This has got to save a lot of tricky bugs.

High-level programming languages are designed for humans. Humans 1-index everything, so these would be better 1-indexed.

Low-level programming languages are designed for computers. You can 0-index there, for the reasons that you stated.

As programmers, we had to explicitly learn 0-indexing. 0-indexing creates an artificial barrier to enter programming, when there are so many other barriers that we should be trying to relieve.

cliffbean6• 13 years ago

It's true that humans hadn't discovered zero until relatively recently in mathematical history. Should we reject these "new" developments in numeracy, and go back to roman numerals? One could make a pretty strong case that roman numerals are more intuitive, more human.

moron4hire2• 13 years ago

point 1 is tautological. point 2 is incorrect. point 3 is a problem of the concept of null being a mistake, not of 0-indexed arrays.

programming is math, and all the math works better if 0-index arrays. Leave programming language design to the adults.

dllthomas• 13 years ago

You don't index pointers by pointers, so I don't see point 3. Your types distinguish zero from null.

mtdewcmu10• 13 years ago

1-indexing is no longer intuitive when numbers become large. Years are 1-indexed; how many people observed the start of the millenium in 2001?

rbehrends• 13 years ago

This is just all very subjective:

  * Zero is the first unsigned integer. If you start at 1, you're wasting one

Counter-argument: If you start indexing at 1, it allows you to encode an exceptional condition (e.g., element of a search not found) as 0 when the result is an unsigned integer.

  * p[0] == *p, and it makes no difference whether pointer arithmetic had been invented, because pointers are just memory addresses, and that's what the cpu works with

Counter-argument: This only holds for fixed-length arrays, strings, and the C/C++ idiosyncrasy that conflates pointers with arrays (at the expense of runtime safety). If you have variable length arrays or strings, then the beginning of the actual array/string contents will be at an offset (allowing for length/capacity/etc. fields). In fact, the offset may be exactly one (if you have a length field the size of each element), making one-based indexing the more efficient choice.

You can make up ANY number of arguments for zero- or one-based indexing, and it will depend entirely on how much weight you assign to each of them.

Or, alternatively, you can use the Pascal approach, where you can specify the beginning index on a per-array basis.

cliffbean6• 13 years ago

Using 0 as a special error value is a kind of a hack though. What you're really doing is returning "either an error or an index", which is a different type than "an index". Empirically, using one language type for two concepts like this, allowing errors to be silently dropped as values can be implicitly converted from one to the other, has been very error prone. See the discussions about nullable pointers for example.

WRT strings with metadata, if you construct your data structure so that the length and other metadata are at negative offsets from the pointer value that gets passed around, then the array data can be at offset zero again, so it's even more efficient. So zero still wins :).

But the arguments for 0-based indexing are also deeper than C arrays. C arrays are just one place where it's clearly visible.

The Pascal approach unfortunately doesn't solve the problem either. "Everyone can do what they like" is fine as long as no one ever has to read or interface with code written by other people.

abvdasker• 13 years ago

Thank you. Having done a limited amount of assembly programming, 0-indexed arrays seem incredibly obvious, since they allow you to simply add the word size times the index to get the memory address of any entry in an indexed data structure. This is still almost exactly how arrays work in most (compiled) languages.

Personally, I think it's cool that there are elements of mid/high-level programming languages which still reflect very low-level operational concepts.

mtdewcmu10• 13 years ago

The reason they seem obvious is that they represent a quantity that has meaning -- the offset.

ingenter• 13 years ago

There are other interesting reasons why it is better to use zero-based indexing. In some algorithms you need to access n-th element modulo something. For example, to fill an array of arrays, in zero-based array

    for (i = 0; i < width*height; i++) {

       arr2d[i / width][i % width] = array[i];

    }

If you use one-based arrays, you have to write

    for (i = 1; i <= width*height; i++) {

       arr2d[(i-1) / width + 1][(i - 1) % width + 1] = array[i];

    }

Yes, you can write two loops, but this example shows how mapping one array onto another is easier if you use zero-based array.

cousin_it• 13 years ago

Good point. You could also say that simulating two-dimensional arrays with one-dimensional arrays is easier with zero-based indexing: a[x + y * w] rather than a[x + (y - 1) * w]. Are there similar use cases that look more natural with one-based indexing?

htns• 13 years ago

This becomes just as simple in one-based indexing if you take the negative view and have division round up and modulo run from (-n + 1) to 0 instead of 0..(n - 1). So you get "arr2d[i / width + 1][i % width] = array[i]" if your language does the logical thing with non-positive indexes. Using modular arithmetic to argue for zero-based indexing is close to circular reasoning.

userbinator• 13 years ago

I can remember that out of all the code I've written, I've very rarely needed a +1/-1 except as part of accessing a next/previous element, so at least from this data point, zero-based indexing makes the code simpler and easier to understand. That second example of yours I had to spend a lot more time reading (and mentally doing increments/decrements) to figure out. I'm almost willing to bet there would be more off-by-one errors if one-based somehow became the norm.

Hellenion• 13 years ago

And why would it be so bad to have a programmer's mythology? Sure it isn't factual history but it lets us explain the world we see around us in a memorable and understandable way.

javert• 13 years ago

It’s hard for me to believe that the IEEE’s membership isn’t going off a demographic cliff these days as their membership ages

It isn't, because anybody who wants to publish in an IEEE conferences has to pay a fee X as a member or Y as a non-member, where X + IEEE membership fee < Y.

So young graduate students just join because our advisers tell us we must to save money.

Of course, we get mail advertiesments from people (like insurers) who IEEE sells our membership information to.

I think everybody in my demographic (young grad students) views this organization as basically operating a racket. I bet they actually do lots of really great stuff. But they've never told me anything about that. It's not like there was an information session when I "joined" (paid up). So it's sad. IEEE has a real image problem.

downer90• 13 years ago

To sum it up, after 20 paragraphs:

  So: the technical reason we started counting arrays at 
  zero is that in the mid-1960′s, you could shave a few 
  cycles off of a program’s compilation time on an IBM 7094. 
  The social reason is that we had to save every cycle we 
  could, because if the job didn’t finish fast it might not
  finish at all and you never know when you’re getting 
  bumped off the hardware because the President of IBM just 
  called and fuck your thesis, it’s yacht-racing time.

roel_v2• 13 years ago

Except that's not even what the guy who emailed it said. He said nothing about compile time - he said basically 'computers work with offsets, and the first element is at offset 0'. But that would have been against the preconceived notion of the author that there is something special about starting at 0, so he needed to make something up to make his 'article' fit.

(not harping on you, just stating for the TL/DR's looking for a summary)

praptak• 13 years ago

I think a lot of people missed the point of the article. Yeah, it's basically memory offsets/pointer arithmetic. But the difference here is "because indices are memory offsets and it just makes sense" and "because indices are memory offsets and I have the research to back it up".

The point of the article is the impressive research.

roel_v2• 13 years ago

Emailing two retired people and then slapping together 20 paragraphs full of hub-bub about nothing is not 'impressive research'. It's not even 'research'.

gnoway• 13 years ago

Well, the third point of the article was that research papers were too expensive. Maybe there's more to this but we have to paid the IEEE $20 to see it.

davidgerard• 13 years ago

It's more than anyone else had bothered doing.

dvanduzer• 13 years ago

I read this and thought "haven't you even read Guido's post on this?" and then retrieved the hyperlink to much chagrin: It turns out this is the original post Guido was responding to.

https://plus.google.com/115212051037621986145/posts/YTUxbXYZ...

adam-a2• 13 years ago

Great article, the last part about understanding programming languages and computers as user interfaces and human constructs is great. I love understanding why things are as they are. Too many people seem to see programming languages as the language the computer speaks, without realising that they're actually at least 2 steps removed, with the precise intent of making it easier for people to use a computer.

My favourite offshoot is this tragic LWN post about a fairly amazing sounding debugging tracer that "three people in the entire world have ever run": http://lwn.net/1999/0121/a/mec.html

phryk• 13 years ago

You know how on a few occasions you stumble over a post that seems benign but at the end you go: "Wow. Much insight. Very inspiration."?

This has been one of these occasions.

jheriko• 13 years ago

not sure exactly why the idea that it saves compile time is supposed to be surprising.

its obvious that you can make 'human friendly' (i don't agree with that at all) one based indexing into zero based indices at the compiler stage by doing a lot of -1's (because it makes sense for memory addressing - thats how memory addresses work). those -1s obviously cost something...

that it slows down run-time code is utterly unthinkable in the context of old school computing - whilst it might make sense today if you are using some high level tool built on piles and piles of other tools, and so far from the metal that you have no idea what is going on... even then i struggle to understand why this would be considered.

off loading run-time costs to compile time is standard optimisation practice... although it was massively more important in the past than it is now. the case from the story shows how language design optimised the compiler design, so that it would optimise the final run-time.

its just optimisation - any programmer assigned this task in this context is highly likely to come up with the same solution because its straightforward and works.

linker3000• 13 years ago

Isn't this the 1th time this has been posted recently?

nshepperd• 13 years ago

Huh?

Mike Hoye: "C inherited its array semantics from B, which inherited them in turn from BCPL, and though BCPL arrays are zero-origin, the language doesn’t support pointer arithmetic, much less data structures."

Martin Richards: "If a BCPL variable represents a pointer, it points to one or more consecutive words of memory. These words are the same size as BCPL variables. Just as machine code allows address arithmetic so does BCPL, so if p is a pointer p+1 is a pointer to the next word after the one p points to. Naturally p+0 has the same value as p."

moron4hire2• 13 years ago

It also makes modulo math easier. Starting at the first element in an array and jumping to every 8th element thereafter gives you indices of 1, 9, 17, 25, etc for 1-indexed arrays. It's not immediately, intuitively, obviously clear that the index is 8n+1. However, 0-index arrays would be 0, 8, 16, 24, which is very clearly 8n.

There is no argument for 1-indexed arrays other than, "so-and-so can't be arsed to learn 0-indexed."

pubby3• 13 years ago

This makes indexing 2d arrays as 1d arrays a lot easier. With 0-based, index = x + y * width, while 1-based, index = ((x-1) + (y-1) * width) + 1

RyanMcGreal• 13 years ago

TL;DR:

"So: the technical reason we started counting arrays at zero is that in the mid-1960′s, you could shave a few cycles off of a program’s compilation time on an IBM 7094. The social reason is that we had to save every cycle we could, because if the job didn’t finish fast it might not finish at all and you never know when you’re getting bumped off the hardware because the President of IBM just called and fuck your thesis, it’s yacht-racing time."

k__2• 13 years ago

really?

I thought the reason is that the index is simply a memory offset. :\

a[0] always meant something like "get me the data whre a is pointing to"

a[1] meant "get me the data 1-offset next to where a is pointing to"

VLM2• 13 years ago

Traditionally this is taught to noobs on a blackboard or I suppose powerpoint now.

One based indexes are just going to confuse the noobs even worse. "So a[2] means get me the data offset by one from a" "uh what, don't you mean offset by two?" "No somebody said pointer arithmetic would be simpler if you had to memorize a bunch of different times to add or subtract one, just as a barrier to entry". "Oh well that sucks. Someone should invent a zero indexed array language..."

kabdib2• 13 years ago

Say I want to index an array modulo N. I have to write

array[ M mod N + 1 ]

to get the right index. This is at best clumsy.

The reality is that, whether people realize it or not, we actually start counting most things from zero. My bank account doesn't start at 1, nor does any stock price, nor number of cattle or NSA agents hiding in bushes. Zero is a perfectly reasonable speed to go (especially at a stop sign). None of these are "at least one".

TwoFactor• 13 years ago

The confusion beginners have is that 0 usually indicates a lack of something, while an array starting at 0 does have content. People don't start counting a heard of cattle with 0, since 0 would indicate the absence of any cows. However array x[0] can contain a value.

TheLoneWolfling• 13 years ago

If you define your modulo operator as returning 1..N (inclusive), that's not an issue.

kabdib2• 13 years ago

... whereupon you redo all your math. Wheee!

talmand• 13 years ago

No, you do not start counting things at zero. Because at zero that thing you are trying to count doesn't exist. If I put five rocks in front of you and ask you to count them, you don't point at each rock and say "zero, one, two, three, and four".

The stupid part of all this is that typically if you request the length of the array of our rocks, you will get five. But request the index of the last entry and you will get four. The simple fact that to refer to the last index in the array you have to use something like array.length - 1 points out the silliness of the whole thing.

EDIT: After a moment I felt the need to add that I'm not necessarily saying that all arrays need to start at one over zero, it's just that the whole thing is silly on first appearance. If the reason to start at zero is technical then fine, but as frustrated developers we have to have something to complain about.

brudgers3• 13 years ago

Bank accounts require an opening deposit, and to preempt any attempt to suggest that's not what was meant, active bank accounts may be overdrawn making the choice of analogy even less justified.

Likewise, stocks first come to market with an initial price And a stock with a price of zero or zero shares is for all practical purposes in the first case and existentially in the second case, not a stock.

And while yes there might be zero NSA agents in the bushes, that means that the list or set of NSA agents in the bushes is empty, I.e. that there is no first agent, and the value at index of the first agent is the same as the value at the second - nil, void, undefined or an error...and hopefully not the latter since there are more than enough of them already.

crististm• 13 years ago

No mention of Djikstra's argument for counting from zero (EWD831)?

Avshalom• 13 years ago

Mean while Pascal side steps this* entire aesthetic debate by letting you define the index range of an array as you see fit and did so years before UNIX convinced everyone that C was somehow a good idea.

*'this' referring to the debate in thread, not in the article.

lmm• 13 years ago

Which is a terrible idea. It's like sidestepping the debate over whether to use spaces or tabs by using both.

mtdewcmu10• 13 years ago

C is spartan with syntax, and you could accomplish much the same thing with a macro. Of course, in C++ you could define your own arrays with their own indexing scheme.

kannanvijayan• 13 years ago

The origins of our current commonly accepted indexing semantics are one thing. The question of which scheme is better is another thing entirely, and it's been settled quite definitely.

There are myriad reasons why zero-based indexing is the correct approach. Djikstra's commentary on the subject gets to the heart of the issue, but let's take the roundabout route.

Consider languages with pointers and pointer arithmetic. In these languages, anything outside of zero-based indexing is confusing and error-prone. The equivalence:

  p[i] is *(p + i)

Only holds with zero based indexing, and it is a crucial property to maintain. The crucial understanding of |i| in this context is that it's not simply a number, but that it is a _vector_ from one location to another. The nullary vector (0) |p| takes you to |p|, or |p == &p[0]|. To get the vector between two pointers, we simply have to subtract the origin from the destination:

  v(p, q) = q - p

So:

  v(p, &p[i]) = &p[i] - p = (p + i) - p == i

These vectors fall into a natural algebraic relationship. Consider two indexes |i| and |j|, and the vectors between |p|, |&p[i]| and |&p[j]|. To help with readability, I'll alias |pi = &p[i]| and |pj = &p[j]|.

The vector from |p| to |pi| is |i|. The vector from |p| to |pj| is |j|. The vector from |pi| to |pj| is:

  v(pi, pj) = pj - pi = (p + j) - (p + i) = j - i

Plug this vector back in as an index from |pi|, and we get back to |pj| naturally:

  pi[v(pi, pj)] = (pi + v(pi, pj)) = (p + i) + (j - i) = p + j = pj

With one-based indexing, this algrebraic consistency breaks down. I'll use caps to distinguish the one-based indexing formulas from the zero-based indexing formulas. In the one-based scheme, |&P[I] == (P + (I - 1))|. Following from that:

  V(PI, PJ) = PJ - PI = (P + (J - 1)) - (P + (I - 1)) = (J - 1) - (I - 1) = J - I

So far so good. The vector calculation yields the same number! Great! Now let's plug it back in:

  PI[V(PI, PJ)] = (PI + (V(PI, PJ) - 1)) = (P + (I - 1)) + ((J - I) - 1) = P + J - 2 = PJ - 1

Nope! Indexing from |PI| with the vector from |PI| to |PJ| no longer takes you to |PJ|. Rather, it takes you to one element _before_ |PJ|.

The consistent, clear relationship between pointers and the vectors between them no longer holds. Vectors no longer compose. Composing two vectors no longer works, as the |-1| term compounds over each composition.

This is no small thing to lose. Algebras are extremely powerful ways of coherently describing the behaviour of systems. Losing these algebras means you lose their powerful regularity. Adding two vectors no longer yields the true composite vector. Multiplying a vector by a scalar no longer yields a scaled vector. At every vector addition or scaling, the programmer will be forced to adjust their result vectors to obtain the true composite vector. This is an enormous burden on the programmer.

Any programming language that imposes this burden on the programmer is simply wrong. We make languages so that it's easier for us, people, to reason about the behaviour of our programs. Destroying the algebraic relationship between pointers and the vectors between them is inexcusable. We may have experimented it during the early years of language development, but we know better now.

The above is just _one_ reason why zero-based indexing is, without a doubt, the correct approach. The other major reason has to do with the superiority of open intervals over that of closed intervals, and of the algebras over those intervals. I might write another comment on that if I get time, but the gist of it is the following (this is the thrust of Djikstra's argument in favour of zero-based indexing):

Zero-based indexing supports a notion of integer intervals that fall into a coherent algebraic framework of open intervals.

Adding to Dijkstra's argument, this notion of an algebra over open intervals is powerful because not only dose it capture integer intervals (array and pointer arithmetic in C and C++), but also can be extended to ranges over a variety of ordered containers (e.g. collections of arbitrary values), and of ordered infinite sets (e.g. the abstract set of all strings, or all JSON values, etc.). The most prominent implementation of this is C++'s STL ranges (there's a very good reason |container.end()| in C++ returns an iterator "past" the last item in the collection). Suffice it to say that for algebras over intervals, open intervals win over closed intervals.

However, I don't have time to write that novel right now ;)

presidentender• 13 years ago

I 'got' zero-based array indexing when I tried making a Tetris clone. If you try to sum Cartesian coordinates stored in an array whose index is 1-based, you have to do subtraction to reset the off-by-one error.

I can't describe the theory in any more detail than that; I don't even know what I'd have to study to describe the issue using technical vocabulary. But it just clicked for me.

dahart3• 13 years ago

  float b[4], *bb;
  bb=b-1;

Voila! I have a single array that is both zero-indexed and one-indexed, in C.

This destroys the argument about pointer arithmetic. Both arrays use exactly the same calculation to access.

Think this looks like a bad idea? That's opinion and convention, and nothing more. This code snippet comes from "Numerical Recipes in C, 2nd Ed.", in which they use one-based arrays in C frequently. In that edition, they also advocated switching on the fly :O. Later editions switched to zero-indexed arrays due to dominant convention.

"It is sometimes convenient to use zero-offset vectors, and sometimes convenient to use unit-offset vectors in algorithms. The choice should be whichever is most natural to the problem at hand." [NR, 2nd ed. pg 18. emphasis mine]

Context is the key to knowing which one is better, and neither one is best in all contexts. Saying zero indexed arrays are always better is like saying scrambled eggs are always better, it doesn't make sense without context, and its imposing an opinion that others may not share.

cliffbean6• 13 years ago

Read their explanation though:

"For example, the coefficients of a polynomial a0 + a1 x + a2 x2 + . . . + an xn clearly cry out for the zero-offset a[0..n], while a vector of N data points x i , i = 1 . . . N calls for a unit-offset x[1..N]"

The polynomial cries out for zero for a real mathematical reason. Zero really is more natural there. The vector of N data points "calls" for a unit-offset because, um, convention?

dragonwriter• 13 years ago

The vector of N data points "calls" for a unit-offset because, um, convention?

I think ordinality reflecting cardinality is, while a convention, more than a purely arbitrary convention. And even if it is a purely arbitrary convention, its one that is so pervasive in dealing with collections outside of computing that it is a cognitive burden not to match it in computing (its a cognitive burden that you get used to dealing with pretty quickly when you've been immersed in languages that don't support it naturally, but its a cognitive burden nonetheless.)

dahart3• 13 years ago

Yes, right! Again, "context is the key to knowing which one is better."

We are violently agreeing, we don't really need to twist words or attempt to disprove what might just be a poorly worded statement, right? We are all educated engineers here, and we can afford each other the benefit of the doubt, no? We both get it.

The important part of the point is that all the other arguments here about which choice is inherently more "natural" is somewhat bogus. Neither is inherently more natural, what is more natural depends on what you're trying to do.

In some cases, there isn't an obvious choice, that's where convention plays the biggest role, but having a default choice made for you doesn't make the convention better or more natural, it just makes it an arbitrary choice that everyone is used to.

jkcxn• 13 years ago

Imagine if we used different symbols for counting and indexing. I think Roman numerals would be good to use for indexing.

  arr[I + 0] = arr[I]
  arr[II + 3] = arr[V]
  arr[I - 10] = undefined

mtdewcmu10• 13 years ago

That's funny. Someone should implement Roman numerals in a real language.

The origin of zero-based array indexing

Related Stories