[regarding &array vs &array[0] ...]
About the wording "the bit values are the same", did you notice that DMR
was suggesting that the bit value coincidence was not a portable
property, for being restricted to the "usual implementation" as he said
himself ? By the way, what exactly is the "usual implementation" ?
"Usual" would be those implementations we use every day on the x86,
ARM (cell phone), MIPS (Playstation), and other such CPUs. They
have a single linear ("flat") address space (sometimes "virtualized"
and/or "per process", so as to separate various running programs,
but each one gets to pretend it is running directly on the CPU with
all memory as a single flat space) where an address is always just
a byte-number. Byte-numbers start at some base -- not necessarily
zero -- and count up.
And what is exactly meant by "the bit values are the same" ? Does this
mean that my_array and &my_array yield the same bit representation ?
On "the usual implementation", yes.
If so, does the standard guarantee such a thing ?
No. Let us take a look at an unusual implementation.
First, consider some background from a couple of other languages.
In particular, consider the following bits of Lisp:
(defun hello-world ()
(print "hello world"))
(defun factorial (n)
(if (<= n 1)
1
(* n (factorial (- n 1)))))
This particular Lisp has "atoms", "lists", "strings", and "numbers"
(and probably splits numbers into integers, floating point numbers,
and bignums). 'defun, 'hello-world, 'factorial, 'n, and so on are
all "atoms". 1 is a number and "hello world" is a string. Putting
a series of atoms in parentheses forms a list, so (defun hello-world)
is a list of two atoms. To execute a list, we look up its first
atom (if it is an atom) to see how it is defined, and pass the rest
of the list to the code for that atom. Or, if we are asked to
execute a number or string, the result is just the number or string.
Lisp compilers, especially Lisp compilers for Lisp-machines, tend
to turn this into machine code in which different types -- i.e.,
atoms, lists, numbers, and strings -- have different "tag bits".
For instance, if there are exactly two tag bits available, we might
have tag = 00 for lists, 01 for atoms, 10 for numbers, and 11 for
strings. On conventional CPUs (Intel x86, MIPS, etc.), implementors
tend to use either the bottom or top couple of address bits for
these tags. That way, you can tell if an object in memory is a
list or an atom just by looking at a couple of its address bits --
and speed is important here because absolutely every operation in
the Lisp system starts by checking the tag bits first.
(Moreover, in a design hack, on CPUs that trap "bad" alignments,
we can put the tag bits at the bottom of the address, then make
*assumptions* about the low-order bits. For instance, if 00 is
for lists, we can *assume* that some pointer is for a list, follow
the pointer, and get an alignment-fault trap if the low two bits
are not zeros. Or, if we assume that some pointer is an "atom
pointer", we can use offset -1 on the address -- since per the
above, tag bits 01 mean "atom" -- and again we will get an alignment
fault trap if our assumption was wrong. So if our assumptions are
right, the code goes just as fast as if it were compiled C code,
and we get the speed of C, but -- unlike C -- complete type-safety.)
On machines specifically *designed* to run Lisp, the hardware
generally provides extra bits on each address that are purely there
for type-checking. So if we were to compile C code for this
hardware, we could make use of these extra bits.
Now let us consider a language like Pascal, in which arrays are
very different from pointers, and never interchangeable. In some
Pascal implementations, arrays are not simply "a block of memory",
and a two (or more) dimensional array is not *just* a bigger block
of memory in which A
[j] is handled as if it were a[i * N + j]
(as compared with C, in which arrays normally *are* just big blocks
of memory, and "two-dimensional" arrays really are just handled
like this). We get runtime checking, in our compiled Pascal,
with the aid of an "array descriptor" and possibly even some
specialized CPU instruction (INDEX on the VAX, for instance).
The array descriptor is a sort of extensible structure and
looks something like this almost-C99 "struct":
struct array_descriptor {
void *base; /* address of array elements */
int dims; /* 1d, 2d, 3d? (hence 1 or more) */
size_t base_stride;
int bounds[dims][2]; /* size depends on dims */
};
The compiled code to handle A[j] looks something like this:
void *find_2d_array_element(struct array_descriptor *ap, int i, int j) {
void *result
size_t stride;
/* Require that the array really be 2d. */
if (ap->dims != 2) {
runtime_error("2d array access to %dd array", ap->dims);
/* NOTREACHED */
}
/* Verify that i and j are both within bounds. The lower
bound for each subscript is ap->dims[][0], and the upper
bound is ap->dims[][1]. */
if (i < ap->dims[0][0] || i > ap->dims[0][1])
runtime_error("array subscript 1 (%d) out of bounds [%d..%d]",
i, ap->dims[0][0], ap->dims[0][1]);
if (j < ap->dims[1][0] || i > ap->dims[1][1])
runtime_error("array subscript 2 (%d) out of bounds [%d..%d]",
j, ap->dims[0][0], ap->dims[0][1]);
/* Adjust index values i and j to work as if the array's
lower bounds were both 0, so that stride computation
is easier. Note that if the lower bounds ARE zero,
these have no effect. */
i -= ap->dims[0][0];
j -= ap->dims[1][0];
/* Use the base stride to find A[0][j] */
stride = ap->base_stride;
result = (unsigned char *)ap->base + j * stride;
/* Now find A[that] */
stride *= ap->dims[1][1] - ap->dims[1][0];
result = (unsigned char *)result + (stride * i);
return result;
}
(The result is used something like:
double *p = find_2d_array_element(descriptor, i, j);
use(*p);
for rvalues, and:
*p = PI;
for lvalues. Here I assume that "descriptor" is probably from an
array parameter, where the caller passed the address of the
descriptor. If the array were local, we might have &descriptor,
except if the array is local, we can optimize away most of this
code. We still need to compute the stride, but this is true in C
as well, and *that* machine code winds up being the same in C as
in any other language.)
(This sort of subscript checking before doing the stride computation
is why a lot of Pascal-like languages run a lot slower than a lot
of C-like languages. In many cases, the checks can be moved out
of loops or done entirely at compile-time, but *some* checks usually
remain, and they cost runtime. As we see over and over again,
people seem to prefer languages and systems that get the wrong
answer as fast as possible, by throwing away this kind of runtime
checking.)
Now, keeping both Lisp machines and typical Pascal implementations
in mind, consider how we might compile C code for a Lisp machine.
We have extra "tag bits" that go with every address. Depending on
how many tag bits we have, and how much runtime we are willing to
expend on runtime array subscript checking and so on, we could
choose to use the tag bits to carry information we then use to
locate array descriptors.[%] If we do all this, &array[0] and
&array might have *different* tag bits.
[% Major handwaving here ... 
The tag bits are invariably too
few to point directly to a separate descriptor, and too few even
to use as a table index into a table of descriptor-pointers. In
order to find the descriptor, we have to use a completely different
technique, in which we take the address of the "block of memory"
that holds the array elements, and look this up in an inversion
table. That is, we know that each descriptor D has a different
D.base, so we find the correct value of "i" by matching the
"memory block address" we have in hand against all possible D.base
values, using some sort of hash table. If we do this the obvious
way, we do not need any tag bits at all -- but we can use some of
the tag bits to speed up this search.]
Given two pointers with different tag bits, but the same "pointer
value" -- that is, one is a "Type A" pointer and the other is a
"Type B" pointer, but both point to the same "RAM address" -- do
we call these "the same value" or "different values"?
Clearly the "bit values" are different, if the term "bit values"
is taken to mean "ALL the bits, including the tag bits". But the
"address portion" of the values -- the result after stripping off
the tag bits -- is the same. So if we convert everything to
"void *", which strips off the original tag bits (pasting on tag
bits that say "void *" instead), the values will then be the same.
They were not the same originally, at least if by "values" we mean
"values including tag bits", but once we convert them to comparable
types, they *become* the same.
Since -- at least in C code -- we can only compare values after
converting them to some common type, the addresses will *appear*
to be the same.
How does one adapt this situation to the array case ? For instance,
declaring
int t[3];
can we expect (int *)&t will always equal to &t[0] ? and conservely, &t
will equal to (int (*)[3])&t[0] ?
I think it would not hurt the C standard to say so explicitly.
(On our Lisp-machine system above, it just means that after any
fiddling with the tag bits, the final bits that get compared in:
(int *)&t == &t[0]
are "the same", so that the result of the == operator is 1.) I
am not sure whether the C Standard actually says this now.
It *does* seem to say that:
(void *)&t == (void *)&t[0]
will always produce 1.