sprintf

[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.

 

[yeti]

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.

Does this mean that a *digital* computer can sow non-deterministic
behaviour even for the programs which standard expects to behave in a
particular fashion. for example
take the statement
int i =0;
I guess standard doesn't cast any doubt over the fact that "i" will be
assigned zero as a value. But it may happen in practise (probably due a
glitch in hardware) that "i" may get some non-zero value ( assuming
that computers are made up of real world matter and those effects can
effect the behaviour C program ). Would then the behaviour of the
statement int i=0 be implementation defined??

 

[Chris Dollin]

Nothing stops an implementation having access to genuine non-deterministic
behaviour [1] (or even physically impossible behaviour [2]), so long
as that doesn't leak through into the defined behaviours.

More practically, nothing stops an implementation being /deterministic/
but /unpredictable/, by virtue of us not having access to the entire
changing machine state. Suppose some piece of behaviour depends on
the state of an IO register that depends on some checksum of the last
block read from some disk attached to the machine. To reproduce some
piece of undefined behaviour would mean having to read /that/ disc
block at the right moment. Good luck.

take the statement
int i =0;
I guess standard doesn't cast any doubt over the fact that "i" will be
assigned zero as a value. But it may happen in practise (probably due a
glitch in hardware) that "i" may get some non-zero value ( assuming
that computers are made up of real world matter and those effects can
effect the behaviour C program ). Would then the behaviour of the
statement int i=0 be implementation defined??

The implementation would be non-conformant.

[1] Assuming it exists (via QM, for example).

[2] The C standard doesn't require implementations to conform to
what we "know" about physics, so an imaginary implementation
can be conformant /and/ have demons fly out of the user's
nose [3].

[3] And what evidence do you have that /you're/ not imaginary,
perhaps a simulation running on an advanced-by-our-puny-
standards machine?

 

[yeti]

[...]
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.

Nothing stops an implementation having access to genuine non-deterministic
behaviour [1] (or even physically impossible behaviour [2]), so long
as that doesn't leak through into the defined behaviours.

More practically, nothing stops an implementation being /deterministic/
but /unpredictable/, by virtue of us not having access to the entire
changing machine state. Suppose some piece of behaviour depends on
the state of an IO register that depends on some checksum of the last
block read from some disk attached to the machine. To reproduce some
piece of undefined behaviour would mean having to read /that/ disc
block at the right moment. Good luck.

take the statement
int i =0;
I guess standard doesn't cast any doubt over the fact that "i" will be
assigned zero as a value. But it may happen in practise (probably due a
glitch in hardware) that "i" may get some non-zero value ( assuming
that computers are made up of real world matter and those effects can
effect the behaviour C program ). Would then the behaviour of the
statement int i=0 be implementation defined??

The implementation would be non-conformant.

Thats what I am saying. Standard does want machine to behave as it
expects (and hence deterministic) and if implementation doesn't behave
in deterministic way (way predefined by standard) all the time then it
would become non-conformant.

[1] Assuming it exists (via QM, for example).

[2] The C standard doesn't require implementations to conform to
what we "know" about physics, so an imaginary implementation
can be conformant /and/ have demons fly out of the user's
nose [3].

[3] And what evidence do you have that /you're/ not imaginary,
perhaps a simulation running on an advanced-by-our-puny-
standards machine?

Damn!!..I have passed the Turing test.

 

[Chris Dollin]

Thats what I am saying. Standard does want machine to behave as it
expects (and hence deterministic) and if implementation doesn't behave
in deterministic way (way predefined by standard) all the time then it
would become non-conformant.

No. An implementations is free to become non-deterministic once it
has undefined behaviour. If your code contains:

int i = 0, j = 0; j = j++; fprintf( "i = %d, j = %d\n", i, j );

the value of `j` and the subsequent behaviour can be as non-deterministic
as the implementation can manage. The value printed for `j` is
arbitrary, the value printed for `i` likewise, and indeed nothing
need be printed, or Fermat's missing proof, whatever, without
the implementation thereby being non-conforming.

Usually this is a Bad Thing, but I offer it as a tip to desperate
mathematical historians. You never know your luck.

 

[Richard Bos]

Yes there has to be, maybe not required by C standard but required by
common sense.

What is called common sense is frequently neither.

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.

No, you're arguing something stronger: that there's a consistent,
rational, computable method behind all computerised behaviour. This is
simply untrue. Often, the rational explanation for the way a computer
behaves on erroneous input or code is "that's so broken that it could
depend on keyboard micro timings; you can't expect consistent behaviour
from it". If you cannot accept that, you're living in a Platonic dream
world rather than in the real one.

Richard

 

[Richard Bos]

Thats what I am saying. Standard does want machine to behave as it
expects (and hence deterministic)

And this is the whole crux of your error. _On erroneous code_ the
Standard does _not_ have any expectation of how the machine behaves, and
this means that it does _not_ require the result to be deterministic.

Of course _defined_ behaviour must be deterministic, excepting obvious
cases such as code which explicitly depends on, say, the time it takes
to enter a line of input. But the whole point of _undefined_ behaviour
is that the Standard explicitly says: "such code is beyond this
Standard's purview, and we don't care what happens".

and if implementation doesn't behave in deterministic way (way
predefined by standard) all the time then it would become non-conformant.

