5 ms·

Something which I occasionally link to, is this: <https://www.cs.utexas.edu/users/EWD/ewd08xx/EWD831.PDF https://www.cs.utexas.edu/users/EWD/ewd08xx/EWD831.PDF>

by teddyh 1y ago

Something which I occasionally link to, is this: <https://www.cs.utexas.edu/users/EWD/ewd08xx/EWD831.PDF https://www.cs.utexas.edu/users/EWD/ewd08xx/EWD831.PDF>. It not only shows why computer languages should start their indexes at 0 (instead of 1), but also shows why intervals should be specified as lower-inclusive and upper-exclusive.

nyrikki 1y ago
While I don’t disagree with his argument for preferred conventions in an era of accumulators/gp registers, I am surprised he didn’t call out why Fortran used 1, The IBM 704's index registers were decrementing, subtracting their contents from an instruction's address field to form an effective address. Type A instructions had a three bit tag, indicating which index registers to use. With those three indexes you get Fortran’s efficient 7D column major arrays. This made data aggregation much more efficient and Cray/Cuda/modern column oriented DBs do similar. But for Algol-like languages on PDP inspired hardware I do like his convention, if like the example you have a total ordering on the indexes. But Fortran also changed the way it was taught, shifting from an offset from memory that was indexed down from an address, which makes sense when the number of bits in an address space changes based on machine configuration, to index values. Technically Fortran, at least in word machines meets his convention. pointer + offset <= word < pointer + offset +1 It is just the offset is always negative.
- adrian_b 1y ago
  FORTRAN was defined a few years before IBM 704 (in 1954). The use of 1-based indexing was just inherited from the index notation used for vectors and matrices in most mathematical journals at that time. When IBM 704 was designed (as the successor of IBM 701 and taking into account the experience from IBM NORC), it was designed to allow an efficient implementation of FORTRAN, not vice-versa. The column-major ordering of FORTRAN allows more efficient implementations of the matrix-vector and matrix-matrix products (by reading the elements sequentially), when these operations are done correctly, i.e. not using the naive dot product definitions that are presented in most linear algebra manuals instead of the useful definitions of these operations (i.e. based on AXPY and on the tensor product of vectors).
ufo 1y ago
That particular EWD is one of my pet peeves, because of how it always pops up in discussion about array indexing. There are several situations where 1-based indexing is better, but which Dijkstra doesn't mention. For instance, one-based is much better for iterating backwards. I think a compelling argument can be made that 0-based is better for offsets and 1-based is better for indexes, and that we should not think of both as the same thing. https://hisham.hm/2021/01/18/again-on-0-based-vs-1-based-indexing/ https://hisham.hm/2021/01/18/again-on-0-based-vs-1-based-ind...
- bazoom42 1y ago
  And Dijkstras argument is actually quite weak if you read carefully. But he has a certain way of writing which make it seem almost like a mathematical proof. And then he sprinkles some “only smart people agree with me” nerd baiting.
  - adrian_b 1y ago
    This is a matter of opinion. I consider Dijkstra's arguments quite strong. Some decades ago, I have disassembled and studied Microsoft's Fortran compiler. The fact that Fortran uses 1-based indexing caused a lot of unnecessary complications in that compiler. After seeing firsthand the problems caused by 1-based indexing I have no doubt that Dijkstra was right. Yes, the compiler could handle perfectly fine 1-based indexing, but there really was no reason for all that effort, which should have been better spent on features providing a serious advantage for the programmer. The use of 1-based indexing and/or closed intervals, instead of consistently using only 0-based indexing and half-open intervals, are likely to be the cause of most off-by-one errors.
- adrian_b 1y ago
  One-based is not better for iterating backwards. Zero-based indexing is naturally coupled with using only half-open ranges. When using zero-based indexing and half-open ranges, accessing an array forwards, backwards or circularly is equally easy. In this case you can also do like in the language Icon, where non-negative indices access the array forwards, while negative indices access the array backwards (i.e. -1 is the index of the last element of the array, while 0 is the index of the first element). In languages lacking the Icon feature, you just have to explicitly add the length of the array to the negative index. There is absolutely no reason to distinguish offsets and indices. The less distinct kinds of things you need to keep in mind, the less chances for errors from using the wrong thing. Therefore one should not add extra kinds of things in a programming language, unless there is a real need for them. There are things that are missing from most languages and which are needed, e.g. separate types for signed integers, unsigned integers, modular numbers, bit strings and binary polynomials (instead of using ambiguous unsigned integers for all the 4 latter types, which prevents the detection of dangerous errors, e.g. unsigned overflow), but distinguishing offsets from indices is not a useful thing. Distinguishing offsets and indices would be useful only if the set of operations applicable to them would be different. However this is not true, because the main reason for using indices is to be able to apply arithmetic operations to them. Otherwise, you would not use numbers for indexing, but names, i.e. you would not use arrays, but structures (or hash tables, when the names used for access are not known at compile time).
cubefox 1y ago
He ignores this basic argument: Positions in sequences like arrays are referred to using ordinal numbers (first, second, third, ...). There is no ordinal "zeroth". Ordinal numbers start at 1. This is contrary to cardinal ("how many?") numbers, which start at 0. And talking of "natural" numbers is besides the point. Therefore, referring to the seventh element in a sequence with the name "6" rather than "7" is confusing and provokes off-by-one errors.
- teddyh 1y ago
  Using the same argument, why not place the origin point of cartesian coordinates at (1, 1, 1)?
  - cubefox 1y ago
    Those use real numbers, which are different from ordinal (or cardinal) numbers. Ordinal numbers are positive whole numbers.

