Does the standard say anything about how deeply nested calls can recurse?  I 
would imagine this is one of those things that's really difficult to 
standardize. Or is this one of those "implementation defined" things, which 
would also seem very difficult to control via the compiler on a modern OS.

-- 
Darren New, San Diego CA, USA (PST)
   "Coding without comments is like
    driving without turn signals."

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> Does the standard say anything about how deeply nested calls can recurse?  I 
> would imagine this is one of those things that's really difficult to 
> standardize. Or is this one of those "implementation defined" things, which 
> would also seem very difficult to control via the compiler on a modern OS.

  That's an interesting question. I don't have the standard here (after all,
it's commercial, so you either have to pay for it, get a free pre-standard
draft, or pirate it), but if I had to guess, it's most probably implementation
defined (the standard *might* recommend a lower limit, but I don't know if
it does).

  In practice you can run out of stack space if you allocate too much on
the stack, and especially if you then recurse deeply. I don't remember now
what kind of error you get in that case (but the end result is probably an
abort()). In many systems the size of the stack can actually be defined from
the outside (iow. the you tell the OS how much stack space it should reserve
for the program you are going to run).

-- 
                                                          - Warp

Post a reply to this message

On 6/22/2011 13:07, Warp wrote:
> (but the end result is probably an abort()).

I would be very, very surprised if it wasn't undefined behavior to violate 
the limits of the stack space.  There's just no good efficient portable way 
of checking on hardware that doesn't do per-access checks (i.e., like a Z80 
or something).

 > In many systems the size of the stack can actually be defined from
> the outside (iow. the you tell the OS how much stack space it should reserve
> for the program you are going to run).

And that's why I'm thinking it can't really be implementation-defined, 
unless the implementation is allowed to define it as "ask the OS."

-- 
Darren New, San Diego CA, USA (PST)
   "Coding without comments is like
    driving without turn signals."

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> On 6/22/2011 13:07, Warp wrote:
> > (but the end result is probably an abort()).

> I would be very, very surprised if it wasn't undefined behavior to violate 
> the limits of the stack space.  There's just no good efficient portable way 
> of checking on hardware that doesn't do per-access checks (i.e., like a Z80 
> or something).

  You can violate any space by poking with pointers and offset at wild,
but the question was what happens if a function recurses too much and the
function calls run out of stack space.

  The official standard probably defines it as either undefined behavior
or implementation defined, but in practice what happens in most systems
is that the C runtime asks the OS to increase the stack space for that
process, the OS says nope, and then the C runtime aborts with some message.

>  > In many systems the size of the stack can actually be defined from
> > the outside (iow. the you tell the OS how much stack space it should reserve
> > for the program you are going to run).

> And that's why I'm thinking it can't really be implementation-defined, 
> unless the implementation is allowed to define it as "ask the OS."

  AFAIK in most systems the C runtime does indeed ask the OS to increase
the stack space as needed (in a similar way as it asks the OS to increase
heap space as needed).

-- 
                                                          - Warp

Post a reply to this message

On 6/22/2011 14:32, Warp wrote:
> Darren New<dne### [at] sanrrcom>  wrote:
>> On 6/22/2011 13:07, Warp wrote:
>>> (but the end result is probably an abort()).
>
>> I would be very, very surprised if it wasn't undefined behavior to violate
>> the limits of the stack space.  There's just no good efficient portable way
>> of checking on hardware that doesn't do per-access checks (i.e., like a Z80
>> or something).
>
>    You can violate any space by poking with pointers and offset at wild,
> but the question was what happens if a function recurses too much and the
> function calls run out of stack space.

I was aware of what question I asked, yes. :)

>    The official standard probably defines it as either undefined behavior
> or implementation defined, but in practice what happens in most systems
> is that the C runtime asks the OS to increase the stack space for that
> process, the OS says nope, and then the C runtime aborts with some message.

