What exactly is the "as-if" rule?

Question

As the title says:

What exactly is the "as-if" rule?

A typical answer one would get is:

The rule that allows any and all code transformations that do not change the observable behavior of the program

From time to time, we keep getting behaviors from certain implementations, which are attributed to this rule. Many times wrongly.

So, what exactly is this rule? The standard does not clearly mention this rule as a section or paragraph, so what exactly falls under the purview of this rule?

To me, it seems like a grey area which is not defined in detail by the standard. Can someone elaborate on the details, citing the references from the standard?

^{Note: Tagging this as C and C++ both, because it is relevant to both languages.}

Landaulet

It refers to the abstract machine. – Wagonage

"Tagging this as C and C++ both, because it is relevant to both languages" It's relevant in any language. – Import

@AlexeyFrunze "It refers to the abstract machine" It refers to the state of the "abstract machine" being a tool and not an end, and being irrelevant in term of conforming, because it's "abstract" that is a specification tool not real. – Import

Answer 1

What is the "as-if" rule?

The "as-if" rule basically defines what transformations an implementation is allowed to perform on a legal C++ program. In short, all transformations that do not affect a program's "observable behavior" (see below for a precise definition) are allowed.

The goal is to give implementations freedom to perform optimizations as long as the behavior of the program remains compliant with the semantics specified by the C++ Standard in terms of an abstract machine.

---

Where does the Standard introduce this rule?

The C++11 Standard introduces the "as-if" rule in Paragraph 1.9/1:

The semantic descriptions in this International Standard define a parameterized nondeterministic abstract machine. This International Standard places no requirement on the structure of conforming implementations. In particular, they need not copy or emulate the structure of the abstract machine. Rather, conforming implementations are required to emulate (only) the observable behavior of the abstract machine as explained below.

Also, an explanatory footnote adds:

This provision is sometimes called the “as-if” rule, because an implementation is free to disregard any requirement of this International Standard as long as the result is as if the requirement had been obeyed, as far as can be determined from the observable behavior of the program. For instance, an actual implementation need not evaluate part of an expression if it can deduce that its value is not used and that no side effects affecting the observable behavior of the program are produced.

---

What does the rule mandate exactly?

Paragraph 1.9/5 further specifies:

A conforming implementation executing a well-formed program shall produce the same observable behavior as one of the possible executions of the corresponding instance of the abstract machine with the same program and the same input. However, if any such execution contains an undefined operation, this International Standard places no requirement on the implementation executing that program with that input (not even with regard to operations preceding the first undefined operation).

It is worth stressing that this constraint applies when "executing a well-formed program" only, and that the possible outcomes of executing a program which contains undefined behavior are unconstrained. This is made explicit in Paragraph 1.9/4 as well:

Certain other operations are described in this International Standard as undefined (for example, the effect of attempting to modify a const object). [ Note: This International Standard imposes no requirements on the behavior of programs that contain undefined behavior. —end note ]

Finally, concerning the definition of "observable behavior", Paragraph 1.9/8 goes as follows:

The least requirements on a conforming implementation are:

— Access to volatile objects are evaluated strictly according to the rules of the abstract machine.

— At program termination, all data written into files shall be identical to one of the possible results that execution of the program according to the abstract semantics would have produced.

— The input and output dynamics of interactive devices shall take place in such a fashion that prompting output is actually delivered before a program waits for input. What constitutes an interactive device is implementation-defined.

These collectively are referred to as the observable behavior of the program. [ Note: More stringent correspondences between abstract and actual semantics may be defined by each implementation. —end note ]

---

Are there situations where this rule does not apply?

To the best of my knowledge, the only exception to the "as-if" rule is copy/move elision, which is allowed even though the copy constructor, move constructor, or destructor of a class have side effects. The exact conditions for this are specified in Paragraph 12.8/31:

When certain criteria are met, an implementation is allowed to omit the copy/move construction of a class object, even if the constructor selected for the copy/move operation and/or the destructor for the object have side effects. [...]

Influence

