14
$\begingroup$

I have came across a weird experience in C programming. Consider this code:

int main(){
  int array1[6] = {0, 1, 2, 3, 4, 5};
  int array2[6] = {6, 7, 8, 9, 10, 11};

  printf("%d\n", array1[-1]);
  return 0;
}

When I compile and run this, I don't get any errors or warnings. As my lecturer said, the array index -1 accesses another variable. I'm still confused, why on earth does a programming language have this capability? I mean, why allow negative array indices?

$\endgroup$
  • 2
    $\begingroup$ While this question is motivated with C as concrete programing language, I think it can be understood as a conceptual question that is ontopic here (if barely). $\endgroup$ – Raphael Mar 27 '13 at 13:32
  • 6
    $\begingroup$ @Raphael I disagree and believe it should belong on SO, either way this is textbook undefined behavior (referencing memory outside the array) and proper compiler flags should warn about this $\endgroup$ – ratchet freak Mar 28 '13 at 11:40
  • $\begingroup$ I agree with @ratchetfreak. It seems to be a compiler flaw since valid index range is [0, 5]. Anything that is outside must be a compilation/runtime error. As of in general, vectors are particular case of functions whose first element index is up to the user. Since C contract is that elements start at index 0, it is error to access negative elements. $\endgroup$ – Val Dec 22 '13 at 17:18
  • 2
    $\begingroup$ @Raphael C has two peculiarities over typical languages with arrays that matter here. One is that C has subarrays and refering to element -1 of a subarray is a perfectly valid way to refer to the element before that array in the larger array. The other is that if the index is invalid, the program is invalid, but in most implementations you'll get silent bad behavior, not an out-of-range error. $\endgroup$ – Gilles 'SO- stop being evil' Mar 24 '14 at 14:21
  • 4
    $\begingroup$ @Gilles If that's the point of the question, this should indeed have been on Stack Overflow. $\endgroup$ – Raphael Mar 24 '14 at 14:36
27
$\begingroup$

The array indexing operation a[i] gains its meaning from the following features of C

  1. The syntax a[i] is equivalent to *(a + i). Thus it is valid to say 5[a] to get at the 5th element of a.

  2. Pointer-arithmetic says that given a pointer p and an integer i, p + i the pointer p advanced by i * sizeof(*p) bytes

  3. The name of an array a very quickly devolves to a pointer to the 0th element of a

In effect, array-indexing is a special case of pointer-indexing. Since a pointer can point to any place inside an array, any arbitrary expression that looks like p[-1] is not wrong by examination, and so compilers don't (can't) consider all such expressions as errors.

Your example a[-1] where a is actually the name of an array is actually invalid. IIRC, it is undefined if there's a meaningful pointer value as the result of the expression a - 1 where a is know to be a pointer to the 0th element of an array. So, a clever compiler could detect this and flag it as an error. Other compilers can still be compliant while allowing you to shoot yourself in the foot by giving you a pointer to a random stack slot.

The computer science answer is:

  • In C, the [] operator is defined on pointers, not arrays. In particular, it's defined in terms of pointer arithmetic and pointer dereference.

  • In C, a pointer is abstractly a tuple (start, length, offset) with the condition that 0 <= offset <= length. Pointer arithmetic is essentially lifted arithmetic on the offset, with the caveat that if the result of the operation violates the pointer condition, it is an undefined value. De-referencing a pointer adds an additional constraint that offset < length.

  • C has a notion of undefined behaviour which allows a compiler to concretely represent that tuple as a single number, and not have to detect any violations of the pointer condition. Any program that satisfies the abstract semantics will be safe with the concrete (lossy) semantics. Anything that violates the abstract semantics can be, without comment, accepted by the compiler and it can do anything it wants to do with it.

$\endgroup$
  • $\begingroup$ Please try to give a general answer, not one depending on idiosyncrasies of any particular programming language. $\endgroup$ – Raphael Mar 27 '13 at 15:24
  • 5
    $\begingroup$ @Raphael, the question was explicitly about C. I think I addressed the specific question of why a C compiler is allowed to compile a seemingly meaningless expression within the definition of C. $\endgroup$ – Hari Mar 27 '13 at 15:58
  • $\begingroup$ Questions about C in particular are offtopic here; note my comment on the question. $\endgroup$ – Raphael Mar 27 '13 at 16:08
  • 4
    $\begingroup$ I believe the comparitive linguistics aspect of the question is still useful. I believe I gave a fairly "computer-science" flavoured description of why a specific implementation exhibited a specific concrete semantics. $\endgroup$ – Hari Mar 27 '13 at 16:12
14
$\begingroup$