In most multitasking systems with virtual memory running user-space 
applications, yes. And my point is that I don't think there's anything in 
the standard that's going to restrict C to that sort of machine.

In practice, under UNIX and Windows and such, yes, that's what happens. On 
the Amiga 1000? On a Z-80 or 68000 or 8086? No, that's not what happens.

>    AFAIK in most systems the C runtime does indeed ask the OS to increase
> the stack space as needed (in a similar way as it asks the OS to increase
> heap space as needed).

Again, assuming you're talking about a multi-user virtual-memory-based 
operating system with demand paging, implying the hardware has per-access 
memory checking.  On systems without per-access memory checking, you don't 
get that, and it would be odd to include in the standard something that 
would have egregious overhead to enforce on low-end hardware.

Am I missing something?  Was I unclear, or were you just not paying as much 
attention as you usually do?  (Serious question, not intended as a 
criticism. I'm just trying to improve my communication skills.)

-- 
Darren New, San Diego CA, USA (PST)
   "Coding without comments is like
    driving without turn signals."

Post a reply to this message

Am 22.06.2011 21:50, schrieb Darren New:
> Does the standard say anything about how deeply nested calls can
> recurse? I would imagine this is one of those things that's really
> difficult to standardize. Or is this one of those "implementation
> defined" things, which would also seem very difficult to control via the
> compiler on a modern OS.

Such a limit wouldn't make much sense, as the nesting of calls is 
typically limited by stack size, the use of which highly depends on the 
number of parameters and local variables in a function call. 
Consequently, according to the standard it's not even "implementation 
defined", nor is the behaviour explicitly "undefined" or "unspecified" 
if such limitations are exceeded.

In a typical software production for embedded systems, the maximum 
required stack size will be determined as part as the build process (by 
examining the call tree), and recursive function calls avoided wherever 
possible. An alternative is to run dedicated tests to determine stack 
(and heap) usage, and makes sure it does not reach the device's limits 
minus a safety margin.

In safety critical applications (e.g. car electronics), dedicated memory 
space might be set aside for a separate "high safety" task with limited 
functionality but well-analyzed requirements, which might in turn watch 
the stack usage of any "convenience" parts of the software at run-time 
(e.g. by filling some safety margin just before that software parts' 
stack limit with a predefined pattern and repeatedly checking whether 
that region remains unchanged). If the expected stack size is ever found 
to have been exceeded, the high safety task would then usually try to 
re-start the convenience tasks (to make sure they're not operating on 
corrupt data), and in case of repeated failure disable them entirely, 
possibly reducing the device's functionality to shutting down safely.

Post a reply to this message

On 6/22/2011 16:31, clipka wrote:
> it's not even "implementation defined", nor is the behaviour
> explicitly "undefined" or "unspecified" if such limitations are exceeded.

It seems odd that a standard wouldn't describe what happens, even if only by 
describing it as "undefined what happens if you exceed a limit that the 
standard also doesn't specify." Because if you don't point out "hey, 
function calls may fail in undefined ways", then it would seem you're 
guaranteeing they'll obey the semantics the standard gives them.

> In a typical software production for embedded systems,

Sure, I understand how the things work. Thanks for the description. I just 
wondered what the standard had to say, if anything.  (But I don't wonder 
intensely enough to try to find it in the draft standards. :-)

-- 
Darren New, San Diego CA, USA (PST)
   "Coding without comments is like
    driving without turn signals."

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> Am I missing something?  Was I unclear, or were you just not paying as much 
> attention as you usually do?  (Serious question, not intended as a 
> criticism. I'm just trying to improve my communication skills.)

  I'm not understanding what you are not understanding.

  I said that I don't know for certain what the standard says (because I don't
have a copy) but that I would guess it's implementation defined. Then I
commented on how it works in practice in many systems.

-- 
                                                          - Warp

Post a reply to this message

On 6/22/2011 23:38, Warp wrote:
>    I said that I don't know for certain what the standard says (because I don't
> have a copy) but that I would guess it's implementation defined. Then I
> commented on how it works in practice in many systems.

