Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

a[i] = x[a[i]]++

1 view
Skip to first unread message

BRG

unread,
Jan 18, 2005, 7:09:46 PM1/18/05
to
Does anyone here know whether the assignment:

a[i] = x[ a[i] ]++;

is legal in C and, if so, what array element in x[] is post incremented?

That is, does the old or the new value of a[i] determine the index in
x[] of the post incremented array element.

I rather suspect the result is undefined - but am I right?

Brian Gladman

Andrey Tarasevich

unread,
Jan 18, 2005, 7:59:41 PM1/18/05
to
BRG wrote:

> Does anyone here know whether the assignment:
>
> a[i] = x[ a[i] ]++;
>
> is legal in C

I think this code can be simplified to

i = x[i]++;

without loss of generality.

The question boils down to checking whether the old value of 'i' is read
only to determine the new value of 'i'. This requirement appears to be
formulated in the standard in rather informal fashion (I have my doubts
about the exact meaning of that "only"), but the intent was, if I
remember correctly, to require the flow of information inside the
expression to force the old value to be read _before_ the new value is
stored. There's a defect report that deals with a similar issue of
whether the

a[a[i]] = 5;

produces undefined behavior. (Unfortunately, I don't remember the defect
number.)

On the first sight, in this expression this requirement is met, i.e.
this expression is OK.

However, on the second sight, one can argue that this expression
violates that "only" requirement: in this case the old value of 'i' is
read not only to determine its new value, but also to determine, which
element of 'x[]' to increment. Personally, I don't think this is a valid
argument (considering what I think was the intent), but I could be wrong.

> and, if so, what array element in x[] is post incremented?

The one specified by the old value of 'a[i]'.

> That is, does the old or the new value of a[i] determine the index in
> x[] of the post incremented array element.

Should be the old one.

> I rather suspect the result is undefined - but am I right?

I'd say that I rather suspect that the result is defined.

--
Best regards,
Andrey Tarasevich

Chris Torek

unread,
Jan 18, 2005, 7:53:24 PM1/18/05
to
In article <41eda53a$0$44983$ed2e...@ptn-nntp-reader04.plus.net>

I myself believe that this is isomorphic to the:

p = p->next = q;

problem, so that if the linked-list version is well-defined, so is
the array version (and vice versa). I also believe that it is not
at all clear whether this is well-defined, and therefore programmers
should not use it, making the question "is it undefined" interesting
but academic. :-)
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603
email: forget about it http://web.torek.net/torek/index.html
Reading email is like searching for food in the garbage, thanks to spammers.

pete

unread,
Jan 18, 2005, 8:39:51 PM1/18/05
to
Chris Torek wrote:
>
> In article <41eda53a$0$44983$ed2e...@ptn-nntp-reader04.plus.net>
> BRG <b...@nowhere.org> wrote:
> >Does anyone here know whether the assignment:
> >
> > a[i] = x[ a[i] ]++;
> >
> >is legal in C and, if so,
> >what array element in x[] is post incremented?
> >
> >That is, does the old or the new value of a[i] determine the index in
> >x[] of the post incremented array element.
> >
> >I rather suspect the result is undefined - but am I right?
>
> I myself believe that this is isomorphic to the:
>
> p = p->next = q;
>
> problem, so that if the linked-list version is well-defined, so is
> the array version (and vice versa). I also believe that it is not
> at all clear whether this is well-defined, and therefore programmers
> should not use it, making the question "is it undefined" interesting
> but academic. :-)

The a[i] = x[a[i]]++ problem,
is a real problem which came from a program
that BRG debugged on comp.programming.

http://groups-beta.google.com/group/comp.programming/msg/fad5a77876d4d991

The actual line of code was
for (i=0;i<len;i++) cmp_index[i] = cum[cmp_index[i]]++;
which he changed to
for (i=0;i<len;i++) {
j = cmp_index[i];
cmp_index[i] = cum[j]++;
}

The sort function wouldn't work on my machine with the
original line of code, but it does with the fix.

--
pete

Ben Pfaff

unread,
Jan 18, 2005, 9:36:32 PM1/18/05
to
pete <pfi...@mindspring.com> writes:

> Chris Torek wrote:
>> I myself believe that this is isomorphic to the:
>>
>> p = p->next = q;
>>

>> problem, [...]


>
> The a[i] = x[a[i]]++ problem,
> is a real problem which came from a program
> that BRG debugged on comp.programming.

The p = p->next = q problem is also a real problem that came from
a program I was writing when I posted a question about it here
years ago.
--
"When in doubt, treat ``feature'' as a pejorative.
(Think of a hundred-bladed Swiss army knife.)"
--Kernighan and Plauger, _Software Tools_

Christopher Benson-Manica

unread,
Jan 18, 2005, 9:46:14 PM1/18/05
to
Chris Torek <nos...@torek.net> spoke thus:

> problem, so that if the linked-list version is well-defined, so is
> the array version (and vice versa). I also believe that it is not
> at all clear whether this is well-defined, and therefore programmers
> should not use it, making the question "is it undefined" interesting
> but academic. :-)

FWIW,

#include <stdio.h>
#include <stdlib.h>

int main( void )
{
int i=3;
int foo[10];
int bar[10];
bar[5]=4;
foo[i]=5;
foo[i]=bar[ foo[i] ]++;
printf( "foo[3]=%d, bar[5]=%d\n", foo[i], bar[5] );
return( EXIT_SUCCESS );
}

prints

foo[3]=4, bar[5]=5

as I at least would expect it to. The expression is (hopefully)
equivalent to

foo[3]=bar[ foo[3] ]++;

foo[3] is 5, and bar[5] is 4. Therefore foo[3] is assigned the value
4, and then bar[5] is postincremented, yielding 5. I can't see any
other reasonable order of evaluation for this statement, so I would
(very humbly) submit that it seems to have consistent behavior. I
agree with your statement that the construct is confusing at any rate
and would be unkind to future maintainers (especially if it didn't
work!) :)

--
Christopher Benson-Manica | I *should* know what I'm talking about - if I
ataru(at)cyberspace.org | don't, I need to know. Flames welcome.

pete

unread,
Jan 18, 2005, 11:12:24 PM1/18/05
to

/* BEGIN new.c */

#include <stdio.h>

int main( void )
{
int i;
int foo[10] = {0};
int bar[10] = {0};

bar[5] = 4;
foo[3] = 5;
foo[3] = bar[foo[3]]++;
printf("foo[3]=%d, bar[5]=%d\n\n", foo[3], bar[5]);

for (i = 0; i != 10; ++i) {
printf("foo[%d]=%d, bar[%d]=%d\n", i, foo[i], i, bar[i]);
}
return 0;
}

/* END new.c */

foo[3]=4, bar[5]=4

foo[0]=0, bar[0]=0
foo[1]=0, bar[1]=0
foo[2]=0, bar[2]=0
foo[3]=4, bar[3]=0
foo[4]=0, bar[4]=1
foo[5]=0, bar[5]=4
foo[6]=0, bar[6]=0
foo[7]=0, bar[7]=0
foo[8]=0, bar[8]=0
foo[9]=0, bar[9]=0

--
pete

aegis

unread,
Jan 18, 2005, 11:54:34 PM1/18/05
to

have a chapter and verse as to why the above expression
results in undefined behavior?

The only problem I see is if x[] is an alias of a[]

i.e.
void foo(int a[], int x[])
{
/* insert code */
}

int main(void)
{
int a[10];

foo(a, a);

return 0;
}

before we begin with this discussion, let's state
5.1.2.3#1

"The semantic descriptions in this International Standard
describe the behavior of an abstract machine in which
issues of optimization are irrelevant."

--
aegis

pete

unread,
Jan 19, 2005, 12:42:02 AM1/19/05
to

The prior value of foo[3]
is used to determine the new value of foo[3],
so the prior value of foo[3],
can't be used to also determine which bar[] element is incremented.


N869
6.5 Expressions

