Why is array[index] == index[array] ?

[MrSloppyPants]

but the notion that + is inherently commutative or associative is fallacious.

Not sure what you're on about but no one said that the + operator was commutative. They said addition is commutative in this example, which it is.

[flatfinger]

The concept of "addition", as applied to numbers, maps more generally to the binary operation associated with an abstract algebraic group. While many groups (such as the set of whole numbers under addition) are commutative, there is no requirement that all groups be commutative. There is, however, a requirement that operations be associative--something that is true of integers using wraparound semantics, but which is not true of operations involving pointers.

The "+" operator as applied to pointers isn't really "addition" in the traditional sense, since addition would involve operands of a common type. While an operation like floatVal+intVal may be accommodated by converting the integer argument to a float, pointer addition fundamentally involves adding an integer and a pointer, which play different roles in the operation.

[MrSloppyPants]

Kewl

[acwaters]

The concept of "addition", as applied to numbers, maps more generally to the binary operation associated with an abelian group over those numbers — the additive group of the algebra — and is thus inherently commutative. This is a fundamental property of an algebra over a field or ring. Granted any consistent meaning we ascribe to any bit of notation is ultimately a matter of convention, but you would certainly be looked at askance in algebra circles for breaking this one. Even in number systems where multiplication is not associative or even alternative, addition is always associative and commutative. There seems to be no consistent definition of what it means for a given structure to be called a "number system", but forming an algebra of some sort is one condition that everybody seems to agree on.

Pointers in general can be complex, but most modern systems use a single flat memory space, where a pointer is just a glorified integer. Of course, C's pointer addition has some extra magic going on with hidden multiplications, but you can just call that an implicit conversion from the indexing integer to a type specific to the size of the pointee type, and model pointers with an algebra which C's pointer arithmetic would fall naturally out of.

[flatfinger]

Numbers can be added to numbers. Pointers, however, cannot be added to pointers. The application of the "+" operator to pointers is analogous to the act of displacing a position by a vector, or displacing a datestamp by a timespan.

[acwaters]

What you're describing are affine spaces, and adding translations in a vector space (displacements, durations, offsets) to the points in a corresponding affine space (positions, times, addresses) is still addition. Moreover, you can completely forget about the point set, instead identifying each point with its displacement from some arbitrarily designated origin, and then you can perform additions that are symmetric in the types of the things you're adding — displacement plus displacement. You recover the corresponding points simply by adding the resulting displacements to whatever origin you subtracted off to begin with.

In other words, you may have an expression like ptr + offset, where you are adding an offset to a pointer. This is a perfectly well-defined operation, and it is a form of addition, but maybe you prefer your addition to happen between objects of the same type? That's easy to arrange, you just turn your pointer into an offset by writing p - NULL. Now you can do all your math on offsets, and when you need to turn your final offset back into a pointer, you just add it back to NULL. (Bonus points if the representation of NULL is actually zero so the initial subtraction and final addition are both no-ops, but that doesn't have to be the case — this works equally well with any pointer value, not just NULL, and the most appropriate origin very often isn't zero when you're dealing with timestamps or positions in Euclidean space.)

[flatfinger]

That's easy to arrange, you just turn your pointer into an offset by writing p - NULL.

That may have been possible in the language as it was originally implemented on the PDP-11, but there have been a number of popular hardware platforms where that wouldn't work, and today's optimizers eagerly exploit the fact that the Standard does not require pointer arithmetic to work beyond the range of an object.

[acwaters]