Oh, OK. I understood what you were saying, indeed. Since you basically 
rephrased in your answer the parts I explained I already knew, I thought 
perhaps I hadn't explained it clearly. But you were just rephrasing to 
clarify anything I might have said that sounded right but was actually not 
understood by me. Cool. Thanks!

-- 
Darren New, San Diego CA, USA (PST)
   "Coding without comments is like
    driving without turn signals."

Post a reply to this message

On 06/22/11 21:50, Darren New wrote:
> Does the standard say anything about how deeply nested calls can
> recurse?

Partially: At least 2, because it says that functions can be called
recursively. :-)


> I would imagine this is one of those things that's really
> difficult to standardize. Or is this one of those "implementation
> defined" things, which would also seem very difficult to control via the
> compiler on a modern OS.

there are a lot of limits and other limitations where "no diagnostic is
required". But I cannot find anything about a maximum of function call
nesting levels, neither in C++ 2003 nor in C 99.

Lars R.

Post a reply to this message

On 6/28/2011 5:26, Lars R. wrote:
> On 06/22/11 21:50, Darren New wrote:
>> Does the standard say anything about how deeply nested calls can
>> recurse?
>
> Partially: At least 2, because it says that functions can be called
> recursively. :-)

Heh heh heh. That's a point.

> there are a lot of limits and other limitations where "no diagnostic is
> required". But I cannot find anything about a maximum of function call
> nesting levels, neither in C++ 2003 nor in C 99.

See, that bothers me. Because it implies a function call will always 
succeed, because they didn't say it might fail but they do tell you the 
semantics of it succeeding.  That's why I wondered what kind of wording they 
were using.

-- 
Darren New, San Diego CA, USA (PST)
   "Coding without comments is like
    driving without turn signals."

Post a reply to this message

>>> Does the standard say anything about how deeply nested calls can
>>> recurse?
>>
>> Partially: At least 2, because it says that functions can be called
>> recursively. :-)
> 
> Heh heh heh. That's a point.
> 
>> there are a lot of limits and other limitations where "no diagnostic is
>> required". But I cannot find anything about a maximum of function call
>> nesting levels, neither in C++ 2003 nor in C 99.
> 
> See, that bothers me.

Me too.

> Because it implies a function call will always
> succeed, because they didn't say it might fail but they do tell you the
> semantics of it succeeding.  That's why I wondered what kind of wording
> they were using.

Indeed.

I'd suggest something like “A recursion depth of at least 5 must be
supported by the platform. The actual limit might be higher and can be
determined by ...”

But such guarantee is not easily definable because the size of the
function parameters is not limited (only their number). On most
platforms the function parameters live on the CPU stack (when the
registers that are used for parameter transfer are exhausted). That
stack is on most platforms much smaller than the available memory, but
its size cannot be determined in a ISO-C++-compliant way.

So even a recursion “depth” of 1 might fail in such pathetic cases.

But statements like “Every function call might fail due to reasons that
are out of scope of this standard“ are also not sensible, I think.

Any other options or opinions? –.–

Lars R.

Post a reply to this message

On 6/29/2011 0:44, Lars R. wrote:
> I'd suggest something like “A recursion depth of at least 5 mus
t be
> supported by the platform. The actual limit might be higher and can be
> determined by ...”

Well, it's not even *recursion* depth, but just call stack depth.

> But such guarantee is not easily definable because the size of the
> function parameters is not limited (only their number).

Not any more. In the original version of C, you couldn't pass structs by 

value, so it would have been easier to figure out how big your arguments 
are.

> So even a recursion “depth” of 1 might fail in such pat
hetic cases.

