Discussion:
Implementation limits
(too old to reply)
Tim Rentsch
2016-06-20 17:30:05 UTC
Permalink
Raw Message
I have some questions related to implementation limits. There
were some comments having to do with implementation limits in a
discussion in comp.lang.c. These comments raised some questions
in my mind, which I would like to ask to the group for any
reactions anyone might have. Here is the background, ie, a
few relevant sentences taken from the aforementioned clc discussion.
(I don't have an attribution line handy, and in any case I'm not
responding to these statements, just giving them as background.)

However, since the standard makes no distinction between the
heap and the stack, and because the behavior is undefined if you
exceed an implementation's limits, including memory limits,
there's literally nothing that an implementation could do with
such code that would constitute an incorrect translation of it.

However, what permits that optimization is the fact that the
behavior is undefined if an implementation's limits (such as the
limit on the total amount of memory available) are exceeded.
The standard imposes no requirements on the implementation with
regards to how much memory any particular program may use, so a
fully conforming implementation is allowed to translate ANY
program in a way that causes it to exceed the implementation's
memory limits. This would give the implementation extremely low
quality, but would not render it non-conforming.

At first blush these assertions seem innocuous enough, or maybe I
should say reasonable. But are they right? The first question,
although the less important of the two, is this: is exceeding an
implementation limit automatically undefined behavior? More
precisely, may we assume that exceeding any implementation limit
is undefined behavior unless the Standard includes an explicit
statement that excuses it from being undefined (eg, defines it,
or says it is unspecified, or implementation-defined, etc)? My
position is that this question does not have a clear answer. In
support of this position, let me draw your attention to 6.4.2.1,
paragraphs 5 and 6 (in N1570). Because of the heading, these
paragraphs clearly are concerned with an implementation limit.
Yet there is an explicit statement about undefined behavior if
the limit is exceeded. There would be no need for that statement
if exceeding an implementation were automatically undefined
behavior. Using a "the exception proves the rule" inference, we
may conclude that exceeding an implementation limit is not by
default undefined behavior. Any reactions?

The second question is more important, and also (in my view) more
profound. Does the circumstance of running out of memory even
qualify as exceeding an implementation limit? Or more starkly,
does the amount of memory available count as "an implemenatation
limit"? The answer hinges on what counts as "the implementation."
My position is that factors like how much memory is available are
not part of "the implementation", and so running out of memory is
not "exceeding an implementation limit". My reasoning goes as
follows. If running out of memory counts as part of "the
implementation", that potentially encompasses an enormous range of
software and hardware. For example, it may depend on how much swap
space is available, which in turn depends on what other programs
are running on the computer at the time. It may depend on whether
certain disk blocks have gone bad, which depends on the particular
drive and also various external events, eg, power glitches from
whatever source is used to supply power. The power surges may even
depend on extra-terrestrial influences, eg, cosmic rays or sunspot
activity. All of these things potentially influence how much
memory is available for a program to use. It's absurd to say all
of these things are included in "the implementation". A line has
to be drawn somewhere. Now the question is where to draw the line.
I believe the Standard supplies a clear answer to this question, in
the last point of section 1, paragraph 2. That says:

[This International Standard does not specify:] all minimal
requirements of a data-processing system that is capable of
supporting a conforming implementation.

All of a systems particulars - the physical computer, how much
memory it has, what operating system it runs, what other programs
are running or may start running, all of that stuff - fall under
the heading of "a data-processing system [that supports] a
conforming implementation", and are not part of the implemenation
itself. Running out of memory is not "exceeding an implementation
limit"; it just means program execution failed for some reason.
As far as the implementation is concerned, that happening is no
different than a power failure or memory being zapped by a cosmic
ray. Surely no one thinks cosmic rays are meant to be part of
"a C implementation".

