Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Why We Start Indexing from 0 in Computer Science

cs.utexas.edu

Post reply on HN
Print view View original

31–38 of 38 posts

Re: Why We Start Indexing from 0 in Computer Science

#31

Post by masklinn »

TorKlingberg wrote: post #26

Matlab, which is commonly used for numerical computing, uses one-based indexes. Just one of the little gotchas when switching between Matlab and "real" programming languages. In mathematics and physics the usage varies. Zero is used when it is really the beginning of something, like t0 for the start time of an experiment. In most other cases lists count from one and up. Matrix elements too are generally denoted from…

> Except deadlocks have nothing to do with sharing memory, and everything to do with sharing state.

Other languages using 1-indexed arrays: Fortran, Cobol, Smalltalk, XPath, Erlang[0] and Lua (and a bunch of other very old languages like PL/1 or Algol).

All Wirthian languages (Pascal, Oberon, Ada, etc...) use configured index ranges (and provide primitives to query the array for its bounds), but I believe the convention is to use 1-index arrays when there are no special index semantics due to their strings being 1-indexed.

VB has configurable index ranges as well, but defaults to 0-indexed arrays.

You can also "configure" initial array index in Perl by setting `$[` I believe. Doing this will lead to you being beaten to death with ethernet cables by your colleagues. And if it does not, it should.

[0] though direct indexation is rarely used in erlang

Re: Why We Start Indexing from 0 in Computer Science

#32

Post by masklinn »

MattJ100 wrote: post #23
lysol wrote: post #15

Earlier quoted context omitted.

Nasty. But it's the same for substring text offsets, array indices etc in Postgres.

Nasty? In a language without pointers it makes total sense. An index is no longer an offset from an array (or string) pointer, so the first element being 1, the second being 2, just makes more sense. Sure, it's a departure from mainstream languages, but in my opinion it's a perfectly sensible one.

> Nasty? In a language without pointers it makes total sense. An index is no longer an offset from an array (or string) pointer, so the first element being 1, the second being 2, just makes more sense.

Not necessarily. The reasoning in e.g. Python is that the index is not to an element, it's to one of the intervals around an element. The "first interval" (right before the first element) is 0, which naturally leads to -1 being right before the last element, thus arr[-1] being an array's last element, and arr[:-1] being everything but the last element.

Re: Why We Start Indexing from 0 in Computer Science

#33

Post by jmesserly »

edtechdev wrote: post #10
goodside wrote: post #7

I suspect the real reason has more to do with the pragmatics of machine code. It's extremely common to want to refer to some dynamic offset of a fixed location in memory, like if you have an array of equal-length items stored consecutively. If you have two literal addresses called Start and Index, you'd like to be able to say something like "Start[Index]" and have it mean "Read from Index, and whatever number is ther…

Right, it makes sense when dealing with machine code and when making the compiler do extra work for you (converting one-based to zero-based indexing) would be too much work for the compiler implementer or is too slow (like on machines back in the 70s and 80s) or it would abstract too far from what is happening underneath the hood, possibly leading to errors. But like many features of programming languages and operati…

Python's colon-before-indented-block resulted from usability tests of people learning how to program. I don't see why that would have different results today.

See page 7 of this presentation: http://mvdirona.com/jrh/TalksAndPapers/GuidoVanRossum_21_yea...

Re: Why We Start Indexing from 0 in Computer Science

#34

Post by mturmon »

omaranto wrote: post #30
mjw wrote: post #21

Earlier quoted context omitted.

> I should also point out that mathematicians don't number at zero unless there is some advantage (the default is to start at one) I disagree. While this may depend a little on which areas of mathematics you study, I've found that in situations where there is a reasonably clear / natural / non-arbtirary preference, it tends to be for zero-based natural numbers. On the other hand, situations in which 1-based numbers a…

