Why are variables stored on the stack?

[santosh]

Keith Thompson wrote:

C (the language, not any particular implementation) does not insist on
the use of a contiguous hardware stack, though that's the most common
implementation.

Are we in agreement?

I think Jacob does agree with you on this point. It's just that some
(many?) people set more weightage by real world practises and actual
implementations than a mere document.

The best way is for both (standards and implementations) to be given due
importance. A large tilt either side could mean either a failed
standard (sounds familiar) or such a plethora of incompatible
implementations that attempting to standardise is probably a lost cause
(BASIC).

 

[CBFalconer]

.... snip ...

This is wrong. All mainframe implementations use a contiguous
memory area that is accessed by a dedicated register. This
register is increased in the function's prologue and decreased
in the functions epilogue. The machine has no universally
dedicated stack registers but within C it HAS A STACK as I
proved with links to the mainframe's compiler documentation A
NUMBER OF TIMES ALREADY

Please look it up and stop telling stories.

No, you have proved nothing. If you can quote a section of any C
standard that insists on a stack, you will get many craven
apologies. I doubt that will occur.

 

[Thad Smith]

If an implementation uses static allocation for all local objects,
then it can't support recursion, and therefore can't be a conforming C
implementation. (It could be a very useful implementation that
doesn't fully conform to the C standard.)

You are, of course, correct. I suppose I should call it a non-recursive
subset of C. ;-)

And yes, these compilers are very useful.

 

[CBFalconer]

.... snip ...

Now to your question. The standard says:
--------------------------------------------------------------
An object whose identifier is declared with no linkage and without
the storage-class specifier static has automatic storage duration.

5 For such an object that does not have a variable length array
type, its lifetime extends from entry into the block with which
it is associated until execution of that block ends in any way.
(Entering an enclosed block or calling a function suspends, but
does not end, execution of the current block.) If the block is
entered recursively, a new instance of the object is created
each time.
------------------------------------------------------------

This is conceptually a stack. There is the PUSH operation (a new
scope) a POP operation (a scope ends, and restores the previous
scope). Obviously you can implement a stack in many ways, but
MOST serious implementations of C use the hardware stack.

If there is a hardware stack, it is likely. Not guaranteed. For
example, take the IBM360. IIRC a function call there uses a
dedicated register to point to a storage area. If the function
calls something else, it has to get another storage area. This IS
NOT A STACK.

The point is that NO STACK IS GUARANTEED by the C standard. It is
not necessary. It may be convenient. "Conceptually a stack" is
not "a stack". Some men look at a sheep, or another man, and say
"Conceptually, that to me is a woman". It is not. It is insulting
to at least one of men, women, and sheep.

 

[jacob navia]

"MOST" implies "NOT ALL", doesn't it?


No, I agree with you on this point, and I think everyone else does as
well.

Most implementations of C use a hardware stack.

Not all implementations of C use a hardware stack.

C (the language, not any particular implementation) does not insist on
the use of a contiguous hardware stack, though that's the most common
implementation.

Are we in agreement?

Yes.


But it would be better if the regulars would not answer
simple queries with blunt posting like

"C has no stack"

"C defines no stack"

or similar.

 

[CBFalconer]

It is perfectly correct. You should update your reading skills.
C does not ***INSIST*** on storing local variables on the stack.

'Insist' is something that can be said of requirements and/or
standards. It is *not* something you say of an *implementation*.

Try: int register foo;

and tell me where that is likely to be stored.

 

[CBFalconer]

A stack is O(1) to allocate a chunk, and chunk sizes can be
variable. O(N) to fill the chunk with useful data, where N is
chunk size. A heap is O( f(N) ) to allocate a chunk, where f(N)
is some complex and platform dependent function of the number of
chunks allocated. Typically it will be about logarithmic,
certainly under N. You can look up broken stick distributions
and the like if you are interested in problems of fragmentation
and how they impact on block search.

A heap is O(N) to fill with useful data, where N is the chunk
size.

So you are not really correct, unless chunk size is very large
in comparision to the number of blocks allocated, in which case
that term will dominate.

