sprintf

[Clark S. Cox III]

Ah.. futility of reason. Well my mistake. I thought "flying of demons
from my nose" was rather an unproabable event and if it did happen then
the behaviour would not be deterministic for demons at least may have
mood swings.

Where do the lines above say about the bahaviour of the computer. It is
basic assumption for all programming languages (including assembly and
machine code) that computers should have perfectly predictable
bahaviour.

Yes, but the factors leading to that behavior may not be knowable.

Without this asumption you won't be sure what a computer would do after
you gave it an instruction to execute.
And the words ".. by providing a definition of the officially
undefined behavior .." in fact suggests that what is left undefined by
the standard need not be inherently unpredictable, for a particular
implementation can define it anyway.

Yes, an implementation can define it, but they are under no requirement
to do so; an implementation would be perfectly within its rights to
replace any instance of undefined behavior with:

int n = call_out_to_hardware_random_number_generator();
if(n < 0) exit(0);

LoL...behaviour will still be perfectly predictable (if not easy to
predict). If you take the same computer with same intial state and run
the same crap code which messes up the control information then you
WILL end up with the same sequence of instruction and output EVERYTIME.

What about quantum effects?

 

[Keith Thompson]

Suppose the function `int flip();` returns 0 or 1 non-deterministically.

Then

flip();

doesn't affect the system's defined behaviour. Neither does

int flop = flip();

[That's the C-visible behaviour, of course.]
But

printf( "flip() returned %d\n", flip() );

/does/ affect the system's defined behaviour -- but no more so than
any other function that returns 0-or-1.

What's more, in:

int j = flip(); j += j;

the non-determinism of `flip` is lost in the undefined behaviour
of the assignment.

[...]

The behavior of the assignment is well defined; it sets j to j+j.

Did you mean

int j = flip(); j = j++; /* undefined behavior */

?

 

[Keith Thompson]

1. I do accept that C standard leaves the behaviour (refer to
first post) undefined.
2. I am arguing that there has to be a rational explanation for
all kinds of behaviour shown by a computer. It doesn't matter if
C standard covers it or not.

[...]

There may be a rational explanation. That doesn't mean the
behavior is necessarily deterministic.

Digital computer hardware is *intended* to be deterministic, but
it's built out of real-world matter, which is ultimately made up
of subatomic particles that, according to quantum theory, exhibit
genuinely nondeterministic behavior. Nothing in the C standard
says or implies that these nondeterministic phenomena cannot
affect the behavior of a C program.

For example a cosmic ray flipping a memory bit.

For example the state of uninitialized memory.

When a system is powered on, what is the state of memory that has not
yet been written? For actual memory systems, I have no idea, but I
can easily imagine systems for which the answer is indeterminate,
perhaps randomly 0 or 1, perhaps even some intermediate state.
Reading the value of a memory location that hasn't been initialized
somehow invokes undefined behavior.

(This wouldn't create true indeterminacy for physical memory that's
been initialized by some other program or by the operating system. An
OS could easily zero all unused memory on startup, but it's not
required to.)

 

[Radamanthe]

Richard Bos said:


Almost true. The implementation could in theory simply remember the sequence
it generated the first time. Pretty pointless (and it would take a lot of
storage), but legal IMHO.

Legal, but that would make rand() implementation over quantum source a
"shoot in the foot" in the long run for programs using it in a main loop
(like games for example).

I guess it would be best to provide another function for this in a third
party library.

 

[Chris Torek]

There may be a rational explanation. That doesn't mean the behavior
is necessarily deterministic.

Indeed. The best we can say today (given quantum physics) is "it
seems to be unknowable, in the limit".

Digital computer hardware is *intended* to be deterministic, but it's
built out of real-world matter, which is ultimately made up of
subatomic particles that, according to quantum theory, exhibit
genuinely nondeterministic behavior.

In particular, the "metastability problem" effectively guarantees
that a computer will eventually screw up.[%] The only control we
have over this is that we can decrease the probability to any extent
we choose, so that the mean time between failures is very long.
See, e.g., <http://www.interfacebus.com/Design_Metastable.html>.

[% At least, if it is connected to any asynchronous input source,
such as a human. This assumes the human is not part of the computer
and not synchronized by the same clock. One can, however, even
make Einsteinian relativity arguments to poke holes in isochrony:
if "the same clock" becomes a meaningless term, metastability again
becomes problematic, even if the human *is* part of the computer
and run via "the same clock".]

Nothing in the C standard says or implies that these
nondeterministic phenomena cannot affect the behavior of a C program.

Yes ... but at the same time, if you write strictly conforming
code, the C standard does *not* acknowledge items like metastability.
The following strictly conforming code:

#include <stdio.h>
int main(void) { puts("hello world"); return 0; }

must always print "hello world" and return successfully, even if
the computer fails in the middle. Obviously, if the hardware
fails (for whatever reason -- whether something as complicated and
fundamental as metastability, or something as simple as the power
going off), the implementation fails to conform for reasons that
have nothing to do with the software. But it still fails to conform.
In that particular sense, no conforming implementations can ever
exist.

If we avoid the extreme boundaries, however, there is a happy
middle-of-the-road position: on a computer that functions correctly,
if we avoid undefined behavior in our C source, and use a conforming
implementation, we can predict the results. What I think "yeti"
misses here is that "undefined behavior" is put into the C
standard for two good reasons, which I describe in my web page
at <http://web.torek.net/torek/c/compiler.html>.

Note that there *are* languages that, in effect, have *no* undefined
behavior at all. But if you want this kind of "safe" language, C
is not the right place to look. (Moreover, they are rarer than
one might expect at first -- most language designers prefer to give
users *some* way to escape the straitjacket.)

 

[CBFalconer]

Does this imply that rand() (which is defined) is limited to
pseudo-random algorithms, and thus should not be implemented
over a quantum noise source to be conform ?

Yes. It is necessary for testing to be able to repeat a sequence.

--
"A man who is right every time is not likely to do very much."
-- Francis Crick, co-discover of DNA
"There is nothing more amazing than stupidity in action."
-- Thomas Matthews
<http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt>

 

[Dik T. Winter]

> Obviously, if the hardware
> fails (for whatever reason -- whether something as complicated and
> fundamental as metastability, or something as simple as the power
> going off), the implementation fails to conform for reasons that
> have nothing to do with the software.

An anecdote. The first Cray-1's did not have a parity check on memory.
As Seymour Cray said: "parity is for farmers". I think that parity was
built in from serial number 4 or somesuch.