Let me mention also another result that bears on this issue. It
isn't too hard to write a strictly conforming program that will
use more memory than is available on any computer on earth. If
running that program runs out of memory, does it have undefined
behavior? I believe it does not. The definition of undefined
behavior is given in section 3.4.3 (again in N1570)

behavior, upon use of a nonportable or erroneous program
construct or of erroneous data, for which this International
Standard imposes no requirements

By definition, a strictly conforming program does not make use of
any nonportable or erroneous program construct or erroneous data.
A strictly conforming program is obliged not to exceed any
/minimum/ implementation limit, but these limits are listed in the
Standard, in section 5.2.4.1 (and perhaps a few other places, but
the key thing is all of them are known), so they can be observed.
Hence a strictly conforming program cannot transgress into
undefined behavior. It follows that the circumstance of running
out of memory is not "undefined behavior" as the Standard uses the
term, but just a failed program execution, about which eventuality
the Standard explicitly chooses not to address.

I welcome any comments or reactions to the above.
s***@casperkitty.com
2016-06-20 19:08:53 UTC
Permalink
Raw Message
Post by Tim Rentsch
The second question is more important, and also (in my view) more
profound. Does the circumstance of running out of memory even
qualify as exceeding an implementation limit? Or more starkly,
does the amount of memory available count as "an implemenatation
limit"? The answer hinges on what counts as "the implementation."
My position is that factors like how much memory is available are
not part of "the implementation", and so running out of memory is
not "exceeding an implementation limit".
From the point of view of the Standard, everything necessary to translate
a program and execute it together comprise an "implementation". I have
stated numerous times that I think the Standard would have been much more
useful if it recognized the concept of a "program builder" which
translates a program into a form which may be used by an "execution
engine". That would make it possible to specify many things more
precisely, e.g. rather than merely leaving integer-to-pointer conversion
"Implementation-Defined" the Standard could require that an
implementation indicate via standard macro whether it converts in a
manner consistent with that defined by the execution engine. It would
also allow most forms of Undefined Behavior to be replaced with a
category of loosely-implementation-defined behavior, where an
implementation would be required to list possible outcomes, but

1. Would be allowed to select among them in Unspecified fashion, and

2. Could describe outcomes in terms of the underlying platform (e.g.
it could specify that a read or write of a null pointer will
generate the same load or store as an access via pointer whose
address happened to be zero, without needing to specify how the
execution engine would process such an operation, since such things
might be under the control of the programmer but not the compiler).

