why does this work ?

[Chris Torek]

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.

Yes. Any queue data structure with last-in-first-out and "top
entry is visible" can be called a "stack", and the values of
variables within a function activation fit this description.

The main problem with saying that local variables are "on the
stack", or even "on a stack", is that people may -- and do in
practice -- draw invalid (in the general case, at least) conclusions
from this wording. We might safely say "local variables participate
in a stack discipline" or "behave in a stack-like manner", but at
that point the meaning may no longer be clear to the reader.

 

[CBFalconer]

In a technical sense, at least, and it *does* matter sometimes.

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". But one
should remember that this "stack" may well be implemented as,
e.g., a linked list of frames:

I just came up with a new system that can confuse many programs
that take liberties.

Assuming that byte, short, int, long are all an increasing size,
i.e. 1,2,4,8, and that we can fit float and double in there, lets
have a machine with 4 separate stacks, separated by size.

We can also have an assortment of sized registers, each of which
represents the top of a stack of items of its own size.

I think it would be a feasible machine. Might be a good basis for
the DS9000.

 

[newsgroup]

Message-ID: <[email protected]>
Subject: Re: why does this work ?
From: Sidney Cadot <[email protected]>
Newsgroups: comp.lang.c
Date: Sun, 12 Oct 2003 03:16:36 +0200

Hi Mark,



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.


None taken, not even for misspelling my name ;-)


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.


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

 

[Bjoern Pedersen]

* 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).

I would vote for this one, as you are exceeding the required minimum
number of objects with your recursive calls ( you have one auto
variable per call, where the lifetime ends on return of the function.)


Björn

 

[Mark McIntyre]

Hi Mark,



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.

it is, but its not necessary for a stack to be used either literally
or logically to achieve this. I have a ladder to access the top shelf
of my books. When I'm pulling down Sci Fi books, I can't access my C
books, and vice versa. But I still don't have a stack of books with
LIFO type behaviour.

To me at least, this seems equivalent to viewing the set of parameters
and local variables as a tuple;

sure, you can regard it that way, its your mindset. I'm just trying to
make clear that the standard doesn't require you to think of it like
that, or implementors to implement it thus

My main argument in this thread is not whether C prescribes a logical
stack or not;

IMHO it does not.

for me that's a useful model

Thats ok with me. I don't feel the need to have it.

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.

I suspect this discussion is now well into the realm of
comp.compilers. Perhaps you should continue it over there?

 

[Sidney Cadot]

Hi Mark,

[snip]

My main argument in this thread is not whether C prescribes a logical
stack or not;

IMHO it does not.

for me that's a useful model

Thats ok with me. I don't feel the need to have it.

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.

I suspect this discussion is now well into the realm of
comp.compilers. Perhaps you should continue it over there?

As stated, my main argument in this thread is not whether C prescribes a
logical stack or not; rather, it is to find out if stack overflows are
covered by the standard, one way or another.

We differ on whether we feel the need to internalize the C runtime model
as a stack; I'm comfortable with that, as are you. Let's just keep it at
that and move on to more interesting matters.

Best regards,

Sidney Cadot

 

[Sidney Cadot]

Hi Björn,

I would vote for this one, as you are exceeding the required minimum
number of objects with your recursive calls ( you have one auto
variable per call, where the lifetime ends on return of the function.)

I am not aware of a requirement in the Standard that prescribes a
minimum number of active objects that an implementation must support
(where 'object' includes things like parameters and automatic
variables). Do you have a reference?

For sure, if there is one, the sample program may well exceed it at some
point. I, for one, would be quite satisfied if you are right.

Best regards,

Sidney Cadot

 

[Bjoern Pedersen]

I am not aware of a requirement in the Standard that prescribes a
minimum number of active objects that an implementation must support
(where 'object' includes things like parameters and automatic
variables). Do you have a reference?

That's the Translation Limits section. I don't have the standard at
hand, but it should be around 5.2.4.1 (see post from C. Torek
upthread). Maybe some of the language lawyers here can give a better
reference.

Björn

 

[Irrwahn Grausewitz]

That's the Translation Limits section. I don't have the standard at
hand, but it should be around 5.2.4.1 (see post from C. Torek
upthread).

I cannot find anything in or around ISO/IEC 9899:1999 5.2.4.1 that
addressess the mentioned problem. This is the part from Chris Torek's
post you are probably referring to:

SC: ... is there a minimum depth of function calls that I can rely on
SC: to be executed properly? ...

CT: I have never found one. The "Translation limits" section (at or
CT: near 5.2.4.1) is the logical place for something like "at least N
CT: function activations down from the initial call to main()", but
CT: there is no such wording. On the other hand, that section is not
CT: a good weapon against Evil Compilers, as it requires only that an
CT: implementation "translate and execute ... one program" that tests
CT: those limits.

Maybe some of the language lawyers here can give a better reference.

Regards

 

[Bjoern Pedersen]

SC: ... is there a minimum depth of function calls that I can rely on
SC: to be executed properly? ...

The problem I addressed was the number of objects allocated by the
example ( it had a local auto variable). This is covered by the normal
allocation limits. A function not allocating anything (i.e. no locals,
no parameters) colud probabaly be called indefinitly.

Björn

 

[Irrwahn Grausewitz]

The problem I addressed was the number of objects allocated by the
example ( it had a local auto variable). This is covered by the normal
allocation limits.