Completely wrong. Have you even _read_ the Standard?

Richard

 

[santosh]

[...]
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.

Nothing stops an implementation having access to genuine non-deterministic
behaviour [1] (or even physically impossible behaviour [2]), so long
as that doesn't leak through into the defined behaviours.

I would've thought that non-deterministic behaviour, by it's very
nature, can affect the system's defined behaviour too. In fact, I would
say, it invariably does.

As far as I can see, the C standard doesn't take into account genuinely
random, non-deterministic behaviour. Every behaviour of the abstract
machine falls under one of the three categories of defined,
implementation defined, or undefined.

[1] Assuming it exists (via QM, for example).
[2] The C standard doesn't require implementations to conform to
what we "know" about physics, so an imaginary implementation
can be conformant /and/ have demons fly out of the user's
nose [3].
[3] And what evidence do you have that /you're/ not imaginary,
perhaps a simulation running on an advanced-by-our-puny-
standards machine?

 

[yeti]

And this is the whole crux of your error. _On erroneous code_ the
Standard does _not_ have any expectation of how the machine behaves, and
this means that it does _not_ require the result to be deterministic.

Of course _defined_ behaviour must be deterministic, excepting obvious
cases such as code which explicitly depends on, say, the time it takes
to enter a line of input. But the whole point of _undefined_ behaviour
is that the Standard explicitly says: "such code is beyond this
Standard's purview, and we don't care what happens".


Completely wrong. Have you even _read_ the Standard?

Richard

Ok just for the heck of it "Does C standard require the implementation
to show deterministic behaviour??"

 

[Chris Dollin]

Nothing stops an implementation having access to genuine non-deterministic
behaviour [1] (or even physically impossible behaviour [2]), so long
as that doesn't leak through into the defined behaviours.

I would've thought that non-deterministic behaviour, by it's very
nature, can affect the system's defined behaviour too. In fact, I would
say, it invariably does.

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.

As far as I can see, the C standard doesn't take into account genuinely
random, non-deterministic behaviour. Every behaviour of the abstract
machine falls under one of the three categories of defined,
implementation defined, or undefined.

`undefined` covers it. Anything can happen [A]. Yes?

[A] ... in the next half-hour ...

 

[Chris Dollin]

Ok just for the heck of it "Does C standard require the implementation
to show deterministic behaviour??"

No. It only requires it to show the /correct/ behaviour, and that only
applies to a restricted set of circumstances.

Where the correct behaviour is deterministic (determined), then of
course deterministic behaviour is required. When it isn't, it isn't.
(In those cases, both deterministic and non-deterministic behaviour
are permitted: the Standard nowhere /requires/ non-deterministic
behaviour.)

 