A low-level language needs to define a predictable relationship between
language constructs and machine constructs. In cases where a programmer
doesn't need rigidly-defined semantics it may be useful to have ways of
giving compilers freedom, but it's important that the programmer and the
compiler have compatible ideas of what aspects of behavior are guaranteed
to match the underlying execution engine and which ones aren't.
Post by Tim Rentsch
My reasoning goes as
follows. If running out of memory counts as part of "the
implementation", that potentially encompasses an enormous range of
software and hardware. For example, it may depend on how much swap
space is available, which in turn depends on what other programs
are running on the computer at the time. It may depend on whether
certain disk blocks have gone bad, which depends on the particular
drive and also various external events, eg, power glitches from
whatever source is used to supply power. The power surges may even
depend on extra-terrestrial influences, eg, cosmic rays or sunspot
activity.
In many cases, a compiler and execution engine will be under the control
of different entities. The behavior of an execution engine if an attempt
is made to load a program that's too big to fit can't really fall under
the jurisdiction of the C Standard if that same execution engine will
also be used to run executables built using other languages.
Post by Tim Rentsch
Let me mention also another result that bears on this issue. It
isn't too hard to write a strictly conforming program that will
use more memory than is available on any computer on earth. If
running that program runs out of memory, does it have undefined
behavior? I believe it does not. The definition of undefined
behavior is given in section 3.4.3 (again in N1570)
behavior, upon use of a nonportable or erroneous program
construct or of erroneous data, for which this International
Standard imposes no requirements
By definition, a strictly conforming program does not make use of
any nonportable or erroneous program construct or erroneous data.
A strictly conforming program is obliged not to exceed any
/minimum/ implementation limit, but these limits are listed in the
Standard, in section 5.2.4.1 (and perhaps a few other places, but
the key thing is all of them are known), so they can be observed.
Hence a strictly conforming program cannot transgress into
undefined behavior. It follows that the circumstance of running
out of memory is not "undefined behavior" as the Standard uses the
term, but just a failed program execution, about which eventuality
the Standard explicitly chooses not to address.
The implementation doesn't require that a compliant implementation must
be capable of processing every program that doesn't go beyond the
minimal implementation limits; it merely requires that for each compliant
implementation there must exist at least one source text which would
exercise the limits to the fullest, and which that implementation would
process correctly. If I recall correctly, the authors of the Standard
have admitted that it would be possible for an implementation to be
compliant but useless, but expect (I forget the exact wording) that most
implementation authors will produce something useful.
Keith Thompson
2016-06-20 19:21:54 UTC
Permalink
Raw Message
***@casperkitty.com writes:
[...]
Post by s***@casperkitty.com
The implementation doesn't require that a compliant implementation must
be capable of processing every program that doesn't go beyond the
minimal implementation limits; it merely requires that for each compliant
implementation there must exist at least one source text which would
exercise the limits to the fullest, and which that implementation would
process correctly. If I recall correctly, the authors of the Standard
have admitted that it would be possible for an implementation to be
compliant but useless, but expect (I forget the exact wording) that most
implementation authors will produce something useful.
That's discussed in section 5.1.4.1 of the C99 Rationale.

(I've said similar things myself. I'm actually not sure whether I had
read that section of the Rationale before doing so.)
--
Keith Thompson (The_Other_Keith) kst-***@mib.org <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
Tim Rentsch
2016-07-11 17:06:18 UTC
Permalink
Raw Message
Post by s***@casperkitty.com
Post by Tim Rentsch
The second question is more important, and also (in my view) more
profound. Does the circumstance of running out of memory even
qualify as exceeding an implementation limit? Or more starkly,
does the amount of memory available count as "an implemenatation
limit"? The answer hinges on what counts as "the implementation."
My position is that factors like how much memory is available are
not part of "the implementation", and so running out of memory is
not "exceeding an implementation limit".
From the point of view of the Standard, everything necessary to
translate a program and execute it together comprise an
"implementation". [...]
This statement is obviously wrong. The description in 5p1 makes it
clear that an implementation is distinct from the two data-processing
systems needed to compile and execute C programs.

By the way, you are using "comprise" wrongly. A whole comprises
its parts, not the other way around.
Kaz Kylheku
2016-07-11 18:16:44 UTC
Permalink
Raw Message
Post by Tim Rentsch
Post by s***@casperkitty.com
Post by Tim Rentsch
The second question is more important, and also (in my view) more
profound. Does the circumstance of running out of memory even
qualify as exceeding an implementation limit? Or more starkly,
does the amount of memory available count as "an implemenatation
limit"? The answer hinges on what counts as "the implementation."
My position is that factors like how much memory is available are
not part of "the implementation", and so running out of memory is
not "exceeding an implementation limit".
From the point of view of the Standard, everything necessary to
translate a program and execute it together comprise an
"implementation". [...]
This statement is obviously wrong. The description in 5p1 makes it
clear that an implementation is distinct from the two data-processing
systems needed to compile and execute C programs.
By the way, you are using "comprise" wrongly. A whole comprises
its parts, not the other way around.
The verb is funny that way in that it actually has both senses:

"The processor comprises a quarter billion transistors".

"The cache comprises more than half the processor die's area."

This second use is correct even if the fraction is 100%, as in, "this
system's software and hardware components comprise an entire C
implementation".