[#2] Between the previous and next sequence point an object
shall have its stored value modified at most once by the
evaluation of an expression. Furthermore, the prior value
shall be accessed only to determine the value to be
stored.

Jun Woong and Douglas A. Gwyn seem to be of one mind on this issue
in the
What language to address "tricky assignment statement"
thread, in news:comp.std.c

--
pete

aegis

unread,
Jan 19, 2005, 1:08:26 AM1/19/05
to

> The prior value of foo[3]
> is used to determine the new value of foo[3],

Did you mean to say is /not/ used?

> so the prior value of foo[3],
> can't be used to also determine which bar[] element is incremented.
>
>
> N869
> 6.5 Expressions
>
> [#2] Between the previous and next sequence point an object
> shall have its stored value modified at most once by the
> evaluation of an expression. Furthermore, the prior value
> shall be accessed only to determine the value to be
> stored.

So you are essentially saying that the use of "foo" on the right
hand side of the assignment operator is not allowed because
we modify the value of that same object on the left hand side of the
assignment operator. In which case, foo[3] is modified before
we use it to determine the value of bar[] to modify foo[3].

This certainly sounds absurd to me. And I don't see how 6.5#2
fits in here. foo[3] is exactly modified once. But before it
is modified me must first evaluate the right hand side of the
assignment expression, yes?

According to 6.5.16.1#2 we have a well defined ordering here.
and 6.5.16.1#5 only reaffirms it.

--
aegis

pete

unread,
Jan 19, 2005, 1:42:47 AM1/19/05
to
aegis wrote:
>
> > The prior value of foo[3]
> > is used to determine the new value of foo[3],
>
> Did you mean to say is /not/ used?

is

>
> > so the prior value of foo[3],
> > can't be used to also determine which bar[] element is incremented.
> >
> >
> > N869
> > 6.5 Expressions
> >
> > [#2] Between the previous and next sequence point an object
> > shall have its stored value modified at most once by the
> > evaluation of an expression. Furthermore, the prior value
> > shall be accessed only to determine the value to be
> > stored.
>
> So you are essentially saying that the use of "foo" on the right
> hand side of the assignment operator is not allowed because
> we modify the value of that same object on the left hand side of the
> assignment operator.
> In which case, foo[3] is modified before
> we use it to determine the value of bar[] to modify foo[3].

No.

The "prior value" of foo[3] is 5.

I'm saying that 5, is used to determine which
element of bar is assigned to foo[3], (bar[5])
and that 5 can't also be used to determine
which element of bar is incremented.

"the prior value shall be accessed

^^^^^ ^^^^^


only to determine the value to be stored."

> foo[3] is exactly modified once. But before it


> is modified me must first evaluate the right hand side of the
> assignment expression, yes?

Yes.
But we can increment the right operand of the assignment,
after the assignment, by which time foo[3] has a value of 4.

--
pete

aegis

unread,
Jan 19, 2005, 2:30:13 AM1/19/05
to

pete wrote:
> aegis wrote:
> >
> > > The prior value of foo[3]
> > > is used to determine the new value of foo[3],
> >
> > Did you mean to say is /not/ used?
>
> is

Then this is wrong.
The prior value of foo[3] in "bar[foo[3]]++"
is not used to determine the new value of
foo[3]. It is used to determine the element
of bar, which bar is used to determine the


new value of foo[3]

>
> >

That doesn't even make sense.

>
> "the prior value shall be accessed
> ^^^^^ ^^^^^
> only to determine the value to be stored."
>
> > foo[3] is exactly modified once. But before it
> > is modified me must first evaluate the right hand side of the
> > assignment expression, yes?
>
> Yes.
> But we can increment the right operand of the assignment,
> after the assignment, by which time foo[3] has a value of 4.

and? how does this affect anything?

--
aegis

BRG

unread,
Jan 19, 2005, 3:41:17 AM1/19/05
to
Andrey Tarasevich wrote:

> BRG wrote:
>
>
>>Does anyone here know whether the assignment:
>>
>> a[i] = x[ a[i] ]++;
>>
>>is legal in C
>
>
> I think this code can be simplified to
>
> i = x[i]++;
>
> without loss of generality.

As far as I can see, yes.

> The question boils down to checking whether the old value of 'i' is read
> only to determine the new value of 'i'. This requirement appears to be
> formulated in the standard in rather informal fashion (I have my doubts
> about the exact meaning of that "only"), but the intent was, if I
> remember correctly, to require the flow of information inside the
> expression to force the old value to be read _before_ the new value is
> stored. There's a defect report that deals with a similar issue of
> whether the
>
> a[a[i]] = 5;
>
> produces undefined behavior. (Unfortunately, I don't remember the defect
> number.)
>
> On the first sight, in this expression this requirement is met, i.e.
> this expression is OK.
>
> However, on the second sight, one can argue that this expression
> violates that "only" requirement: in this case the old value of 'i' is
> read not only to determine its new value, but also to determine, which
> element of 'x[]' to increment. Personally, I don't think this is a valid
> argument (considering what I think was the intent), but I could be wrong.
>
>>and, if so, what array element in x[] is post incremented?
>
> The one specified by the old value of 'a[i]'.

This is where I think the action becomes undefined. There are three
steps in evaluation and two separate stores:

(1) compute a[i] and then x[ a[i] ]
(2) store the result in a[i]
(3) access x[ a[i] ], add 1 to it and store in x[ a[i] ]

I am not convinced that we can rely on the order of (2) and (3) and the
result does depend on whether the order is (2) and then (3) or (3) and
then (2).

And then a[i] - which has been written to - is used to determine _which_
element of x[] is postincremented -and this appears to violate the
principal that items that are written to during evaluation must only be
used to compute the _values_ written and not the addresses at which
writes take place.

So in my view it is not the write of a[i] that violates this clause but
the write that is a part of the post increment operation.

>>That is, does the old or the new value of a[i] determine the index in
>>x[] of the post incremented array element.
>
> Should be the old one.

On Microsft VC++ it is the new value of a[i] that is used.

>>I rather suspect the result is undefined - but am I right?
>
> I'd say that I rather suspect that the result is defined.

I remain unconvinced of this and still lean towards 'undefined' (a)
because of the problem with the order of write operations, and (b)
because a written to value is being used to determine the address at
which the post increment write operation takes place.

Brian Gladman

aegis

unread,
Jan 19, 2005, 4:58:39 AM1/19/05
to

Your idea is more closely related to assembler than
what is described in the C standard.

The standard does not dictate that this expression
would require two separate stores. Stop thinking this way.

--
aegis

BRG

unread,
Jan 19, 2005, 5:27:30 AM1/19/05
to

I'll stop thinking this way when you show, in the normal case where x[]
and a[] don't overlap, how the expression can be fully evaluated with
less than two store operations.

Brian Gladman

aegis

unread,
Jan 19, 2005, 5:44:25 AM1/19/05
to

I don't have to because the standard does not concern itself
with such issues. It is irrelevant to it. The standard describes
things in such a way that any details on how an implementation
goes about making writes or stores etc is abstracted away.
If you are looking for an authoritative answer to your
original question, you will more than likely get it in comp.std.c
not comp.lang.c

--
aegis

BRG

unread,
Jan 19, 2005, 6:07:23 AM1/19/05
to
aegis wrote:

[snip]


>>>>This is where I think the action becomes undefined. There are three
>>>>steps in evaluation and two separate stores:
>>>>
>>>>(1) compute a[i] and then x[ a[i] ]
>>>>(2) store the result in a[i]
>>>>(3) access x[ a[i] ], add 1 to it and store in x[ a[i] ]
>>>>
>>>
>>>Your idea is more closely related to assembler than
>>>what is described in the C standard.
>>>
>>>The standard does not dictate that this expression
>>>would require two separate stores. Stop thinking this way.
>>
>>I'll stop thinking this way when you show, in the normal case where x[]
>>and a[] don't overlap, how the expression can be fully evaluated with
>>less than two store operations.
>
> I don't have to because the standard does not concern itself
> with such issues.

To be of any use here the standard has to be concerned with such issues.

The standard describes
> things in such a way that any details on how an implementation
> goes about making writes or stores etc is abstracted away.

But it cannot avoid the fact that, except in unusual cases, the statment
in question updates two objects, a[i] and x[ a[i] ]. Since the result
is different depending on the order in which these updates occur the
standard either has to specify this order or allow any order. And in the
latter case the result will be undefined.

> If you are looking for an authoritative answer to your
> original question, you will more than likely get it in comp.std.c
> not comp.lang.c

I agree.

Brian Gladman

pete

unread,
Jan 19, 2005, 8:02:59 AM1/19/05
to
aegis wrote:
>
> pete wrote:

> > But we can increment the right operand of the assignment,
> > after the assignment, by which time foo[3] has a value of 4.
> and? how does this affect anything?

It means that the two side effects invoked by the code are
foo[3] = 4;
bar[4]++;

--
pete

Richard Bos

unread,
Jan 19, 2005, 10:14:49 AM1/19/05
to
"aegis" <ae...@mad.scientist.com> wrote:

> pete wrote:
> > aegis wrote:
> > >
> > > > The prior value of foo[3]
> > > > is used to determine the new value of foo[3],
> > >
> > > Did you mean to say is /not/ used?
> >
> > is
>
> Then this is wrong.
> The prior value of foo[3] in "bar[foo[3]]++"
> is not used to determine the new value of
> foo[3]. It is used to determine the element
> of bar, which bar is used to determine the
> new value of foo[3]

Yes. This means that, indirectly, foo[3] _is_ used to determine the new
value of foo[3]. The big question here is, is this indirect action
enough to save this from being undefined behaviour? To be honest, I
don't know the answer myself, but I know enough to see that it is far
from obvious.

Richard

Joona I Palaste

unread,
Jan 19, 2005, 11:33:22 AM1/19/05
to
BRG <b...@nowhere.org> scribbled the following:

I would first intuitively consider it defined, but when I look at it
more closely, it becomes obvious that the old value of a[i] is *NOT*
only used to determine the new value, it is also being used to index
to the x array. Therefore the behaviour is undefined.
Someone also mentioned something along the lines of a[a[i]]=i. This I
would consider defined behaviour, because what is being modified is
a[a[i]], and its old value is never used in the expression at all. And
indexing to an array with an element from the same array is perfectly
legal, as long as the array's element type is an integer type.
However, p = p->next = q looks like undefined behaviour, precisely
because the old value of p is also used to point to a structure, whose
"next" field is being modified.

--
/-- Joona Palaste (pal...@cc.helsinki.fi) ------------- Finland --------\
\-------------------------------------------------------- rules! --------/
"He said: 'I'm not Elvis'. Who else but Elvis could have said that?"
- ALF

Joona I Palaste

unread,
Jan 19, 2005, 11:39:33 AM1/19/05
to
Andrey Tarasevich <andreyta...@hotmail.com> scribbled the following:

> BRG wrote:
>> Does anyone here know whether the assignment:
>>
>> a[i] = x[ a[i] ]++;
>>
>> is legal in C

> I think this code can be simplified to

> i = x[i]++;

> without loss of generality.

> The question boils down to checking whether the old value of 'i' is read
> only to determine the new value of 'i'.

Yes it does, and no it is not. The old value of i is also being used as
an index to the x array. Therefore this caused undefined behaviour.

> This requirement appears to be
> formulated in the standard in rather informal fashion (I have my doubts
> about the exact meaning of that "only"), but the intent was, if I
> remember correctly, to require the flow of information inside the
> expression to force the old value to be read _before_ the new value is
> stored. There's a defect report that deals with a similar issue of
> whether the

> a[a[i]] = 5;

> produces undefined behavior. (Unfortunately, I don't remember the defect
> number.)

> On the first sight, in this expression this requirement is met, i.e.
> this expression is OK.

Of course the expression "a[a[i]]=5" is OK. But were you talking about
the earlier expression "i=x[i]++" instead?

> However, on the second sight, one can argue that this expression
> violates that "only" requirement: in this case the old value of 'i' is
> read not only to determine its new value, but also to determine, which
> element of 'x[]' to increment. Personally, I don't think this is a valid
> argument (considering what I think was the intent), but I could be wrong.

If you were talking about "a[a[i]]=5" above, then this is plain
nonsense. However, if you were talking about "i=x[i]++", as I think you
were, you are right.

>> and, if so, what array element in x[] is post incremented?

> The one specified by the old value of 'a[i]'.

No, not necessarily.

>> That is, does the old or the new value of a[i] determine the index in
>> x[] of the post incremented array element.

> Should be the old one.

Again, not necessarily.

>> I rather suspect the result is undefined - but am I right?

> I'd say that I rather suspect that the result is defined.

I'd say I rather suspect the exact opposite. There is no guarantee which
order C executes the modifications in, or indeed whether it executes
them at all. This is due to the lack of an intervening sequence point.

--
/-- Joona Palaste (pal...@cc.helsinki.fi) ------------- Finland --------\
\-------------------------------------------------------- rules! --------/

"'So called' means: 'There is a long explanation for this, but I have no
time to explain it here.'"
- JIPsoft

BRG

unread,
Jan 19, 2005, 12:04:48 PM1/19/05
to
Joona I Palaste wrote:
> BRG <b...@nowhere.org> scribbled the following:
>
>>Does anyone here know whether the assignment:
>
>
>> a[i] = x[ a[i] ]++;
>
>
>>is legal in C and, if so, what array element in x[] is post incremented?
>
>
>>That is, does the old or the new value of a[i] determine the index in
>>x[] of the post incremented array element.
>
>
>>I rather suspect the result is undefined - but am I right?
>
>
> I would first intuitively consider it defined, but when I look at it
> more closely, it becomes obvious that the old value of a[i] is *NOT*
> only used to determine the new value, it is also being used to index
> to the x array. Therefore the behaviour is undefined.

That's my view too. I also suspect that the two possible orders of the
two update operations - a[i] and x[a[i]] - would make it undefined as well.

Thanks to you and others for taking the time to comment on this.

[snip]

Brian Gladman

Andrey Tarasevich

unread,
Jan 19, 2005, 12:15:37 PM1/19/05
to
Joona I Palaste wrote:
>>> Does anyone here know whether the assignment:
>>>
>>> a[i] = x[ a[i] ]++;
>>>
>>> is legal in C
>
>> I think this code can be simplified to
>
>> i = x[i]++;
>
>> without loss of generality.
>
>> The question boils down to checking whether the old value of 'i' is read
>> only to determine the new value of 'i'.
>
> Yes it does, and no it is not. The old value of i is also being used as
> an index to the x array. Therefore this caused undefined behaviour.

I don't see how this alone can cause undefined behavior. The same can be
said about the following expression

i = x[i];

but there's no undefined behavior in this case. Using 'i' as an index
for 'x' array is a part of that "reading of 'i' only to determine the
new value of 'i'". Everything is fine here.

The problem appears once you add the increment. With the increment, the
only thing that's not exactly clear to me is whether this attempt to use
the same subexpression 'x[i]' (that evaluates lvalue 'x[i]' for 'i ='
assignment) as an argument for some other operator (post-increment in
this case) violates that "only" requirement from the standard.

Or, at lower level, whether implementations are required to calculate
lvalue 'x[i]' only once (and use it as an argument in both assignment
and increment) or allowed to do it twice (first time - for assignment,
second time - for increment). In the first case one would expect to see
"consistent" behavior.

>> This requirement appears to be
>> formulated in the standard in rather informal fashion (I have my doubts
>> about the exact meaning of that "only"), but the intent was, if I
>> remember correctly, to require the flow of information inside the
>> expression to force the old value to be read _before_ the new value is
>> stored. There's a defect report that deals with a similar issue of
>> whether the
>
>> a[a[i]] = 5;
>
>> produces undefined behavior. (Unfortunately, I don't remember the defect
>> number.)
>
>> On the first sight, in this expression this requirement is met, i.e.
>> this expression is OK.
>
> Of course the expression "a[a[i]]=5" is OK. But were you talking about
> the earlier expression "i=x[i]++" instead?

Yes. I was talking about 'i=x[i]++' I added 'a[a[i]] = 5' later and
missed the fact that it makes the text below rather confusing.

'a[a[i]]=5' is not immediately "OK", BTW. It can be argued that in
situation when a[i] == i the inner reading of the value of 'a[i]' is not
done for the sole purpose of forming its new value and therefore the
whole expression causes undefined behavior from the formal point of
view. However, once you consider the flow of info inside this
expression, it is obvious that the value of 'a[i]' cannot be modified
before the inner 'a[i]' is evaluated. Which rises the question whether
such expressions were outlawed intentionally.

Andrey Tarasevich

unread,
Jan 19, 2005, 12:18:28 PM1/19/05
to
Joona I Palaste wrote:
> Someone also mentioned something along the lines of a[a[i]]=i. This I
> would consider defined behaviour, because what is being modified is
> a[a[i]], and its old value is never used in the expression at all.

In general case it is possible that a[i] == i, in which case the problem
is rather obvious. This example is specifically targeted at this
particular situation.

Thomas Stegen

unread,
Jan 19, 2005, 12:29:14 PM1/19/05
to
Joona I Palaste wrote:
> Andrey Tarasevich <andreyta...@hotmail.com> scribbled the following:
>
>>BRG wrote:
>>
>>>Does anyone here know whether the assignment:
>>>
>>> a[i] = x[ a[i] ]++;

> Yes it does, and no it is not. The old value of i is also being used as


> an index to the x array. Therefore this caused undefined behaviour.

a[i] = (*(x + a[i]))++;

Why is the above so very different from "i = i + 3;"?
Point is, why is the index operator so different from the addition
operator?

i is read to be used as an operand for the addition operator.
a[i] is read to be used as an operand for the index operator.
Then in both cases the result is written back.

If someone can explain to me how the addition operator can be used
to only determine the result to store while the index operator cannot
I would appreciate it.

An operator takes a set of operands and delivers a value. It seems to
me that in both cases the operands are read only to determine the
value of this operation.

The more I think about the surer I become that the above is defined.
The basic semantics for operators apply to all operators and I don't
see any differences in this case.


>>On the first sight, in this expression this requirement is met, i.e.
>>this expression is OK.
>
>
> Of course the expression "a[a[i]]=5" is OK.

Hint: a[i] == i

>
>>However, on the second sight, one can argue that this expression
>>violates that "only" requirement: in this case the old value of 'i' is
>>read not only to determine its new value, but also to determine, which
>>element of 'x[]' to increment. Personally, I don't think this is a valid
>>argument (considering what I think was the intent), but I could be wrong.
>
>
> If you were talking about "a[a[i]]=5" above, then this is plain
> nonsense.

If "this" refers to what you are saying you are correct.

--
Thomas.

Joona I Palaste

unread,
Jan 19, 2005, 12:27:43 PM1/19/05
to
Andrey Tarasevich <andreyta...@hotmail.com> scribbled the following:

If a[i]==i, then the expression is equivalent to a[i]=i. However, this
is still very much defined behaviour, as the object being modified is
a[i], and its old value is not actually used for anything at all in the
above code. Note that even though a[i]==i that doesn't mean that
&(a[i])==&i, i.e. changing one won't affect the other.

--
/-- Joona Palaste (pal...@cc.helsinki.fi) ------------- Finland --------\
\-------------------------------------------------------- rules! --------/

"'It can be easily shown that' means 'I saw a proof of this once (which I didn't
understand) which I can no longer remember'."
- A maths teacher

BRG

unread,
Jan 19, 2005, 1:03:59 PM1/19/05
to
Thomas Stegen wrote:
> Joona I Palaste wrote:
>
>> Andrey Tarasevich <andreyta...@hotmail.com> scribbled the following:
>>
>>> BRG wrote:
>>>
>>>> Does anyone here know whether the assignment:
>>>>
>>>> a[i] = x[ a[i] ]++;
>
>
>> Yes it does, and no it is not. The old value of i is also being used as
>> an index to the x array. Therefore this caused undefined behaviour.
>
> a[i] = (*(x + a[i]))++;
>
> Why is the above so very different from "i = i + 3;"?
> Point is, why is the index operator so different from the addition
> operator?

In my view its really the post-increment operation that needs to be
considered.

This is because, if the post-increment is the last thing done in
evaluating the right hand side (i.e it is done before a[i] on the left
hand side is updated), then x[ old a[i] ] will be post-incremented.

However, if the post-increment is the last thing done in evaluating the
whole expression (i.e it is done after a[i] on the left hand side is
updated) then x[ new a[i] ] will be post-incremented.

[snip]
Brian Gladman

Joona I Palaste

unread,
Jan 19, 2005, 1:09:42 PM1/19/05
to
Thomas Stegen <thomas...@gmail.com> scribbled the following:

> Joona I Palaste wrote:
>> Of course the expression "a[a[i]]=5" is OK.

> Hint: a[i] == i

Hmm, now I think I see what people mean here. It's not i that matters
here, it's a[i]. If a[i]==i, then a[i] is both assigned a new value and
used for computing something other than its new value, i.e. the value of
a[a[i]].


--
/-- Joona Palaste (pal...@cc.helsinki.fi) ------------- Finland --------\
\-------------------------------------------------------- rules! --------/

"We're women. We've got double standards to live up to."
- Ally McBeal

Andrey Tarasevich

unread,
Jan 19, 2005, 1:19:47 PM1/19/05
to
Joona I Palaste wrote:
> Andrey Tarasevich <andreyta...@hotmail.com> scribbled the following:
>> Joona I Palaste wrote:
>>> Someone also mentioned something along the lines of a[a[i]]=i. This I
>>> would consider defined behaviour, because what is being modified is
>>> a[a[i]], and its old value is never used in the expression at all.
>
>> In general case it is possible that a[i] == i, in which case the problem
>> is rather obvious. This example is specifically targeted at this
>> particular situation.
>
> If a[i]==i, then the expression is equivalent to a[i]=i.

That's a pretty strong statement. It would be equivalent if one could be
sure that the original one does not produce UB.

> However, this
> is still very much defined behaviour, as the object being modified is
> a[i], and its old value is not actually used for anything at all in the
> above code.

Huh? What do you mean by "not used"? The expression 'a[a[i]] = i', or
simply 'a[a[i]] = 0' formally violates the requirements if the standard.
In general case it is possible that a[i] == i, which means that this
expression modifies the value of 'a[i]' object (outer 'a[]', assigns 0
to it) and at the same time reads its value (inner 'a[]'). It can't be
said that this act of reading is performed for the sole purpose of
determining the new value of the object, therefore it's UB.

> Note that even though a[i]==i that doesn't mean that
> &(a[i])==&i, i.e. changing one won't affect the other.

It looks like you were looking in wrong direction. The problem is not
with 'i'. The problem is with 'a[i]', which is modified and read at in
the same expression if a[i] == i. The problem still exists, once again, in

a[a[i]] = 0;

Joona I Palaste

unread,
Jan 19, 2005, 1:49:10 PM1/19/05
to
Andrey Tarasevich <andreyta...@hotmail.com> scribbled the following:
> Joona I Palaste wrote:
>> However, this
>> is still very much defined behaviour, as the object being modified is
>> a[i], and its old value is not actually used for anything at all in the
>> above code.

> Huh? What do you mean by "not used"? The expression 'a[a[i]] = i', or
> simply 'a[a[i]] = 0' formally violates the requirements if the standard.
> In general case it is possible that a[i] == i, which means that this
> expression modifies the value of 'a[i]' object (outer 'a[]', assigns 0
> to it) and at the same time reads its value (inner 'a[]'). It can't be
> said that this act of reading is performed for the sole purpose of
> determining the new value of the object, therefore it's UB.

Ignore what I said. I thought about it a bit more and found out you were
right.

--
/-- Joona Palaste (pal...@cc.helsinki.fi) ------------- Finland --------\
\-------------------------------------------------------- rules! --------/

"Bad things only happen to scoundrels."
- Moominmamma

Andrey Tarasevich

unread,
Jan 19, 2005, 1:50:40 PM1/19/05
to
BRG wrote:
> ...

> On Microsft VC++ it is the new value of a[i] that is used.
> ...

Indeed. Which means that MSVC++ re-evaluates the subexpression 'x[a[i]]'
before performing the increment. This doesn't really look like a usual
real-life manifestation of UB, but more like a deliberate effort made by
the authors of the compiler. Which immediately begs for the following
experiment. How is MSVC++ going to evaluate this

a[i] = x[e[d[c[b[a[i]]]]]]++;

? Is it going to re-evaluate the whole 'x[e[d[c[b[a[i]]]]]]' in order to
apply the increment? A simple experiment shows that MSVC++ generates
code that does essentially the following

1. t = x[e[d[c[b[a[i]]]]]]
2. a[i] = t
3. t = x[e[d[c[b[t]]]]] (i.e. it re-evaluates the whole thing using
the new value of a[i])
4. t++;
5. x[e[d[c[b[a[i]]]]]] = t (i.e. it re-evaluates the whole thing one
more time)

Indeed, the x[] element is re-evaluated. To me this definitely looks
like a deliberate effort. Looks like the authors of the compiler didn't
want to leave it "undefined" and actually thought that the new value of
'a[i]' _has_ to be used in this case.

What I don't understand though is why they re-evaluate it one more time
at step 5. It doesn't seem to make any sense. But then again, the whole
thing doesn't make much sense.

Andrey Tarasevich

unread,
Jan 19, 2005, 2:00:24 PM1/19/05
to
BRG wrote:
> ...

> This is because, if the post-increment is the last thing done in
> evaluating the right hand side (i.e it is done before a[i] on the left
> hand side is updated), then x[ old a[i] ] will be post-incremented.
>
> However, if the post-increment is the last thing done in evaluating the
> whole expression (i.e it is done after a[i] on the left hand side is
> updated) then x[ new a[i] ] will be post-incremented.
> ...

It is not really about when the post-increment is done. It is about when
the _argument_ for the post-increment is determined.

If the compiler decides to evaluate 'x[a[i]]' only once and use it as
argument for both assignment and post-increment, then the old value of
'a[i]' is always used. The sequence of steps can be illustrated by the
following code sketch

p = &x[a[i]] and then a[i] = (*p)++

But if the compiler decides to re-evaluate the argument of the
post-increment then, of course, the new value of 'a[i]' will be used

a[i] = x[a[i]] and then x[a[i]]++

BRG

unread,
Jan 19, 2005, 2:34:23 PM1/19/05
to
Andrey Tarasevich wrote:
> BRG wrote:
>
>>...
>>This is because, if the post-increment is the last thing done in
>>evaluating the right hand side (i.e it is done before a[i] on the left
>>hand side is updated), then x[ old a[i] ] will be post-incremented.
>>
>>However, if the post-increment is the last thing done in evaluating the
>>whole expression (i.e it is done after a[i] on the left hand side is
>>updated) then x[ new a[i] ] will be post-incremented.
>>...
>
> It is not really about when the post-increment is done. It is about when
> the _argument_ for the post-increment is determined.

Of course - as my use of 'old a[i]' and 'new a[i]' above makes clear.

> If the compiler decides to evaluate 'x[a[i]]' only once and use it as
> argument for both assignment and post-increment, then the old value of
> 'a[i]' is always used. The sequence of steps can be illustrated by the
> following code sketch
>
> p = &x[a[i]] and then a[i] = (*p)++
>
> But if the compiler decides to re-evaluate the argument of the
> post-increment then, of course, the new value of 'a[i]' will be used
>
> a[i] = x[a[i]] and then x[a[i]]++

I think we have an analysis but we still have no answer to the original
question until we know whether or not compiler writers are free to chose
either order of evaluation.

I suspect that they do have such a choice and hence that the statement
produces an undefined result.

Brian Gladman

Old Wolf

unread,
Jan 19, 2005, 3:48:21 PM1/19/05
to
Chris Torek wrote:

> BRG <b...@nowhere.org> wrote:
> >Does anyone here know whether the assignment:
> >
> > a[i] = x[ a[i] ]++;
> >
> >is legal in C and, if so, what array element in x[] is post
incremented?
> >That is, does the old or the new value of a[i] determine the index
in
> >x[] of the post incremented array element.

Here's my take on the situation. I thnk we can agree that the
above statement is isomorphic to:

. i = x[i]++;

I dislike the wording in the standard; when considering these
problems I use this: "If there is 1 write of FOO and 1 or more
reads of FOO with no intervening sequence point, then the
behaviour is defined if and only if it is impossible to perform
the write without first performing all of the reads".
In the context of the abstract machine of course.
I believe this reflects the committee's intent, although it
does differ from the actual wording.

In this example there are TWO reads of i: as part of
reading x[i] in order to determine the value to be assigned
to i, and also in reading the location of x[i] in order
to increment it. The former must come before the write, but
the latter may come after it.

We must remember that we are talking in the context of the
abstract machine, rather than doing what is intuitively obvious
and optimising the two calculations of &x[i] to one.
The behaviour of MSVC bears this out.


> I myself believe that this is isomorphic to the:
>
> p = p->next = q;

I'm not convinced yet :)
This is clearly isomorphic to:

. p = p[5] = q;

This example is clear to me. The two operations are (p = q)
and (p->next = q). NOT (p = p->next) as some people have got
hung up on; the standard is quite clear that in (a = b = 3.1),
a gets the value 3.1 even if b were an int.

Going by my formulation of the rule, the read of p
for (p->next = q) may occur after the write of p
in (p = q), so the behaviour is undefined.

> I also believe that it is not
> at all clear whether this is well-defined, and therefore programmers
> should not use it, making the question "is it undefined" interesting
> but academic. :-)

Although it is still 2 reads and 1 write, I don't yet see
the isomorphism. As an aside, I wonder if the sequence
point model could be expressed in formal logic and then
we could automatically solve all of these problems.

Regarding a[a[i]] = 5, I haven't seen this before, but
it appears there is only a problem when i == a[i].
'i' is never written and does not depend on 'a', so
we could reformulate it to:
. a[0] = 0;
. a[ a[0] ] = 5;
There is one read of a[0] and one write of a[0], and
the read must come before the write (otherwise, how
do you know where to write), so the behaviour is defined.

Andrey Tarasevich wrote that the read occurs "at the same
time" as the write, but in the abstract machine this
is impossible, one must come first. If this example
is undefined then I'd consider it a defect in the
standard's wording; it appears to comply with the committee
intent, and I really don't see how it is possible for a
compiler to get this wrong. (NB. all this is IMHO of course)

Andrey Tarasevich

unread,
Jan 19, 2005, 6:06:02 PM1/19/05
to
Old Wolf wrote:
>> >Does anyone here know whether the assignment:
>> >
>> > a[i] = x[ a[i] ]++;
>> >
>> >is legal in C and, if so, what array element in x[] is post
> incremented?
>> >That is, does the old or the new value of a[i] determine the index
> in
>> >x[] of the post incremented array element.
>
> Here's my take on the situation. I thnk we can agree that the
> above statement is isomorphic to:
>
> . i = x[i]++;

Only if we assume that there's no aliasing.

> In this example there are TWO reads of i: as part of
> reading x[i] in order to determine the value to be assigned
> to i, and also in reading the location of x[i] in order
> to increment it. The former must come before the write, but
> the latter may come after it.

That's the key question. Is this really ONE or TWO reads of 'i'? I
couldn't find a definitive answer in the standard.

> We must remember that we are talking in the context of the
> abstract machine, rather than doing what is intuitively obvious
> and optimising the two calculations of &x[i] to one.

If the standard defines this as two reads of 'i', then indeed that would
be optimization. Otherwise, I wouldn't call it "optimization".

> Regarding a[a[i]] = 5, I haven't seen this before, but
> it appears there is only a problem when i == a[i].
> 'i' is never written and does not depend on 'a', so
> we could reformulate it to:
> . a[0] = 0;
> . a[ a[0] ] = 5;
> There is one read of a[0] and one write of a[0], and
> the read must come before the write (otherwise, how
> do you know where to write), so the behaviour is defined.

That's AFAIK the rationale behind the requirement given in the standard.
The intent was to make such code legal. However, the current wording in
the standard insists that this code produces UB.

> Andrey Tarasevich wrote that the read occurs "at the same
> time" as the write,

Hmm... I don't remember writing that.

> but in the abstract machine this
> is impossible, one must come first. If this example
> is undefined then I'd consider it a defect in the
> standard's wording; it appears to comply with the committee
> intent, and I really don't see how it is possible for a
> compiler to get this wrong. (NB. all this is IMHO of course)

That's exactly what I'm saying.

Christian Kandeler

unread,
Jan 20, 2005, 2:51:49 AM1/20/05
to
Old Wolf wrote:

> the standard is quite clear that in (a = b = 3.1),
> a gets the value 3.1 even if b were an int.

Really? You should tell that to the gcc people, then:

$ cat > test.c
#include <stdio.h>
#include <stdlib.h>

int main(void)
{
double a;
int b;

a = b = 3.1;

printf("a = %f\nb = %d\n", a, b);

return EXIT_SUCCESS;
}
^D
$ gcc -W -Wall -ansi -pedantic test.c
$ ./a.out
a = 3.000000
b = 3


Christian

Richard Bos

unread,
Jan 20, 2005, 3:37:37 AM1/20/05
to
Christian Kandeler <christian...@hob.de_invalid> wrote:

> Old Wolf wrote:
>
> > the standard is quite clear that in (a = b = 3.1),
> > a gets the value 3.1 even if b were an int.
>
> Really? You should tell that to the gcc people, then:

Or to the C Standard committee:

# The type of an assignment expression is the type of the left operand
# unless the left operand has qualified type, in which case it is the
# unqualified version of the type of the left operand.
(From 6.5.16#3. Identical wording in C89.)

Richard

Lawrence Kirby

unread,
Jan 20, 2005, 9:03:00 AM1/20/05
to

If "indirect action" were not allowed then expressions like i = i + 1
would be undefined. I can see nothing in the standard that could be used
as a basis for a distinction between + and operators like = [] or ++ in
this respect. In particular there is no connection between the "only"
in 6.5p2 and side-effects if you accept that this is undefined
(void)((i = j) + i). Indeed I maintain that this sort of expression is the
real target of the word "only".

Lawrence

Albert van der Horst

unread,
Jan 20, 2005, 5:40:57 PM1/20/05
to
In article <41eda53a$0$44983$ed2e...@ptn-nntp-reader04.plus.net>,

BRG <b...@nowhere.org> wrote:
>Does anyone here know whether the assignment:
>
> a[i] = x[ a[i] ]++;

I never use a statement like
x++;
on its own.
I always do the equivalent (barring the result value)
x += 1;
This shows that it is an assignment, rather than a side effect.
(The result of x++ is of course x, then it is thrown away,
oh and by the way, I have incremented x for you.
Extremely silly.)

Now the above is using the side effect,
to mix up in one statement
new = x[ old ];
x[ old ] += 1;

It is *not* equivalent to
a[i] = x[ a[i] ] += 1;
because, being a post-increment, the original value of
x[ a[i] ] must be used.

This is valid, but is more appropriate for iocc than
supposedly maintainable code. There couldn't be a problem,
because there is nothing that is changed twice between the
sequence points, neither x[ old ] nor a[i] .

>
>is legal in C and, if so, what array element in x[] is post incremented?
>
>That is, does the old or the new value of a[i] determine the index in
>x[] of the post incremented array element.
>

>I rather suspect the result is undefined - but am I right?

Because the optimiser got confused?

> Brian Gladman

--
--
Albert van der Horst,Oranjestr 8,3511 RA UTRECHT,THE NETHERLANDS
One man-hour to invent,
One man-week to implement,
One lawyer-year to patent.

Peter Nilsson

unread,
Jan 20, 2005, 7:41:57 PM1/20/05
to
Albert van der Horst wrote:
> In article <41eda53a$0$44983$ed2e...@ptn-nntp-reader04.plus.net>,
> BRG <b...@nowhere.org> wrote:
> >Does anyone here know whether the assignment:
> >
> > a[i] = x[ a[i] ]++;
>
> I never use a statement like
> x++;
> on its own.

Why?!

> I always do the equivalent (barring the result value)
> x += 1;
> This shows that it is an assignment, rather than a side effect.

Rather poor reasoning since x++ is idiomatic, and because _all_
statements are _only_ evaluated for their side effects,
assignments or otherwise (e.g. function calls.)

> (The result of x++ is of course x, then it is thrown away,
> oh and by the way, I have incremented x for you.
> Extremely silly.)

Yes, ": @++ dup @ dup 1+ over ! ;" _is_ silly, but only because
Forth is silly. ;)

--
Peter

Andrey Tarasevich

unread,
Jan 20, 2005, 8:04:12 PM1/20/05
to
Albert van der Horst wrote:
>>Does anyone here know whether the assignment:
>>
>> a[i] = x[ a[i] ]++;
>
> I never use a statement like
> x++;
> on its own.
> I always do the equivalent (barring the result value)
> x += 1;
> This shows that it is an assignment, rather than a side effect.

The assignment itself is also a side effect. What you do is in no way
different from using the increment.

> (The result of x++ is of course x, then it is thrown away,
> oh and by the way, I have incremented x for you.
> Extremely silly.)

Not sillier than your variant. The result of 'x += 1' is the old value
of 'x' plus 1 and it is thrown away in exactly the same way. The change
of the value of 'x' is nothing else than a side effect of 'x += 1' (yes,
it's like you said "oh and by the way, I have incremented x for you").

Keep in mind that the result of expression statement in C is _always_
thrown away. Any changes in values of objects involved in the expression
are _always_ caused by side effects. There's absolutely no difference
between 'x += 1' and 'x++' in this respect.

> Now the above is using the side effect,
> to mix up in one statement
> new = x[ old ];
> x[ old ] += 1;
>
> It is *not* equivalent to
> a[i] = x[ a[i] ] += 1;
> because, being a post-increment, the original value of
> x[ a[i] ] must be used.

This is completely irrelevant. If you read this thread carefully, you'll
see that the real question is which value of 'a[i]' is used (old or
new), not which value of 'x[a[i]]' is used. The latter is pretty much
irrelevant.

The issue with 'a[i]' is present in your version of the expression just
like it is present in the original version. You haven't changed anything
important by replacing post-increment with compound assignment.

> This is valid, but is more appropriate for iocc than
> supposedly maintainable code. There couldn't be a problem,
> because there is nothing that is changed twice between the
> sequence points, neither x[ old ] nor a[i] .

"Changed twice"? It is not about changing anything twice and it's never
been. The rule in the standard consists of two parts. In short: 1) don't
change anything twice, 2) if you change some object, you can only read
the old value of that object to determine its new value. The discussion
here is centered around the second part of the rule. Nobody mentioned
the first one yet simply because it has noting to do with the expression
in question. The question is, once again, whether the original
expression violates the second part of the rule. This question applies
in exactly the same manner to your version. You haven't really changed
anything.

BRG

unread,
Jan 21, 2005, 4:19:24 AM1/21/05
to
Albert van der Horst wrote:

> In article <41eda53a$0$44983$ed2e...@ptn-nntp-reader04.plus.net>,
> BRG <b...@nowhere.org> wrote:
>
>>Does anyone here know whether the assignment:
>>
>> a[i] = x[ a[i] ]++;

[snip]


> This is valid, but is more appropriate for iocc than
> supposedly maintainable code. There couldn't be a problem,
> because there is nothing that is changed twice between the
> sequence points, neither x[ old ] nor a[i] .

Having had many good responses here, for which I am most grateful, my
own conclusion is that this statement produces an undefined result.

One relevant extract from the standard is:

"Between the previous and next sequence point an
object shall have its stored value modified at
most once by the evaluation of an expression.
Furthermore, the prior value shall be accessed
only to determine the value to be stored"

In the statement: k = x[ k ]++;

the value of k is modified once but its prior value is being used not
only to determine the new (stored) value but also to determine which
element in x[] is post-incremented. The latter use violates the last
sentence in the quoted paragraph.

Moreover, there appears to be nothing in the C standard to prevent
either of the interpretations:

t = k; k = x[t]; x[t]++;
or
k = x[k]; x[k]++;

each of which we know is implemenented in some compilers. And a
statement that can produce two different results has to produce
undefined behaviour as far as the C standard is concerned.

>>is legal in C and, if so, what array element in x[] is post incremented?
>>That is, does the old or the new value of a[i] determine the index in
>>x[] of the post incremented array element.
>>
>>I rather suspect the result is undefined - but am I right?
>
> Because the optimiser got confused?

I checked this with the optimiser both on and off. I also checked the
assembler code being produced and it was quite evident that the
implementation of the second possible result above was deliberate.

Brian Gladman

xarax

unread,
Jan 21, 2005, 10:27:03 AM1/21/05
to
"BRG" <b...@nowhere.org> wrote in message
news:41f0c919$0$60694$ed2e...@ptn-nntp-reader04.plus.net...

> Albert van der Horst wrote:
>
> > In article <41eda53a$0$44983$ed2e...@ptn-nntp-reader04.plus.net>,
> > BRG <b...@nowhere.org> wrote:
> >
> >>Does anyone here know whether the assignment:
> >>
> >> a[i] = x[ a[i] ]++;
>
> [snip]
> > This is valid, but is more appropriate for iocc than
> > supposedly maintainable code. There couldn't be a problem,
> > because there is nothing that is changed twice between the
> > sequence points, neither x[ old ] nor a[i] .
>
> Having had many good responses here, for which I am most grateful, my
> own conclusion is that this statement produces an undefined result.
>
> One relevant extract from the standard is:
>
> "Between the previous and next sequence point an
> object shall have its stored value modified at
> most once by the evaluation of an expression.
> Furthermore, the prior value shall be accessed
> only to determine the value to be stored"
>
> In the statement: k = x[ k ]++;
>
> the value of k is modified once but its prior value is being used not
> only to determine the new (stored) value but also to determine which
> element in x[] is post-incremented. The latter use violates the last
> sentence in the quoted paragraph.