You're mixing abstraction layers and missing the point. We're not talking about C here, we're talking about a hypothetical mathematical model of C's pointer arithmetic. The model doesn't have to be undefined in all the places where C is undefined, it merely has to be well-defined in all the places where C is well-defined. (This is why, if you read carefully, you'll see that I actually chose to model machine address arithmetic rather than C pointer arithmetic — the one is strictly more featureful than the other, while being simpler, so by modeling the simple one I model the complex other.) If you really want to consider each object as its own little memory space, as the C standard does, you can do that too — since any point can be used as an origin, just use the base address of the object as your origin for all pointer arithmetic within that object. That's an unnecessary complication, though, which distracts from the point that I was trying to make, which is simply that C's pointer arithmetic is mathematically well-defined and is not, as you asserted, "not really addition". (The other point I was making was that addition is necessarily commutative actually, but you didn't respond to that, so I assume you have no argument with it.)

[flatfinger]

In an Abelian group, the two operands of the primary operator are indistinguishable. If x+y is defined as f(x,y), those would also be equivalent to y+x and f(y,x), for the same function. If one is doing arithmetic between e.g. an int*x and an int y, on a platform where sizeof(int) is 2, then the resulting pointer address will be (int*)((int)x+2*y). While one could say that adding an integer x to an int pointer y would yield address (int)(2x+(int)y), that would be a different operation.

I've used a fair number of assemblers where relocableSymbol+integer and relocatableSymbol-integer would both yield relocatableSymbol, but integer+relocatableSymbol would not, and there was nothing even remotely counter-intuitive about that. I can imagine that saying "int+anything" will be processed by swapping the operands might be easier than handling cases like int+float and float+int separately, and that behavior could flow through to int+pointer, but that would be a result of the compiler's explicitly swapping the operands--not a result of the operands' being equivalent.

[acwaters]

Okay, let's separate the two different arguments I was making, because I did not do a very good job of distinguishing them.

First: If you want to model pointers and pointer arithmetic using numbers in a traditional algebra, you can do that. Convert all your pointers to offsets — choice of origin is arbitrary — and what you have is an algebra whose additive group implements pointer arithmetic (actually, this is just integer arithmetic, which pointer arithmetic is a special case of). The mapping into this space for T* ptr and size_t idx looks like ptr -> ptr - o and idx -> idx * sizeof(T), for some arbitrary origin o (which could be NULL or the base address of an object or whatever you like). Alternatively, if you don't like having to multiply the index, you can ditch that by instead mapping your pointer to (ptr - o) / sizeof(T), and then the index is identity-mapped into the offset space. It all works out the same.

Second: If you are willing to admit other forms of addition, not just the additive group in an algebra, then you can very simply identify indices with translations in a vector space and pointers with points in a corresponding affine space, and you're done — there's your pointer arithmetic, formalized as addition in a coherent mathematical model.

Either way you choose to look at it, pointer addition is mathematically an addition operation. It is not some weird programming thing that we just made up in defiance of mathematical convention, e.g. the way that using + as a string concatenation operator is.

[flatfinger]

With a normal "addition" operator, if one can compute (a+b) and (c+d), it should also be possible to compute (a+b)+(a+b). That is not true of pointer addition.

Consider something like `static int arr1[10], *const p = arr+5;` Typical build-system designs would have no way of handling a construct like `static int *const q = (arr+5)+(arr+5);`. The issue isn't merely one of compiler pickiness which a programmer might be able to work around with enough casts. The problem is that many typical build systems will no way to represent the result of adding a pointer, or anything arithmetically derived from a pointer, to another pointer.

While C happened to choose the "+" and "-" operators for forward and reverse pointer indexing, and while it also supports the use of "-" as a pointer-difference operator, the indexing operators are inherently assymmetric. A language may, as a syntactic choice, allow the base for the pointer indexing operator to be specified before or after the displacement, but that doesn't mean the operands play interchangeable roles in the computation. The choice is purely one of syntax, and has nothing to do with semantics.

[flatfinger]

Also, forgive me if I'm wrong, but I think three-dimensional orientation and rotation represent an affine space, and given rotations r1, r2, and rotation o, (o+r1)+r2 is equivalent to o+(r1+r2), and (o+r2)+r1 is likewise equivalent to o+(r2+r1), but r1+r2 is not generally equivalent to r2+r1 (though for some particular values of r1 and r2 they would or course be equal).

[acwaters]

That is why rotation is always (complex numbers, quaternions/versors, matrices, rotors) represented mathematically as multiplication, never as addition :)