The usage that, I think, is widely considered incorrect is "comprised
of" as a synonym for "composed of".
Tim Rentsch
2016-07-20 14:38:09 UTC
Permalink
Raw Message
Post by Kaz Kylheku
Post by Tim Rentsch
Post by s***@casperkitty.com
Post by Tim Rentsch
The second question is more important, and also (in my view) more
profound. Does the circumstance of running out of memory even
qualify as exceeding an implementation limit? Or more starkly,
does the amount of memory available count as "an implemenatation
limit"? The answer hinges on what counts as "the implementation."
My position is that factors like how much memory is available are
not part of "the implementation", and so running out of memory is
not "exceeding an implementation limit".
From the point of view of the Standard, everything necessary to
translate a program and execute it together comprise an
"implementation". [...]
This statement is obviously wrong. The description in 5p1 makes it
clear that an implementation is distinct from the two data-processing
systems needed to compile and execute C programs.
By the way, you are using "comprise" wrongly. A whole comprises
its parts, not the other way around.
"The processor comprises a quarter billion transistors".
"The cache comprises more than half the processor die's area."
This second use is correct even if the fraction is 100%, as in, "this
system's software and hardware components comprise an entire C
implementation".
The usage that, I think, is widely considered incorrect is "comprised
of" as a synonym for "composed of".
Unfortunately in recent times the word has been used wrongly
so often that now both senses are recognized, eg, in standard
dictionaries.

Despite that, it's still a good idea to use "comprise" always
in the sense of a whole comprising its parts, for several
different reason. The other sense is advised against in many
style guides. Indeed, "comprise" is one of several words
listed specifically in Strunk and White (on every list of
writing advice in existence) not to use wrongly. Also, in
certain kinds of formal writing, "comprise" is always used
in the sense of a whole comprising its parts. IIANM patent
filings are an example of that.
s***@casperkitty.com
2016-07-11 19:09:01 UTC
Permalink
Raw Message
Post by Tim Rentsch
This statement is obviously wrong. The description in 5p1 makes it
clear that an implementation is distinct from the two data-processing
systems needed to compile and execute C programs.
An implementation is a single entity which conducts part of its operation
in one environment and part of its operation in a potentially-different
environment. The allowance for separate environments makes it possible to
use a cross-compiler on a machine that uses the EBCDIC character set to
generate code that will talk to ASCII terminals, but does not represent a
semantic between the translator and the executive.
Tim Rentsch
2016-07-20 14:40:30 UTC
Permalink
Raw Message
Post by s***@casperkitty.com
Post by Tim Rentsch
This statement is obviously wrong. The description in 5p1 makes it
clear that an implementation is distinct from the two data-processing
systems needed to compile and execute C programs.
An implementation is a single entity which conducts part of its operation
in one environment and part of its operation in a potentially-different
environment. The allowance for separate environments makes it possible to
use a cross-compiler on a machine that uses the EBCDIC character set to
generate code that will talk to ASCII terminals, but does not represent a
semantic between the translator and the executive.
It still is true that the description in 5p1 makes it clear that
an implementation is distinct from the two data-processing
systems needed to compile and execute C programs, and does
not include them.

Kaz Kylheku
2016-06-20 20:51:32 UTC
Permalink
Raw Message
Post by Tim Rentsch
implementation limit automatically undefined behavior? More
precisely, may we assume that exceeding any implementation limit
is undefined behavior unless the Standard includes an explicit
statement that excuses it from being undefined (eg, defines it,
or says it is unspecified, or implementation-defined, etc)? My
position is that this question does not have a clear answer. In
support of this position, let me draw your attention to 6.4.2.1,
paragraphs 5 and 6 (in N1570). Because of the heading, these
paragraphs clearly are concerned with an implementation limit.
Yet there is an explicit statement about undefined behavior if
the limit is exceeded. There would be no need for that statement
if exceeding an implementation were automatically undefined
behavior. Using a "the exception proves the rule" inference, we
may conclude that exceeding an implementation limit is not by
default undefined behavior. Any reactions?
Is it the case that the statement is necessary? Maybe it isn't.

