11
$\begingroup$

In my answer to another question, What was the purpose of Tartan's "disable" statement?, I asserted that it's anachronistic to use our modern C-derived definition of "undefined behavior", when reading a document about another language from 1978. (EDIT: The wording used in that document was actually "the consequences are not defined", not the exact phrase "undefined behavior". I think my overall question here is still interesting.)

The C and C++ standards define "undefined behavior" as "behavior for which this document imposes no requirements". The first instance of this definition I can find is in the first official C standard, which was apparently published as a draft in 1985, and officially in 1989. The unofficial standard for C before that was "The C Programming Language" by Kernighan and Ritchie, published in 1978. I don't completely trust my PDF copy of it, but I didn't find a definition (or even a mention) of "undefined behavior" in a quick search of that book, and it does not appear in the index.

So: Is the 1989 publication of the C89 standard the first origin of the notion that "undefined behavior" means "anything can happen"? (The phrase "nasal demons" was to my knowledge not coined until 1992: https://groups.google.com/g/comp.std.c/c/ycpVKxTZkgw/m/S2hHdTbv4d8J?hl=en ) What was the common understanding of "undefined behavior" in 1978, if there was one?

$\endgroup$
5
  • 1
    $\begingroup$ The phrase "undefined behaviour" wasn't actually used in any of the documents in the other question, or even "undefined". $\endgroup$
    – Michael Homer
    Nov 4, 2023 at 22:19
  • $\begingroup$ Hm, you're right, it said "the consequences are not defined". So my question here is not quite the thing relevant to know. I still think it's worth asking as I wrote it, so I'll leave it up (slightly edited) and see what I learn. $\endgroup$ Nov 4, 2023 at 22:26
  • $\begingroup$ Be sure to check for synonyms when researching. Appendix A Section 16 in my first edition of TCPL uses the phrase "unspecified" or "not specified" to refer to the order of evaluation of function arguments and side effects. $\endgroup$ Nov 5, 2023 at 3:49
  • 1
    $\begingroup$ Interesting find. "Unspecified" is very definitely not a synonym here, though. In the modern C standard, "unspecified" means something completely different from "undefined". In TCPL there I assume it is just taking the ordinary English meaning... $\endgroup$ Nov 5, 2023 at 7:03
  • $\begingroup$ Comments have been moved to chat; please do not continue the discussion here. Before posting a comment below this one, please review the purposes of comments. Comments that do not request clarification or suggest improvements usually belong as an answer, on Programming Language Design and Implementation Meta, or in Programming Language Design and Implementation Chat. Comments continuing discussion may be removed. $\endgroup$
    – lyxal
    Nov 20, 2023 at 10:50

3 Answers 3

3
$\begingroup$

The ANSI Common Lisp specification contains the following definition in its Error Terminology section:

The consequences are undefined
This means that the consequences are unpredictable. The consequences may range from harmless to fatal. No conforming code may depend on the results or effects. Conforming code must treat the consequences as unpredictable. In places where the words "must," "must not," or "may not" are used, then "the consequences are undefined" if the stated requirement is not met and no specific consequence is explicitly stated. An implementation is permitted to signal an error in this case.
For example: "Once a name has been declared by defconstant to be constant, any further assignment or binding of that variable has undefined consequences."

It also has a related "consequences are unspecified" designation. This stipulates that the consequences are unpredictable but harmless. "harmless" isn't defined rigorously, but we can presume this precludes it from launching a nuclear missile. It might prohibit nasal demons, but allow nasal angels.

This was published in 1994, but the standardization committee was formed in 1986. I think this terminology was determined early in the process.

$\endgroup$
10
  • 3
    $\begingroup$ The phrasing "the consequences are undefined" and "no conforming code may depend on the results or effects" seems to suggest that it's only what happens after the offending operation that is undefined. That is, the behaviour of the program up to the point where the offending operation is executed, should still exactly match the specified behaviour of the same program without that operation. If my interpretation is correct then that's a subtle difference between this notion and the modern notion of UB, which allows time travel. $\endgroup$
    – kaya3
    Nov 7, 2023 at 23:01
  • 1
    $\begingroup$ I tend to think of Lisp as an interpreted language, in which case undefined behavior would be a runtime event, rather than a static fact about a program. As such the effects could of course only move forward in time. Of course, many Lisps could also be compiled. But I could imagine the mental model of undefined behavior as a dynamic event in an ongoing computation, rather than a static property of a program, could still apply. $\endgroup$ Nov 8, 2023 at 4:28
  • $\begingroup$ Lisp should be thought of as a compiled language that includes an embedded interpreter. But in several implementations, the interpreter actually uses the compiler internally. @GlennWillen $\endgroup$
    – Barmar
    Nov 8, 2023 at 16:43
  • 2
    $\begingroup$ @supercat If you follow the link in my answer you'll see that CL has a much finer grained taxonomy of erroneous situations. Lisp has traditionally had lots of runtime error checking (e.g. array bounds checks), CL has configuration capabilities to enable/disable this, and the spec says how the error checks are affected by this. There are also specific points that are noted as places for implementation extension. C tends to lump almost everything into UB, although it does have so implementation-dependent situations. $\endgroup$
    – Barmar
    Nov 8, 2023 at 18:47
  • 1
    $\begingroup$ @supercat Well, Lisp has been used to write the OS for Lisp Machines, which has lots of implementation dependencies (including primitives to access memory directly). And much of the runtime library of conventional Lisp implementations is written in Lisp, and they may have lots of implementation dependencies. $\endgroup$
    – Barmar
    Nov 8, 2023 at 18:58
2
$\begingroup$

To add to supercat's answer, in which they state that C89 did not define "undefined behaviour" in this way, I have seen the argument made that this is a possible yet originally unintended reading of the standard, which was only adopted in C99.

To summarize the argument from the linked blog post, as I understand it, C89 defined the term as:

Undefined behavior --- behavior, upon use of a nonportable or erroneous program construct, of erroneous data, or of indeterminately-valued objects, for which the Standard imposes no requirements. Permissible undefined behavior ranges from ignoring the situation completely with unpredictable results, to behaving during translation or program execution in a documented manner characteristic of the environment (with or without the issuance of a diagnostic message), to terminating a translation or execution (with the issuance of a diagnostic message).

Now, depending on how you interpret the commas, this can either be paraphrased as "Undefined behaviour is the behaviour which occurs upon using certain constructs whose behaviour the standard does not otherwise define. This behaviour SHALL be any one of [a list of permissible behaviours]", or "Undefined behaviour is the behaviour, which this standard does not define, which occurs upon using certain constructs. This behaviour SHALL be any one of [a list of permissible behaviours]" (where I use "SHALL" in the RFC 2119 sense)

Since the latter interpretation is contradictory (by claiming the standard places no requirements on what the behaviour may be immediately before defining such requirements), the argument goes that the former interpretation is evidently the intended one. Nevertheless, for C99 this ambiguity was resolved in favor of the latter interpretation, changing the definition to:

1 undefined behavior
behavior, upon use of a nonportable or erroneous program construct or of erroneous data,
for which this International Standard imposes no requirements
2 NOTE Possible undefined behavior ranges from ignoring the situation completely with unpredictable
results, to behaving during translation or program execution in a documented manner characteristic of the
environment (with or without the issuance of a diagnostic message), to terminating a translation or
execution (with the issuance of a diagnostic message).

The comma placement leaves less room for ambiguity, and the addition of "NOTE" and the use of "Possible" instead of "Permissible" changes what follows from normative to advisory. Giving us an approximate definition of "Undefined behaviour is the behaviour, which this standard does not define, upon using certain constructs. This behaviour MAY be any one of [a list of permissible behaviours]" (again, see RFC 2119 for my use of "MAY").

Granted, you are welcome to disagree with with that argument, you're evidently in plentiful company if you do.

So if not C89, then when?

Well, I also can't provide a specific date. But if the C89 authors (or even just a portion of them) intended to use the term differently, that tells us that they didn't expect the modern definition of the term to be what readers would assume in case of perceived ambiguity (and presumably they also wouldn't expect there to be any ambiguity in the first place). While this is certainly not proof that the term had never been used that way before, it does suggest that this definition at least did not become dominant until some time after the 1989 publication of the C89 standard.

$\endgroup$
7
  • $\begingroup$ I don't think the list of possible outcomes was intended to be exhaustive even in C89. Far more significant is that the Standard was never intended to be the only thing which constrained how implementations would process various corner cases. Market forces were expected to act as a check to gratuitously nonsensical behaviors. $\endgroup$
    – supercat
    Nov 5, 2023 at 23:08
  • $\begingroup$ Fundamentally, the authors of C89 used UB as a catch-all for situations where they didn't want to concern themselves with details of what exactly could or couldn't happen. Trying to parse the definition of UB to decide what exactly is allowed to happen misses the point, which is that the authors of the Stanard wanted to avoid having to consider such issues in such cases. $\endgroup$
    – supercat
    Nov 5, 2023 at 23:17
  • $\begingroup$ Thanks, this is exactly the sort of thing I'm interested in learning. I am hoping perhaps more people have older primary sources to chime in with, but existing arguments made later are also very welcome data. $\endgroup$ Nov 5, 2023 at 23:29
  • $\begingroup$ @supercat I'm told that ANSI and/or ISO standards do distinguish the use of "permissible" for requirements and the use of "possible" for advisory content, but I freely admit I don't read enough standards to be certain whether or not I've been misled. It's also possible that I could have misinterpreted the intended strictness, confusing (what RFC 2119 would call) SHOULD and MUST. Still, I'll leave the post as it is, based on how the standard's wording was explained to me, until someone convinces me that explanation was wrong $\endgroup$
    – Sara J
    Nov 5, 2023 at 23:32
  • $\begingroup$ @SaraJ: A good standard for things that are supposed to work together (e.g. Acme plugs and Acme sockets) should be designed broadly enough that anything that can be accomplished by a device that fits an Acme socket should be possible with a conforming Acme plug, anything that can be done by a device that fits an Acme plug should be possible with a conforming Acme socket. It should, however, be tight enough to say something useful about arbitrary combinations of Acme plugs and Acme sockets. Doing this with C programs and implementations would have been impossible... $\endgroup$
    – supercat
    Nov 5, 2023 at 23:37
0
$\begingroup$

No, C89 is not the first place that notion was articulated, because C89 doesn't articlate that notion (and nor does any subsequent version of the Standard).

As far as the Standard is concerned, the term "Undefined Behavior" means nothing more nor less than that the behavior of the construct or corner case falls outside its jurisdiction. This implies that such case must not arise in any program whose behavior is to be fully specified by the Standard, i.e. strictly conforming C programs. Outside of the narrow realm of strictly conforming programs, however, the range of ways in which most compilers could behave in cases where the Standard imposes no requirements was expected to be constrained by a desire of compiler writers to sell compilers, and a consequent need to avoid behaving in a way customers and potential customers would view as unacceptable. While the Standard doesn't exclude the possibility that a compiler whose maintainers are hostile or indifferent to the needs of programmers targeting it might behave in completely unconstrained fashion in situations where the Stanard imposes no requirements, the "UB means anything can happen" notion would only be applicable to people who are stuck targeting such compilers.

A religion has formed among compiler writers who are sheltered from normal market forces, around the idea that the Standard only uses the phrase "Undefined Behavior" in situations which would never arise in any correct programs, interpreting the phrase "non-portable or erroneous" as "non-portable, and therefore erroneous", but that ignores not only the published Rationale documents for C89 and C99, but also every version of the C Standards Committee's charter to date, every single one of which has explicitly recognized the legitimacy of non-portable C code, and stated that the Standard it not meant to preclude the use of C as a form of "high-level assembly langauge".

I think the real shift came when proponents of clang and gcc were able to describe as "mainstream" behaviors which are unique to those two compilers and derivatives thereof, which for many tasks are effectively exempt from market competition by commercial compilers. If a programmer buys a $500 compiler that totally wipes the floor with clang and gcc, but wants to distribute code in contexts which would require that the recipients rebuild it, such distribution would require that the code be reworked to run on lower-quality freely distributable compilers, effectively negating any advantage the programmer should have been able to reap from buying a better compiler.

Incidentally, the C89 Standard does make a key distinction between "UB" and other behaviors that aren't fully specified by the Standard in the "as-if" rule and a corollary to it whose effects were intended to be minimal but which have become disastrous. Under the as-if rule, compilers may only perform optimizing transforms whose effects would not be observable under any defined program executions. A consequence of this is that if such a transform would observably affect the behavior of some sequence of actions, at least one of the actions involved must be characterized as invoking Undefined Behavior. This wouldn't be a problem if compilers interpreted the latitude they were given to be as narrow as required to perform specific useful tranforms. Unfortunately, aggressive compilers go beyond that, performing transforms that are seldom useful and are often best counter-productive.

An unfortunate aspect of this situation is that in many cases it may not be impossible to predict precisely how the optimal machine code that satisfies an application's requirements would behave in certain corner cases. Thus, allowing implementations to perform optimizing transforms in ways that might replace one acceptable corner-case behavior with another equally acceptable behavior would allow them to satisfy application requirements more efficiently than would otherwise be practical. If integer overflow were characterized as Implementation-Defined Behavior rather than UB, a compiler for a platform where integer overflows are trapped, given something like:

int test(int a, int b)
{
  int temp=a*b;
  if (f1())
    f2(temp,a,b);
}

would be required to perform the multiplication (or at least determine whether it would overflow) unconditionally, before calling f1(), even though code would likely not care about whether the computation of a*b would overflow in cases where f1() returned zero. Most applications whose requirements would be satisfied by the above code if integer overflow were characterized as Implementation-Defined Behavior would be satisfied equally well if not better if the code were transformed into:

int test(int a, int b)
{
  if (f1())
    f2(a*b,a,b);
}

even on platforms where the transformation would affect program behavior, but the Standard's abstraction model is incapable of allowing the above transformation without waiving jurisdiction over program behavior in case of integer overflow. While some compiler writers claim this allows more efficient code generation, it actually does the opposite by forcing programmers to write code in a manner that would block any optimizations transforms that could yield behaviors which would satisfy application requirements despite being inconsistent with the behavior of non-transformed code.

$\endgroup$
10
  • $\begingroup$ "...such distribution would require that.." require in which sense? The only one that I could infer assumes it is unreasonable to expect from the recipients of the distribution to purchase the compiler, but if this is the case it's not clear where this assumption comes from. $\endgroup$ Nov 5, 2023 at 7:02
  • 3
    $\begingroup$ Presumably supercat is referring to open source. Nobody is going to buy a \$500 compiler to build an open source project. Most people not building on behalf of an employer can't afford a \$500 compiler. $\endgroup$ Nov 5, 2023 at 7:05
  • 1
    $\begingroup$ ...shouldn't have been to figure out some way of interpreting the Standard to forbid it, nor to figure out some way for programmers to work aroun the limitation imposed thereby, but instead to have said "The Standard would probably allow a garbage compiler to behave in that fashion. Why--do you want to write one?" Many things are left undefined by the Standard not because there wasn't any commonplace behavior, but rather because there was a behavior which it was obvious immplementations should follow absent a good reason for doing otherwise. $\endgroup$
    – supercat
    Nov 5, 2023 at 17:07
  • 5
    $\begingroup$ -1: While tangentially relevant, this does not answer the question. $\endgroup$
    – Alexis King
    Nov 5, 2023 at 18:34
  • 2
    $\begingroup$ @AlexisKing Unfortunately, this is not an isolated incident. Every time someone asks about something UB-related on the network, supercat uses this as an excuse to write an off-topic jeremiad about what UB was “supposed” to mean and how his unicorn interpretation of the relevant specifications that avoids running into the principle of explosion is totally achievable, guys. You may have to adjust your remedies accordingly to something more substantial than just downvoting. $\endgroup$ Nov 20, 2023 at 9:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .