Why are variables stored on the stack?

J

jacob navia

Ian said:
Please look up the word "stack" in the standard and tell us where it occurs.

1: I said that no example of a C implementation without a stack has been
put forward by the regulars.
2: K. Thompson said that mainframes do not have a stack.
3: I proved him wrong using the documentation of the mainframe
compilers.

And now you say:
Please look up the word "stack" in the standard and tell us where it occurs.

You *ignore* the whole argumentation and just throw a sentence
again, without any context.

The word "stack" doesn't appear in the standard. It is implied.
The word "computer" doesn't appear. It is implied.
The word "programmer" doesn't appear. It is implied.

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.

This is SO OBVIOUS that it needs the twisted "regulars" mentality to
deny it.
 
S

santosh

jacob said:
1: I said that no example of a C implementation without a stack has
been
put forward by the regulars.

Hasn't Jack Klein mentioned the 8051 already?

Other examples were mentioned in the past including a TI series
processor and something, IIRC, that Dik T. Winter mentioned.
2: K. Thompson said that mainframes do not have a stack.

No. He said that a particular mainframe used the heap for auto
variables.

If you twist words like this, no wonder that some posters give them
right back at you.
3: I proved him wrong using the documentation of the mainframe
compilers.

Was the documentation for the exact machine that Keith mentioned? Is
the "stack" that's mentioned in the documentation a hardware supported
one?
And now you say:
Please look up the word "stack" in the standard and tell us where it
occurs.

You *ignore* the whole argumentation and just throw a sentence
again, without any context.

The word "stack" doesn't appear in the standard. It is implied.
The word "computer" doesn't appear. It is implied.
The word "programmer" doesn't appear. It is implied.

The word computer I agree is implied, but I don't see how "stack"
and "programmer" are implied. The standard specifies explicitly it's
constraints. Anything that is implied can probably done by several
methods and no one is better than the others.
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.

You are yourself admitting here that only *most* C implementations use a
hardware stack, not all. Thank you. Maybe we can end this boring
discussion now.

As I said before, C's auto objects strongly model a conceptual stack,
but the actual implementation needn't use a hardware stack.

<snip>
 
R

Richard

santosh said:
Hasn't Jack Klein mentioned the 8051 already?

Other examples were mentioned in the past including a TI series
processor and something, IIRC, that Dik T. Winter mentioned.

And this is important to C programmers who come here for help who
program 99.9999% of the worlds Computers how?
No. He said that a particular mainframe used the heap for auto
variables.

If you twist words like this, no wonder that some posters give them
right back at you.

An OBN for you Santosh. It seems no matter how petty or ridiculous
Collins or the other "regs" get you are always there to back them up.
Was the documentation for the exact machine that Keith mentioned? Is
the "stack" that's mentioned in the documentation a hardware supported
one?

Who cares? Let the specialist worry about that.
The word computer I agree is implied, but I don't see how "stack"
and "programmer" are implied. The standard specifies explicitly it's

You dont think a stack implied?

A "stack" can be anything ....
constraints. Anything that is implied can probably done by several
methods and no one is better than the others.


You are yourself admitting here that only *most* C implementations use a
hardware stack, not all. Thank you. Maybe we can end this boring
discussion now.

As I said before, C's auto objects strongly model a conceptual stack,
but the actual implementation needn't use a hardware stack.

Yawn. Do you have nothing better to do that play silly word games. Real
programmers think of a stack in nearly ALL C implementations. No one
cares about Keith's rusty mainframe. Keep it real!
 
J

jacob navia

santosh said:
Hasn't Jack Klein mentioned the 8051 already?

Maybe he has mentioned but... BAD LUCK FOR YOU.

The 8051 HAS a hardware stack. See the PUSH and POP
instructions in
http://www.atmel.com/dyn/resources/prod_documents/DOC4316.PDF
The compilers can use the internal stack or
an external stack.
Other examples were mentioned in the past including a TI series
processor and something, IIRC, that Dik T. Winter mentioned.


No. He said that a particular mainframe used the heap for auto
variables.

It allocated the stack from the heap. THEN it is used as a
normal hardware stack with a dedicated register to hold the
stack pointer!
If you twist words like this, no wonder that some posters give them
right back at you.

I did not "twist" anything
Was the documentation for the exact machine that Keith mentioned? Is
the "stack" that's mentioned in the documentation a hardware supported
one?

Both yes
 
F

Flash Gordon

