«

On Sun, 12 Oct 2003, Sidney Cadot wrote:
>
> >>> [[does the Standard require a stack?]]
> >
> > The constraints in the standard force "stack-like behavior" for
> > local variables inside functions (including any parameters), and
> > I think it is not out of line to call this "a stack". [...]
>
> As for me: If it walks like a stack and talks like a stack, so to say -
> I'd prefer to call it a stack.

But lots of non-pedants like to say things like, "automatic variables
are declared on the stack," or "the function parameters are pushed on
the stack in reverse order," or things like that -- which are blatantly
false, given some of the "stack-like" models that [whomever you were
quoting] demonstrated.

> If I understand what you're saying correctly, the standard does not (of
> course!) force the underlying hardware to support anything stack-like,
> but the runtime model implies something that can in good faith only be
> called a stack

....or two stacks, or three. Or one three-element "stack" per function
(giving a maximum recursion depth of 3 calls). Or whatever else the
implementor comes up with...

> (albeit perhaps one that implemented in software, as your
> IBM 370 and other examples show). Interesting.
>
> >>... is there a minimum depth of function calls that I can rely on to
> >>be executed properly? I would hate to rewrite all my programs to do
> >>everything within main() without function calls, for the ultimate
> >>portability
> >
> > I have never found one. The "Translation limits" section (at or
> > near 5.2.4.1) is the logical place for something like "at least N
> > function activations down from the initial call to main()", but
> > there is no such wording. On the other hand, that section is not
> > a good weapon against Evil Compilers, as it requires only that an
> > implementation "translate and execute ... one program" that tests
> > those limits.
>
> That's interesting... Based on a literal reading of the standard at
> least, I'd say my sample program is fully compliant and there's no
> reason for it ever to not reach the 'return 0' statement.

Correct. The only reason the program doesn't work is because we
live in the pesky physical world.

> Now the actual behavior, segfaulting, is usually classified as a
> manifestation of 'undefined behavior' in other contexts. Moreover, it is
> obvious that one cannot sensibly expect arbitrarily deep function calls
> to work (although the standard doesn't give limits).
>
> To me, perhapse naively, this seems then like a point where the standard
> is not complete. Anybody care to comment on that point of view?

Yup. The Standard doesn't give any hint of a min-max recursion depth.
In practice, I think most compiler systems use sensible recursion
strategies, limited only by the amount of RAM available. But yes, in
theory, all C compilers are non-conforming in this regard.

You might be interested in this old thread:
http://groups.google.com/groups?
threadm=Pine.LNX.4.53L-

which is also continued under different subject lines here:
http://groups.google.com/groups?
threadm=Pine.LNX.4.53L-031.0304251302260.9612%40unix44.andrew.cmu.edu
threadm=3eb1049b$
and several other places. [I hate the way Google Groups handles
threads with changing subject lines!] Search for "C turing-complete"
in comp.programming and comp.lang.c, and see what pops up, if you're
still interested. (Bottom line: An infinite stack can't simulate an
infinite tape.)

-Arthur

On Sun, 12 Oct 2003 00:12:38 +0200, in comp.lang.c , Sidney Cadot
<> wrote:

>Hi Chris,
>
>>>> [[does the Standard require a stack?]]
>
>> The constraints in the standard force "stack-like behavior" for
>> local variables inside functions (including any parameters), and
>> I think it is not out of line to call this "a stack". [...]
>
>As for me: If it walks like a stack and talks like a stack, so to say -
>I'd prefer to call it a stack.

Except that its not. The standard doesn't require, or even force,
implementations to put variables into a stack. I don't think thats
what Chris was saying. For example all parameters could be (and even
on stack based machines generally are) passed via registers. All
automatics could be created in reserved memory, in no particular
order.


--
Mark McIntyre
CLC FAQ <http://www.eskimo.com/~scs/C-faq/top.html>
CLC readme: <http://www.angelfire.com/ms3/bchambless0/welcome_to_clc.html>


----== Posted via Newsfeed.Com - Unlimited-Uncensored-Secure Usenet News==----
http://www.newsfeed.com The #1 Newsgroup Service in the World! >100,000 Newsgroups
---= 19 East/West-Coast Specialized Servers - Total Privacy via Encryption =---

Hi Barry,

>> [snip program]
>>As far as I can see, this is a perfectly valid C program that should
>>reach the 'return 0' statement always, were it not for the fact that in

> It is valid in the theoretical sense but it executes in the real
> world.

Of course I agree, but this being comp.lang.c, I think it's valid to
look at the ill-lit corners of the language as it is specified.

I mean, people here sometimes insist that code like:

#include <stdio.h>
int main(void)
{
int a[1];
printf("%d", a[1]);
return 0;
}

....could cause nuclear detonation or even (perish the thought!)
harddrive formatting, so I think there's a bit of a tradition with
regard to projecting theoretical issues onto practice.

> All systems have limited resources. Even virtual memory is backed up
> in some kind of file. I could not find in the standard a minimum for
> the number of recursive function calls an implementation was required
> to support. It does state that a function can be recursively called
> at least once.

Of course you're right. I would be already half satisfied if there would
be a statement in the standard to the effect that "function calls are
allowed to consume an unspecified amount of an unspecified type of one
or more unspecified types of resources, which the function will release
upon completion of execution. Undefined behavior can occur when the
amount of said resources in use at any one time exceeds an unspecified
threshold."

The downside of such a statement of course would be that any program
performing function calls could cause undefined behavior. But right now
that seems to be an accurate representation of the state of affairs
anyway, so the question is: which one of the two evils is the most evil?

Please realize that I'm playing the devil's advocate here... I'm just
curious if I'm either missing something crucial in the Standard, or that
perhaps a wording could be found to mend the situation to the effect
that something real we sometimes observe in practice (stack overflows)
is covered by the Standard.

> [[ some numbers on estimate of memory usage in the sample program ]]

The sample program was of course devised exactly to trigger a stack
overflow on any (or at least most) practical implementations.

An interesting point is that by recognizing tail recursion, a very smart
compiler could even come up with a translation that does, indeed,
eventually reach the 'return 0' statement.

> Would you be asking your question if your program simply issued malloc
> requests until no more memory was available? The only difference is
> that malloc fails "politely" by returning NULL.

That's a good homologous case, yes, with the exception (as you point
out) that there is a perfectly good provision within the Standard to
handle it.