If you don't have actual *recursive* functions, you don't need to allocat
e 
locals or arguments on the stack at all. On a machine with limited hardwa
re 
stack (like a 6502 say), you might very well generate code that will 
allocate bigger items in the heap and clean them up when you return, for 

example.

I've used Pascal compilers (on a Z-80 for example) that stored all local 

variables at fixed addresses. I don't remember how it handled recursion, 
but 
since I was writing a B-Tree library, I'm pretty sure it recursed OK.


> But statements like “Every function call might fail due to reas
ons that
> are out of scope of this standard“ are also not sensible, I thi
nk.

I think you could require a minimum amount of stack space to be available
, 
if you wanted. The standard could guarantee that the number of bytes of a
uto 
and parameter values passed not exceeding a particular value could be 
specified, if they wanted. It's not like the concept of "size of memory 
occupied" isn't common in C.

-- 
Darren New, San Diego CA, USA (PST)
   "Coding without comments is like
    driving without turn signals."

Post a reply to this message

Lars R. <rou### [at] gmxnet> wrote:
> I'd suggest something like ???A recursion depth of at least 5 must be
> supported by the platform.

  They can't do that because then all compilers would become non-standard
in this regard.

  You can't impose a minimum amount of recursions because it depend on the
size of the stack and how much stuff is allocated on it. You can allocate
such a huge array on the stack that you might not be able to recurse even
once without running out of stack space, regardless of how large the stack
is.

-- 
                                                          - Warp

Post a reply to this message

On 6/29/2011 12:55, Warp wrote:
>    You can't impose a minimum amount of recursions because it depend on the
> size of the stack and how much stuff is allocated on it. You can allocate
> such a huge array on the stack that you might not be able to recurse even
> once without running out of stack space, regardless of how large the stack
> is.

That's why I thought maybe imposing a minimum stack size in bytes would work 
out better. Of course, compilers wouldn't become non-standard to support 
this - they'd just have to allocate big locals somewhere other than the 
stack, which is of course a bad idea for any reason other than compatibility 
with lame requirements. :-)

-- 
Darren New, San Diego CA, USA (PST)
   "Coding without comments is like
    driving without turn signals."

Post a reply to this message

Am 29.06.2011 18:49, schrieb Darren New:

> If you don't have actual *recursive* functions, you don't need to
> allocate locals or arguments on the stack at all. On a machine with
> limited hardware stack (like a 6502 say), you might very well generate
> code that will allocate bigger items in the heap and clean them up when
> you return, for example.

... which does not prevent you from failure due to hitting the memory limit.

> I've used Pascal compilers (on a Z-80 for example) that stored all local
> variables at fixed addresses. I don't remember how it handled recursion,
> but since I was writing a B-Tree library, I'm pretty sure it recursed OK.

In that case it either can't have placed all local variables at fixed 
addresses, or must have placed a hard limit on recursions.

Either way, there /always/ is a limit on recursion depth, and AFAIK 
determining at compile-time whether an arbitrary program ever hits that 
depth is as hard as solving the halting problem.

Post a reply to this message

On 6/29/2011 20:40, clipka wrote:
> ... which does not prevent you from failure due to hitting the memory limit.

Of course.  I wasn't trying to imply there might not be a recursion limit. 
Of course anything that allocates memory might fail, and a function call 
that's going to allocate a large chunk of memory for a parameter could fail.

> In that case it either can't have placed all local variables at fixed
> addresses, or must have placed a hard limit on recursions.

I honestly don't remember. I remember I had to switch to a C compiler 
because I didn't have enough memory for all local variables at once.

> Either way, there /always/ is a limit on recursion depth, and AFAIK
> determining at compile-time whether an arbitrary program ever hits that
> depth is as hard as solving the halting problem.

Right.  Sorry if what I wrote implied I thought that wasn't the case.

-- 
Darren New, San Diego CA, USA (PST)
   "Coding without comments is like
    driving without turn signals."

Post a reply to this message

