Does any change in the state of the program have observed behavior?

Question

Consider the following two programs:

program one

int main() { printf( "hello\n" ); } 

program

 int main() { srand( 0 ); if( rand() ) { printf( "hello\n" ); } else { printf( "hello\n" ); } } 

Do they have the same observed behavior or not? According to the C ++ standard (1.9 / 6), the observed behavior includes:

• reads and writes volatile data
• library input / output functions

Now srand() and rand() are most likely not I / O functions (although I don’t know if this implementation uses any source of hardware noise), but they change the internal state of the program. Do they manipulate volatile data? I dont know. The printf() calls are clear I / O, and their sequences are identical in both programs.

Do the two above programs have the same observable behavior? How do I know if two given programs have the same observable behavior?

Answer 1

Do the above two programs have the same observable behavior?

As you say, it depends on whether srand() and rand() have observed side effects. They should not; there can be no external noise source, since the sequence must be repeated for a given seed, and there is no other reason for doing I / O or accessing volatile data.

If the compiler can determine that they do not (for example, if they are defined inside the line in the header or the linker is smart enough to perform additional optimizations), then he can omit them; otherwise, he must assume that they are doing this and turn them on. In many implementations, these functions will be in a precompiled library, and the linker will not be so smart, so you will end up calling the functions; however, a decent compiler should notice that both if branches are identical and omit the test.

(UPDATE: as noted in the comments, the call to rand() can also be omitted only if the compiler can determine that no future observable behavior can depend on its side effects).

How do I know if two given programs have the same observable behavior?

In general, this is a very complex problem, and there will be some programs where it is impossible to say (for reasons similar to the stop problem). For such simple programs, you can simply list the observed operations and compare them; if the behavior depends on the input of the program in a non-trivial order, then it will very soon become very difficult.