Why do arrays in C decay to pointers?

Question

[This is a question inspired by a recent discussion elsewhere, and I'll provide an answer right with it.]

I was wondering about the odd C phenomenon of arrays "decaying" to pointers, e.g. when used as function arguments. That just seems so unsafe. It is also inconvenient to pass the length explicitly with it. And I can pass the other type of aggregate -- structs -- perfectly well by value; structs do not decay.

What is the rationale behind this design decision? How does it integrate with the language? Why is there a difference to structs?

Answer 1

Rationale

Let's examine function calls because the problems are nicely visible there: Why are arrays not simply passed to functions as arrays, by value, as a copy?

There is first a purely pragmatic reason: Arrays can be big; it may not be advisable to pass them by value because they could exceed the stack size, especially in the 1970s. The first compilers were written on a PDP-7 with about 9 kB RAM.

There is also a more technical reason rooted in the language. It would be hard to generate code for a function call with arguments whose size is not known at compile time. For all arrays, including variable length arrays in modern C, simply the addresses are put on the call stack. The size of an address is of course well known. Even languages with elaborate array types carrying run time size information do not pass the objects proper on the stack. These languages typically pass "handles" around, which is what C has effectively done, too, for 40 years. See Jon Skeet here and an illustrated explanation he references (sic) here.

Now a language could make it a requirement that an array always have a complete type; i.e. whenever it is used, its complete declaration including the size must be visible. This is, after all, what C requires from structures (when they are accessed). Consequently, structures can be passed to functions by value. Requiring the complete type for arrays as well would make function calls easily compilable and obviate the need to pass additional length arguments: sizeof() would still work as expected inside the callee. But imagine what that means. If the size were really part of the array's argument type, we would need a distinct function for each array size:

// for user input. int average_ten(int arr[10]);  // for my new Hasselblad. int average_twohundredfivemilliononehundredfourtyfivethousandsixhundred(int arr[16544*12400]); // ... 

In fact it would be totally comparable to passing structures, which differ in type if their elements differ (say, one struct with 10 int elements and one with 16544*12400). It is obvious that arrays need more flexibility. For example, as demonstrated one could not sensibly provide generally usable library functions which take array arguments.

This "strong typing conundrum" is, in fact, what happens in C++ when a function takes a reference to an array; that is also the reason why nobody does it, at least not explicitly. It is totally inconvenient to the point of being useless except for cases which target specific uses, and in generic code: C++ templates provide compile-time flexibility which is not available in C.

If, in existing C, indeed arrays of known sizes should be passed by value there is always the possibility to wrap them in a struct. I remember that some IP related headers on Solaris defined address family structures with arrays in them, allowing to copy them around. Because the byte layout of the struct was fixed and known, that made sense.

For some background it's also interesting to read The Development of the C Language by Dennis Ritchie about the origins of C. C's predecessor BCPL didn't have any arrays; the memory was just homogeneous linear memory with pointers into it.

Answer 2

The answer to this question can be found in Dennis Ritchie's "The Development of the C Language" paper (see "Embryonic C" section)

According to Dennis Ritchie, the nascent versions of C directly inherited/adopted array semantics from B and BCPL languages - predecessors of C. In those languages arrays were literally implemented as physical pointers. These pointers pointed to independently allocated blocks of memory containing the actual array elements. These pointers were initialized at run time. I.e. back in B and BCPL days arrays were implemented as "binary" (bipartite) objects: an independent pointer pointing to an independent block of data. There was no difference between pointer and array semantics in those languages, aside from the fact that array pointers were initialized automatically. At any time it was possible to re-assign an array pointer in B and BCPL to make it point somewhere else.

Initially, this approach to array semantics got inherited by C. However, its drawbacks became immediately obvious when struct types were introduced into the language (something neither B nor BCPL had). And the idea was that structs should naturally be able to contain arrays. However, continuing to stick with the above "bipartite" nature of B/BCPL arrays would immediately lead to a number of obvious complications with structs. E.g. struct objects with arrays inside would require non-trivial "construction" at the point of definition. It would become impossible to copy such struct objects - a raw memcpy call would copy the array pointers without copying the actual data. One wouldn't be able to malloc struct objects, since malloc can only allocate raw memory and does not trigger any non-trivial initializations. And so on and so forth.

This was deemed unacceptable, which led to the redesign of C arrays. Instead of implementing arrays through physical pointers Ritchie decided to get rid of the pointers entirely. The new array was implemented as a single immediate memory block, which is exactly what we have in C today. However, for backward compatibility reasons the behavior of B/BCPL arrays was preserved (emulated) as much as possible at superficial level: the new C array readily decayed to a temporary pointer value, pointing to the beginning of the array. The rest of the array functionality remained unchanged, relying on that readily available result of the decay.

To quote the aforementioned paper

The solution constituted the crucial jump in the evolutionary chain between typeless BCPL and typed C. It eliminated the materialization of the pointer in storage, and instead caused the creation of the pointer when the array name is mentioned in an expression. The rule, which survives in today's C, is that values of array type are converted, when they appear in expressions, into pointers to the first of the objects making up the array.

This invention enabled most existing B code to continue to work, despite the underlying shift in the language's semantics. The few programs that assigned new values to an array name to adjust its origin—possible in B and BCPL, meaningless in C—were easily repaired. More important, the new language retained a coherent and workable (if unusual) explanation of the semantics of arrays, while opening the way to a more comprehensive type structure.

So, the direct answer to your "why" question is as follows: arrays in C were designed to decay to pointers in order to emulate (as close as possible) the historical behavior of arrays in B and BCPL languages.