I have seen this citation. What is not clear is the definition of observable behavior. What exactly qualify's as an observable behavior? Copy elision being an exception to as-if rule is pretty much well known and not a part of my question really. – Landaulet

@AlokSave: Well in the C standard, we see "Accessing a volatile object, modifying an object, modifying a file, or calling a function that does any of those operations are all side effects". Presumably there's something equivalent in the C++ standard(s). Informally, I guess "anything that changes its interaction with the outside world". – Stipe

Any behaviour that changes the state of the abstract machine (so, something that changes a variable passed in or global variable, or reads and writes to I/O devices). – Astolat

@AlokSave: I think that just means that if the C++ program always gives the correct output and has the correct side-effects according to the semantics it is given by the C++ language definition, then the "as if" rule is satisfied – Influence

@AlokSave: I will try to elaborate later on, I have to leave for a while now. – Influence

@MatsPetersson: Is that the formal definition of the standard? or the best possible definition that can be perceived? Andy: Thank you for the answer, I am looking forward to the ellaboration. – Landaulet

@OliCharlesworth: Yes as you correctly clarified, I believe we all know the informal definition of it in tits and bits and round abouts but is there an formal definition put forth by the standard? As you say, perhaps Yes. If so, what is it? Maybe I was not clear enough with the wording in the OP. – Landaulet

@AlokSave: See clause 8 of [intro.execution]. It pretty much mirrors the C definition I quoted above. – Stipe

Side effects are not observable behavior... they can be, but need not be. – Sabaean

@AlokSave: Sorry for the interruption. I added the definition of "observable behavior" given in the Standard. – Influence

@AlokSave: "Is that the formal definition of the standard?" The standard only defines the behavior of the abstract machine. So by definition, that's the only "observable behavior" it can define. – Hiltonhilum

Does this mean that deleting an infinite loop that does nothing is allowed, as long as nothing observable happens afterwards? – Kimikokimitri

@harold: Good question. Based on common sense, my answer would be "no", but in fact I cannot see how the definition of "observable behavior" above would forbit it. – Influence

@AndyProwl: Thank you for the updated answer. The q Harold makes, I find the rules quoted in the standard does not clearly address such situations or atleast I don't see how the rules apply to these situations and that was the reason I came up with this Q to beginwith. But looks like what you quoted above is is all that is there to be answered and perhaps I don't know how to make sense of it(atleast till now). – Landaulet

@OliCharlesworth: Thank you, Yes is it pretty much what you quoted. But, As I said above it is my feeling that the rules are not comprehensive or atleast I find them so. – Landaulet

One point to note particularly is that it applies only to legal programs. Anything invoking undefined behaviour is explicitly out of any coverage. – Drastic

Since this question is also tagged as c, could you indicate if there is a C counterpart to C++ 1.9/5? See e.g. this recent discussion and in particular this gcc bug report which was closed as invalid. I'm wondering if there is a difference between C and C++ invocations of that program from the gcc bug report. If you think it's out-of-scope for this Q, then I can ask a new one. – Auger

@TemplateRex: It's not out of scope at all, but I am no C expert unfortunately. – Influence

some more digging brought up this (looooong) thread on std.lang.c: groups.google.com/forum/#!topic/comp.std.c/… Read the contributions of DA Gwyn in particular, he states that C does not provide any guarantees about UB, even time travel of instructions is allowed. – Auger

As for the deleting an infinite loop, wouldn't it always be legal to delete one that does nothing, since it doesn't have side effects? Obviously it wouldn't be wise to expect this, but none of the listed rules seems to indicate that the loop would have any (per the standard) observable behavior. – Optometry

@Tim: Removal of empty loops is allowed per 1.10/24. See the normative note: "This is intended to allow compiler transformations such as removal of empty loops, even when termination cannot be proven." – Influence

@AndyProwl Ok, you seemed unsure when harold asked. – Optometry

@Tim: Yeah, that was 8 months ago :D – Influence

Regarding the removal of side-effect-free infinite loops: blog.regehr.org/archives/161 – Kolivas

@TavianBarnes the paragraph quoted in that article was pulled before C++11 came out, in November 2010 – Wilkens