Arrays are simply laid out as contiguous chunks of memory. An array access such as a[i] is converted to an access to memory location addressOf(a)+i. This the code a[-1] is perfectly understandable, it simply refers to the address one before the start of the array.

This may seem crazy, but there are many reasons why this is allowed:

  • it is expensive to check whether the index i to a[-] is within bounds of the array.
  • some programming techniques actually exploit the fact that a[-1] is valid. For instance, if I know that a is not actually the start of the array, but a pointer into the middle of the array, then a[-1] simply gets the element of the array that is to the left of the pointer.
$\endgroup$
  • 6
    $\begingroup$ In other words, it should probably not be used. Period. What, your name is Donald Knuth and you try to save another 17 instructions? By all means, go ahead. $\endgroup$ – Raphael Mar 27 '13 at 13:34
  • $\begingroup$ Thanks for the reply, But I didn't get the idea. BTW I'll read it again and again until I understand.. :) $\endgroup$ – Mohammed Fawzan Mar 27 '13 at 13:36
  • 2
    $\begingroup$ @Raphael: The implementation of the cola object model uses the -1 position to store the vtable: piumarta.com/software/cola/objmodel2.pdf. Thus the fields are stored in the positive part of the object and the vtable in the negative. I cannot remember the details, but I think it is to do with consistency. $\endgroup$ – Dave Clarke Mar 27 '13 at 13:40
  • $\begingroup$ @DeZéroToxin: An array is really just a location in memory, with some locations next to it that are logically part of the array. But really, an array is just a pointer. $\endgroup$ – Dave Clarke Mar 27 '13 at 13:41
  • 1
    $\begingroup$ @Raphael, a[-1] makes perfect sense for some cases of a, in this particular case it is plain illegal (but not caught by the compiler) $\endgroup$ – vonbrand Mar 27 '13 at 15:46
4
$\begingroup$

As the other answers explain, this is undefined behaviour in C. Consider that C was defined (and is mostly used) as a "high level assembler". C's users value it for its uncompromising speed, and checking stuff at runtime is (mostly) out of the question for the sake of sheer performance. Some C constructs that look nonsensical for people comming from other languages make perfect sense in C, like this a[-1]. Yes, it doesn't always make sense (

$\endgroup$
  • 1
    $\begingroup$ I like this answer. Gives a real reason for why this is okay. $\endgroup$ – darxsys Jul 19 '13 at 4:03
3
$\begingroup$

One can use such a feature to write memory allocation methods that access memory directly. One such use is to check the previous memory block using a negative array index to determine if the two blocks can be merged. I've used this feature when I develop a non-volatile memory manager.

$\endgroup$
2
$\begingroup$

C is not strongly typed. A standard C compiler wouldn't check array bounds. The other thing is that an array in C is nothing but a contiguous block of memory and indexing starts at 0 so an index of -1 is the location of whatever bit-pattern is before a[0].

Other languages exploit negative indices in a nice way. In Python, a[-1] will return the last element, a[-2] will return the second-to-last element and so on.

$\endgroup$
  • 2
    $\begingroup$ How do strong typing and array indices relate? Are there languages with a type for naturals where array indices must be naturals? $\endgroup$ – Raphael Mar 27 '13 at 16:09
  • $\begingroup$ @Raphael As far as I know, strong typing means that type errors are caught. An array is a type, IndexOutOfBounds is an error so in a strongly typed language this will be reported, in C this will not. That's what I meant. $\endgroup$ – saadtaame Mar 27 '13 at 16:23
  • $\begingroup$ In the languages I know, array indices are of type int, so a[-5] and, more generally, int i; ... a[i] = ...; are correctly typed. Index errors are only detected at runtime. Of course, a clever compiler may detect some violations. $\endgroup$ – Raphael Mar 27 '13 at 16:35
  • $\begingroup$ @Raphael I'm talking about the array data type as a whole, not index types. That explains why C does allow users to write a[-5]. Yes, -5 is the correct index type but it's out of bounds and that's an error. There is no mention of compile or runtime type checking in my answer. $\endgroup$ – saadtaame Mar 27 '13 at 16:41
1
$\begingroup$

In simple words:

All variables(including arrays) in C are stored in memory. Let's say you have 14 bytes of "memory" and you initialize the following:

int a=0;
int array1[6] = {0, 1, 2, 3, 4, 5};

Also,consider the size of an int as 2 bytes. Then,hypothetically, in the first 2 bytes of memory the integer a will be saved.In the next 2 bytes the integer of the first position of the array will be saved(that means array[0]).

Then, when you say array[-1] is like referring to the integer saved in memory that is just before array[0],which in our is,hypothetically, integer a. In reality, this is not exactly the way that variables are stored in memory.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.