CJ wrote, On 15/03/08 10:24:
Thanks for all the replies, this is an interesting discussion.

Here are a couple of points that occur to me:

1) Buffer overflows are a more serious security problem on the stack
than on the heap, because the program counter is stored on the stack and
not the heap, so that a malicious stack overflow can execute arbitrary
code. The heap is used for data exclusively, which is what I meant by
"separate data from executable code".

This can be sorted by separate stacks for return addresses and data as I
stated in my response.
Even if a buffer on the heap overflows, the worst that can happen is
some (probably insignificant) data corruption. Since malloc() generally
allocates space in powers of 2, often an off-by-one error or similar
won't overwrite anything anyway, but will just land in the gap between
the end of the buffer and the next power of 2.

You obviously do not have much experience. Off by one errors on the heap
have been the cause of many a malloc/free crash.
2) I believe the argument about it being more efficient to use the stack
than the heap is spurious - if I recall, both are O(N) data structures.

Allocating space on a hardware stack is normally a single instruction
acting in a fixed small number of clock cycles (1 cycle on a number of
processors), same for deallocating. Allocating space on the heap
involves hunting for space. Repeated allocation/deallocation of memory
often leads to memory fragmentation (especially if the program is
explicitly allocating space with malloc as well) which further increases
the time involved in malloc/free cycles and the risk of an allocation
failure even if there is space available. In short, calling malloc/free
is likely to be a minimum of an order of magnitude slower that
allocating space on the stack, and often several orders of magnitude slower.
 
H

Harald van Dijk

Keith said:
jacob navia said:
I have yet to see a SINGLE example of an implementation that doesn't
use a stack for the local variables. Yes, a single one.

Until now, there wasn't any that the regulars could put forward.

(Obviously in machines running now, and having a certain minimum size.
Coffee machines with less than 1K of RAM and similars do not count)

For the umpteenth time, it depends on what you mean by "stack".
[...] If you mean
a typical contiguous hardware stack managed via a stack pointer, at
least one example of an implementation that *doesn't* use such a thing
has been mentioned here many times, namely an IBM mainframe system that
allocates function activation records on the heap (or something
similar).

This is wrong. All mainframe implementations use a contiguous memory
area that is accessed by a dedicated register.

It is accessed by a dedicated register, but it is not a contiguous memory
area.
This register is
increased in the function's prologue and decreased in the functions
epilogue.

This register is modified in the function's prologue and restored in the
function's 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

You've been told why you're wrong, too. You responded to Keith Thompson's
assumption that by stack, you mean "a typical contiguous hardware stack
managed via a stack pointer", which the system described doesn't have. It
manages auto objects via a linked list.

If you want to call that a stack, then he also addressed that, by first
agreeing with you that C requires a stack, and then pointing out that
your use of the word "stack" differs from the OP's.
Please look it up and stop telling stories.

Please try to read and understand the replies you receive. This has been
pointed out to you before.

[ Disclaimer: like you, I have never worked with the mentioned system. ]
 
H

Harald van Dijk

Thanks for all the replies, this is an interesting discussion.

Here are a couple of points that occur to me:

1) Buffer overflows are a more serious security problem on the stack
than on the heap, because the program counter is stored on the stack and
not the heap, so that a malicious stack overflow can execute arbitrary
code. The heap is used for data exclusively, which is what I meant by
"separate data from executable code".

Actually, some programs do put executable code in malloc'ed storage, and
use equally system-specific tricks to make sure that storage becomes
executable. Look up libffi, for example, if you're interested.
 
J

jacob navia

Jack said:
Not on most C compilers for 8051 architecture.

This is not true
1) The 8051 supports PUSH/POP instructions
2) It can use either an internal or an external stack
As has been said to death, C does not. Quite a few C compilers
specifically do not.

This is not true. Till now, there are no C implementations
without some form of stack, and a stack pointer.
I know of at least one architecture where it is
quite impossible, as the stack is completely inaccessible to
instructions other than call and return.

Who cares?

We are speaking about mainstream implementations here.
I think I can see two definite disadvantages with people pontificating
about subjects in which they have insufficient. Deducing what they
are is left as an exercise to the reader.


Solving your exercise. You are the first one that doesn't know what
you are talking about.

Revise the specs for the 8051.
http://www.atmel.com/dyn/resources/prod_documents/DOC4316.PDF

And the small device C compiler can use an external stack, to
make for the small size of the built-in stack.
 
R

