ISO/ IEC JTC1/SC22/WG14 N853

SC22/WG14/N853


                          Conformance issues
                             Clive Feather
                            clive@demon.net
                               1998-09-24


[All references in this paper are to CD2.]

Summary
=======

The definition of conformance has always been a problem with the C
Standard, being described by one author as "not even rubber teeth, more
like rubber gums". Though there are improvements in C9X compared with C89,
many of the issues still remain.

This paper proposes changes which, while not perfect, hopefully improve the
situation.


Detailed description
====================

Now that the C Standard is being cited in contractual and legal matters,
there is more interest in the meanings and interpretation of the sections
on conformance. In particular, implementations are only required to
correctly translate and execute "strictly conforming" programs. However,
this term is extremely narrowly defined, and the wording of the translation
limits section makes it too easy for an implementer to claim that any given
program is outside the limits. This in turn allows them to escape liability
for a defect on a technicality.

Another problem is that CD2 uses several terms in the definition of
conformance without actually defining those terms. These terms are:
- "accept"
- "correct"
- "execute"
- "translate"
It is reasonable to assume that "translate" refers to the process described
in 5.1.1, and "execute" to that in 5.1.2. However, the other two terms are
used in clause 4 without any unambiguous meaning. For example, what is
"correct data" and what is a "correct program" ? 4p3 does not define the
latter, but merely gives it licence to use certain constructs.

The first step is to replace these uses of "correct" with a new term - a
"reliably conforming" program. (This term is meant to show tha the
programmer can rely on the program conforming on all conforming
implementations. If anyone has a better term, please suggest it.) Change
4p3 from:

    [#3] A  program  that  is  correct  in  all  other  aspects,
    operating  on  correct data, containing unspecified behavior
    shall be a  correct  program  and  act  in  accordance  with
    5.1.2.3.

to:

    A /reliably conforming/ program shall use only those features
    of the language and library specified in this International
    Standard and shall not produce output dependent on any undefined
    behavior. When translated and executed it shall act in
    accordance with 5.1.2.3.

Similarly, the term "strictly conforming" should be loosened to exclude a
reliance on translation limits. Otherwise it is possible to claim that no
program except the one special one is strictly conforming. To do this,
delete from 4p5:

    "and shall not exceed any minimum implementation limit"

Finally, change 4p6 to the following:

    [#6] The two forms of conforming implementation  are  hosted
    and  freestanding.  A conforming hosted implementation shall
 || translate and execute any reliably conforming program.
    A conforming freestanding implementation shall
 || translate and execute any reliably conforming program
    does not use complex  types  and  in
    which  the  use  of  the  features  specified in the library
    clause (clause  7)  is  confined  to  the  contents  of  the
    standard    headers   <float.h>,   <iso646.h>,   <limits.h>,
    <stdarg.h>,  <stdbool.h>,  <stddef.h>,  and  <stdint.h>.
 || In either case translation or execution might fail if the
 || size or complexity of a program or its data exceeds the
 || capacity of the implementation. A
    conforming  implementation  may  have  extensions (including
    additional library functions), provided they  do  not  alter
    the behavior of any strictly conforming program.3)

This changes the primary test on an implementation to be the ability to
handle reliably conforming programs, rather than stricly conforming ones
(which are a subset). The added words make it clear that the following text
from 1p2 applies:

    [#2] This International Standard does not specify
[...]
    -- the  size  or complexity of a program and its data that
       will  exceed  the  capacity  of  any   specific   data-
       processing  system  or  the  capacity  of  a particular
       processor;

The sum effect of these changes is to require an implementation to
translate and execute *all* "correct" programs unless they are "too big"
or "too complex". This is somewhat more realistic than just having to
handle a small set of strictly conforming programs.

However, without an understanding of what "too big" or "too complex"
actually means, the conformance wording remains week. The following text
should be appended to 5.2.4.1:

    The implementation shall document a way to determine if the
    size or complexity of a correct program exceeds or might exceed
    the capacity of the implementation.

This requires the limitations to be documented by the implementer.

Finally, here is some material for the Rationale:

4. A conforming implementation is one that, roughly speaking, honours the
requirements of the Standard. Any program that that implementation accepts
is a conforming program on that implementation.

One important class of programs is those that every implementation must
translate and execute correctly (ignoring issues of resource limits for the
moment). These are called reliably conforming programs. Such a program does
not make use of any undefined behavior or any extensions, and so it has a
well-defined "meaning" in an abstract sense. However, its behavior can
depend on implementation-specific choices, and so it can produce different
output on different implementations. For example:

    #include <limit.h>
    #include <stdio.h>
    int main (void)
    {
        printf ("%d", INT_MAX);
        return 0;
    }

is a reliably conforming program, but produces different outputs.

An implementation must obey the requirements of the Standard, including
"correct" translation and execution, for any reliably conforming program,
and also for any other conforming program unless the behavior has been
explicitly modified by an extension.

If a reliably conforming program does not make use of anything unspecified
(including implementation-defined matters) it is called strictly
conforming. All strictly conforming programs generate the same output in
the "C" locale, but can generate varying outputs in other locales (provided
that a program does not rely on the presence of a specific locale, it can
remain strictly conforming).

All of the above discussion assumes that resources are unlimited. Of
course, in reality compilers must operate in a fixed amount of memory and
programs are restricted in various ways when they come to execute. So the
Standard allows an implementation to fail to translate, or to execute, a
program which is "too big" or "too complex" for the available resources.
However, as described in 5.2.4.1 it must still document what the limits
are.

5.2.4.1. An implementation is always free to state that a given program is
too large or too complex to be translated or executed. However, to stop
this being a way to claim conformance while providing no useful facilities
whatsoever, the implementer must show provide a way to determine whether a
program is likely to exceed the limits. The method need not be perfect, so
long as it errs on the side of caution.

One way to do this would be to have a formula which converted values such
as the number of variables into, say, the amount of memory the compiler
would need. Similarly, if there is a limit on stack space, the formula need
only show how to determine the stack requirements for each function call
(assuming this is the only place the stack is allocated) and need not work
through every possible execution path (which would be impossible in the
face of recursion). The compiler could even have a mode which output a
value for each function in the program.
====

-- 
Clive D.W. Feather   | Regulation Officer, LINX | Work: <clive@linx.org>
Tel: +44 1733 705000 | (on secondment from      | Home: <cdwf@i.am>
Fax: +44 1733 353929 |  Demon Internet)         | <http://i.am/davros>
Written on my laptop; please observe the Reply-To address