Er, nevermind , it was just moved to 1.10 and made more general – Wilkens

"because an implementation is free to disregard any requirement of this International Standard as long as the result is as if the requirement had been obeyed" That's obvious nonsense. Clearly if it's a requirement, it can't be "disregarded". There is no "as if rule". – Import

@vonbrand: The Standard explicitly distinguishes "conforming" and "strictly conforming" programs; those that make use of what the Standard classifies as "Undefined Behavior" are not strictly conforming, but that merely makes them non-portable, not "illegal". The Standard does not require that implementations meaningfully process non-portable programs, but quality general-purpose implementations are often configurable to do so. – Enlarger

not even with regard to operations preceding the first undefined operation. Wow. – Briannebriano

Answer 2

In C11 the rule is never called by that name. However C, just like C++, defines the behaviour in terms of abstract machine. The as-if rule is in C11 5.1.2.3p4 and p6:

4. In the abstract machine, all expressions are evaluated as specified by the semantics. An actual implementation need not evaluate part of an expression if it can deduce that its value is not used and that no needed side effects are produced (including any caused by calling a function or accessing a volatile object).

5. [...]

6. The least requirements on a conforming implementation are:

   • Accesses to volatile objects are evaluated strictly according to the rules of the abstract machine.
   • At program termination, all data written into files shall be identical to the result that execution of the program according to the abstract semantics would have produced.
   • The input and output dynamics of interactive devices shall take place as specified in 7.21.3. The intent of these requirements is that unbuffered or line-buffered output appear as soon as possible, to ensure that prompting messages actually appear prior to a program waiting for input.

    

   This is the observable behavior of the program.

Filar

Answer 3

In C, C++, Ada, Java, SML... in any programming language well specified by describing the (usually many possible, non-deterministic) behavior(s) of a program (exposed to series of interactions on I/O ports), there is no distinct as-if rule.

An example of distinct rule is the one that says that a division by zero raises an exception (Ada, Caml) or a null dereference raises an exception (Java). You could change the rule to specify something else and you would end up with a different language (that some people would rather call a "dialect"(*). A distinct rule is there to specify some distinct uses of a programming language like a distinct grammatical rule cover some syntax constructs.

(*) A dialect according to some linguists is a language with an "army". in that context, that could mean a programming language without a committee and a specific industry of compiler editors.

The as-if rule is not a distinct rule; it doesn't cover any program in particular and is not even a rule that could be discussed, removed, or altered in any way: the so called "rule" simply reiterates that program semantics is defined, and can only be portably (universally) defined, in term of the visible interactions of an execution of the program with the "external" world.

The external world can be I/O interfaces (stdio), a GUI, even an interactive interpreter that output the resulting value of a pure applicative language. In C and C++ is includes the (vaguely specified) accesses to volatile objects, which is another way of saying that some objects at given point must be represented in memory strictly according to the ABI (Application Binary Interface) without ever mentioning the ABI explicitly.

The definition of what is a trace of execution, also called the visible or observable behavior defines what is meant by "as-if rule". The as-if rule tries to explain it, but by doing so, it confuses people more than it clarifies things as it gives the expression of being an additional semantic rule giving more leeway to the implementation.

Summary:

• The so called "as-if rule" does not relax any constraints on implementations.
• You cannot remove the as-if rule in any programming language specified in term of visible behavior (execution traces composed for interaction with the external world) to get a distinct dialect.
• You cannot add the as-if rule to any programming language not specified in term of visible behavior.

Import

If people believes I'm wrong, and there is a distinct "as if rule", why don't they try to describe a variant of C++ (a dialect) w/o that "rule"? What would the C++ specification even mean w/o it? It would be absolutely impossible to tell whether a compiler is conforming. Or to even define conforming. – Import

The "as-if" rule implies that in any situation where a potentially-useful optimization might affect program behavior, either the optimization would need to be forbidden, or any combination of actions resulting in that situation would need to be characterized as UB. – Enlarger

there is no distinct as-if rule Umm, wrong. The "as-if rule" is even in the index of the C11 standard as - wait for it - the "as-if rule" – Borszcz