[yeti]

No. It only requires it to show the /correct/ behaviour, and that only
applies to a restricted set of circumstances.

What is meant by "correct" behaviour?? is it pre-defined ??

 

[CBFalconer]

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.

--
"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>

 

[Richard Bos]

Ok just for the heck of it "Does C standard require the implementation
to show deterministic behaviour??"

Ok, you are now officially too stupid to educate. Welcome to the
killfile.

Richard

 

[Chris Dollin]

What is meant by "correct" behaviour?? is it pre-defined ??

For the purposes of this discussion, it's what the Standard defines.

Whether or not that counts as "pre-defined" is going to depend where
you want to start.

I've forgotten the original point of this digression by now, and
coincidentally it's nearly time to leave for the day. So I'll
summarise as best I can:

The Standard defines some behaviours in some circumstances. An
implementation that doesn't exhibit those behaviours in those
circumstances is non-conforming. The defined behaviours are pretty
much deterministic. Some behaviours are left to the implementation
to define.

In some circumstances, the Standard leaves the behaviour of the
code undefined. An implementation can behave as it wishes in
those circumstances: the Standard places /no/ further requirements
on it. Whether that behaviour is deterministic or not is not
relevant, since either are legal.

Some behaviours that are "unpredictable" and appear non-deterministic
may, when examined in detail, be deterministic after all -- they
may depend on fine details of the machine state, such as the
behaviour of previous programs or the content of disc blocks
or the detailed timing of keystrokes. Since that knowledge is
typically not known (maybe not knowbale) to us when we provoke
the dependant behaviours, calling them "unpredictable" is
reasonable. A machine may have access to quantum noise to
produce behaviour as random as we believe possible.

Either way it doesn't matter: the implementation must
show the required behaviour, when there is some, to be
conformant, and when the behaviour is undefined, may
behave predictably, pseudo-unpredictably, or quantum-
unpredictably, as it finds convenient.

I see I have a certain Paarfian gift for summary.
Perhaps I can hope for his success as well.

 

[Radamanthe]

Either way it doesn't matter: the implementation must
show the required behaviour, when there is some, to be
conformant, and when the behaviour is undefined, may
behave predictably, pseudo-unpredictably, or quantum-
unpredictably, as it finds convenient.

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 ?

 

[Nelu]

The standard's definition of "implementation" is (C99 3.12):

particular set of software, running in a particular translation
environment under particular control options, that performs
translation of programs for, and supports execution of functions
in, a particular execution environment"

If the OS "supports execution of functions", it's part of the
implementation.

Does this apply however deep? I mean you can have a number of virtual
machines running inside each other implementing functionality for
different hardware and the last one runs the C program.
Does the definition apply recursively to all the
virtual machines until the hardware level is reached or does it only
refer to the last virtual machine?

 

[Richard Heathfield]

Radamanthe said:

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 ?

See 4.10.2.1 (or 7.20.2.1), depending on what you use:
"The rand function computes a sequence of pseudo-random integers in
the range 0 to RAND_MAX." But hey, you could get away with that - after all,
who's to know the difference? *BUT*...

See also 4.10.2.2 (or 7.20.2.2):

"If srand is then called with the same seed value, the sequence of
pseudo-random numbers shall be repeated."

....so if your implementation does use genuinely random numbers, it has to
remember them all.

 

[Richard Bos]

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. Not necessarily because of rand() itself, which could easily have
been defined as returning a pseudo- _or_ truly random sequence, instead
of the strictly pseudo-random sequence we have now. The function which
makes the pseudo- a necessity is srand(), which requires that the same
seed will always start the same rand() sequence.

Richard

 

[Richard Heathfield]

Richard Bos said:

Yes. Not necessarily because of rand() itself, which could easily have
been defined as returning a pseudo- _or_ truly random sequence, instead
of the strictly pseudo-random sequence we have now. The function which
makes the pseudo- a necessity is srand(), which requires that the same
seed will always start the same rand() sequence.

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.