WG14 Document: N1013
Date: 07-May-2003


Abstract
A presentation was given in Oxford basing on N1001 on sequence point. This document summarizes that presentation and the subsequent discussion.

Reference Document: DR087, N925, N926, N927, N1001, N008


Introduction

C99 talks about sequence point in a number places. The main concept is captured in the following paragraphs. In 5.1.2.3 paragraph 2:

"... At certain specified points in the execution sequence called sequence points, all side effects of previous evaluations shall be complete and no side effects of subsequent evaluations shall have taken place."

And in 6.5 paragraph 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 read only to determine the value to be stored."

There are events happening during the evaluation of an expression. Examples are reads and writes from and to memory locations. The above two paragraphs impose restrictions on the relative timing of these events in relation sequence points. These two paragraphs constitutes the first part of the specification. The second part specifies where sequence points occurs; C99 inserts sequence points when defining the semantics of an expression. An example is after the evaluation of the left operand of a comma operator. Taken these two parts together, C99 imposes restrictions on the relative timing of events happening during the evaluation of an expression. In particular, it restricts when side effects can occur.

The terms prior, subsequent and between are used in the above paragraphs. But what are the real meanings of these terms in this context ?
 

Discussion
The choice of wording in the above paragraphs implicitly assumes that the timing of events can be put into a linear sequence. It is against this background that the words prior, subsequent, and between are interpreted. However, events happening in an expression cannot always be laid out in a linear sequence. Consider the following expression:

(x++, x) + (x++, x);

Note that events happening during the evaluation of an expression can be represented by a syntax tree. The one for the above is:

                           +
                         /   \
                        /     \
                       /       \
                      ,         ,
                     $ \       $ \
                    /   \     /   \
                  x++   x   x++    x
 

The $-sign represents sequence point. Nodes in a tree are related by a partial ordering; and the nodes here are the events happening during the evaluation of an expression. Since not all nodes in a partial ordering can be compared, it is not always clear which events occur before a given event. For example, which events occur before the sequence point in the right subexpression (the node highlighted in blue) ? This ambiguity is the root cause of difficulties in interpreting sequence point semantics.

This situation is made clear by drawing the partial ordering in a directed graph:

                          +
                        /   \
                       /     \
                      x       x
                      |       |
                      $       $
                      |       |
                     x++     x++
                       \     /
                        \   /
                        o

The edges in the graph are directed downwards. That is, lower nodes are compared smaller, and smaller means earlier in time. The question is: which events occur before the right $-sign node (the one in blue) ? Strictly speaking, the nodes that compare smaller to the $-sign node are x++ and o (the red highlights). However, in order to determining the status of this expression - that is, if the side effects produced by the two post increment operator violate the standard - the nodes that have no ordering (the three nodes on the left branch) should also be considered. In fact, it could be argued that 6.5 paragraph 2 is meant to apply to the two post increment operations in this example.

For our purpose, if we were to give meaning to prior, subsequent and between, and similar terms that refer to relative timing relating to sequence points, we need to redefine the ordering relationship. For the sake of illustration, let us define sp_smaller as follows ('sp' stands for sequence point). For events x and y, x is sp_smaller than y iff x is smaller than y or x has no ordering relationship with y.

We then define prior and subsequent using sp_smaller. This definition is used only when we are talking about events in an expression. Also, for two events x and y, a third event z occurs between  x and y iff x is sp_smaller than z and z is sp_smaller than y.

If we use this extended ordering relationship to interpret sequence point semantics, the meaning would be clear while the original intention of the standard is unchanged.

The above suggests there is something missing in the standard, or at least is not made explicit - that is, events in an expression is not well ordered. sp_smaller is one way to express this. But redefining words like prior and subsequent that have common meaning is not the best way to change the standard. The following suggests a different approach. Also, there are issues concerning function calls and floating point status flags. Refer to N1001 for details.
 
 

An attempt to provide the missing piece
To illustrate what is missing, we try the following modifications to the standard.

Note: Change/new text are highlighted in blue.

Add to 3 Terms, definitions, and symbols

3.19

Unordered event
There are events happen during the evaluation of an expression. These include the execution of operators, read and write to memory locations, and side effects. The standard imposes certain restrictions on the relative timing of these events. Since not all event timing are specified, this timing relationship is not well ordered. Relative to a given event, there are events that have no specified timing. These are called unordered events with respect to the event in question.
 

Modify 5.1.2.3 paragraph 4 and 5:

5.1.2.3

[#4] When the processing of the abstract machine is interrupted by receipt of a signal, only the values of objects as of the previous sequence point may be relied on. Objects that may be modified between the previous and next sequence point, or may be modified by unordered events with respect to the previous sequence point, need not receive their correct value yet.

[#5] The least requirements on a  conforming  implementation are:
- At sequence points, volatile objects are stable in the sense that previous access are complete and subsequent accesses have not yet occurred, provided that there is no unordered write event with respect to the sequence point.
 

Change 6.5 paragraph 2 to:

6.5

[#1] An expression is a sequence of operators and operand that specifies computation of a value, or that designates and object or a function, or that  generates side effects, or that performs a combination thereof.

[#2] Between the previous and next sequence point there are events happening in between, and events that have no ordering relationship with either sequence points. An object shall have its stored value modified at most once by these events. Furthermore, among these events, if the value is read, the read events shall precede any write events of the object. An exception to this shall be permitted if the object is a floating point flag and the modification sets the flag.

[#3]  The grouping of operators and operands is indicated by the syntax. 71)  Except as specified later (for the function-call  (),  &&,  ||,  ?:,  and comma operators), the order of evaluation of subexpressions and the order in which  side effects take place are both unspecified.

Note that the original sentence in [#2]  "Furthermore, the prior value shall be read only to determine the value to be stored" seems unnecessary and is removed.
 

Modify the last sentence of 6.5.2.2 paragraph 5 to:

6.5.2.2

[#5] If an attempt is made to modify the result of a function call or to access it after the next sequence point, or to access it in an unordered event with respect to the next sequence point, the behavior is undefined.
 

Modify the last sentence of 6.5.17 paragraph 2 to:

6.5.17

[#2] If an attempt is made to modify the result of a comma operator or to access it after the next sequence point, or to access it in an unordered event with respect to the next sequence point, the behavior is undefined.
 

Modify the last sentence of 6.7.3 paragraph 6 to:

6.7.3

Furthermore, at every sequence point the value last stored in the object shall agree with that prescribed by the abstract machine, except as modified by unknown factors mentioned previously,and except when there are unordered write events to the object.
 

Add to 6.5.2.2 paragraph 10:

6.5.2.2

[#10]  The  order  of evaluation of the function designation and the actual arguments is unspecified, but there are sequence points before and after the actual call. Only side effects that occur within the function body shall take effect between these two sequence points.

Note: this is to address DR087, that function calls do not overlap. However the DR only talks about the case of two function calls; it could be argue that the above is stronger than the provision of the DR.

Note that library functions that can be implemented as macros need not be restricted by the above due to footnote 157. Since the intend of this footnote is to explicitly give leeway to these functions, we will leave out of the current discussion the issue whether such leeway is desirable.
 
 

Conclusion
The above changes make it explicit that events with no ordering with respect to a sequence point is important. As long as a programmer is aware of the effect of unordered events, the status of an expression is not difficult to determine. Not all the fine details are addressed here, but the above can be used as an illustration of the major missing piece. Other approaches can probably express this more cleanly; refer also to N1008 for a different approach.