> There doesn't seem to be any way for a recursion failure to be "polite." Both fail for
> exactly the same reason. Only the symptoms of that failure are
> different.

I beg to differ on your first statement, I think there is a way, but it
would require an amendment to the standard.

A function invocation could check if it would exceed the stack resource,
and (if so) abort execution, for example. This would require a change of
the standard, and would have performance ramifications. But it would be
possible.

> Welcome to the limitations of practicality.

That's all good and dandy, but we still seem to be stuck in a situation
where a fully compliant program invokes a segmentation fault, which can
only signify undefined behavior (as the Standard doesn't talk about
segmentation faults). If that situation could be improved (and the point
of this discussion, for me at least, is to see if it can), I for one
would welcome it!

Best regards,

Sidney Cadot
The Netherlands

Hi Mark,

>>Is this 'incorrect behavior' of all these compilers, or is there some
>>wording in the Standard that covers for machines with a finite stack
>>(much to my dismay, this covers all machines I have access to)?

> The C standard sets limits on the size, number and so forth of objects
> that an implementation is required to provide. Infinite recursion, or
> even relatively deep recursion, tends to break them. See 5.2.4 of the
> Standard.

I've just browsed 5.2.4 of the Committee Draft dated August 3, 1998
(it's Saturday night after all - what else to do?).

5.2.4.1 gives some lower bounds on compile-time constructs a compiler
should be able to handle, and the other subsections give numeric
constraints that should be met.

I honestly see nothing in there that a program using infinite or
relatively deep recursion (such as my example) violates.

Best regards,

Sidney Cadot

Hi Arthur,

>>As for me: If it walks like a stack and talks like a stack, so to say -
>>I'd prefer to call it a stack.

> But lots of non-pedants like to say things like, "automatic variables
> are declared on the stack," or "the function parameters are pushed on
> the stack in reverse order," or things like that -- which are blatantly
> false, given some of the "stack-like" models that [whomever you were
> quoting] demonstrated.

Ok. To clarify my understanding of this: the Standard sets forth a
number of constraints that amount to implementing an (abstract) stack,
that can be /though of/ as something on which things are pushed or
popped. The implementor is free to devise a way to implement this
abstract mechanism any way (s)he chooses.

>>If I understand what you're saying correctly, the standard does not (of
>>course!) force the underlying hardware to support anything stack-like,
>>but the runtime model implies something that can in good faith only be
>>called a stack

> ...or two stacks, or three. Or one three-element "stack" per function
> (giving a maximum recursion depth of 3 calls). Or whatever else the
> implementor comes up with...

Yes. I'm just not happy that the concept of a 'maximum recursion depth'
is brought in without any backing from the Standard.

