"At least one" in C standard translation limits specification

494 Views Asked by At

(This question was prompted by an answer to this previous question)

The C11 standard makes use of the following formulation when discussing the complexity of programs which a compliant compiler should be able to support:

5.2.4.1 Translation limits

The implementation shall be able to translate and execute at least one program that contains at least one instance of every one of the following limits:

...

  • 127 arguments in one function call

...

This "at least one" phrasing seems curious to me, as it appears like a standards compliant program could put arbitrary restrictions on most usages and still be compliant. For example, by having a 63 argument limit on variadic functions, but a 127 argument limit for functions with explicit parameters. Or requiring that only functions with names starting "BIGARG_" can be called with more than 99 parameters. Or some other such restriction.

Even with potentially arbitrary restrictions, there could be some odd condition where the 127 argument limit would be supported, so at least one program that contains at least one instance of that limit could be translated and executed. It's just that not all - or even most - programs that come close to that limit would be supported.

Is there a rationale for this particular phrasing? Why not explicitly require support of every program (else-wise compliant) which obeys those limits? Or is there some other mechanism to require uniform support of, for example, 127 arguments in function calls?

2

There are 2 best solutions below

2
On

Yes, an implementation could place arbitrary restrictions on the programs it can handle while still conforming to the letter of the standard. But the intent of 5.2.4.1 is that the easiest way to meet its specific requirements is to support reasonable limits for all programs.

You could create a single program that hits every one of the translation limits defined in 5.2.4.1 (and that, for example, produces no output), then write a "compiler" that recognizes that single program and produces an executable that does the equivalent of int main(void){}, while rejecting every other program with a diagnostic message saying that it exceeds the implementation's translation limits.

Such a compiler would, of course, be completely useless, which is why (as far as I know) nobody has bothered to create such a thing. (I've thought about doing it myself, just for the heck of it.)

In practice, compiler writers want to produce useful compilers that will correctly compile real C code.

The requirements of 5.2.4.1 are designed so that the easiest way to satisfy them (if you're writing a useful C compiler) is to impose as few actual limits as possible.

For example, a conforming compiler must support 127 nesting levels of blocks for that mythical "one program". The easiest way to meet that requirement is to support an arbitrary depth of nested blocks by having the compiler use dynamic data structures. In practice, the depth is limited, not by a hardwired limit in the compiler source, but by the amount of memory available at compile time. (Or a compiler could use some fixed-size internal data structure that permits exactly 127 levels, but it's probably easier to permit dynamic sizes.)

You might think it would be better for the standard to impose more "reasonable" requirements, so that a conforming compiler must accept all programs that do not exceed certain specified limits. The problem is that such "reasonable" limits are extremely difficult to specify precisely. There are always going to be some programs that exceed the capacity of a compiler -- and the size or complexity of such programs depends on the internal data structures and algorithms used by the compiler, and by the capacity of the particular system the compiler is running on. There was no way the standard could cover such details, or anticipate what limits might be "reasonable" for future systems.

2
On

The standard cannot require an implementation to accept all such compliant programs. Consider several limits, say, 127 nesting levels of blocks and 511 identifiers with block scope. Now imagine a program that has 127 levels of nesting blocks and 511 identifiers in each of those levels. Throw in 63 significant characters in each identifier, and you've got a program of a formidable size. An implementation that runs on a 16-bit microcomputer like, say, PDP-7 :) probably wouldn't be able to cope with it.