Sunday, May 25, 2008

One-based indexes in XPath

Justin Johansson asked an interesting question on the xsl-list.

Would someone please give me advice as to why "1-based" indexes are used in XPath, such as para[1] instead of para[0] for the first para item/element?

Why does the spec for XPath (and its/XQuery operator/function library) go against the norm for modern programming languages in which zero is the base for array-like collections?

An interesting discussion happened on xsl-list after this query.

Colin Adams wrote: Zero is not the norm for modern programming languages. It might well be for ancient ones. It is a very poor choice, justifiable only when trying to squeeze the last ounce of speed in a highly numerically-intensive application.

And even there it is not justified - you simply use data structures that have an unused first element, and so avoid the subtract one operation in that way.

I reasoned:
Let's say, we have to select a node as following:

following-sibling::xx[1]

To me traversal on following (or say preceding) axis will make sense if indexes start from 1.

I also think 0 based indexes in low level languages (I consider Java or C to be low level than XPath. I am talking about assembly languages too.) have relation to hardware addressing.

For e.g., a memory might have addresses ranging from 0000 to 1111 (this is just a small amount of memory). This probably has got to do with logic of bits, where 0 has a very important meaning.

Lot of programming languages (also mentioned by you) have 0 based indexes (in arrays, strings etc.), so compilers can easily map them to hardware locations.

Indexes in XPath start from 1 because it's more convenient for the users.

Michael Kay commented on my reasoning as follows, "I don't think hardware addressing is the only benefit of 0-based addressing. It also makes computations easier. If you number the rows and columns on a chessboard from 0-7, and the squares from 0-63, then the square number is row*8+column, whereas with 1-based addressing it is (row-1)*8+column.

And we do sometimes use 0-based logic in real life too. In many countries the "first floor" is the one above where you enter the building; and in many societies a child is "1 year old" between 12 months and 24 months after their birth.

But on balance I do think 1-based logic was the right choice for XPath and XSLT."

Michael further said, "Because the language was designed for users, not for programmers, and users still have this old-fashioned habit of referring to the first chapter in a book as Chapter One. (Though I did once hear Dijkstra refer to the fourth slide in someone's presentation as the third.)

(I fully agree that when handling tables, or subscripting into strings, zero-based addressing would often be much more convenient. There are arguments both ways, and as always, I can't tell you what the actual history of the decision was; I can only post-rationalize it.)".

Owen Rees shared an interesting point: Dijkstra wrote a note "Why numbering should start at zero": http://www.cs.utexas.edu/users/EWD/transcriptions/EWD08xx/EWD831.html.

The book "Informal introduction to ALGOL 68" numbers its chapters from zero. I remember that as being unusual, amusing, and also appropriate given the audience.

Since XSLT does not have multi-dimensional sequences, the issues that arise when multi-dimensional arrays can be treated as one-dimensional arrays do not arise. Zero-based indexing tends to make the index formulae simpler when accessing a multi-dimensional array with a one-dimensional array access expression but on the whole I think it is best to just not do that sort of thing at all.

I don't think that the age of language or design for programmer or user arguments stand up very well.

FORTRAN is a counterexample to the "old languages use zero" argument, it uses 1. Modern versions of FORTRAN allow the lower bound to be specified (as Algol did) but the default is still 1.

Dartmouth BASIC used zero-based indexing, I have no information about why, but I doubt if it has anything to do with being close to assembly code or concern for the last ounce of speed.

I think that both of these languages were originally aimed at people who did not think of themselves as being or intending to become programmers.

One related point here is that those thinking in terms of other programming languages may be misled by the syntactic similarity of the XPath expression para[1] to an array indexing expression in various other languages. Understanding that para[1] is just a shorthand for para[position()=1] moves the issue to the question of why position() is defined the way it is.

Defining last() to be the context size means that context position has to count from one unless you are going to cause either 'last' or 'size' to have a very counterintuitive meaning.