2

If the stack size in C is an implementation detail, and stack overflow is undefined behavior, is is possible whatsoever to perform any recursion at all without the possibility of summoning nose demons?

If I traverse through a data structure recursively, to give a naïve example:

struct tree {
    int leaf;
    struct tree *left;
    struct tree *right; 
}
struct tree *get(const struct tree *t, int i) {
    if (t == NULL) return NULL;
    return i == t->leaf ? t : (i > t ? get(t->right) : get(t->left));
}

Is there some sort of check that can be implemented so that this example can run safely on any standards-following C compiler, is there some sort of macro for that, or is it completely impossible, and there is no way to make this example or any similar pattern safe?

lemonhuman
  • 66
  • 7
  • I have a microprocessor with 256 bytes of memory. I have no idea how many stack frames that is, but it can't be many. If the functions are inlined then there is no problem but how do you know the compiler's optimizer can do that? Related: https://stackoverflow.com/questions/190232/can-a-recursive-function-be-inline – Jerry Jeremiah Nov 10 '20 at 21:11
  • This looks like tail recursion, so a sane optimizing compiler will produce code without much stack usage. – Eugene Sh. Nov 10 '20 at 21:11
  • But said that - your concern is that no one dictates the minimum size of stack, so any recursive function might fail with stack overflow. But the same would be true with *any* C function making use of stack for local variables and/or return addresses. So the question can be rephrased just for any C program. – Eugene Sh. Nov 10 '20 at 21:13
  • @EugeneSh. The problem is that the standard doesn't require a "sane optimizing compiler" and some of those microprocessors come with proprietary compilers. So unless you know it is compiled by a certain compiler, all bets are off. – Jerry Jeremiah Nov 10 '20 at 21:15
  • @JerryJeremiah: The Standard allows almost any compiler to behave in almost any fashion given almost any source text, but the authors expect that implementations will attempt to behave usefully when practical anyhow. – supercat Nov 10 '20 at 21:18

1 Answers1

3

In the Rationale for the C99 Standard, page 24, discussing translation limits:

The Standard requires that an implementation be able to translate and execute some program that meets each of the stated limits. This criterion was felt to give a useful latitude to the implementor in meeting these limits. While a deficient implementation could probably contrive a program that meets this requirement, yet still succeed in being useless, the C89 Committee felt that such ingenuity would probably require more work than making something useful. The sense of both the C89 and C99 Committees was that implementors should not construe the translation limits as the values of hard-wired parameters, but rather as a set of criteria by which an implementation will be judged.

Provided that there exists at least one--possibly contrived and useless--program that nominally exercises the given translation limits, and that an implementation will process in a fashion consistent with the Standard, nothing the implementation does with any other program could render it non-conforming. Thus, it's not actually possible for any program to meaningfully avoid Undefined Behavior, but the authors of the Standard expected that most implementations would focus more on what would be necessary to make them useful, rather than on trying to do the bare minimum required by the Standard.

supercat
  • 77,689
  • 9
  • 166
  • 211
  • But in practicality, is there a way to make sure that a C program using recursion is memory safe in a sane compiler? – lemonhuman Nov 10 '20 at 21:21
  • @lemonhuman Limit the recursion depth making assumption you know the allowed stack size. – Eugene Sh. Nov 10 '20 at 21:22
  • 1
    @lemonhuman: It depends on what you mean by "make sure" and "sane". There is no easy way to check stack usage on different platforms. In practice, if your program does not use very large stack frames, it will probably *crash* rather than cause other, more insidious errors if it exceeds the stack on "big" systems like desktops and phones, because these systems have stacks with guard pages. On embedded systems, you will probably want to use testing or perhaps analyze the object files if you are concerned. – Dietrich Epp Nov 10 '20 at 21:25
  • 2
    @lemonhuman: Unfortunately not. The vast majority of C implementations use "hope for the best" semantics. Use implementation-specific means to measure stack usage, estimate how much stack the implementation seems to need for each level of nesting, and try to ensure that the available stack exceeds estimated requirements by a reasonable margin. Some compilers for tiny micros that don't support recursion can do better, but the Standard's mandated support for recursion has discouraged implementations from supporting static stack checking. – supercat Nov 10 '20 at 21:25
  • @lemonhuman: BTW, I'd like to see the Standard recognize a category of implementations and programs such that conforming implementations would be allowed to reject any program, but source texts could demand certain behavioral guarantees, and implementations would be *required* to reject any program whose guarantees they cannot fulfill. Such categories of programs and implementations would avoid the need for the "one program rule" and could also resolve many of the conflicts between programmers and compiler writers regarding "Undefined Behavior". – supercat Nov 12 '20 at 16:33
  • @lemonhuman: If a program specifies that integer computations that overflow must behave as they compute some kind of possibly-meaningless value that need not be within range of `int`, but must have no other side effects, an implementation that can't uphold such guarantees would be free to reject it, but implementations that can usefully process a wide range of useful programs would be recognizable as superior to those that can't. – supercat Nov 12 '20 at 16:36