No.

> Moreover, there appears to be nothing in the C standard to prevent
> either of the interpretations:
>
> t = k; k = x[t]; x[t]++;

That is the correct implementation.

> or
> k = x[k]; x[k]++;

That is two accesses to the value at the memory
location named 'k' and one modification. The second
access occurs after the location is modified, which
is incorrect behavior (not undefined behavior).

There is nothing in the standard that allows the
compiler to re-evaluate the location of x[k] for
performing the post-increment.

> each of which we know is implemenented in some compilers. And a
> statement that can produce two different results has to produce
> undefined behaviour as far as the C standard is concerned.

The compilers that generate the second implementation
are incorrect.

>
> >>is legal in C and, if so, what array element in x[] is post incremented?
> >>That is, does the old or the new value of a[i] determine the index in
> >>x[] of the post incremented array element.
> >>
> >>I rather suspect the result is undefined - but am I right?
> >
> > Because the optimiser got confused?
>
> I checked this with the optimiser both on and off. I also checked the
> assembler code being produced and it was quite evident that the
> implementation of the second possible result above was deliberate.

Deliberately broken.


Albert van der Horst

unread,
Jan 21, 2005, 8:47:20 AM1/21/05
to
In article <1106268117.5...@z14g2000cwz.googlegroups.com>,

