Why does C use zero-based indexing?

Many people find zero-based indexing difficult and non-intuitive. Why 
doesn't C start indices from 1 instead? This would be much easier for 
people.

   A. It doesn't. At least, it doesn't have to. See ISO/IEC 9899:1999 
6.5.2.1 'Array subscripting', which doesn't even mention zero-based 
indexing. The indexing base is implementation-defined, and is often 
configurable via a compiler switch, a bit like OPTION BASE 0 / OPTION BASE 
1 in various BASICs.
   B. An array index is merely another way of describing the number of 
objects that sit between the first element in the array and the element we 
wish to access. Clearly, if we are trying to access the first element, the 
number of objects between is 0, so it makes sense to use 0 as the array 
index for the first element.
   C. One-based indexing leads to unnecessarily complicated arithmetic, 
especially when dealing with multi-dimensional arrays. These complications 
just fall away into nothing if zero-based indexing is used.
   D. None of the above, because...

-- 
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

Richard Heathfield wrote:

> Why does C use zero-based indexing?
> 
> Many people find zero-based indexing difficult and non-intuitive. Why
> doesn't C start indices from 1 instead? This would be much easier for
> people.

<snip>

Because array access in C is done in terms of pointer arithmetic. If
indexing began with 1, compilers would very likely need to do an
unnecessary subtraction step in implementing the array access.

C aims to "deal with the same sort of abstractions" as real machines,
and most hardware architectures start memory addressing at zero. C
follows this for the sake of efficiency and logical clarity.

I think answer C is the one I would choose, if I had to do so.