If you take that statement out, can you infer the behavior upon
exceeding a limit?

It's implicitly clear that a program cannot continue if a limit is
exceeded.

There is no requirement anywhere like that in the event a limit
is exceeded, a signal must be raised or the program must stop with a
diagnostic message or the like.
Post by Tim Rentsch
By definition, a strictly conforming program does not make use of
any nonportable or erroneous program construct or erroneous data.
A strictly conforming program is obliged not to exceed any
/minimum/ implementation limit, but these limits are listed in the
Standard, in section 5.2.4.1 (and perhaps a few other places, but
the key thing is all of them are known), so they can be observed.
Hence a strictly conforming program cannot transgress into
undefined behavior. It follows that the circumstance of running
out of memory is not "undefined behavior" as the Standard uses the
term, but just a failed program execution, about which eventuality
the Standard explicitly chooses not to address.
Suppose a strictly conforming program is run. Nay, suppose that it's
not only strictly conforming, but it's a program which exercises every
single one of the implementation limits *and* is an element of the
set of such programs which are successfully translated and executed
by the implementation. (That set which must include at least
one such program for conformance.)

If that program fails for any reason (such as running out of memory),
then the implementation is not conforming. It might be temporarily
nonconforming due to some overload or your aforementioned VM issue due
to cosmically influenced bad sectors. Temporarily or not, it is
not conforming.

For that matter, if the power is cut midway through the program's
execution, then the implementation was nonconforming that time.
When the power is restored, there may be a good run of the program;
the implementation is conforming then.

By definition, the program has no undefined behavior. The standard gives
the requirements as to what its behavior is, yet events do not unfold
according to the requirements.

If a program which is not strictly conforming runs out of memory,
then that's an UB case.

To me, the situations that are in "limbo" involve programs which are
strictly conforming, and touch every limit, yet are not in that set of
"at least one" program acceptable to the implementation.

What is their status? If the implementation is conforming (it does
translate and execute other such programs), then the program's behavior
must be undefined. But every implementation can have a totally
different set of such programs, which points to *all* such programs not
being portable. I.e. they all have undefined behavior. No single one
of them is required to work on all possible implementations, in spite
of being strictly conforming.

How the situation can be resolved is by understanding that all strictly
conforming programs which exercise each limit in fact have undefined
behavior (only on grounds of testing all the limits, and for no other
reason: their meaning is clear when resources are available to satisfy
their demand for every limit).

Yet, in spite of the undefined status, every implementation must show
that it can handle one such a program, otherwise it is not conforming.

The undefined behavior of the class of such programs as a whole
excuses implementations from having to handle *all* of them; it's just
a special case requirement that at least one element out of an
undefined class must be handled.
s***@casperkitty.com
2016-06-20 22:34:25 UTC
Permalink
Raw Message
Post by Kaz Kylheku
To me, the situations that are in "limbo" involve programs which are
strictly conforming, and touch every limit, yet are not in that set of
"at least one" program acceptable to the implementation.
What is their status? If the implementation is conforming (it does
translate and execute other such programs), then the program's behavior
must be undefined. But every implementation can have a totally
different set of such programs, which points to *all* such programs not
being portable. I.e. they all have undefined behavior. No single one
of them is required to work on all possible implementations, in spite
of being strictly conforming.
That is true, and I would suggest that it implies that the Standard does
not describe all of the requirements for a useful C implementation, and
that failure of the Standard to mandate something should not be taken to
imply that implementations should not endeavor to support it anyway.

It's unfortunate that the Committee sought to pretend there were only
two kinds of C implementations in the universe (hosted and free-
standing), supposedly in the name of preventing the C universe from
becoming too "fragmented", when the refusal to acknowledge the variety
of implementation capabilities and application requirements makes the
Standard useless for defining what implementations can support what
applications.