On 06/29/11 21:55, Warp wrote:
> Lars R. <rou### [at] gmxnet> wrote:
>> I'd suggest something like ???A recursion depth of at least 5 must be
>> supported by the platform.
> 
>   They can't do that because then all compilers would become non-standard
> in this regard.
> 
>   You can't impose a minimum amount of recursions because it depend on the
> size of the stack and how much stuff is allocated on it.

Hence I wrote: "I would". And in the next sentence I explained why this
whish is not realizable.

L.

Post a reply to this message

On 06/29/11 18:49, Darren New wrote:
> On 6/29/2011 0:44, Lars R. wrote:
>> I'd suggest something like “A recursion depth of at least 5 must be
>> supported by the platform. The actual limit might be higher and can be
>> determined by ...”
> 
> Well, it's not even *recursion* depth, but just call stack depth.

If a language allows recursion you need some kind of stack. If a
language only allows non-recursive function calls you can hold the local
variables at fix addresses, as you also wrote below.

Some tricks like tail recursion optimization allows such fix addresses
also for a limited kind of recursive functions, though...

>> But such guarantee is not easily definable because the size of the
>> function parameters is not limited (only their number).
> 
> Not any more. In the original version of C, you couldn't pass structs by
> value, so it would have been easier to figure out how big your arguments
> are.

Outdated non-standard versions don't interest me. ^^

>> But statements like “Every function call might fail due to reasons that
>> are out of scope of this standard“ are also not sensible, I think.
> 
> I think you could require a minimum amount of stack space to be
> available, if you wanted.

If you require that (non-recursive) function calls use a "stack" at all.
That's why both the C and C++ standards avoid to use the term "stack" in
this context.

> The standard could guarantee that the number
> of bytes of auto and parameter values passed not exceeding a particular
> value could be specified, if they wanted.

Sounds better. So it doesn't matter whether parameters are passed on
some kind of "stack" (in memory or CPU registers) or on fixed locations
(im memory or fixed CPU registers).


		Lars R.

Post a reply to this message

On 6/30/2011 0:54, Lars R. wrote:
> On 06/29/11 18:49, Darren New wrote:
>> On 6/29/2011 0:44, Lars R. wrote:
>>> I'd suggest something like “A recursion depth of at least 5 m
ust be
>>> supported by the platform. The actual limit might be higher and can b
e
>>> determined by ...”
>>
>> Well, it's not even *recursion* depth, but just call stack depth.
>
> If a language allows recursion you need some kind of stack. If a
> language only allows non-recursive function calls you can hold the loca
l
> variables at fix addresses, as you also wrote below.

Sure. I was just saying that supporting a call stack depth of at least fi
ve 
is more precise than supporting a recursion depth of at least five. I.e.,
 
it's possible to run out of stack space even if there's no recursion 
involved, assuming you're allocating locals on a stack.

And it's possible for each function to have its own stack, so it can get 

really messy.

>> I think you could require a minimum amount of stack space to be
>> available, if you wanted.
>
> If you require that (non-recursive) function calls use a "stack" at all
.
> That's why both the C and C++ standards avoid to use the term "stack" i
n
> this context.

Right. But you could still phrase it as requiring a minimum amount of spa
ce 
for arguments and auto variables.  I.e., you could express it as adding u
p 
the value of sizeof() for each argument in the call chain and each auto 
local in the call chain and have a minimum number there. That doesn't mea
n 
you can't implement it differently, but it does give some guarantees abou
t 
how much space you have to provide for user variables.

> Sounds better. So it doesn't matter whether parameters are passed on
> some kind of "stack" (in memory or CPU registers) or on fixed locations

> (im memory or fixed CPU registers).

Exactly. It has to be written in terms of the semantics of the language, 
not 
in terms of an implementation.

-- 
Darren New, San Diego CA, USA (PST)
   "Coding without comments is like
    driving without turn signals."

Post a reply to this message