Peter Nilsson <ai...@acay.com.au> wrote:
>Albert van der Horst wrote:
>> In article <41eda53a$0$44983$ed2e...@ptn-nntp-reader04.plus.net>,
>> BRG <b...@nowhere.org> wrote:
>> >Does anyone here know whether the assignment:
>> >
>> > a[i] = x[ a[i] ]++;
>>
>> I never use a statement like
>> x++;
>> on its own.
>
>Why?!
>
>> I always do the equivalent (barring the result value)
>> x += 1;
>> This shows that it is an assignment, rather than a side effect.
>
>Rather poor reasoning since x++ is idiomatic, and because _all_
>statements are _only_ evaluated for their side effects,
>assignments or otherwise (e.g. function calls.)

You use side-effect in a politically correct way here.
I thought the context made clear that is not what I say.
In an expression like (i + j++)
two thing are happening with j, getting its value and the
incrementation which I call a side-effect. (And the use is
not improper, because it is indeed a lasting effect.).

>
>> (The result of x++ is of course x, then it is thrown away,
>> oh and by the way, I have incremented x for you.
>> Extremely silly.)
>
>Yes, ": @++ dup @ dup 1+ over ! ;" _is_ silly, but only because
>Forth is silly. ;)

This leaves a pointer to x and has its value incremented.
It could be simplified to: @++ 1 over +! ;
It is not equivalent to the c-code x += 1;