If the committee were to recognize that different implementations have
different amounts of memory, then it would be possible to specify some
execution profiles such that all programs whose call nesting depth and
variable usage meet certain criteria could be guaranteed to run on
certain platforms without hitting any implementation limits thereof.
There would be something of a gap between the amount of memory that a
platform would have to have to be in a certain category, and the
amount of memory that a typical application for that category would be
able to use, but at least it would be possible to guarantee that small
applications will run correctly even on small hardware, and even
large applications will run correctly on larger hardware.
Keith Thompson
2016-06-20 23:21:36 UTC
Permalink
Raw Message
Post by s***@casperkitty.com
Post by Kaz Kylheku
To me, the situations that are in "limbo" involve programs which are
strictly conforming, and touch every limit, yet are not in that set of
"at least one" program acceptable to the implementation.
What is their status? If the implementation is conforming (it does
translate and execute other such programs), then the program's behavior
must be undefined. But every implementation can have a totally
different set of such programs, which points to *all* such programs not
being portable. I.e. they all have undefined behavior. No single one
of them is required to work on all possible implementations, in spite
of being strictly conforming.
That is true, and I would suggest that it implies that the Standard does
not describe all of the requirements for a useful C implementation, and
that failure of the Standard to mandate something should not be taken to
imply that implementations should not endeavor to support it anyway.
Of course the standard doesn't define which C implementations are
"usful". How could it? Usefulness is determined by the market,
and ultimately by each user.
Post by s***@casperkitty.com
It's unfortunate that the Committee sought to pretend there were only
two kinds of C implementations in the universe (hosted and free-
standing), supposedly in the name of preventing the C universe from
becoming too "fragmented", when the refusal to acknowledge the variety
of implementation capabilities and application requirements makes the
Standard useless for defining what implementations can support what
applications.
C11 has a number of optional features. Perhaps what you're suggesting
could be accomplished by making a few more features optional. For
example, as we discussed earlier, the standard might say that 64-bit
integers, floating-point wider than type float, and recursion are
optional for freestanding implementations. That would make it a bit
easier for C implementations for very small target systems to be
conforming. (I'm not convinced that's necessary, since the market for
C-like compilers for very small systems seems to be doing ok as it is.)
Post by s***@casperkitty.com
If the committee were to recognize that different implementations have
different amounts of memory, then it would be possible to specify some
execution profiles such that all programs whose call nesting depth and
variable usage meet certain criteria could be guaranteed to run on
certain platforms without hitting any implementation limits thereof.
There would be something of a gap between the amount of memory that a
platform would have to have to be in a certain category, and the
amount of memory that a typical application for that category would be
able to use, but at least it would be possible to guarantee that small
applications will run correctly even on small hardware, and even
large applications will run correctly on larger hardware.
How would the standard specify the amount of memory required for
a given program? Sizes of types are implementation-defined, and
the amount of memory needed for overhead is entirely unspecified.

You say that *all* programs that meet certain criteria could be
guaranteed to run. How do you ensure that the documented criteria
are exhaustive? In other words, how do you prevent me from writing
a program that meets all the criteria for your profile, but still
manages to use more of some resource than the system can provide?

The kind of "execution profile" you suggest might be an interesting
idea, but I don't think the standard is the place to define it --
at least not initially, and IMHO probably not ever.