On Dec 21, 11:35 am, Richard Heathfield <r...@see.sig.invalid> wrote:
> Why does C use zero-based indexing?
>
> Many people find zero-based indexing difficult and non-intuitive. Why
> doesn't C start indices from 1 instead? This would be much easier for
> people.
People that find the concept of "zero-based indexing" (which doesn't
even exist in C as you mentioned, it's pointer arith) should simply
avoid C.
Plus if that changes now, many C programs would break.
So.. no matter how much you complain and how many points you make, it
won't happen, not in C.

vippstar@gmail.com wrote:

> On Dec 21, 11:35 am, Richard Heathfield <r...@see.sig.invalid> wrote:
>> Why does C use zero-based indexing?
>>
>> Many people find zero-based indexing difficult and non-intuitive. Why
>> doesn't C start indices from 1 instead? This would be much easier for
>> people.
> People that find the concept of "zero-based indexing" (which doesn't
> even exist in C as you mentioned, it's pointer arith) should simply
> avoid C.
> Plus if that changes now, many C programs would break.

Would they? What if the compilers did the necessary translation. A
recompile would be all that's needed.

> So.. no matter how much you complain and how many points you make, it
> won't happen, not in C.

Perhaps you missed the wood for the trees? Richard started this thread
in respose to the other thread asking for regular "quiz" questions.
This is a quiz question. He is very well aware of the answer[s]
himself.

On Dec 21, 2:35 pm, Richard Heathfield <r...@see.sig.invalid> wrote:
> Why does C use zero-based indexing?
>
> Many people find zero-based indexing difficult and non-intuitive. Why
> doesn't C start indices from 1 instead? This would be much easier for
> people.
>
>    A. It doesn't. At least, it doesn't have to. See ISO/IEC 9899:1999
> 6.5.2.1 'Array subscripting', which doesn't even mention zero-based
> indexing. The indexing base is implementation-defined, and is often
> configurable via a compiler switch, a bit like OPTION BASE 0 / OPTION BASE
> 1 in various BASICs.
>    B. An array index is merely another way of describing the number of
> objects that sit between the first element in the array and the element we
> wish to access. Clearly, if we are trying to access the first element, the
> number of objects between is 0, so it makes sense to use 0 as the array
> index for the first element.
>    C. One-based indexing leads to unnecessarily complicated arithmetic,
> especially when dealing with multi-dimensional arrays. These complications
> just fall away into nothing if zero-based indexing is used.
>    D. None of the above, because...
>
> --
> Richard Heathfield <http://www.cpax.org.uk>
> Email: -http://www. +rjh@
> Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
> "Usenet is a strange place" - dmr 29 July 1999

I think it is option D.
C uses zero based indexing because it is easier for compiler writers
who like to think in terms of offsets.The starting element of an array
will have an offset of zero and so it is indexed zero.

Richard Heathfield wrote:
> Why does C use zero-based indexing?
> 
> Many people find zero-based indexing difficult and non-intuitive. Why 
> doesn't C start indices from 1 instead? This would be much easier for 
> people.
> 
>    A. It doesn't. At least, it doesn't have to. See ISO/IEC 9899:1999 
> 6.5.2.1 'Array subscripting', which doesn't even mention zero-based 
> indexing. The indexing base is implementation-defined, and is often 
> configurable via a compiler switch, a bit like OPTION BASE 0 / OPTION BASE 
> 1 in various BASICs.
>    B. An array index is merely another way of describing the number of 
> objects that sit between the first element in the array and the element we 
> wish to access. Clearly, if we are trying to access the first element, the 
> number of objects between is 0, so it makes sense to use 0 as the array 
> index for the first element.
>    C. One-based indexing leads to unnecessarily complicated arithmetic, 
> especially when dealing with multi-dimensional arrays. These complications 
> just fall away into nothing if zero-based indexing is used.
>    D. None of the above, because...
> 
D, the real reason is K&R starts from chapter 0.

-- 
Ian Collins.

santosh said:

> Perhaps you missed the wood for the trees? Richard started this thread
> in respose to the other thread asking for regular "quiz" questions.
> This is a quiz question. He is very well aware of the answer[s]
> himself.

Thanks, santosh. The question is already archived, btw - at 
http://www.cpax.org.uk/prg/portable/c/luca/luca0.php

but Flash's Wiki might be a better home?

-- 
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

On Dec 21, 1:35 am, Richard Heathfield <r...@see.sig.invalid> wrote:
> Why does C use zero-based indexing?
>
> Many people find zero-based indexing difficult and non-intuitive. Why
> doesn't C start indices from 1 instead? This would be much easier for
> people.

No.  Besides having an obvious tiling property, consider the following
problem:

Suppose you arrange a sorted list of numbers onto pages, 10 per page
in a book.  Now you want to take those same numbers and put them into
another list with 13 per page.  If an element was at position i on
page p of the first book, what page does it appear on in the second
book?

With 0-indexing the problem is just a bunch of simplistic modulo
arithmetic.  With 1-indexing, you have extra +1's and -1's and you
might have to special case the one of the end of each page (or at
least you have examine all the edge cases a lot more carefully to get
the mapping right.)

Over the years, I have run into this and similar problems for which I
am grateful for C's typical idiom of being 0-indexed rather than 1-
indexed.

I have recently started embracing the language Lua in a very serious
way. Unfortunately, they have chosen 1-based array indexing.  Or well,
not exactly, but many of their range idioms (for loops, etc.) are 1-
based instead of 0-based.  I find that its *mostly* not a problem,
until you have to solve a problem such as the one described above.
The way I solve it, is that I write pseudo-code for a 0-based array
solution, then translate it to 1-based, then simplify the arithmetic
and implement it -- I end up having slight "off by 1" adjustments
which are hard to explain in a just few comments.  (Its the only
really serious weakness I find in that language.)

--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/

In article <D5-dnUzxzIe7FfbanZ2dnUVZ8tninZ2d@bt.com>,
Richard Heathfield  <rjh@see.sig.invalid> wrote:

>Why does C use zero-based indexing?

Are you looking for a historical, teleological, or psychoanalytic
explanation?

I'll go with Bismarck's comment on the Franco-Prussian war: it was in
the logic of history.

-- Richard
-- 
:wq

Richard Heathfield wrote:
> 
> Why does C use zero-based indexing?
> 
> Many people find zero-based indexing difficult and non-intuitive. Why
> doesn't C start indices from 1 instead? This would be much easier for
> people.
> 
>    A. It doesn't. At least, it doesn't have to. See ISO/IEC 9899:1999
> 6.5.2.1 'Array subscripting', which doesn't even mention zero-based
> indexing. The indexing base is implementation-defined, and is often
> configurable via a compiler switch,
> a bit like OPTION BASE 0 / OPTION BASE
> 1 in various BASICs.
>    B. An array index is merely another way of describing the number of
> objects that sit between the first element in the array and the 
> element we
> wish to access. Clearly,
> if we are trying to access the first element, the
> number of objects between is 0, so it makes sense
> to use 0 as the array
> index for the first element.
>    C. One-based indexing leads to unnecessarily complicated 
> arithmetic,
> especially when dealing with multi-dimensional arrays. These > complications
> just fall away into nothing if zero-based indexing is used.
>    D. None of the above, because...

E. All of the above(including choice D.)

Concerning the original premise:
"Many people find zero-based indexing difficult and non-intuitive."

Zero-based indexing is non-intuitive.
First Prize has a number one on it.
Ordinarilly we expect that the third and fourth
will be numbered as three and four.

As for zero-based indexing being difficult,
I think that's more of a phobia than a real problem,
as is suggested by choice C.

-- 
pete

On 21 Dec, 09:35, Richard Heathfield <r...@see.sig.invalid> wrote:
> Why does C use zero-based indexing?
>
> Many people find zero-based indexing difficult and non-intuitive. Why
> doesn't C start indices from 1 instead? This would be much easier for
> people.
>
> =A0 =A0A. It doesn't. At least, it doesn't have to. See ISO/IEC 9899:1999
> 6.5.2.1 'Array subscripting', which doesn't even mention zero-based
> indexing. The indexing base is implementation-defined, and is often
> configurable via a compiler switch, a bit like OPTION BASE 0 / OPTION BASE=

> 1 in various BASICs.
> =A0 =A0B. An array index is merely another way of describing the number of=

> objects that sit between the first element in the array and the element we=

> wish to access. Clearly, if we are trying to access the first element, the=

> number of objects between is 0, so it makes sense to use 0 as the array
> index for the first element.
> =A0 =A0C. One-based indexing leads to unnecessarily complicated arithmetic=
,
> especially when dealing with multi-dimensional arrays. These complications=

> just fall away into nothing if zero-based indexing is used.
> =A0 =A0D. None of the above, because...

You've missed one possible answer...

C uses zero-based indexing because BCPL uses zero-based indexing and
because this wasn't changed when BCPL was changed into C.

Incidentally, BCPL's handling of arrays was a little different from
C's. The statement LET V =3D VEC 5 would actually reserve 6 consecutive
locations, so you could use indexes of 0-4 or 1-5 or even 0-5 if you
wanted to. For good measure, it also created a variable V as well,
which started off pointing at the 6 reserved locations but could be
made to point elsewhere if you wanted...

I'm replying before reading any response, to prevent my answer being 
prejudiced by them.

Richard Heathfield wrote:
> Why does C use zero-based indexing?
> 
> Many people find zero-based indexing difficult and non-intuitive. Why 
> doesn't C start indices from 1 instead? This would be much easier for 
> people.
> 
>    A. It doesn't. At least, it doesn't have to. See ISO/IEC 9899:1999 
> 6.5.2.1 'Array subscripting', which doesn't even mention zero-based 
> indexing. The indexing base is implementation-defined, and is often 
> configurable via a compiler switch, a bit like OPTION BASE 0 / OPTION BASE 
> 1 in various BASICs.

This is nonsense, at least according to n1256 and n869. Both say that 
x[i] is equivalent to (*((x)+(i))), and when i == 0, x[0] == *x. If x is 
an array, in this context x decays to a pointer to its first member, and 
dereferencing that pointer yields the lvalue of the first member.

[Explanation of n-numbers: The official C Standards cost money, but you 
can get draft C standards for free. n869 is the name of the last draft 
before C99, and n1256 is the current latest draft, which is C99 plus 
Technical Corrigenda TC1,TC2 and TC3. The drafts are useful for general 
knowledge, but since the Standard is final and definitive, 
implementations should be judged against that. ISO/IEC 9899:1999 above 
refers to the C99 standard.]

>    B. An array index is merely another way of describing the number of 
> objects that sit between the first element in the array and the element we 
> wish to access. Clearly, if we are trying to access the first element, the 
> number of objects between is 0, so it makes sense to use 0 as the array 
> index for the first element.

Another way of saying this is that array subscripts are offsets rather 
than indices - they are a measure of distance, not a count. However this 
solution merely defines the problem away - if we give array indices a 
definition which requires them to be zero-indexed, then of course they 
should be zero-indexed!

This is not a justification for zero-based indexing, but it /is/ a 
useful way of thinking of C indices.

>    C. One-based indexing leads to unnecessarily complicated arithmetic, 
> especially when dealing with multi-dimensional arrays. These complications 
> just fall away into nothing if zero-based indexing is used.

I can't imagine how. Here is a loop over a multidimensional array:
for(i = 0; i < isize; i++)
    for(j = 0; j < jsize; j++)
       for(k = 0; k < ksize; k++)
          f(x[i][j][k]);

In a C where arrays are indexed from one, the same loop is as follows:
for(i = 1; i <= isize; i++)
    for(j = 1; j <= jsize; j++)
       for(k = 1; k <= ksize; k++)
          f(x[i][j][k]);

Perhaps this answer is referring to multidimensional arrays which are 
faked through single-dimension arrays, in a manner such as:

x[i*rowsize+j]

which accesses the cell at (i,j) where 0 <= i < rowsize and 0 <= j < 
colsize, and x has size rowsize*colsize. The same index calculation for 
one-based arrays is:

x[(i-1)*rowsize+j]

where 1 <= i <= rowsize and 1 <= j <= colsize.

The abstract machine has to implement different rules to implement the 
one-based indexing. Here x[n] is equivalent to *(x+n-1), so every array 
access adds one decrement operation to each array subscript. This is 
intrinsic in the fact that arrays in C are almost equivalent to pointers 
to the first element of an array.

>    D. None of the above, because...

If we accept the rule that C arrays decay to 
pointers-to-the-first-element, then answer C. above shows why it is 
logical for x[0] to be equivalent to *(x+0). Because C is a systems 
language, and not only provides pointers but relies on them to 
implmement arrays, it is natural that its arrays be zero-indexed.

Other languages are able to be one-indexed because their focus is 
different; the arithmetic inefficiencies introduced by one-based 
indexing either do not arise or are inconsequential compared to making 
the language more familiar to those who prefer one-based indexing (such 
as mathematicians).

Old versions of Perl allowed you to change the starting array index 
through the $[ variable. It defaulted to 0, but allowed you to change it 
to 1 to make it more familiar to awk and Fortran users. This is now 
deprecated as a Bad Idea.

Philip Potter said:

> I'm replying before reading any response, to prevent my answer being
> prejudiced by them.

I think I could give you 1.5 / 3, Philip. I don't think you read B closely 
enough. (B is not quite as nonsensical as A, but it's still wrong.)

-- 
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

gw7rib@aol.com wrote:
> On 21 Dec, 09:35, Richard Heathfield <r...@see.sig.invalid> wrote:
>> Why does C use zero-based indexing?
>>
>> Many people find zero-based indexing difficult and non-intuitive. Why
>> doesn't C start indices from 1 instead? This would be much easier for
>> people.
....
>>    D. None of the above, because...
> 
> You've missed one possible answer...

That's covered by D.

> C uses zero-based indexing because BCPL uses zero-based indexing and
> because this wasn't changed when BCPL was changed into C.

That merely moves the question back one step. Why did BCPL use 
zero-based indexing? Keep recursing backwards as needed until you find 
an actual reason.

Richard Heathfield wrote:
> Philip Potter said:
> 
>> I'm replying before reading any response, to prevent my answer being
>> prejudiced by them.
> 
> I think I could give you 1.5 / 3, Philip. I don't think you read B closely 
> enough. (B is not quite as nonsensical as A, but it's still wrong.)

Your stock answer merely shows that the language is woolly, but I 
consider my interpretation to be as valid as yours. "between" is a 
frequently misused preposition, and so I tend to infer what the writer 
meant rather than read what the writer literally said.

I don't think that B is "Not far off" as your stock answer says, because 
even when the wording is corrected [1], it just defines the problem away 
rather than justifying the design of the language. The problem is 
reduced to "Why are indices defined as another way of describing the 
number of elements preceding the element we wish to access?" but not 
solved properly. Note that other languages are quite happy with other 
definitions for indices, so this definition is not obviously correct. As 
a result, I would not give you full marks either.

(How come noone else has been given marks?)

[1] To something like "An array index describes the number of elements 
preceding the element we wish to access".

Philip Potter said:

> "between" is a
> frequently misused preposition, and so I tend to infer what the writer
> meant rather than read what the writer literally said.

But the writer was ME! So I don't need to infer anything; I know 
*precisely* what the author meant, and I wrote precisely what I intended 
to write (i.e. a not-quite-right answer).

Incidentally, regardless of the frequent errors of others, I am not 
accustomed to misusing "between". I make no claim to perfection in all 
matters, but I do know what "between" means.

> I would not give you full marks either.

Neither would I, so we are in full agreement there.

> (How come noone else has been given marks?)

Cos you and me, we da smart ones, dat why.

-- 
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

Richard Heathfield wrote:
> Philip Potter said:
> 
>> "between" is a
>> frequently misused preposition, and so I tend to infer what the writer
>> meant rather than read what the writer literally said.
> 
> But the writer was ME! So I don't need to infer anything; I know 
> *precisely* what the author meant, and I wrote precisely what I intended 
> to write (i.e. a not-quite-right answer).

But that's not what it is. It's not not-quite-right, for reasons which 
I've already explained.

>> I would not give you full marks either.
> 
> Neither would I, so we are in full agreement there.

:)

>> (How come noone else has been given marks?)
> 
> Cos you and me, we da smart ones, dat why.

*bangs rocks together*

On Fri, 21 Dec 2007 09:35:36 +0000, Richard Heathfield
<rjh@see.sig.invalid> wrote:

>Why does C use zero-based indexing?
>
>Many people find zero-based indexing difficult and non-intuitive. Why 
>doesn't C start indices from 1 instead? This would be much easier for 
>people.
>
>   A. It doesn't. At least, it doesn't have to. See ISO/IEC 9899:1999 
>6.5.2.1 'Array subscripting', which doesn't even mention zero-based 
>indexing. The indexing base is implementation-defined, and is often 
>configurable via a compiler switch, a bit like OPTION BASE 0 / OPTION BASE 
>1 in various BASICs.
>   B. An array index is merely another way of describing the number of 
>objects that sit between the first element in the array and the element we 
>wish to access. Clearly, if we are trying to access the first element, the 
>number of objects between is 0, so it makes sense to use 0 as the array 
>index for the first element.
>   C. One-based indexing leads to unnecessarily complicated arithmetic, 
>especially when dealing with multi-dimensional arrays. These complications 
>just fall away into nothing if zero-based indexing is used.
>   D. None of the above, because...

D - Historical.  Whether to use 0 based or 1 based is a language
design question.  I can't find my copy of Dijkstra at the moment
but he had some marvelously snarky comments about why 0 based is
better.  Fortran used 1 based, though I believe that the later
versions let you use anything you like.  I have the impression
that Algol used 0 based and that BCPL was out of the Algol
tradition.

As to the arguments one way or another, in 0 based an index is an
offset, in 1 based it is an ordinal number.  The reason that
ordinals are 1 based is because that way they map directly to
cardinal numbers, i.e., the nth item in a series is the last of n
items.  This is more convenient and less confusing in ordinary
usage, though not, perhaps, in programming.

Paul Hsieh wrote:
> On Dec 21, 1:35 am, Richard Heathfield <r...@see.sig.invalid> wrote:
>> Why does C use zero-based indexing?
>>
>> Many people find zero-based indexing difficult and non-intuitive. Why
>> doesn't C start indices from 1 instead? This would be much easier for
>> people.
> 
> No.  [...]

     Well, *some* people find it difficult.  I've seen more
than one Heapsort implementation whose authors seemed to
regard one-based indexing as algorithmically indispensable.
(It isn't, of course, but ...)

> I have recently started embracing the language Lua in a very serious
> way.

     I hope that she reciprocates your feeling and that
your intentions are honorable.  ;-)

-- 
Eric.Sosman@sun.com

On Dec 21, 8:30 pm, c...@tiac.net (Richard Harter) wrote:

> D - Historical.  Whether to use 0 based or 1 based is a language
> design question.  I can't find my copy of Dijkstra at the moment
> but he had some marvelously snarky comments about why 0 based is
> better.

This might be what you are talking about:
link: http://www.cs.utexas.edu/users/EWD/transcriptions/EWD08xx/EWD831.html

However according to the book "Expert C Programming, Deep C Secrets"
zero based indexing was put just for the benefit of compiler writers.

Richard Heathfield <rjh@see.sig.invalid> wrote:
# Why does C use zero-based indexing?
# 
# Many people find zero-based indexing difficult and non-intuitive. Why 
# doesn't C start indices from 1 instead? This would be much easier for 
# people.

#include <stdio.h>

#define array(lwb,upb,Element,name) \
	Element name##_ARRAY[(upb)-(lwb)+1], \
	*name = name##_ARRAY-(lwb)

int main(int N,char **P) {
	array(1,5,int,twice); int i;
	for (i=1; i<=5; i++) twice[i] = 2*i;
	for (i=1; i<=5; i++) printf("i=%d twice=%d\n",i,twice[i]);
	return 0;
}

--
SM Ryan http://www.rawbw.com/~wyrmwif/
I think that's kinda of personal; I don't think I should answer that.

SM Ryan wrote:
> Richard Heathfield <rjh@see.sig.invalid> wrote:
> # Why does C use zero-based indexing?
> # 
> # Many people find zero-based indexing difficult and non-intuitive. Why 
> # doesn't C start indices from 1 instead? This would be much easier for 
> # people.
> 
> #include <stdio.h>
> 
> #define array(lwb,upb,Element,name) \
> 	Element name##_ARRAY[(upb)-(lwb)+1], \
> 	*name = name##_ARRAY-(lwb)
> 
> int main(int N,char **P) {
> 	array(1,5,int,twice); int i;
> 	for (i=1; i<=5; i++) twice[i] = 2*i;
> 	for (i=1; i<=5; i++) printf("i=%d twice=%d\n",i,twice[i]);
> 	return 0;
> }

Undefined behaviour. The offending expression is twice_ARRAY-(1).

n1256 6.5.6p9 states "If both the pointer operand and the result point 
to elements of the same array object, or one past the last element of 
the array object, the evaluation shall not produce an overflow; 
otherwise, the behavior is undefined."

Phil

On Fri, 21 Dec 2007 08:15:42 -0800 (PST), harsha
<harsha.dsh@gmail.com> wrote:

>On Dec 21, 8:30 pm, c...@tiac.net (Richard Harter) wrote:
>
>> D - Historical.  Whether to use 0 based or 1 based is a language
>> design question.  I can't find my copy of Dijkstra at the moment
>> but he had some marvelously snarky comments about why 0 based is
>> better.
>
>This might be what you are talking about:
>link: http://www.cs.utexas.edu/users/EWD/transcriptions/EWD08xx/EWD831.html

Probably - it's been a decade or two since I've read the book.  I
have the vague impression that that wasn't the only time he
discussed the subject.

>
>However according to the book "Expert C Programming, Deep C Secrets"
>zero based indexing was put just for the benefit of compiler writers.

In article <D5-dnUzxzIe7FfbanZ2dnUVZ8tninZ2d@bt.com>,
Richard Heathfield  <rjh@see.sig.invalid> wrote:
>Why does C use zero-based indexing?
>
>Many people find zero-based indexing difficult and non-intuitive. Why 
>doesn't C start indices from 1 instead? This would be much easier for 
>people.
>
>   A. It doesn't. At least, it doesn't have to. See ISO/IEC 9899:1999 
>6.5.2.1 'Array subscripting', which doesn't even mention zero-based 
>indexing. The indexing base is implementation-defined, and is often 
>configurable via a compiler switch, a bit like OPTION BASE 0 / OPTION BASE 
>1 in various BASICs.
>   B. An array index is merely another way of describing the number of 
>objects that sit between the first element in the array and the element we 
>wish to access. Clearly, if we are trying to access the first element, the 
>number of objects between is 0, so it makes sense to use 0 as the array 
>index for the first element.
>   C. One-based indexing leads to unnecessarily complicated arithmetic, 
>especially when dealing with multi-dimensional arrays. These complications 
>just fall away into nothing if zero-based indexing is used.
>   D. None of the above, because...

It falls naturally out of the definition of array indexing in terms of
pointer arithmetic.
This is close enough to (B) that I'm not going to commit to whether I'm
giving an explanation of (B) or a completion of (D) without more
coffee.

This isn't quite a reason for why array indexing was defined that way,
though.  I suspect that the root cause is "because B/BCPL/the PDP-11
did it that way and nobody thought it was worth changing since".


dave

On 2007-12-21, dj3vande@csclub.uwaterloo.ca.invalid <dj3vande@csclub.uwaterloo.ca.invalid> wrote:
> In article <D5-dnUzxzIe7FfbanZ2dnUVZ8tninZ2d@bt.com>,
> Richard Heathfield  <rjh@see.sig.invalid> wrote:
>>Why does C use zero-based indexing?
>>
>>Many people find zero-based indexing difficult and non-intuitive. Why 
>>doesn't C start indices from 1 instead? This would be much easier for 
>>people.
>>
>>   A. It doesn't. At least, it doesn't have to. See ISO/IEC 9899:1999 
>>6.5.2.1 'Array subscripting', which doesn't even mention zero-based 
>>indexing. The indexing base is implementation-defined, and is often 
>>configurable via a compiler switch, a bit like OPTION BASE 0 / OPTION BASE 
>>1 in various BASICs.
>>   B. An array index is merely another way of describing the number of 
>>objects that sit between the first element in the array and the element we 
>>wish to access. Clearly, if we are trying to access the first element, the 
>>number of objects between is 0, so it makes sense to use 0 as the array 
>>index for the first element.
>>   C. One-based indexing leads to unnecessarily complicated arithmetic, 
>>especially when dealing with multi-dimensional arrays. These complications 
>>just fall away into nothing if zero-based indexing is used.
>>   D. None of the above, because...
>
> It falls naturally out of the definition of array indexing in
> terms of pointer arithmetic. This is close enough to (B) that
> I'm not going to commit to whether I'm giving an explanation of
> (B) or a completion of (D) without more coffee.

No, B is actually nonsense. Yes, there are no elements between
the first and the first element. But there are *also* no elements
between the first and the second element.

> This isn't quite a reason for why array indexing was defined
> that way, though.  I suspect that the root cause is "because
> B/BCPL/the PDP-11 did it that way and nobody thought it was
> worth changing since".

I think the fact that array indexing is syntactic sugar for
pointer arithmetic neatly explains the reasoning. Imagine using
pointer arithmetic if a + 1 equaled a.

-- 
Neil Cerutti

santosh wrote:
> 
> vippstar@gmail.com wrote:
> 
> > On Dec 21, 11:35 am, Richard Heathfield <r...@see.sig.invalid> wrote:
> >> Why does C use zero-based indexing?
> >>
> >> Many people find zero-based indexing difficult and non-intuitive. Why
> >> doesn't C start indices from 1 instead? This would be much easier for
> >> people.
> > People that find the concept of "zero-based indexing" (which doesn't
> > even exist in C as you mentioned, it's pointer arith) should simply
> > avoid C.
> > Plus if that changes now, many C programs would break.
> 
> Would they? What if the compilers did the necessary translation. A
> recompile would be all that's needed.

Are you sure?

What happens with for-loops starting at zero, and using the loop
variable as a subscript?

If "p[1]" is now the first element, what does "p[0]" mean?

What happens when "*p" and "p[1]" now mean the same thing?

What happens when "*(p+1)" and "p[1]" now mean different things?

> > So.. no matter how much you complain and how many points you make, it
> > won't happen, not in C.
> 
> Perhaps you missed the wood for the trees? Richard started this thread
> in respose to the other thread asking for regular "quiz" questions.
> This is a quiz question. He is very well aware of the answer[s]
> himself.


-- 
+-------------------------+--------------------+-----------------------+
| Kenneth J. Brody        | www.hvcomputer.com | #include              |
| kenbrody/at\spamcop.net | www.fptech.com     |    <std_disclaimer.h> |
+-------------------------+--------------------+-----------------------+
Don't e-mail me at: <mailto:ThisIsASpamTrap@gmail.com>

In article <slrnfmo14g.1dg.horpner@FIAD06.norwich.edu>,
Neil Cerutti  <horpner@yahoo.com> wrote:
>On 2007-12-21, dj3vande@csclub.uwaterloo.ca.invalid
><dj3vande@csclub.uwaterloo.ca.invalid> wrote:
>> In article <D5-dnUzxzIe7FfbanZ2dnUVZ8tninZ2d@bt.com>,
>> Richard Heathfield  <rjh@see.sig.invalid> wrote:
>>>Why does C use zero-based indexing?

[...]
>>>   B. An array index is merely another way of describing the number of 
>>>objects that sit between the first element in the array and the element we 
>>>wish to access. Clearly, if we are trying to access the first element, the 
>>>number of objects between is 0, so it makes sense to use 0 as the array 
>>>index for the first element.


>> It falls naturally out of the definition of array indexing in
>> terms of pointer arithmetic. This is close enough to (B) that
>> I'm not going to commit to whether I'm giving an explanation of
>> (B) or a completion of (D) without more coffee.
>
>No, B is actually nonsense. Yes, there are no elements between
>the first and the first element. But there are *also* no elements
>between the first and the second element.

Ahh.  Yes, I was reading "between the first element in the array
and..." as "between the beginning of the array and...".

So it looks like I was at least right about needing more coffee.


dave

cri@tiac.net (Richard Harter) writes:

> D - Historical.  Whether to use 0 based or 1 based is a language
> design question.  I can't find my copy of Dijkstra at the moment
> but he had some marvelously snarky comments about why 0 based is
> better.  Fortran used 1 based, though I believe that the later
> versions let you use anything you like.  I have the impression
> that Algol used 0 based and that BCPL was out of the Algol
> tradition.

Algol had VLA with index starting where you wanted.  Far more sophisticated
than C
 
See http://www.fh-jena.de/~kleine/history/languages/Algol60-Naur.pdf

-- 
Jean-Marc

James Kuyper wrote:
> 
> gw7rib@aol.com wrote:
> > On 21 Dec, 09:35, Richard Heathfield <r...@see.sig.invalid> wrote:
> >> Why does C use zero-based indexing?
> >>
> >> Many people find zero-based indexing difficult and non-intuitive. Why
> >> doesn't C start indices from 1 instead? This would be much easier for
> >> people.
> ...
> >>    D. None of the above, because...
> >
> > You've missed one possible answer...
> 
> That's covered by D.
> 
> > C uses zero-based indexing because BCPL uses zero-based indexing and
> > because this wasn't changed when BCPL was changed into C.
> 
> That merely moves the question back one step. Why did BCPL use
> zero-based indexing? Keep recursing backwards as needed until you find
> an actual reason.

Well, let's all go back to day zero...

In the beginning Brian created the stdio.h and the main().

And the main() was without form, and void; and darkness was
upon the face of the kernel. And the Spirit of Brian moved upon
the face of the kernel.

And Brian said, Let there be int and there was int main().

And Brian saw the int, that it was good: and Brian divided the
int from the void.

-- 
+-------------------------+--------------------+-----------------------+
| Kenneth J. Brody        | www.hvcomputer.com | #include              |
| kenbrody/at\spamcop.net | www.fptech.com     |    <std_disclaimer.h> |
+-------------------------+--------------------+-----------------------+
Don't e-mail me at: <mailto:ThisIsASpamTrap@gmail.com>

Richard Heathfield wrote, On 21/12/07 10:05:
> santosh said:
> 
>> Perhaps you missed the wood for the trees? Richard started this thread
>> in respose to the other thread asking for regular "quiz" questions.
>> This is a quiz question. He is very well aware of the answer[s]
>> himself.
> 
> Thanks, santosh. The question is already archived, btw - at 
> http://www.cpax.org.uk/prg/portable/c/luca/luca0.php
> 
> but Flash's Wiki might be a better home?

I don't claim to own the Wiki, I only provide the server it runs on. 
Having said that, yes, I think the Wiki would be a good home. Then 
others who want to post more questions can do so.
-- 
Flash Gordon

On Dec 21, 9:35=A0am, Richard Heathfield <r...@see.sig.invalid> wrote:
> Why does C use zero-based indexing?

You claim that many people find zero-based indexing counter-intuitive.
Many people find any kind of indexing non-intuitive. However, look
back a few years. How many people were convinced that this millennium
started on Jan. 1st 2000 instead of Jan. 1st 2001? They just couldn't
understand that years form a one-based array.

Now seriously. If we wanted to have non-zero based arrays, they could
easily be added to C in a backwards compatible way. I won't try to
write down the syntax, but you could have

  int a [1 : 10];

mean an array with ten elements, indexed from 1 to 10. And

  int b [1900 : 2100, -5 : 5];

could mean a two-dimensional array of 201 x 11 elements, with the
first index ranging from 1900 to 2100, the second index from -5 to 5.
Such an array could only be used with the array [] operator, and for
multi-dimensional arrays (or all arrays with lower and upper bound),
comma expressions would not be allowed for indices, same as for
function parameters.

It wouldn't be possible to (reasonably) have an assignment

  int *p =3D a;

Either p would point to the first array element, in which case p[0]
and a[1] would refer to the same array element, which would be more
than weird. On the other hand, p cannot be a pointer to int with the
property that p[1] and a[1] point to the same array element, because
you cannot have a pointer p such that p+1 points to the first element
of an array.

You could obviously write

  int *p =3D &a [1];

which would work as everyone thinks. So with the "enhanced" array
syntax, you wouldn't get automatic decay from array to pointer, and
you wouldn't get the automatic decay from parameters looking like
arrays to parameters of pointer type.

In article <476bd84c.240428374@news.sbtc.net> cri@tiac.net (Richard Harter) writes:
....
 >                                          I have the impression
 > that Algol used 0 based and that BCPL was out of the Algol
 > tradition.

In Algol 60 you could use any base.  Actually, in the array declaration
you had to supply both lower- and upper-bound of the index.  Algol 68
was similar, but when the bound pair started with "1:", the "1:" could be
omitted.  I do not think Algol 58 (from which BCPL derives) was sufficiently
developed to have any idea about it.
-- 
dik t. winter, cwi, kruislaan 413, 1098 sj  amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn  amsterdam, nederland; http://www.cwi.nl/~dik/

"santosh" <santosh.k83@gmail.com> wrote in message
news:fkg1mc$moe$1@registered.motzarella.org...
> Richard Heathfield wrote:
>
>> Why does C use zero-based indexing?

> <snip>
>
> Because array access in C is done in terms of pointer arithmetic. If
> indexing began with 1, compilers would very likely need to do an
> unnecessary subtraction step in implementing the array access.

This is a fallacy. Sometimes, an offset may incur a runtime penalty, but so
what? And it would be 'offset' by not needing a -1 in user code sometimes.

Having a choice of 0- or 1-based wouldn't have been difficult and would have
kept everyone happy except those wanting any base.

>
> C aims to "deal with the same sort of abstractions" as real machines,
> and most hardware architectures start memory addressing at zero. C
> follows this for the sake of efficiency and logical clarity.

Processors also have means for applying offsets to addresses.

>
> I think answer C is the one I would choose, if I had to do so.

I would have said D (or F on the link), because 1-based (or a mix) would
have upset the special relationship between arrays and pointer arithmetic.

Bart

On Dec 21, 1:32=A0pm, Philip Potter <p...@doc.ic.ac.uk> wrote:
> Richard Heathfield wrote:
> > Why does C use zero-based indexing?
>
> > =A0 =A0C. One-based indexing leads to unnecessarily complicated arithmet=
ic,
> > especially when dealing with multi-dimensional arrays. These complicatio=
ns
> > just fall away into nothing if zero-based indexing is used.
>
> I can't imagine how. Here is a loop over a multidimensional array:
> for(i =3D 0; i < isize; i++)
> =A0 =A0 for(j =3D 0; j < jsize; j++)
> =A0 =A0 =A0 =A0for(k =3D 0; k < ksize; k++)
> =A0 =A0 =A0 =A0 =A0 f(x[i][j][k]);
>
> In a C where arrays are indexed from one, the same loop is as follows:
> for(i =3D 1; i <=3D isize; i++)
> =A0 =A0 for(j =3D 1; j <=3D jsize; j++)
> =A0 =A0 =A0 =A0for(k =3D 1; k <=3D ksize; k++)
> =A0 =A0 =A0 =A0 =A0 f(x[i][j][k]);
>
> Perhaps this answer is referring to multidimensional arrays which are
> faked through single-dimension arrays, in a manner such as:
>
> x[i*rowsize+j]
>
> which accesses the cell at (i,j) where 0 <=3D i < rowsize and 0 <=3D j <
> colsize, and x has size rowsize*colsize. The same index calculation for
> one-based arrays is:
>
> x[(i-1)*rowsize+j]
>
> where 1 <=3D i <=3D rowsize and 1 <=3D j <=3D colsize.

Or in cases where one has to transform from 2-dimensional
to 1-dimensional arrays and vice versa. Once I was helping
a statistician friend who's rather weak at programming to
write some programmes in Matlab, a language I don't actually
know. As far as I could tell Matlab has fully fledged
multi-dimensional arrays , you don't have to fake anything,
but arrays are 1 based. As part of his statistical
manipulations he often had to transform from 2-d to 1-d or
vice versa and these 1-off corrections were driving me crazy.

Paul Hsieh also gave a good example elsethread.

> Other languages are able to be one-indexed because their focus is
> different; the arithmetic inefficiencies introduced by one-based
> indexing either do not arise or are inconsequential compared to making
> the language more familiar to those who prefer one-based indexing (such
> as mathematicians).

What makes you think that mathematicians prefer 1-based ?
I'm one and I prefer 0-based.

> Old versions of Perl allowed you to change the starting array index
> through the $[ variable. It defaulted to 0, but allowed you to change it
> to 1 to make it more familiar to awk and Fortran users.

Arrays in awk start from 1 ? That's news to me , the versions
of awk I'm familiar with use associative arrays so a "start"
cannot be defined in a natural way.


Any discussion on where array indexing should start ought
to mention the well known quote by Stan Kelly-Bootle:

"Should array indices start at 0 or 1? My compromise of
0.5 was  rejected without, I thought, proper consideration."

On Sat, 22 Dec 2007 04:38:06 -0800 (PST), Spiros Bousbouras
<spibou@gmail.com> wrote:

> On Dec 21, 1:32�pm, Philip Potter <p...@doc.ic.ac.uk> wrote:

> > Old versions of Perl allowed you to change the starting array index
> > through the $[ variable. It defaulted to 0, but allowed you to change it
> > to 1 to make it more familiar to awk and Fortran users.
> 
> Arrays in awk start from 1 ? That's news to me , the versions
> of awk I'm familiar with use associative arrays so a "start"
> cannot be defined in a natural way.
> 
A few language-defined ones are integers:
  ARGV [1..ARGC]
  the result of split()
  (in gawk) the result of asort() and asorti()
  $1..NF if you count that as an array (it is in perl FWTW)

and (as a result?) IME it is usual (but not required) for user-defined
arrays whose indices _are_ an integer range to be 1-based.

- formerly david.thompson1 || achar(64) || worldnet.att.net