Richard Heathfield

jacob navia said:
Jack Klein wrote:


Who cares?

The OP.
We are speaking about mainstream implementations here.

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.

I do not expect you to understand this. I wish I did.
 
S

santosh

Richard said:
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.

I do not expect you to understand this. I wish I did.

I can't imagine why jacob is so stuck up on this issue. Yes, we all know
that the majority (perhaps even a vast majority) of C implementations
use a hardware enabled stack. But majority is not all!

And in any case there is no *requirement* in the C standard that auto
variables be allocated on a stack (hardware or not). Yes, their model
strongly suggests using a LIFO structure, but this not, as far as I can
see, absolutely necessary.

Why can't jacob just admit this point, so that we can stop these
periodic redundant discussions? No one is, AFAIK, saying a stack isn't
commonly used, nor that it is not suitable.
 
R

Richard

santosh said:
I can't imagine why jacob is so stuck up on this issue. Yes, we all know
that the majority (perhaps even a vast majority) of C implementations
use a hardware enabled stack. But majority is not all!

And in any case there is no *requirement* in the C standard that auto
variables be allocated on a stack (hardware or not). Yes, their model
strongly suggests using a LIFO structure, but this not, as far as I can
see, absolutely necessary.

Why can't jacob just admit this point, so that we can stop these
periodic redundant discussions? No one is, AFAIK, saying a stack isn't
commonly used, nor that it is not suitable.

Change the record Santosh. It's important because the concept of a stack
makes explaining C much, much easier. And as previously discussed the
concept of a stack (and its physical presence) is of paramount
importance in the REAL WORLD where REAL people use REAL debuggers in
order to debug REAL LIFE PROBLEMS. Not all of us fix programs from
reading a 6 foot high printout ....
 
B

Bartc

santosh said:
Hasn't Jack Klein mentioned the 8051 already?

It's quite an achievement to have created a language Standard that works
even on these lowly processors, but surely it would have been better to
split the language into two?

Then the low-level C can go to town on all the features relevant to those
platforms.

And the high-level C can finally be unconstrained.

And if someone really wants to write 8051 code that also runs on the lastest
64-bit processors, or vice-versa, I'm sure there can be a common subset.

I remember using the 8051 (or was it 8031?) and is was a welcome relief to
get back to the Z80, which seemed like a supercomputer in comparison.
 
S

santosh

Richard said:
santosh said:
I can't imagine why jacob is so stuck up on this issue. Yes, we all
know that the majority (perhaps even a vast majority) of C
implementations use a hardware enabled stack. But majority is not
all!

And in any case there is no *requirement* in the C standard that auto
variables be allocated on a stack (hardware or not). Yes, their model
strongly suggests using a LIFO structure, but this not, as far as I
can see, absolutely necessary.

Why can't jacob just admit this point, so that we can stop these
periodic redundant discussions? No one is, AFAIK, saying a stack
isn't commonly used, nor that it is not suitable.

Change the record Santosh. It's important because the concept of a
stack makes explaining C much, much easier. [ ... ]

Exactly which concept in C is explained easier by introducing a stack?
If explaining a stack was critical to explaining C then how come the
Standard doesn't mention a stack at all? After all the very purpose of
the Standard is to explain C.

I think you are confusing debugging C programs (which is facilitated by
a knowledge of machine level details, which includes the stack, if
there is one), with C per se.
 
S

santosh

Bartc said:
It's quite an achievement to have created a language Standard that
works even on these lowly processors, but surely it would have been
better to split the language into two?

Then the low-level C can go to town on all the features relevant to
those platforms.

And the high-level C can finally be unconstrained.

Isn't this what Stroustrup set out to do? :)

<snip>
 
R

Richard

santosh said:
Richard said:
santosh said:
Richard Heathfield wrote:

jacob navia said:

Jack Klein wrote:

<snip>

I know of at least one architecture where it is
quite impossible, as the stack is completely inaccessible to
instructions other than call and return.


Who cares?

The OP.

We are speaking about mainstream implementations here.

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.

I do not expect you to understand this. I wish I did.

I can't imagine why jacob is so stuck up on this issue. Yes, we all
know that the majority (perhaps even a vast majority) of C
implementations use a hardware enabled stack. But majority is not
all!

And in any case there is no *requirement* in the C standard that auto
variables be allocated on a stack (hardware or not). Yes, their model
strongly suggests using a LIFO structure, but this not, as far as I
can see, absolutely necessary.