You are in error about heaps. For an example where all calls to
malloc, realloc, free are O(1) see nmalloc.zip, available at:

<http://cbfalconer.home.att.net/download/>

 

[Richard Heathfield]

Keith Thompson said:

C does insist on a "stack" in the sense of last-in first-out
allocation for local objects across function calls.

No, it doesn't. All auto objects defined within a given block die at the
same time, and the Standard doesn't specify in which order they must be
killed. Neither does the Standard require that they be defined in any
particular order, provided the behaviour is correct. Thus, if the code
reads: int a; double b; then the Standard doesn't give two hoots about
which is allocated first. If it's int a = 5, b = a; that's a slightly
different matter, although not much.

A hash table would do it. You certainly don't need a stack.

 

[CBFalconer]

Keith Thompson wrote:
.... snip ...

Progress.


But it would be better if the regulars would not answer
simple queries with blunt posting like

"C has no stack"
"C defines no stack"

or similar.

Which you immediately threw away by this false statement.

 

[Geoff]

CJ wrote:

This problem is not unique to C. It is a function of how any stack is
used to store temporary variables and what kinds of data can be placed
in them and where the data comes from. Securely coded and tested C
programs won't fail this way. Improperly coded programs can fail no
matter what source language is used unless that language is
implemented in a way that prevents these kinds of errors.

Only if you can execute code in the stack

Which is precisely what makes the stack vulnerable to exploitation.
Most stack-oriented implementations store the return address of the
caller on the stack. Overflow the stack and you can make the program
execute arbitrary code. This is what makes the stack vulnerable. On
the x86, this is a problem. On Modified Harvard Architecture machines
it would not be a problem since the code space cannot be modified and
smashing a stack on them would most likely simply crash the system.
While this is a DoS on such a system, it can't be used to execute
arbitrary code.

Nothing in the standard "requires" a stack. Very few x86
implementations (if any) don't use a stack but this is not because the
standard requires it. Stacks, and what they can be used for is a
function of the target processor, not C. Most processors have a stack
pointer and associated PUSH and POP instructions that make storing
program counters and variables onto the stack easier and faster than
using another mechanism but this is not unique to C or to the C
standard. Other computer languages can and do use the stack if it
outperforms other methods of storing temporary variables or return
addresses.

 

[Keith Thompson]

Yes.

Then what in the world have you been arguing about?

But it would be better if the regulars would not answer
simple queries with blunt posting like

"C has no stack"

"C defines no stack"

or similar.

The question was "Why does C insist on storing local variables on the
stack in the first place?"

The response that it doesn't (from several people) was perfectly
correct.

You insisted that this correct response was wrong. And that is what
led to this entire wasteful argument.

 

[Keith Thompson]

If there is a hardware stack, it is likely. Not guaranteed. For
example, take the IBM360. IIRC a function call there uses a
dedicated register to point to a storage area. If the function
calls something else, it has to get another storage area. This IS
NOT A STACK.

Yes, it is, in the sense that the word "stack" (as has been pointed
out many many times) can refer to the abstraction of a last-in
first-out data structure.

Suppose I write a program or library that implements last-in first-out
data structure, with "push" and "pop" operations, using a linked list.
Am I not allowed to call that a "stack"?

The point is that NO STACK IS GUARANTEED by the C standard. It is
not necessary. It may be convenient. "Conceptually a stack" is
not "a stack". Some men look at a sheep, or another man, and say
"Conceptually, that to me is a woman". It is not. It is insulting
to at least one of men, women, and sheep.

You, like jacob, are ignoring the fact the word "stack" has more than
one meaning.

C does require a last-in first-out data structure of some kind to
implement local variables; this can reasonably be called "a stack".
It does not require (but most implementations use) a contiguous
hardware stack, sometimes referred to as "the stack". Can we all
agree on that?

 

[Keith Thompson]

Keith Thompson said:



No, it doesn't. All auto objects defined within a given block die at the
same time, and the Standard doesn't specify in which order they must be
killed. Neither does the Standard require that they be defined in any
particular order, provided the behaviour is correct. Thus, if the code
reads: int a; double b; then the Standard doesn't give two hoots about
which is allocated first. If it's int a = 5, b = a; that's a slightly
different matter, although not much.

A hash table would do it. You certainly don't need a stack.

Certainly the standard doesn't care about the order of allocation of
objects declared within the same block; I didn't mean to imply that it
does. Typically they're allocated simultaneously (e.g., if a block
declares 2 4-byte ints, they're likely to be allocated as a single
8-byte chunk).

The unit of allocation is a collection of automatic objects declared
in a particular scope. That collection is conceptually created in
what can be thought of as a single "push" operation, and destroyed in
what can be thought of as a single "pop" operation. In that sense,
the language rules do imply a stack (an abstract last-in first-out
data structure, however it's implemented).

 

[santosh]

Keith Thompson wrote:

C does require a last-in first-out data structure of some kind to
implement local variables;

Shadowing of an object in an outer scope by another of the same name in
an inner scope seems to imply a LIFO.

this can reasonably be called "a stack".
It does not require (but most implementations use) a contiguous
hardware stack, sometimes referred to as "the stack". Can we all
agree on that?

Yes.

 

[jacob navia]

[...]
Obviously you can implement a stack in many ways, but MOST serious
implementations of C use the hardware stack.
"MOST" implies "NOT ALL", doesn't it?

This is SO OBVIOUS that it needs the twisted "regulars" mentality to
deny it.
No, I agree with you on this point, and I think everyone else does as
well.

Most implementations of C use a hardware stack.

Not all implementations of C use a hardware stack.

C (the language, not any particular implementation) does not insist on
the use of a contiguous hardware stack, though that's the most common
implementation.

Are we in agreement?

Yes.

Then what in the world have you been arguing about?

But it would be better if the regulars would not answer
simple queries with blunt posting like

"C has no stack"

"C defines no stack"

or similar.

The question was "Why does C insist on storing local variables on the
stack in the first place?"

The response that it doesn't (from several people) was perfectly
correct.

You insisted that this correct response was wrong. And that is what
led to this entire wasteful argument.

Yes, discussing with you and falconer is a waste of time
You just say

"C has no stack"

without explaining anything, just throwing remarks that even if
they are "right" in a pedantic sense, they are wrong in the
common usage of language

 

[Ben Bacarisse]

Keith Thompson said:



No, it doesn't. All auto objects defined within a given block die at the
same time, and the Standard doesn't specify in which order they must be
killed. Neither does the Standard require that they be defined in any
particular order, provided the behaviour is correct. Thus, if the code
reads: int a; double b; then the Standard doesn't give two hoots about
which is allocated first. If it's int a = 5, b = a; that's a slightly
different matter, although not much.

Keith Thompson said "across function calls" not "within a block". The
implicit LIFO allocation is in the nesting of the lifetimes of auto
variables across a call:

void g(void) {
int a, b, c;
f(); /* all f's auto variables start life after a, b and c exist */
/* and they must end their life before any of a, b or c do */
}

As Keith pointed out, this can all be managed with a simple static
block for each function (as early FORTRAN compilers often used)
provided that no function call chain contain a cycle. Without that
assurance, some form of stacking is the obvious solution.

A hash table would do it. You certainly don't need a stack.

Yes, but again, the obvious solution is a hash table where collisions
are handled with a linked list so when g() calls f() which calls g()
the old bindings for a, b and c get "pushed".

Note that I say "obvious". I think it is possible to construct a
contrived but conforming implementation in which there is almost no
identifiable LIFO structure (it will still be there in ghostly
form due to the wording of the standard). I'll outline it for
variables in functions, but it needs to be extended to nested blocks
as well.

Every function starts with code that collects the time from a counter
(maybe click ticks). This value is concatenated with the variable
name to make a hash key. In g() above, an assignment 'a = 42;' will
lookup a@234 if the call to g started at cycle 234. Functions save
their return address in a special variable so, when g() calls f() at
cycle 336 a variable RETURN-FROM@336 holds the location in g() where
f() was called from, and all of f()'s auto variables will have the
form <name>@336.

A special variable (hash key), CURRENT-CALL-CYCLE, stores the cycle
the current call stated on. This means that to find a variable we
construct sprintf("%s@%d", var_name, lookup("CURRENT-CALL-CYCLE"))
and look that up.

So far, no LIFO in sight -- not even in the return addresses. But all
good things must come to an end. When the call to f() at cycle 336
returns, control is passed to the location in RETURN-FROM@336. There
the compiler had planted code to set CURRENT-CALL-CYCLE back to 234.
(This requires a writable code segment but, hey, we are in fantasy
land here so does it matter if we do that too? An extra variable can
avoid any writable code, but it make the LIFO nature of the storage
scheme more obvious so I've not used it.)

It is very hard to see the LIFO structure here. It *is* there, of
course, in the odd variable names and ever-changing numbers in the
code stream, but it is there only in a ghostly way. I doubt, though,
that anyone could call this a stack.

 

[Ian Collins]

Yes, discussing with you and falconer is a waste of time
You just say

"C has no stack"

Come on then, put up or shut up, where did Keith say that?

 

[Rod Pemberton]

jacob navia said:


The OP.


Well, *you* are. The rest of us are actually addressing the OP's question,
by discussing what the C Standard actually requires. The OP asked "Why
does C insist on storing local variables on the stack in the first
place?", to which the proper answer is that it does not.

Richard,

How so? How is the OP's usage of "insist" any different from Ritchie's
usage of "suggest strongly"? Ritchie said the exactly same thing that the
OP asked. So, how can you claim the OP is wrong without proclaiming Ritchie
was wrong also?

"Any function in C may be recursive (without special declaration) and most
possess several 'automatic' variables local to each invocation. These
characteristics suggest strongly that a stack must be used to store the
automatic variables, caller's return point, and saved registers local to
each function; in turn, the attractiveness of an implementation will depend
heavily on the ease with which a stack can be maintained."

"Portability of C Programs and the UNIX System" SC Johnson and DM Ritchie
http://cm.bell-labs.com/cm/cs/who/dmr/portpap.html


Rod Pemberton

 

[Rod Pemberton]

The question was "Why does C insist on storing local variables on the
stack in the first place?"

The response that it doesn't (from several people) was perfectly
correct.

Keith,

How so? How is the OP's usage of "insist" any different from Ritchie's
usage of "suggest strongly"? Ritchie said the exactly same thing that the
OP asked. So, how can you claim the OP is wrong without proclaiming Ritchie
was wrong also?

"Any function in C may be recursive (without special declaration) and most
possess several 'automatic' variables local to each invocation. These
characteristics suggest strongly that a stack must be used to store the
automatic variables, caller's return point, and saved registers local to
each function; in turn, the attractiveness of an implementation will depend
heavily on the ease with which a stack can be maintained."

"Portability of C Programs and the UNIX System" SC Johnson and DM Ritchie
http://cm.bell-labs.com/cm/cs/who/dmr/portpap.html


Rod Pemberton

 

[jacob navia]

Richard,

How so? How is the OP's usage of "insist" any different from Ritchie's
usage of "suggest strongly"? Ritchie said the exactly same thing that the
OP asked. So, how can you claim the OP is wrong without proclaiming Ritchie
was wrong also?

"Any function in C may be recursive (without special declaration) and most
possess several 'automatic' variables local to each invocation. These
characteristics suggest strongly that a stack must be used to store the
automatic variables, caller's return point, and saved registers local to
each function; in turn, the attractiveness of an implementation will depend
heavily on the ease with which a stack can be maintained."

"Portability of C Programs and the UNIX System" SC Johnson and DM Ritchie
http://cm.bell-labs.com/cm/cs/who/dmr/portpap.html


Rod Pemberton

It is hopeless. They just not listen to any arguments and will
go on repeating "The standard mentions no stack".