Ah, I see, but still I can't find anything in the standard that imposes
such a limit; but of course I'm neither a C expert nor a "language
lawyer".

A function not allocating anything (i.e. no locals,
no parameters) colud probabaly be called indefinitly.

[ ITYM infinitely ^^^^^^^^^^^ ]

I don't think so, because even with a function not containing automatic
variables at least the return address has to be stored somewhere (in
RealWorld[tm] implementations without magic).

Hm, thinking further, I imagine a compiler that completely optimizes
away such code, but then actually no calls take place at all .....
well, it's of no pratical use anyway.

Regards

 

[Mark McIntyre]

As stated, my main argument in this thread is not whether C prescribes a
logical stack or not; rather, it is to find out if stack overflows are
covered by the standard, one way or another.

fair enough. In that case, the answer is probably "no".

 

[CBFalconer]

.... snip ...

[ ITYM infinitely ^^^^^^^^^^^ ]

I think he meant indefinitely. It's idiomatic for as many times
as you like. Just a minor spelling error.

 

[Irrwahn Grausewitz]

... snip ...

[ ITYM infinitely ^^^^^^^^^^^ ]

I think he meant indefinitely. It's idiomatic for as many times
as you like. Just a minor spelling error.

Hm, maybe I have to update my English dictionary.

From Oxford Advanced Learner's, 3rd edition (1974!):

in-defi-nite /adj/ vague; not clearly defined or stated [...]
the ~ article, /a or an/. ~-ly /adv/

in-fi-nite /adj/ endless; without limits; that cannot be
measured, calculated or imagined [...] ~-ly /adv/

Maybe I get something totally wrong here, or my English is just
too bad. Dunno.

Regards

 

[Micah Cowan]

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.

Only a C implementation for a genuine Turing machine could handle
infinite recursion.

The above statement isn't actually *quite* true. According to the
as-if rule, an implementation could rewrite recursive code to be
iterative; and since all recursive algorithms are equivalent to
at least one iterative algorithm, this could be done for all
recursive calls. However, this would require an *extremely*
intelligent implementation; and, in the case of indirect
recursion between functions defined in separate translation
units, might require that the actual *object* code (assuming its
a compiler or whatnot) be rewritten. Even then, there are
certainly many examples of recursive functions which cannot be
implemented without some sort of stack that grows to some degree
with each new call, so still not all infinite recursions could be
handled.

-Micah

 

[Arthur J. O'Dwyer]

A function not allocating anything (i.e. no locals,
no parameters) colud probabaly be called indefinitly.

[ ITYM infinitely ^^^^^^^^^^^ ]

I think he meant indefinitely. It's idiomatic for as many times
as you like. Just a minor spelling error.

Hm, maybe I have to update my English dictionary.

Not really; but remember that English (and other languages, too)
can leave out a lot of non-essential words. For "indefinitely,"
read "an indefinite number of times" -- i.e., a number of times
which could be indefinitely (arbitrarily) large.

-Arthur

 

[Arthur J. O'Dwyer]

That's the Translation Limits section. I don't have the standard at
hand, but it should be around 5.2.4.1 (see post from C. Torek
upthread). Maybe some of the language lawyers here can give a better
reference.

Nope, because there is no such reference.
The closest 5.2.4 comes is saying that an implementation
must support at least one 65535-byte object; but nothing is
said about supporting (or not supporting) millions of 1-byte
objects -- especially, as in this case, millions of objects
of which only one is accessible at any one time.

(Again, this has been done to death in the early stages of
the threads I posted earlier.)

-Arthur

 

[Irrwahn Grausewitz]

Irrwahn Grausewitz wrote:

A function not allocating anything (i.e. no locals,
no parameters) colud probabaly be called indefinitly.
[ ITYM infinitely ^^^^^^^^^^^ ]

I think he meant indefinitely. It's idiomatic for as many times
as you like. Just a minor spelling error.

Hm, maybe I have to update my English dictionary.

Not really; but remember that English (and other languages, too)
can leave out a lot of non-essential words. For "indefinitely,"
read "an indefinite number of times" -- i.e., a number of times
which could be indefinitely (arbitrarily) large.

Thanks. C.l.c seems to be a good place to brush up both
one's C and English knowledge.

Irrwahn

 

[CBFalconer]

.... snip ...

Only a C implementation for a genuine Turing machine could handle
infinite recursion.

The above statement isn't actually *quite* true. According to the
as-if rule, an implementation could rewrite recursive code to be
iterative; and since all recursive algorithms are equivalent to
at least one iterative algorithm, this could be done for all
recursive calls. However, this would require an *extremely*

No it can't. Only for some particular forms of recursive
functions. Where are you going to put the local storage for that
recursive function? Conversion of recursive arbitrary functions
requires an auxiliary stack.

 

[Sidney Cadot]

Hi Micah,

Only a C implementation for a genuine Turing machine could handle
infinite recursion.

The above statement isn't actually *quite* true. According to the
as-if rule, an implementation could rewrite recursive code to be
iterative; and since all recursive algorithms are equivalent to
at least one iterative algorithm, this could be done for all
recursive calls. [...]

Memory serving, this is true only for so-called 'primitive recursive'
functions; a counterexample is the Ackermann function:

int ackermann(int x, int y)
{
return (x==0) ? y+1 : (y==0) ? ackermann(x-1,1) :
ackermann(x-1,ackermann(x,y-1));
}

Best regards, Sidney Cadot