Well, whole numbers come up in mathematics in different ways. Of course if you're talking about cardinality you should include zero: it simply is the cardinality of some set, you can't avoid that. I was talking about a completely different use of numbers: numbering, that is assigning numbers as labels to things. There I think mathematicians on the whole prefer to number starting at 1 (or not to number at all and work…

To continue with your example, take cases where a (finite) collection of discrete objects is summed over (unioned over, whatever).

You'd let N be the number of such objects, and then twenty following pages of text would contain summations from 1 to N. This is more compact than summations from 0 to N-1. And in a certain sense, there's one less "token" to remember (i.e., if you start at 1, you have 1 and N to remember, but when you start at 0, you have N, 0, and N-1 to remember).

The one that's more compact tends to be discipline-specific.

Re: Why We Start Indexing from 0 in Computer Science

#35

Post by LeafStorm »

My main issue with the start-from-0 convention is that while it makes sense if you consider an array as a pointer with more pointers coming after it, it doesn't make as much sense when it is simply a list of objects.

When I have a five-page document, I number the pages as one, two, three, four, five, and say that the length of the document is five pages. If I have an "empty" document (assuming such a thing makes sense in the real world), it would have length zero, and since there are no elements to assign indices to, I would not assign them numbers.

I have to admit that I much prefer the Lua convention: in a sequence of N items, they are numbered 1, 2...N-1, N. The length of the sequence is equal to the index of the last item in the sequence. "Negative" indices are treated as if one was counting backwards from the end of the sequence, such that the items are numbered -N, (-N)+1, (-N)+2...-2, -1, i.e. the spoken forms "last," "second-to-last," "third-to-last..." This means that 1 to -1 encompasses the whole sequence. This does have the unfortunate side effect that 0 refers to no item, but even when describing an array implemented as a pointer we refer not to the "zeroth" element, but to the first and the last.

This also has an added benefit that the range notation used by Lua's numeric for loops makes perfect sense when compared to the notation used by Python's range statement. In Lua,

    for n = 1, #tbl
produces all of the indices in the given table, as does

    for n in range(len(ls))
in Python, for a list. In Lua, this can simply produce the numbers 1, 2, 3, 4, 5, 6 for a table of six elements, which is intuitive even when using the numeric for to simply generate a series of integers:

   for n = 1, 6
However, in Python, the fact that range is used to generate the indices also means that range(1, 6) produces 1, 2, 3, 4, 5 ("Where the heck is the 6?") and a simple range(6) produces 0, 1, 2, 3, 4, 5 ("Still no 6, and where did that 0 come from?") To get 1, 2...6, you need range(7) ("What does this have to do with 7?")

Re: Why We Start Indexing from 0 in Computer Science

#36

Post by masklinn »

LeafStorm wrote: post #35

My main issue with the start-from-0 convention is that while it makes sense if you consider an array as a pointer with more pointers coming after it, it doesn't make as much sense when it is simply a list of objects. When I have a five-page document, I number the pages as one, two, three, four, five, and say that the length of the document is five pages. If I have an "empty" document (assuming such a thing makes sens…

So... you prefer Lua because half-open ranges confuse you?

Re: Why We Start Indexing from 0 in Computer Science

#37

Post by warmfuzzykitten »

We index from zero because it requires the least translation to machine code. One idea in this note, however, is pernicious: 2 <= i < n. In the for statement - for (int i = 0; i < n; i++) a[i] = i - i must take on a value that is not in the range of indices of the array, 0..n-1, to terminate the loop. This doesn't help reasoning about the loop. The problem is worse when pointer arithmetic is involved - e.g. for (p = start; p < end; p++) *p = 0 - as the final value of p may not even be a valid address. We would be better off with closed intervals and index types that restrict the range of values to those intervals.

Re: Why We Start Indexing from 0 in Computer Science

#38

Post by sesqu »

masklinn wrote: post #36
LeafStorm wrote: post #35

My main issue with the start-from-0 convention is that while it makes sense if you consider an array as a pointer with more pointers coming after it, it doesn't make as much sense when it is simply a list of objects. When I have a five-page document, I number the pages as one, two, three, four, five, and say that the length of the document is five pages. If I have an "empty" document (assuming such a thing makes sens…

So... you prefer Lua because half-open ranges confuse you?

If we're going for half-open ranges, range(n) ≝ 0Dijkstra argued against this by noting that that makes adding 0 to the range impractical, but then he was considering natural numbers, not the half-open ranges we're talking about and using notation for here.

Me, I prefer integers and the a..b style, despite the off-by-one error.

Post reply on HN