Why can't jacob just admit this point, so that we can stop these
periodic redundant discussions? No one is, AFAIK, saying a stack
isn't commonly used, nor that it is not suitable.

Change the record Santosh. It's important because the concept of a
stack makes explaining C much, much easier. [ ... ]

Exactly which concept in C is explained easier by introducing a stack?

Just about everything. I am amazed you have to ask this. You have been
in CLC too long.
If explaining a stack was critical to explaining C then how come the
Standard doesn't mention a stack at all? After all the very purpose of
the Standard is to explain C.

No its not. Its to define C. A not so subtle difference.
I think you are confusing debugging C programs (which is facilitated by
a knowledge of machine level details, which includes the stack, if
there is one), with C per se.

No I am not.
 
W

Willem

Richard wrote:
)> Exactly which concept in C is explained easier by introducing a stack?
)
) Just about everything. I am amazed you have to ask this. You have been
) in CLC too long.

You're dodging the question.

PS: It may be true that a lot of 'how does it do it' questions are most
easily answered by 'it uses a stack', but for C programming concepts as
such, I see no need.


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
 
S

santosh

Richard said:
santosh said:
Richard wrote:
Change the record Santosh. It's important because the concept of a
stack makes explaining C much, much easier. [ ... ]

Exactly which concept in C is explained easier by introducing a
stack?

Just about everything. [...]

I can't see any aspect of C that needs a stack to be introduced to
explain it. Can you cite a specific example? Function arguments? Return
values? Auto variables? Variadic functions? Recursion?

The concepts of C can be, AFAICS, explained without resorting to
introducing a stack. Obviously, explaining things in deeper detail,
with reference to actual systems and implementations will need an
introduction to a stack at some point.

<snip>
 
E

Eric Sosman

CJ said:
Thanks for all the replies, this is an interesting discussion.

Here are a couple of points that occur to me:

1) Buffer overflows are a more serious security problem on the stack
than on the heap, because the program counter is stored on the stack and
not the heap, so that a malicious stack overflow can execute arbitrary
code. The heap is used for data exclusively, which is what I meant by
"separate data from executable code".

Subroutine return addresses are stored in many ways.
Quite often they live in registers and never get to memory
at all.
Even if a buffer on the heap overflows, the worst that can happen is
some (probably insignificant) data corruption.

"Probably insignificant?" Ye gods and little fishes!
Since malloc() generally
allocates space in powers of 2,

Some do, some don't. I don't think you can defend the
"generally."
often an off-by-one error or similar
won't overwrite anything anyway, but will just land in the gap between
the end of the buffer and the next power of 2.

So you suggest not only that auto storage be obtained
from malloc() or something like it, but that each variable
be allocated in its own little buffer? A function with ten
auto variables make ten separate allocations?

How 'bout this: Leave everything on the stack, but
put padding bytes between all the items, enough of them
so an "off-by-one error or similar" lands in the empty
space. Happy now?
2) I believe the argument about it being more efficient to use the stack
than the heap is spurious - if I recall, both are O(N) data structures.

What is the "N" to which you refer, and what quantity
are you describing as "O(N)?"
 
R

Richard

Willem said:
Richard wrote:
)> Exactly which concept in C is explained easier by introducing a stack?
)
) Just about everything. I am amazed you have to ask this. You have been
) in CLC too long.

You're dodging the question.

PS: It may be true that a lot of 'how does it do it' questions are most
easily answered by 'it uses a stack', but for C programming concepts as
such, I see no need.

Sigh. You just answered it yourself.
 
R

Richard

santosh said:
Richard said:
santosh said:
Richard wrote:
Change the record Santosh. It's important because the concept of a
stack makes explaining C much, much easier. [ ... ]

Exactly which concept in C is explained easier by introducing a
stack?

Just about everything. [...]

I can't see any aspect of C that needs a stack to be introduced to
explain it. Can you cite a specific example? Function arguments? Return
values? Auto variables? Variadic functions? Recursion?

All contribute.
The concepts of C can be, AFAICS, explained without resorting to
introducing a stack. Obviously, explaining things in deeper detail,
with reference to actual systems and implementations will need an
introduction to a stack at some point.

Exactly.

But a stack is easy. Introduce it earlier. You guys crack me up. I think
I need a break from the legalese of this NG. You are getting more
ridiculous by the day.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,483
Members
44,901
Latest member
Noble71S45

Latest Threads

Top