POSIX is in part just such a profile. It imposes requirements on
top of those imposed by the C standard; for example CHAR_BIT==8
and int is at least 32 bits. (It's a lot more than that as well,
with its collection of library functions.)
--
Keith Thompson (The_Other_Keith) kst-***@mib.org <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
s***@casperkitty.com
2016-06-21 00:18:21 UTC
Permalink
Raw Message
supercat writes:/
Post by s***@casperkitty.com
That is true, and I would suggest that it implies that the Standard does
not describe all of the requirements for a useful C implementation, and
that failure of the Standard to mandate something should not be taken to
imply that implementations should not endeavor to support it anyway.
Of course the standard doesn't define which C implementations are
"usful". How could it? Usefulness is determined by the market,
and ultimately by each user.
Indeed, but some compiler writers think that the lack of a mandate to
do something should be a greater consideration than the fact that doing
the action in question anyway would be useful.
Post by s***@casperkitty.com
It's unfortunate that the Committee sought to pretend there were only
two kinds of C implementations in the universe (hosted and free-
standing), supposedly in the name of preventing the C universe from
becoming too "fragmented", when the refusal to acknowledge the variety
of implementation capabilities and application requirements makes the
Standard useless for defining what implementations can support what
applications.
C11 has a number of optional features. Perhaps what you're suggesting
could be accomplished by making a few more features optional. For
example, as we discussed earlier, the standard might say that 64-bit
integers, floating-point wider than type float, and recursion are
optional for freestanding implementations. That would make it a bit
easier for C implementations for very small target systems to be
conforming. (I'm not convinced that's necessary, since the market for
C-like compilers for very small systems seems to be doing ok as it is.)
Recognizing the concept of optional features is a definite step in the
right direction, but there really should be a lot more optional features
than are presently provided for. The "burden of proof" required to
justify an optional feature should be much lower than for mandatory
features, since if annex Q47 describing some optional feature is written
in such a way that it imposes no requirements whatsoever on an
implementation that refrains from defining a macro STDC_ANNEXQ47, then
compiler vendors could, if so inclined, completely ignore that annex
unless or until their customers started asking for support (which would
presumably only happen if the customers saw sufficient value as to
justify the effort to ask for it).

A lot of things used to be "negotiated" on an ad-hoc basis, but that is
no longer a reasonable approach given the evolution of compiler
optimization.
Post by s***@casperkitty.com
If the committee were to recognize that different implementations have
different amounts of memory, then it would be possible to specify some
execution profiles such that all programs whose call nesting depth and
variable usage meet certain criteria could be guaranteed to run on
certain platforms without hitting any implementation limits thereof.
There would be something of a gap between the amount of memory that a
platform would have to have to be in a certain category, and the
amount of memory that a typical application for that category would be
able to use, but at least it would be possible to guarantee that small
applications will run correctly even on small hardware, and even
large applications will run correctly on larger hardware.
How would the standard specify the amount of memory required for
a given program? Sizes of types are implementation-defined, and
the amount of memory needed for overhead is entirely unspecified.
It could, e.g. specify that implementations specify constants X and Y
such that after rounding the size of every automatic variable up to
the next multiple of "int", and regarding function calls within
expressions as creating variables for all temporary terms used
therein, and regarding each nested function call as using space
equivalent to X integers, the implementation must not cause stack-
related UB on any program whose stack utilization would be less than
Y. Note that many programs would use less stack than predicted, but
since stack space is rarely a large part of a program's overall RAM
requirement, allocating more stack space than a program will actually
use is usually not a major problem.
You say that *all* programs that meet certain criteria could be
guaranteed to run. How do you ensure that the documented criteria
are exhaustive? In other words, how do you prevent me from writing
a program that meets all the criteria for your profile, but still
manages to use more of some resource than the system can provide?
Code space is perhaps the toughest to quantify, but has the nice trait
that implementations should be able to yield deterministic behavior in
case a program is simply too big. Even there, however, one could
define costs to various categories of operations, figure out the worst-
case ratio of code size to estimated cost, and then figure out a
value C such that any program whose computed cost would be less than C
could be guaranteed to fit if the system has a certain amount of RAM,
in which case one would specify that the implementation would be
conforming when it has that amount of RAM available to it.