Lets discuss @+ which leaves an incremented address
and a content, the equivalent of *p++ in c.

In the context of Forth it is indeed silly to
do
@+ DROP
instead of just
@
This is analogous. In the first example you calculate
two results, then throw one away. Instead of just calculating
a result.

But more on topic.
Is my
x += 1;
sufficiently un-idiomatic to get some eyes browsed?

What about
p += sizeof(struct x);

>--
>Peter
>

--
Groetjes Albert

pete

unread,
Jan 21, 2005, 10:51:49 AM1/21/05
to
Albert van der Horst wrote:
>
> In article <1106268117.5...@z14g2000cwz.googlegroups.com>,
> Peter Nilsson <ai...@acay.com.au> wrote:
> >Albert van der Horst wrote:
> >> In article <41eda53a$0$44983$ed2e...@ptn-nntp-reader04.plus.net>,
> >> BRG <b...@nowhere.org> wrote:
> >> >Does anyone here know whether the assignment:
> >> >
> >> > a[i] = x[ a[i] ]++;
> >>
> >> I never use a statement like
> >> x++;
> >> on its own.
> >
> >Why?!
> >
> >> I always do the equivalent (barring the result value)
> >> x += 1;
> >> This shows that it is an assignment, rather than a side effect.
> >
> >Rather poor reasoning since x++ is idiomatic, and because _all_
> >statements are _only_ evaluated for their side effects,
> >assignments or otherwise (e.g. function calls.)
>
> You use side-effect in a politically correct way here.
> I thought the context made clear that is not what I say.
> In an expression like (i + j++)
> two thing are happening with j, getting its value and the
> incrementation which I call a side-effect. (And the use is
> not improper, because it is indeed a lasting effect.).

"side effect" is a technical term in C.
This is a forum for discussing C.

--
pete

Keith Thompson

unread,
Jan 21, 2005, 11:06:10 AM1/21/05
to
Albert van der Horst <alb...@spenarnc.xs4all.nl> writes:
[...]

> But more on topic.
> Is my
> x += 1;
> sufficiently un-idiomatic to get some eyes browsed?

It's sufficiently un-idiomatic that my first thought on reading it
would be that the author hasn't yet learned about the ++ operator.
I'd only use it if it were part of a pattern, like:

x += 1;
y += 2;
z += 4;

> What about
> p += sizeof(struct x);

If p is a char*, it's fine. If p is a struct x*, it doesn't make much
sense.

--
Keith Thompson (The_Other_Keith) ks...@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

Thomas Stegen

unread,
Jan 21, 2005, 11:12:50 AM1/21/05
to
Keith Thompson wrote:
> Albert van der Horst <alb...@spenarnc.xs4all.nl> writes:
>
>>What about
>> p += sizeof(struct x);
>
>
> If p is a char*, it's fine. If p is a struct x*, it doesn't make much
> sense.
>

Unless struct x is used to hold information about a byte and p is a
pointer to the first element of array an array of struct x's which are
storing information about struct x objects. Then the above
would take you to the struct x which holds information about the
first byte in the second struct x object.

I am not sure it makes sense in writing, but rest assured it does in
my head.

--
Thomas.

BRG

unread,
Jan 21, 2005, 11:20:32 AM1/21/05
to
xarax wrote:

>>Having had many good responses here, for which I am most grateful, my
>>own conclusion is that this statement produces an undefined result.
>>
>>One relevant extract from the standard is:
>>
>> "Between the previous and next sequence point an
>> object shall have its stored value modified at
>> most once by the evaluation of an expression.
>> Furthermore, the prior value shall be accessed
>> only to determine the value to be stored"
>>
>>In the statement: k = x[ k ]++;
>>
>>the value of k is modified once but its prior value is being used not
>>only to determine the new (stored) value but also to determine which
>>element in x[] is post-incremented. The latter use violates the last
>>sentence in the quoted paragraph.
>
> No.

The wording is quite clear. If k is modified then the _only_ purpose for
which the previous value of k can be accessed is in determining the new
value of k. Which means in this case that it cannot be legally accessed
to determine which element of x[] is to be post-incremented.

>>Moreover, there appears to be nothing in the C standard to prevent
>>either of the interpretations:
>>
>> t = k; k = x[t]; x[t]++;
>
> That is the correct implementation.
>>or
>> k = x[k]; x[k]++;
>
> That is two accesses to the value at the memory
> location named 'k' and one modification. The second
> access occurs after the location is modified, which
> is incorrect behavior (not undefined behavior).

> There is nothing in the standard that allows the
> compiler to re-evaluate the location of x[k] for
> performing the post-increment.

The issue is whether there is anything in the standard that prevents
this interpretation.

>>each of which we know is implemenented in some compilers. And a
>>statement that can produce two different results has to produce
>>undefined behaviour as far as the C standard is concerned.
>
> The compilers that generate the second implementation
> are incorrect.

>>>>is legal in C and, if so, what array element in x[] is post incremented?
>>>>That is, does the old or the new value of a[i] determine the index in
>>>>x[] of the post incremented array element.
>>>>
>>>>I rather suspect the result is undefined - but am I right?
>>>
>>>Because the optimiser got confused?
>>
>>I checked this with the optimiser both on and off. I also checked the
>>assembler code being produced and it was quite evident that the
>>implementation of the second possible result above was deliberate.
>
> Deliberately broken.

I believe you are wrong.

Brian Gladman

Chris Torek

unread,
Jan 21, 2005, 2:54:29 PM1/21/05
to
>"BRG" <b...@nowhere.org> wrote in message
>> In the statement: k = x[ k ]++;
[ ... snippage ]

>> Moreover, there appears to be nothing in the C standard to prevent
>> either of the interpretations:
>> t = k; k = x[t]; x[t]++;

[equivalently: old_val = x[k]++; k = old_val;]

>> or
>> k = x[k]; x[k]++;

In article <bb9Id.1622$YD5....@newsread3.news.pas.earthlink.net>
xarax <xa...@email.com> wrote:
>[The first] is the correct implementation.

This may be the one you prefer (and the one I prefer, too!), but
unless the Standard actually *says* that, the Standard does not
*say* that.

I believe the wording in the C standards (both C89 and C99) can
reasonably be interpreted *not* to say that. In other words, the
Standard does not say what I want it to say. Too bad for me (and
you, too). :-) So just write:

old_val = x[k]++;
k = old_val;

when you mean that -- and/or lobby for a future DR or TC and/or a
future C standard to actually *say* that the expression has to mean
what you and I want it to mean.