>>[snip]

>>That's interesting... Based on a literal reading of the standard at
>>least, I'd say my sample program is fully compliant and there's no
>>reason for it ever to not reach the 'return 0' statement.

> Correct. The only reason the program doesn't work is because we
> live in the pesky physical world.

It's a drag, isn't it? I would be happy to see this reflected in the
Standard.

>>To me, perhapse naively, this seems then like a point where the standard
>>is not complete. Anybody care to comment on that point of view?

> Yup. The Standard doesn't give any hint of a min-max recursion depth.
> In practice, I think most compiler systems use sensible recursion
> strategies, limited only by the amount of RAM available. But yes, in
> theory, all C compilers are non-conforming in this regard.

Surely the founding fathers of C99 have considered this issue(?) I
wonder if they couldn't come up with a good formulation, or decided it
was just not worth the effort.

> You might be interested in this old thread: [...]

Thanks, I will go and read this. I used to toy with issues of Turing
completeness of different formal systems so this will make an
interesting read I'm sure.

Best regards,

Sidney Cadot

Hi Mark,

>>>>>[[does the Standard require a stack?]]
>>
>>>The constraints in the standard force "stack-like behavior" for
>>>local variables inside functions (including any parameters), and
>>>I think it is not out of line to call this "a stack". [...]
>>
>>As for me: If it walks like a stack and talks like a stack, so to say -
>>I'd prefer to call it a stack.

> Except that its not. The standard doesn't require, or even force,
> implementations to put variables into a stack. I don't think thats
> what Chris was saying. For example all parameters could be (and even
> on stack based machines generally are) passed via registers. All
> automatics could be created in reserved memory, in no particular
> order.

I think the issue here is to distinguish between something that
/logically/ behaves like a stack, and something that is a classical
stack implementation as supported by many hardware platforms.

Reading Chris' reply I feel that his statement amounted to the effect
that, given the constraints in the Standard, it follows that an
implementation must support something that behaves like a /logical/ stack.

Your example of register based parameter passing hits home for me, as I
did some assembly coding on the PowerPC RISC architecture; parameter
passing by register is the preferred way of working there. However, when
doing recursive function calls where each invocation manages a local
state (dare I say: stack-frame), one is in effect emulating a /logical/
stack.

I'm curious about Chris' opinion on the matter, whether I did correctly
understand his reply.

Best regards,

Sidney Cadot

On Sun, 12 Oct 2003 01:09:01 +0200, in comp.lang.c , Sidney Cadot
<> wrote:

>5.2.4.1 gives some lower bounds on compile-time constructs a compiler
>should be able to handle, and the other subsections give numeric
>constraints that should be met.
>
>I honestly see nothing in there that a program using infinite or
>relatively deep recursion (such as my example) violates.

There are other min and max requirements scattered throughout the
standard as well, but, indeed, its probable that there's nothing to
specifically outlaw infinite recursion. Remember tho the standard is
notionally implemented in a theoretical machine. We live in the Real
World (tm) where infinite memory is not available.

--
Mark McIntyre
CLC FAQ <http://www.eskimo.com/~scs/C-faq/top.html>
CLC readme: <http://www.angelfire.com/ms3/bchambless0/welcome_to_clc.html>


----== Posted via Newsfeed.Com - Unlimited-Uncensored-Secure Usenet News==----
http://www.newsfeed.com The #1 Newsgroup Service in the World! >100,000 Newsgroups
---= 19 East/West-Coast Specialized Servers - Total Privacy via Encryption =---

On Sun, 12 Oct 2003 01:21:39 +0200, in comp.lang.c , Sidney Cadot
<> wrote:

>> But lots of non-pedants like to say things like, "automatic variables
>> are declared on the stack," or "the function parameters are pushed on
>> the stack in reverse order," or things like that -- which are blatantly
>> false, given some of the "stack-like" models that [whomever you were
>> quoting] demonstrated.
>
>Ok. To clarify my understanding of this: the Standard sets forth a
>number of constraints that amount to implementing an (abstract) stack,
>that can be /though of/ as something on which things are pushed or
>popped.

AFAIK No, the standard sets out no constraints that /require/ anything
to be pushed or popped from a stack, or even to amount to doing that.
Thats merely one way to represent what the standard requires which is
that for example copies of the values of the parameters to a function
be made available in the function, or that array members shall appear
to be adjacent in memory.


--
Mark McIntyre
CLC FAQ <http://www.eskimo.com/~scs/C-faq/top.html>
CLC readme: <http://www.angelfire.com/ms3/bchambless0/welcome_to_clc.html>