by teddyh 1y ago

nyrikki 1y ago

While I don’t disagree with his argument for preferred conventions in an era of accumulators/gp registers, I am surprised he didn’t call out why Fortran used 1, The IBM 704's index registers were decrementing, subtracting their contents from an instruction's address field to form an effective address. Type A instructions had a three bit tag, indicating which index registers to use. With those three indexes you get Fortran’s efficient 7D column major arrays. This made data aggregation much more efficient and Cray/Cuda/modern column oriented DBs do similar. But for Algol-like languages on PDP inspired hardware I do like his convention, if like the example you have a total ordering on the indexes. But Fortran also changed the way it was taught, shifting from an offset from memory that was indexed down from an address, which makes sense when the number of bits in an address space changes based on machine configuration, to index values. Technically Fortran, at least in word machines meets his convention. pointer + offset <= word < pointer + offset +1 It is just the offset is always negative.

adrian_b 1y ago
FORTRAN was defined a few years before IBM 704 (in 1954). The use of 1-based indexing was just inherited from the index notation used for vectors and matrices in most mathematical journals at that time. When IBM 704 was designed (as the successor of IBM 701 and taking into account the experience from IBM NORC), it was designed to allow an efficient implementation of FORTRAN, not vice-versa. The column-major ordering of FORTRAN allows more efficient implementations of the matrix-vector and matrix-matrix products (by reading the elements sequentially), when these operations are done correctly, i.e. not using the naive dot product definitions that are presented in most linear algebra manuals instead of the useful definitions of these operations (i.e. based on AXPY and on the tensor product of vectors).

ufo 1y ago

That particular EWD is one of my pet peeves, because of how it always pops up in discussion about array indexing. There are several situations where 1-based indexing is better, but which Dijkstra doesn't mention. For instance, one-based is much better for iterating backwards. I think a compelling argument can be made that 0-based is better for offsets and 1-based is better for indexes, and that we should not think of both as the same thing. https://hisham.hm/2021/01/18/again-on-0-based-vs-1-based-indexing/ https://hisham.hm/2021/01/18/again-on-0-based-vs-1-based-ind...

bazoom42 1y ago
And Dijkstras argument is actually quite weak if you read carefully. But he has a certain way of writing which make it seem almost like a mathematical proof. And then he sprinkles some “only smart people agree with me” nerd baiting.
- adrian_b 1y ago
  This is a matter of opinion. I consider Dijkstra's arguments quite strong. Some decades ago, I have disassembled and studied Microsoft's Fortran compiler. The fact that Fortran uses 1-based indexing caused a lot of unnecessary complications in that compiler. After seeing firsthand the problems caused by 1-based indexing I have no doubt that Dijkstra was right. Yes, the compiler could handle perfectly fine 1-based indexing, but there really was no reason for all that effort, which should have been better spent on features providing a serious advantage for the programmer. The use of 1-based indexing and/or closed intervals, instead of consistently using only 0-based indexing and half-open intervals, are likely to be the cause of most off-by-one errors.
adrian_b 1y ago
One-based is not better for iterating backwards. Zero-based indexing is naturally coupled with using only half-open ranges. When using zero-based indexing and half-open ranges, accessing an array forwards, backwards or circularly is equally easy. In this case you can also do like in the language Icon, where non-negative indices access the array forwards, while negative indices access the array backwards (i.e. -1 is the index of the last element of the array, while 0 is the index of the first element). In languages lacking the Icon feature, you just have to explicitly add the length of the array to the negative index. There is absolutely no reason to distinguish offsets and indices. The less distinct kinds of things you need to keep in mind, the less chances for errors from using the wrong thing. Therefore one should not add extra kinds of things in a programming language, unless there is a real need for them. There are things that are missing from most languages and which are needed, e.g. separate types for signed integers, unsigned integers, modular numbers, bit strings and binary polynomials (instead of using ambiguous unsigned integers for all the 4 latter types, which prevents the detection of dangerous errors, e.g. unsigned overflow), but distinguishing offsets from indices is not a useful thing. Distinguishing offsets and indices would be useful only if the set of operations applicable to them would be different. However this is not true, because the main reason for using indices is to be able to apply arithmetic operations to them. Otherwise, you would not use numbers for indexing, but names, i.e. you would not use arrays, but structures (or hash tables, when the names used for access are not known at compile time).

cubefox 1y ago

He ignores this basic argument: Positions in sequences like arrays are referred to using ordinal numbers (first, second, third, ...). There is no ordinal "zeroth". Ordinal numbers start at 1. This is contrary to cardinal ("how many?") numbers, which start at 0. And talking of "natural" numbers is besides the point. Therefore, referring to the seventh element in a sequence with the name "6" rather than "7" is confusing and provokes off-by-one errors.

teddyh 1y ago
Using the same argument, why not place the origin point of cartesian coordinates at (1, 1, 1)?
- cubefox 1y ago
  Those use real numbers, which are different from ordinal (or cardinal) numbers. Ordinal numbers are positive whole numbers.