"If the Standard says that the result depends on the phase of the
moon, the programmer should be prepared to look out the window as
necessary." --me
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603
email: forget about it http://web.torek.net/torek/index.html
Reading email is like searching for food in the garbage, thanks to spammers.

BRG

unread,
Jan 21, 2005, 3:39:42 PM1/21/05
to
Chris Torek wrote:

>>"BRG" <b...@nowhere.org> wrote in message
>>
>>>In the statement: k = x[ k ]++;
>
> [ ... snippage ]
>
>>>Moreover, there appears to be nothing in the C standard to prevent
>>>either of the interpretations:
>>> t = k; k = x[t]; x[t]++;
>
> [equivalently: old_val = x[k]++; k = old_val;]
>
>>>or
>>> k = x[k]; x[k]++;
>
> In article <bb9Id.1622$YD5....@newsread3.news.pas.earthlink.net>
> xarax <xa...@email.com> wrote:
>
>>[The first] is the correct implementation.
>
> This may be the one you prefer (and the one I prefer, too!), but
> unless the Standard actually *says* that, the Standard does not
> *say* that.

I agree. I was hoping to find that the C Standard would make this
interpretation correct but I can't see that it does. It seems to me
that it allows either version and this means that we have to treat the
result of this statement as undefined.

> I believe the wording in the C standards (both C89 and C99) can
> reasonably be interpreted *not* to say that. In other words, the
> Standard does not say what I want it to say. Too bad for me (and
> you, too). :-) So just write:
>
> old_val = x[k]++;
> k = old_val;
>
> when you mean that -- and/or lobby for a future DR or TC and/or a
> future C standard to actually *say* that the expression has to mean
> what you and I want it to mean.

I wonder who we lobby. Maybe there is a Committee member watching this?

Brian Gladman

Friedhelm Usenet Waitzmann

unread,
Jan 21, 2005, 5:47:55 PM1/21/05
to
Old Wolf <old...@inspire.net.nz>:

>Going by my formulation of the rule, the read of p
>for (p->next = q) may occur after the write of p
>in (p = q), so the behaviour is undefined.

You mean, the standard permits that the left operand (i.e. the
lvalue) of the assignment p->next = q is evaluated *after* the
evaluation of the result?

From draft ISO/IEC JTC1/SC22/WG14 N794:

6.3.16 Assignment operators

Syntax

[...]

Constraints

[...]

Semantics


[#3] An assignment operator stores a value in the object
designated by the left operand. An assignment expression
has the value of the left operand after the assignment,
but is not an lvalue. [...] The side effect of updating
the stored value of the left operand shall occur between
the previous and the next sequence point.

[#4] The order of evaluation of the operands is
unspecified.

The working group regarded the order of evaluation of the
operands as worth to be mentioned ([#4]) but left open the less
obvious possibility, that the left operand (i.e. the lvalue)
might not be computed until the result has been computed and used
in another assignment?

[#3] permits that the "side effect of updating the stored value"
may occur late, but it does not say anything about the time, when the
lvalue itself is computed.

Any comments?

Richard Tobin

unread,
Jan 21, 2005, 8:51:11 PM1/21/05
to
In article <csrml...@news4.newsguy.com>,
Chris Torek <nos...@torek.net> wrote:

>"If the Standard says that the result depends on the phase of the
>moon, the programmer should be prepared to look out the window as
>necessary." --me

This would make phase-of-the-moon programs either trivial or
fiendishly complicated.

-- Richard

Friedhelm Usenet Waitzmann

unread,
Jan 22, 2005, 12:22:58 AM1/22/05
to
Andrey Tarasevich <andreyta...@hotmail.com>:

>Albert van der Horst wrote:
>> Now the above is using the side effect,
>> to mix up in one statement
>> new = x[ old ];
>> x[ old ] += 1;
>>
>> It is *not* equivalent to
>> a[i] = x[ a[i] ] += 1;
>> because, being a post-increment, the original value of
>> x[ a[i] ] must be used.

>This is completely irrelevant. If you read this thread
>carefully, you'll see that the real question is which value of
>'a[i]' is used (old or new), not which value of 'x[a[i]]' is
>used. The latter is pretty much irrelevant.

>The issue with 'a[i]' is present in your version of the
>expression just like it is present in the original version. You
>haven't changed anything important by replacing post-increment
>with compound assignment.

I think, he has: If you replace x[ a[i] ]++ with
(x[ a[i] ] += 1), the following rule regarding the += applies:

From ISO/IEC JTC1/SC22/WG14 N794:

6.3.16.2 Compound assignment

[...]

Semantics

[#3] A compound assignment of the form E1 op= E2
differs from the simple assignment expression
E1 = E1 op (E2) only in that the lvalue E1 is evaluated
only once.

Therefore, in a[i] = (x[ a[i] ] += 1) the prior value of a[i] is
accessed only once before the new value is stored in a[i],
because 6.3.16.2[#3] garanties that x[a[i]] is not evaluated a
second time. Or I am wrong?

Peter Nilsson

unread,
Jan 22, 2005, 12:28:38 AM1/22/05
to
Albert van der Horst wrote:
> Peter Nilsson <ai...@acay.com.au> wrote:
> > Albert van der Horst wrote:
> > > BRG <b...@nowhere.org> wrote:
> > > > Does anyone here know whether the assignment:
> > > >
> > > > a[i] = x[ a[i] ]++;
> > >
> > > I never use a statement like
> > > x++;
> > > on its own.
> >
> > Why?!
> >
> > > I always do the equivalent (barring the result value)
> > > x += 1;
> > > This shows that it is an assignment, rather than a side effect.
> >
> > Rather poor reasoning since x++ is idiomatic, and because _all_
> > statements are _only_ evaluated for their side effects,
> > assignments or otherwise (e.g. function calls.)
>
> You use side-effect in a politically correct way here.

It's a term defined in the standard...

"Accessing a volatile object, modifying an object, modifying a
file, or calling a function that does any of those operations
are all _side effects_, ..."

> I thought the context made clear that is not what I say.
> In an expression like (i + j++)
> two thing are happening with j, getting its value and the
> incrementation which I call a side-effect. (And the use is
> not improper, because it is indeed a lasting effect.).

I (think) I understand that. I was pointing out that C turned
assignments and function calls into expression operators. [It's
not the only language to do this, but the consequences do
surprise many people who program other languages.]

> > > (The result of x++ is of course x, then it is thrown away,
> > > oh and by the way, I have incremented x for you.
> > > Extremely silly.)
> >
> > Yes, ": @++ dup @ dup 1+ over ! ;" _is_ silly, but only because
> > Forth is silly. ;)
>
> This leaves a pointer to x and has its value incremented.

Drat! I meant ": @++ dup @ dup 1+ rot ! ;"

> It could be simplified to: @++ 1 over +! ;

I was hoping you would simplify it, although I didn't anticipate
getting my version wrong. ;( But I'm pretty sure what I was
aiming for could be simplified to... : @++ 1 over +! @ ;

Anyway, my point is that, to a Forth programmer, the optimisation
seems obvious. Within C, the same 'obviousness' surrounds the
optimisation of x += 1 to x++; or ++x;.

> It is not equivalent to the c-code x += 1;

It was meant to be equivalent to x++;, i.e. (adr -- n) where
adr is the lvalue (address) of x.

> Lets discuss @+ which leaves an incremented address
> and a content, the equivalent of *p++ in c.
>
> In the context of Forth it is indeed silly to
> do
> @+ DROP
> instead of just
> @
> This is analogous.

In C it depends on the context: *p++; is silly, however
c = *p++; or f(*p++); isn't.

> In the first example you calculate
> two results, then throw one away. Instead of just calculating
> a result.
>
> But more on topic.
> Is my
> x += 1;
> sufficiently un-idiomatic to get some eyes browsed?

As Keith points out, there are subjective cases where it's valid,
but in general it will raise eyebrows.

It will make the reader think that you're entirely clued up
in C, just as my posted attempt at Forth was obviously naive
from a Forth perspective.

> What about
> p += sizeof(struct x);

[Again See Keith's comment, but also....]

Note that sizeof(struct x) cannot generally be expected to be 1.
There is no unary auto-increment-by-something-other-than-1
operator in C. So, p += 2; is not un-idiomatic.

--
Peter

pete

unread,
Jan 23, 2005, 6:21:29 AM1/23/05
to

What happens is:
a gets (double)(int)3.1
b gets (int)3.1
and the assignments are made in no particular order.

--
pete

0 new messages