It may be that a program that would actually require 200K to run on a
platform could only be guaranteed to run in cases where the platform
had 2MB available to it, but there are a lot of useful programs that
only require a fraction of the available system resources; being able
to guarantee that they'll run on at least some systems would be better
than not being able to guarantee that 16GB of RAM will be sufficient
for a simple "Hello world".
The kind of "execution profile" you suggest might be an interesting
idea, but I don't think the standard is the place to define it --
at least not initially, and IMHO probably not ever.
POSIX is in part just such a profile. It imposes requirements on
top of those imposed by the C standard; for example CHAR_BIT==8
and int is at least 32 bits. (It's a lot more than that as well,
with its collection of library functions.)
That's rather coarse-grained. There are a lot of microcontroller
implementations which conform with parts of POSIX (e.g 8-bit chars,
ints without padding, etc.) but not all of it. Given the variety
of implementations and applications, there should be more fine-
grained determinations available (e.g. can an implementation
guarantee that for *any* two pointers x or y, the expression x>y

... will define a consistent ordering relationship such that pointers
to different portions of disjoint objects will have non-overlapping
rankings except that a past-one pointer may compare equal to (but
not greater than) a pointer to the start of another object.

... will define a consistent ordering relationship, but with no guarantee
that pointers compare in unique or non-overlapping fashion.

... will yield a 1 or 0 in some fashion with no side-effects.

... might do anything at all.

Some implementations could easily offer the first guarantee. Others might
conceivably have trouble even offering the third. Some algorithms would
require the first, while others would get by with the third. I'm not sure
exactly what degree of granularity is optimal, but the cost of specifying
more granularity than is really helpful should be pretty small (e.g. even
if there aren't any platforms that guarantee #3 without also guaranteeing
#2, having #3 listed as a possibility wouldn't really cost much of
anything).
Tim Rentsch
2016-07-11 17:10:51 UTC
Permalink
Raw Message
Post by Tim Rentsch
implementation limit automatically undefined behavior? More
precisely, may we assume that exceeding any implementation limit
is undefined behavior unless the Standard includes an explicit
statement that excuses it from being undefined (eg, defines it,
or says it is unspecified, or implementation-defined, etc)? My
position is that this question does not have a clear answer. In
support of this position, let me draw your attention to 6.4.2.1,
paragraphs 5 and 6 (in N1570). Because of the heading, these
paragraphs clearly are concerned with an implementation limit.
Yet there is an explicit statement about undefined behavior if
the limit is exceeded. There would be no need for that statement
if exceeding an implementation were automatically undefined
behavior. Using a "the exception proves the rule" inference, we
may conclude that exceeding an implementation limit is not by
default undefined behavior. Any reactions?
Is it the case that the statement is necessary? Maybe it isn't.
If you take that statement out, can you infer the behavior upon
exceeding a limit?
It's implicitly clear that a program cannot continue if a limit is
exceeded.
There is no requirement anywhere like that in the event a limit
is exceeded, a signal must be raised or the program must stop with a
diagnostic message or the like.
Post by Tim Rentsch
By definition, a strictly conforming program does not make use of
any nonportable or erroneous program construct or erroneous data.
A strictly conforming program is obliged not to exceed any
/minimum/ implementation limit, but these limits are listed in the
Standard, in section 5.2.4.1 (and perhaps a few other places, but
the key thing is all of them are known), so they can be observed.
Hence a strictly conforming program cannot transgress into
undefined behavior. It follows that the circumstance of running
out of memory is not "undefined behavior" as the Standard uses the
term, but just a failed program execution, about which eventuality
the Standard explicitly chooses not to address.
Suppose a strictly conforming program is run. Nay, suppose that it's
not only strictly conforming, but it's a program which exercises every
single one of the implementation limits *and* is an element of the
set of such programs which are successfully translated and executed
by the implementation. (That set which must include at least
one such program for conformance.)
If that program fails for any reason (such as running out of memory),
then the implementation is not conforming. [...]
This assertion begs the question. It assumes an answer to
exactly the point under discussion.
Loading...