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