pattis@june.cs.washington.edu (Richard Pattis) (03/03/88)
I too detest 0-based arrays (and think 1-based arrays are better). In trying to rationalize this choice, I came up the the following argument: When we process arrays, we often need to know the size of the array and/or the position of the last element. In 0-based arrays, these quantites are off by one; in 1-based arrays they are the same. Hence, I think that people will make fewer errors with 1-based arrays. Rich Pattis
karl@haddock.ISC.COM (Karl Heuer) (03/03/88)
In article <4343@june.cs.washington.edu> pattis@june.cs.washington.edu (Richard Pattis) writes: >I too detest 0-based arrays (and think 1-based arrays are better). In trying >to rationalize this choice, I came up the the following argument: When we >process arrays, we often need to know the size of the array and/or the >position of the last element. In 0-based arrays, these quantites are off by >one; in 1-based arrays they are the same. Hence, I think that people will >make fewer errors with 1-based arrays. When dealing with 0-based arrays, the appropriate concept is a half-open interval: the index for an N-element array comes from [0,N). I find that this makes things simpler than with 1-based arrays, because half-open intervals can be abutted without having to adjust by one. (I.e., [0,N) U [N,P) = [0,P).) I very seldom need to know the position of the last element. Instead, I use the position of the first element beyond the array. Always use postincrement and/or predecrement to traverse it; everything works out fine. Karl W. Z. Heuer (ima!haddock!karl or karl@haddock.isc.com), The Walking Lint
conor@goose.UUCP (Conor Rafferty) (03/03/88)
Sender:
Reply-To:
Followup-To:
If you have a circular list of length n stored as an array,
the increment-and-wrap operation on the index is
0-based 1-based
i = (i+1)%n i = i%n+1
Walking with a stride of three looks like
for (j = 0; j < n/3; j++) for (j = 1; j <= n/3; j++)
frob( a[3*j]); frob( a[3*(j-1)+1])
In both cases the 0-based code looks more intuitive to me.pds@quintus.UUCP (Peter Schachte) (03/04/88)
In article <2851@haddock.ISC.COM>, karl@haddock.ISC.COM (Karl Heuer) writes: > When dealing with 0-based arrays, the appropriate concept is a half-open > interval: the index for an N-element array comes from [0,N). I find that this > makes things simpler than with 1-based arrays, because half-open intervals can > be abutted without having to adjust by one. (I.e., [0,N) U [N,P) = [0,P).) How is that any different than for 1-based arrays? [1,N) U [N,P) = [1,P), non? In both of the rebuttals to the pro-1-based-array postings, I didn't see anything that said where 1-based arrays fall down. The only problem I see with them is efficiency: you have to subtract 1 (or 2 or 4 or sizeof(element)) when you index into the array. Or do you? There's nothing to say that the compiler can't actually allocate an array one element bigger than you ask for, and just waste the first element, is there? If you've got the memory to burn. C, of course would be in trouble with this approach, since arrays in C are so often traversed by pointer manipulation. But in languages that don't allow this (and, I hope, their compilers produce similar code anyway), there shouldn't be a problem. As someone said, one-based arrays often seem more natural. I want to store 10 of these things. So I allocate a ten element array. Now, quick, which is the last element? Number NINE? Huh? -- -Peter Schachte pds@quintus.uucp ...!sun!quintus!pds
barmar@think.COM (Barry Margolin) (03/05/88)
In article <35@goose.UUCP> writes: [First example elided] >Walking with a stride of three looks like > 0-based 1-based > for (j = 0; j < n/3; j++) for (j = 1; j <= n/3; j++) > frob( a[3*j]); frob( a[3*(j-1)+1]) >In both cases the 0-based code looks more intuitive to me. And neither looks as intuitive as: for (j = {0,1}; j {<,<=} n; j = j+3) frob (a[j]); does to me (where {X,Y} means to use X in 0-based and Y in 1-based). Barry Margolin Thinking Machines Corp. barmar@think.com uunet!think!barmar
kjepo@amnesix.liu.se (Kjell Post) (03/07/88)
As long as mod returns 0 I will have 0-based arrays!
--
-------------------------------------------------------------------------------
(Y F) = (F (Y F)) |Dept of Comp&Info Science, Linkoping Sweden
"This super-amazing, clever thing" | kjepo@majestix.liu.se
- G.J. Sussman | ...liuida!majestix.liu.se!kjepocsnjr@its63b.ed.ac.uk (Nick Rothwell) (03/07/88)
In article <726@sandino.quintus.UUCP> pds@quintus.UUCP (Peter Schachte) writes: >As someone said, one-based arrays often seem more natural. I want to >store 10 of these things. So I allocate a ten element array. Now, >quick, which is the last element? Number NINE? Huh? Yes. 'fraid so! The "9" popped into my head straight away. I'm an ML hacker. I'm used to traversing lists. If I have a list of 10 elements, I have to take its tail 9 times. If I want the first element, I do 0 operations. So, I think from 0 upwards... -- Nick Rothwell, Laboratory for Foundations of Computer Science, Edinburgh. nick%lfcs.ed.ac.uk@nss.cs.ucl.ac.uk <Atlantic Ocean>!mcvax!ukc!lfcs!nick ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ...while the builders of the cages sleep with bullets bars and stone, they do not see your road to freedom that you build with flesh and bone.
sommar@enea.se (Erland Sommarskog) (03/08/88)
My critics against Oberon seems to have set of some discussion
about the base on arrays. Just a few more comments.
I have full respect for those prefer zero-based arrays, and there
are certainly occasions I would use one or two myself, but the
occasions are rare. As I said in my original post, removing the
freedoom to choose the lower limit is bad thing.
Some have said that if one wants one-based arrays, when only zero-based
arrays are available, one could just simply declare the array one
element too large, and waste the one at index zero. This method does
not always work. As I recall from Modula-2 you can have dynamic arrays
in procedures. (Both as parameters and local variables? Doesn't matter.)
They are always zero based. If I call such a procedure with a string
the first character will be at index zero, unless I do any strange
tricks with a leading blank or so.
--
Erland Sommarskog
ENEA Data, Stockholm
sommar@enea.UUCP "Souvent pour s'amuser les hommes d'equipages
and it's like talking to a stranger" -- H&C.ray@micomvax.UUCP (Ray Dunn) (03/16/88)
In article <4343@june.cs.washington.edu> pattis@june.cs.washington.edu (Richard Pattis) writes: >I too detest 0-based arrays (and think 1-based arrays are better). In trying >to rationalize this choice, I came up the the following argument: When we >process arrays, we often need to know the size of the array and/or the >position of the last element. In 0-based arrays, these quantites are off by >one; in 1-based arrays they are the same. Hence, I think that people will >make fewer errors with 1-based arrays. > The question is, I believe, does the 'structure' fit naturally with the problem you are trying to solve when using the array. Sometimes 0-based is what you want, sometime 1-based is what you want, sometimes n, or -n or etc is what you want! How does the Algol declaration go?? (thinks back about 15 years) array[x:y]?? (I probably have the syntax wrong!) where x and y are positive or negative integers defining the lower and upper bounds of the array's index! Thus i[-20:50] is a 71 element array indexed from -20 through 50. Ray Dunn. {philabs, mnetor, musocs}!micomvax!ray
uday@mips.COM (Uday Kurkure) (03/18/88)
In article <942@micomvax.UUCP>, ray@micomvax.UUCP (Ray Dunn) writes: > The question is, I believe, does the 'structure' fit naturally with the problem > you are trying to solve when using the array. > > Sometimes 0-based is what you want, sometime 1-based is what you want, > sometimes n, or -n or etc is what you want! In Mathematics, zero means nothing, void. In computer science, zero has a meaning depending on the the context. There exists a memory location at zero address. As long as there are addresses starting from zero, 0-based/ 1-based arrays would be a matter of taste. ..Uday
darryl@ism780c.UUCP (Darryl Richman) (03/19/88)
In article <1886@gumby.mips.COM> uday@mips.COM (Uday Kurkure) writes: > In Mathematics, zero means nothing, void. In computer science, zero I'm not a math major, but 0 is not void. Void is null (e.g., the slashed capital O). This is a very important distinction. --Darryl Richman -- Copyright (c) 1988 Darryl Richman INTERACTIVE Systems Corporation "Curiouser and curiouser" An Eastman Kodak Company The views expressed above are ...!cca!ima!ism780c!darryl those of the author. ...!sdcrdcf!
g-rh@cca.CCA.COM (Richard Harter) (03/20/88)
In article <9475@ism780c.UUCP> darryl@ism780c.UUCP (Darryl Richman) writes: >In article <1886@gumby.mips.COM> uday@mips.COM (Uday Kurkure) writes: >> In Mathematics, zero means nothing, void. In computer science, zero >I'm not a math major, but 0 is not void. Void is null (e.g., the slashed >capital O). This is a very important distinction. Please, let us not confuse things. The word 'number' has different meanings in different contexts. This may be obscured by that fact one uses the same symbols and the same 'things' so to speak, but it is nonetheless true. A cardinal number is (or can be treated as) the measure of the size of a set. I.e. some sets have one element, some sets have two elements, and so on. [A set, for the totally non-mathematical, is a collection of things considered as a whole. The things in the collection are called elements of the set.] The void set, or empty set, is [the] set with no elements. Zero (0) is measure of the size of the void set. Cardinal numbers start with 0 and go 0,1,2,... An ordinal number is a specification of the position of an element in an ordered sequence. If I have a sequence, <a,b,c> a is the first element, b is the second, and c is the third. An ordinal number is related to a cardinal number since the ordinal of the last element of the sequence is the 'same' as the cardinal measuring the size of the sequence, considered as a set. I.e., in a sequence with n elements the last one is the n'th. Ordinals start with 1, and go 1,2,3,... In arithmetic the numbers are primitive elements with arithmetic operations defined on them. Zero is the identity element, i.e. the number such that for all x, x+0 = x. It turns out that there is a direct correspondence between the non-negative integers of arithmetic and the cardinal numbers. And so on. Sorry to be pedantic, but what a number is and what it means depends on what you are talking about and what you mean. -- In the fields of Hell where the grass grows high Are the graves of dreams allowed to die. Richard Harter, SMDS Inc.
jcb@its63b.ed.ac.uk (J Bradfield) (03/21/88)
In article <25739@cca.CCA.COM> g-rh@CCA.CCA.COM.UUCP (Richard Harter) writes: >An ordinal number is a specification of the position of an element in an >ordered sequence. If I have a sequence, <a,b,c> a is the first element, >b is the second, and c is the third. An ordinal number is related to >a cardinal number since the ordinal of the last element of the sequence >is the 'same' as the cardinal measuring the size of the sequence, considered >as a set. I.e., in a sequence with n elements the last one is the n'th. >Ordinals start with 1, and go 1,2,3,... > >In arithmetic the numbers are primitive elements with arithmetic operations >defined on them. Zero is the identity element, i.e. the number such that >for all x, x+0 = x. It turns out that there is a direct correspondence >between the non-negative integers of arithmetic and the cardinal numbers. > >And so on. Sorry to be pedantic, but what a number is and what it means >depends on what you are talking about and what you mean. If we're going to be pedantic and mathematical, let's at least get it right. The ordinals start at zero: ordinals are defined as equivalence classes of well-ordered sets, and the smallest ordinal is the order type of the empty set, to wit, zero. Cardinals are defined either as equivalence classes of ordinals (all those having the same size), or as the smallest ordinal in the equivalence class. For example, the smallest infinite cardinal, aleph-0, is the size of the sequence <0,1,2,...> -- but it's also the size of the sequence <0,1,2,...,0,1,2,...>, which has twice the length of the first one. See any book on elementary set theory for more about ordinals and cardinals. There is a one-one corrspondence between *finite* cardinals and the non-negative integers; but there's a one-one correspondence between finite ordinals and finite cardinals: it's only in the infinite case that it is necessary to distinguish carefully. All this is rather irrelevant to arrays; set theory is not necessarily a good guide for language designers! Personally, I use whichever base seems more appropriate for the task in hand---which is why I object to languages that won't let me start arrays at zero. Julian Bradfield.
g-rh@cca.CCA.COM (Richard Harter) (03/22/88)
In article <1106@its63b.ed.ac.uk> jcb@lfcs.ed.ac.uk (J Bradfield) writes: >In article <25739@cca.CCA.COM> g-rh@CCA.CCA.COM.UUCP (Richard Harter) writes: ... Loose description of ordinals deleted >If we're going to be pedantic and mathematical, let's at least get it right. >The ordinals start at zero: ordinals are defined as equivalence classes of >well-ordered sets, and the smallest ordinal is the order type of the empty >set, to wit, zero. Cardinals are defined either as equivalence classes of >ordinals (all those having the same size), or as the smallest ordinal in >the equivalence class. For example, the smallest infinite cardinal, >aleph-0, is the size of the sequence <0,1,2,...> -- but it's also the size >of the sequence <0,1,2,...,0,1,2,...>, which has twice the length of the >first one. See any book on elementary set theory for more about ordinals >and cardinals. Er, well, no. Ordinals may be defined as equivalence classes of well-ordered sets in set theories which permit this definition. In set theories which do not, e.g. Zermelo Frankel, they are defined quite differently. You are correct that most set theoretic definitions permit an ordinal zero. Transfinite arithmetic may be relevant for usenet discussions, but not programming languages :-). The set theoretic definitions, in any case, are not definitions of ordinals, per se; they are definitions of sets that may be used to instantiate ordinals. There are some fine logical points here that are blissfully ignored in books on elementary set theory. >All this is rather irrelevant to arrays; set theory is not necessarily >a good guide for language designers! True enough. The reason for mentioning ordinals is rather more basic -- people use ordinals all of the time. The problem is really the more simple one that the first element of an array is at displacement zero from the address of the array. Some people conclude from this that counting should start from zero. >Personally, I use whichever base seems more appropriate for the task >in hand---which is why I object to languages that won't let me start >arrays at zero. Since it is (or so it seems to me) that one usually, in programming, want to use indices as displacements, I agree, and would further say that that it is far more useful to have the default start at zero. The problem is that it is rather more natural to think of loop indices as ordinals, i.e. process the first instance, then the second, and so on. Experience says that it is simpler to treat them as displacemnt values. -- In the fields of Hell where the grass grows high Are the graves of dreams allowed to die. Richard Harter, SMDS Inc.
uday@mips.COM (Robert Redford) (03/22/88)
In article <6276@ames.arpa>, eugene@pioneer.arpa (Eugene N. Miya) writes: > In article <1886@gumby.mips.COM> uday@mips.COM (Uday Kurkure) writes: > > In Mathematics, zero means nothing, void. In computer science, zero > > has a meaning depending on the the context. There exists a memory location > > at zero address. As long as there are addresses starting from zero, 0-based/ > > 1-based arrays would be a matter of taste. > > Sorry, nope. Zero is a place holder, the additive identity, it does not > mean void, etc. This is why the null set, $phi$, and {} were created > by Cantor(?). Zero based starts are excellent for initial conditions, > and negative subscripts are useful on occasion. Sorry for using the terms nothing, void rather loosely. My statement was based on the very common, day to day interpretation given to zero. ( i.e. cardinality of a null set ) When someone has zero apples, it means that he has no apples. If there are three apples on the table, one would start refering to them as first apple, second apple, third apple. If there are 3 memory cells in the computer, one starts refering to them as zeroth memory cell, first memory cell and second memory cell. ..Uday
mj@myrias.UUCP (Michal Jaegermann) (03/23/88)
Long, long time before any computers were invented - even before times were Turing was born - there was a mathematician and logician with a name of Gottlieb Frege. He was deeply convinced that we should always start counts from 0 and was trying hard to pass that idea to everybody else. ( I think that he had some valid points. Remember that humanity managed to loose one whole year - year 0. :-) ) An apocryphic story claims, that once he had a surgery and was asked to count loudly, when given anesthetic. And he was counting: "ZERO, one, two, three...." Michal Jaegermann Myrias Research Corporation Edmonton, Alberta, CANADA ...ihnp4!alberta!myrias!mj
jk3k+@andrew.cmu.edu (Joe Keane) (04/01/88)
In article <1915@mips.mips.COM>, uday@mips.COM (Robert Redford) writes: > When someone has zero apples, it means that he has no > apples. If there are three apples on the table, one would start > refering to them as first apple, second apple, third apple. > If there are 3 memory cells in the computer, one starts refering > to them as zeroth memory cell, first memory cell and second memory > cell. The problem with this is that most people agree that memory cell 0 is the `first' one. But then we get the same off-by-one stupidity we have with centuries, that memory cell 100 would be the `hundred-and-first' one. So we need to insert another ordinal. Etymologically, it should go: `first', `second', `twoth', `third', ... (I'd like to hear something better than `twoth'.) The French don't even need a new word: `premier', `second', `deuxieme', `troisieme', ... But what do i know, i also think we should use hexadecimal... --Joe