----== Posted via Newsfeed.Com - Unlimited-Uncensored-Secure Usenet News==----
http://www.newsfeed.com The #1 Newsgroup Service in the World! >100,000 Newsgroups
---= 19 East/West-Coast Specialized Servers - Total Privacy via Encryption =---

On Sun, 12 Oct 2003 01:31:51 +0200, in comp.lang.c , Sidney Cadot
<> wrote:

>I think the issue here is to distinguish between something that
>/logically/ behaves like a stack,

In what way does the standard /REQUIRE/ the logical behaviour of a
stack.

Thats as opposed to "S Cabot needs an internal mental picture of how
function calls etc work, and he finds the idea of a stack easy to
visualise and operate with". No offense intended.

For myself I don't need this mental picture. I think of function
calls, recurnsion and automatics as involving the computer storing
different data in various places, and remembering where it is at the
relevant time.

A bit like me working on something, and using various books from my
bookshelf. I feel no compulsion to make a "stack" of hte ones I need,
pushing the most recently used one to the top, and then popping it off
again when I'm done. I merely pull them off the shelf when needed, and
put 'em back afterwards, generally in much the same place but a few
books to the left or right doesn't matter, I'm no Dewey obsessive.


--
Mark McIntyre
CLC FAQ <http://www.eskimo.com/~scs/C-faq/top.html>
CLC readme: <http://www.angelfire.com/ms3/bchambless0/welcome_to_clc.html>


----== Posted via Newsfeed.Com - Unlimited-Uncensored-Secure Usenet News==----
http://www.newsfeed.com The #1 Newsgroup Service in the World! >100,000 Newsgroups
---= 19 East/West-Coast Specialized Servers - Total Privacy via Encryption =---

Hi Mark,

>>I think the issue here is to distinguish between something that
>>/logically/ behaves like a stack,

> In what way does the standard /REQUIRE/ the logical behaviour of a
> stack.

Well, in a very obvious way really. Actual parameters and local
variables are accessible during execution of a function; they become
inaccessible during a recursive call as the same formal parameters and
local variables now refer to new, independent variables, which cease to
exist upon return from the secondary call to the same function. I think
you will agree that this behavior is prescribed by the standard.

To me at least, this seems equivalent to viewing the set of parameters
and local variables as a tuple; the ordered list of these tuples
associated with recursive invocations of a function, of which only the
current one is accessible, has all the hallmark properties of a stack of
which only the top-most element is accessible at any given time.

> Thats as opposed to "S Cabot needs an internal mental picture of how
> function calls etc work, and he finds the idea of a stack easy to
> visualise and operate with". No offense intended.

None taken, not even for misspelling my name

> For myself I don't need this mental picture. I think of function
> calls, recurnsion and automatics as involving the computer storing
> different data in various places, and remembering where it is at the
> relevant time.

My main argument in this thread is not whether C prescribes a logical
stack or not; for me that's a useful model (so good, in fact, that I
would be interested to see where this model falls apart), and for you it
isn't. That's A-ok by me.

On the risk of committing speculation, I think you would be hard-pressed
to find a compiler implementor who doesn't use the stack as a very
useful model while implementing a C (or any other) compiler.

What I /would/ like to get to is the phenomenon that a seemingly
standard-compliant program can exhibit undefined behavior. There's a
number of explanations (perhaps there are more):

* the standard does in fact cover this case through a specific limit
exceeded (for example) by my small program, and nobody mentioned
it so far in this thread.
* the standard does in fact cover this case, as it presumes an
idealized machine where certain practical constraints do not
hold (I'd welcome a clear reference).
* the standard does not cover this case.

Presuming for the moment that the third case is what's going on, I think
it is a worthwile exercise to ponder if/how the standard could be
amended in such a way as to cover this case. Stack overflow (perhaps
'resource depletion due to many nested function calls' is a better, but
clumsier term), in my opinion, is a phenomenon that is important enough
to deserve mention in the standard. I would be interested to know if
people disagree with this.

> A bit like me working on something, and using various books from my
> bookshelf. I feel no compulsion to make a "stack" of hte ones I need,
> pushing the most recently used one to the top, and then popping it off
> again when I'm done. I merely pull them off the shelf when needed, and
> put 'em back afterwards, generally in much the same place but a few
> books to the left or right doesn't matter, I'm no Dewey obsessive.

But then, you're not a running C program which, I hope, exhibits a level
of neurotic-obsessive behavior that would make a clinical psychiatrist
dance with joy.

Best regards,

Sidney Cadot