468,457 Members | 1,598 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 468,457 developers. It's quick & easy.

Why are variables stored on the stack?

CJ
Hello:

We know that C programs are often vulnerable to buffer overflows which
overwrite the stack.

But my question is: Why does C insist on storing local variables on the
stack in the first place?

I can see two definite disadvantages with this:
1) deeply nested recursive calls to a function (especially if it defines
large local arrays) can easily overflow the stack
2) the problems described above of security vulnerabilities.

My solution would be for C instead to store its local variables on the
heap - effectively separating data from executable code.

What do people think?

Mar 14 '08
87 4897
Stephen Sprunk wrote:
"Richard" <de***@gmail.comwrote in message
news:fr**********@registered.motzarella.org...
>santosh <sa*********@gmail.comwrites:
>>jacob navia wrote:
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.

And this is important to C programmers who come here for help who
program 99.9999% of the worlds Computers how?

Um, you do realize that embedded systems comprise the _vast_ majority of
computers in existence today and that "traditional" computers like
you're used to are a small minority, right?

Just because _you_ don't program 8051s, DSPs, etc. doesn't mean that
they're not important.

S
They are not important for C since there are no conforming
implementations in those machines, they are just too small.

Either recursion is absent, or floating point, or similar
restrictions (no 64 bit long long, for instance)

Yes, in the embedded world is important to care about
those small processors. But let's not generalize OK?

Behind all this arguments is the idea that C is for
small embedded processors. Real development should be done
in C++.

--
jacob navia
jacob at jacob point remcomp point fr
logiciels/informatique
http://www.cs.virginia.edu/~lcc-win32
Mar 15 '08 #51
jacob navia said:
Stephen Sprunk wrote:
<snip>
>Just because _you_ don't program 8051s, DSPs, etc. doesn't mean that
they're not important.
They are not important for C since there are no conforming
implementations in those machines, they are just too small.
<sigh>

Google search terms: 8051 ANSI C

Some of the first few hits:

http://www.crossware.com/datasheets/c8051nt.htm
http://sdcc.sourceforge.net/
http://www.wickenhaeuser.de/
http://www.keil.com/c51/c51.asp

All of these claim to conform to ANSI C (by which I presume they mean C90).
In what ways are they mistaken?

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999
Mar 15 '08 #52
"jacob navia" <ja***@nospam.comwrote in
>
Yes, that is why stack allocation of large arrays is not a very
good idea.
To be precise, using the same stack for large arrays and frequently-accessed
small data items is a bad idea. Unless the arrays are huge, having a
separate stack and a function - I call it salloc() - to allocate from it can
speed up the program quite a bit. Remember most data items can be written in
a LIFO fashion.

--
Free games and programming goodies.
http://www.personal.leeds.ac.uk/~bgy1mm


Mar 15 '08 #53
jacob navia wrote:
Ian Collins wrote:
>jacob navia wrote:
>>Please look it up and stop telling stories.
Please look up the word "stack" in the standard and tell us where it
occurs.

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.
No, I've asked you several times for the reference and you keep telling
stories about C insisting on a stack.
The word "stack" doesn't appear in the standard. It is implied.
Thank you, at last a clear admission that C does not insist on a stack.

The original argument was not whether most implementations use a stack,
which no one here denies, but whether they are required to.

--
Ian Collins.
Mar 15 '08 #54
Thad Smith <Th*******@acm.orgwrites:
jacob navia wrote:
>Please stop confusing people by using word games.
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)

I suppose I don't post enough to be considered a "regular".

In Message ID:<47***********************@auth.newsreader.octa news.com>
(Macro that allocates storage and "returns" value) I mentioned that
some embedded processors use static allocation rather than a
stack. Besides 1k coffee machines, it also also used on PICs with 128k
code space and a few k of RAM.

Could a stack be used? Yes, especially for the larger memory
processors, but the instruction set does not provide an efficient
means of accessing stack-based variables, so performance and code size
would suffer.
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.)

It could still conform to the C standard if it uses static allocation
only for functions that it knows are never called recursively.

C does insist on a "stack" in the sense of last-in first-out
allocation for local objects across function calls. It absolutely
does not insist that this "stack" be implemented as a contiguous
hardware stack (even though most implementations do so). I don't
believe the embedded systems you refer to are a counterexample to any
claim that C requires a contiguous hardware stack.

--
Keith Thompson (The_Other_Keith) <ks***@mib.org>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
Mar 15 '08 #55
jacob navia <ja***@nospam.comwrites:
[...]
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?

--
Keith Thompson (The_Other_Keith) <ks***@mib.org>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
Mar 15 '08 #56
Keith Thompson wrote:
Thad Smith <Th*******@acm.orgwrites:
>jacob navia wrote:
>>Please stop confusing people by using word games.
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.
>In Message ID:<47***********************@auth.newsreader.octa news.com>
(Macro that allocates storage and "returns" value) I mentioned that
some embedded processors use static allocation rather than a
stack. Besides 1k coffee machines, it also also used on PICs with 128k
code space and a few k of RAM.
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.

--
Thad
Mar 15 '08 #57
Keith Thompson wrote:
jacob navia <ja***@nospam.comwrites:
[...]
>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.
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.

--
jacob navia
jacob at jacob point remcomp point fr
logiciels/informatique
http://www.cs.virginia.edu/~lcc-win32
Mar 15 '08 #58
Malcolm McLean wrote:
"CJ" <cj@nospam.comwrote in message
>>
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.

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/>

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.

--
Posted via a free Usenet account from http://www.teranews.com

Mar 15 '08 #59
Willem wrote:
jacob wrote:
>Willem wrote:
>>CJ wrote:

But my question is: Why does C insist on storing local
variables on the stack in the first place?

It doesn't. Your question is moot.

This is wrong. Most C implementations use the hardware stack

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.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.

--
Posted via a free Usenet account from http://www.teranews.com

Mar 15 '08 #60
jacob navia wrote:
Keith Thompson wrote:
.... snip ...
>>
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.
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.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.

--
Posted via a free Usenet account from http://www.teranews.com

Mar 16 '08 #61
jacob navia <ja***@nospam.comwrites:
Keith Thompson wrote:
>jacob navia <ja***@nospam.comwrites:
[...]
>>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.

--
Keith Thompson (The_Other_Keith) <ks***@mib.org>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
Mar 16 '08 #62
Keith Thompson wrote:

<snip>
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.

Mar 16 '08 #63
Keith Thompson wrote:
jacob navia <ja***@nospam.comwrites:
>Keith Thompson wrote:
>>jacob navia <ja***@nospam.comwrites:
[...]
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

--
jacob navia
jacob at jacob point remcomp point fr
logiciels/informatique
http://www.cs.virginia.edu/~lcc-win32
Mar 16 '08 #64
jacob navia wrote:
Keith Thompson wrote:
>>
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"
Come on then, put up or shut up, where did Keith say that?

--
Ian Collins.
Mar 16 '08 #65

"Richard Heathfield" <rj*@see.sig.invalidwrote in message
news:5c******************************@bt.com...
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.
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

Mar 16 '08 #66
"Keith Thompson" <ks***@mib.orgwrote in message
news:87************@kvetch.smov.org...
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

Mar 16 '08 #67
Rod Pemberton wrote:
"Richard Heathfield" <rj*@see.sig.invalidwrote in message
news:5c******************************@bt.com...
>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.

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".

--
jacob navia
jacob at jacob point remcomp point fr
logiciels/informatique
http://www.cs.virginia.edu/~lcc-win32
Mar 16 '08 #68
Keith Thompson said:

<snip>
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).
Well, again that isn't quite true. Consider, for example, the following
code:

{
int a = foo();
int b = bar();
if(a + b < c)
{
int d = c - (a + b); /* X */
baz(d * quux() / (d - foo()));
quuy(&d);
quuz(d * quua());
}
}

The line marked X is the last line in which a and b are used. The Standard
therefore allows implementations licence to destroy a and b /before/ it
destroys d - for example, a and b can be history by the time the sequence
point in line X occurs, even though d still exists, because the program
still behaves "as if" a and b exist, and no strictly conforming program
can tell the difference (because if it could, obviously the compiler
wouldn't do the early destruction in the first place). By virtue of its
"as if" rule, the C language *does not mandate* LIFO auto allocation.

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999
Mar 16 '08 #69
Rod Pemberton said:
"Keith Thompson" <ks***@mib.orgwrote in message
news:87************@kvetch.smov.org...
>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?
Dennis Ritchie wrote the cited text in 1978, so not only is it
non-normative, but it also pre-dates the ISO C language specification by
over a decade. The fact remains that the internationally agreed language
spec doesn't require implementations to use a stack. They probably will,
but they don't have to. If an implementor finds a clever way to speed
things up that requires him /not/ to use a stack, C allows him to take
advantage of that cleverness. I can't understand why several people in
this discussion seem to be trying to deprive implementors of this licence.

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999
Mar 16 '08 #70
Rod Pemberton said:

<snip>
>
Richard,

How so? How is the OP's usage of "insist" any different from Ritchie's
usage of "suggest strongly"?
This looks familiar. I think you posted exactly the same question
elsethread, yes? I answered it there.

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999
Mar 16 '08 #71
Ian Collins <ia******@hotmail.comwrites:
jacob navia wrote:
>Keith Thompson wrote:
>>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"
Come on then, put up or shut up, where did Keith say that?
I'm fairly sure I've never said that. In fact, I've criticized
CBFalconer for saying that. It's arguably a true statement (for one
particular meaning of the word "stack"), and I think we both
understand what he means by it, but it's also incomplete and
potentially misleading.

If you had jumped on somebody responding to the original post in this
thread for saying "C has no stack", you might have a point. Instead,
you jumped on people for saying that C does not *insist* on storing
local variables on the stack. Those responses were both correct (the
C language doesn't insist on any such thing) and very relevant to the
original question.

--
Keith Thompson (The_Other_Keith) <ks***@mib.org>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
Mar 16 '08 #72
"Rod Pemberton" <do*********@nohavenot.cmmwrites:
"Keith Thompson" <ks***@mib.orgwrote in message
news:87************@kvetch.smov.org...
>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?
There's a big difference between "insist" and "suggest strongly". The
former implies a requirement; for example, C insists that a byte is at
least 8 bits.
"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
Which is why, as has been acknowledged repeatedly in this thread, most
implementations do use a contiguous hardware stack. But there is no
requirement that they do so. Also, (a) the paper was written in 1978;
things have changed since then; (b) the paper is about C and UNIX,
which were more closely tied together than they are now; and (c) I'm
not sure that Johnson and Ritchie were necessarily referring to a
contiguous hardware stack. I suspect they would have acknowledged
that anything scheme that works in a last-in first-out fashion would
work. Note that they refer to "a stack", not to "the stack" (though
perhaps I'm reading too much into that distinction).

And it's not impossible that Ritchie could have been wrong (and even
more likely that I might disagree with him). I don't recall that he's
ever claimed to be infallible; note that the errata list for K&R is
not empty.

--
Keith Thompson (The_Other_Keith) <ks***@mib.org>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
Mar 16 '08 #73
santosh <sa*********@gmail.comwrites:
Keith Thompson wrote:
<snip>
>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.
[...]

Perhaps I'm missing something, but I don't see your point. The
stack-like nature of local variable (strictly speaking, automatic
object) allocation is about lifetime, not visibility. I suppose
there's probably a stack-like data structure that's part of the
compile-time symbol table, but that's not what we've been discussing.

--
Keith Thompson (The_Other_Keith) <ks***@mib.org>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
Mar 16 '08 #74
Richard Heathfield <rj*@see.sig.invalidwrites:
Keith Thompson said:
<snip>
>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).

Well, again that isn't quite true. Consider, for example, the following
code:

{
int a = foo();
int b = bar();
if(a + b < c)
{
int d = c - (a + b); /* X */
baz(d * quux() / (d - foo()));
quuy(&d);
quuz(d * quua());
}
}

The line marked X is the last line in which a and b are used. The Standard
therefore allows implementations licence to destroy a and b /before/ it
destroys d - for example, a and b can be history by the time the sequence
point in line X occurs, even though d still exists, because the program
still behaves "as if" a and b exist, and no strictly conforming program
can tell the difference (because if it could, obviously the compiler
wouldn't do the early destruction in the first place). By virtue of its
"as if" rule, the C language *does not mandate* LIFO auto allocation.
Fair enough. And by the "as if rule", if the implementation can prove
that no function is ever called recursively, it can use static storage
for everything. But in the abstract machine, something LIFOish is
necessary. To put it another way, a program must behave *as if*
automatic allocation is done in a LIFO manner.

--
Keith Thompson (The_Other_Keith) <ks***@mib.org>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
Mar 16 '08 #75
Keith wrote:
) It quacks like a stack, so yes, I'd call it (a rather unconvention
) implementation of) a stack.

But not _the_ stack. See the subject header.
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
Mar 16 '08 #76
jacob navia wrote:
Keith Thompson wrote:
>[...]
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"
Can you provide a reference to the posting where
Keith made this statement?

--
Eric Sosman
es*****@ieee-dot-org.invalid
Mar 16 '08 #77
The C standard does not require a C implementation to have bugs.
The C standard doesn't even define the term "bug".

Does this mean that C has no bugs? No.

Does this mean that a given C implementation has no bugs? No, although
not requiring an implementation to have bugs doesn't mean it's required
to have no bugs.

Does this mean that someone is wrong for saying "Most C implementations
have bugs"? No.
Mar 16 '08 #78
Richard Heathfield wrote:
Rod Pemberton said:

<snip>
>>
How so? How is the OP's usage of "insist" any different from
Ritchie's usage of "suggest strongly"?

This looks familiar. I think you posted exactly the same question
elsethread, yes? I answered it there.
Again, time for a thread plonk.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.

--
Posted via a free Usenet account from http://www.teranews.com

Mar 17 '08 #79
jacob navia <ja***@nospam.comwrote:
Willem wrote:
CJ wrote:
) But my question is: Why does C insist on storing local variables on the
) stack in the first place?

It doesn't. Your question is moot.

This is wrong. Most C implementations use the hardware stack
Well, here's the thing: you're both right. Willem is right that C
doesn't require the use of the (single, hardware) stack. You are right
that C implementors tend to use that stack anyway. So the OP really
shouldn't blame C itself for all those buffer overflow attacks, but the
authors of the C implementations which do use that stack.

Richard
Mar 17 '08 #80
In article <sl********************@snail.stack.nlWillem <wi****@stack.nlwrites:
Richard wrote:
) santosh <sa*********@gmail.comwrites:
)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.
Moreover, I think that when somebody needs C to be explained and you wish
to use the stack in explaining, you have first to explain the stack.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
Mar 17 '08 #81
Richard Bos wrote:
So the OP really
shouldn't blame C itself for all those buffer overflow attacks, but
the authors of the C implementations which do use that stack.
Authors of C programs which overflow.

Mar 17 '08 #82
In article <87************@kvetch.smov.orgKeith Thompson <ks***@mib.orgwrites:
....
Fair enough. And by the "as if rule", if the implementation can prove
that no function is ever called recursively, it can use static storage
for everything.
Right. And this is done in Fortran 77. On the other hand, the system
may provide a different stack for each function.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
Mar 17 '08 #83
jacob navia wrote:
>
Ian Collins wrote:
jacob navia wrote:
Willem wrote:
CJ wrote:
) But my question is: Why does C insist on storing local variables on the
) stack in the first place?

It doesn't. Your question is moot.
SaSW, Willem
This is wrong. Most C implementations use the hardware stack
Please stop confusing practical implementation with requirements.

Please stop confusing people by using word games.
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.
While I haven't looked into this in great detail, here is a likely
candidate:

http://www.cc65.org/

As I recall, the 6502 has only 256 bytes for its stack.
(Obviously in machines running now, and having a certain
minimum size. Coffee machines with less than 1K of
RAM and similars do not count)
Just curious why you eliminate such things?

--
+-------------------------+--------------------+-----------------------+
| Kenneth J. Brody | www.hvcomputer.com | #include |
| kenbrody/at\spamcop.net | www.fptech.com | <std_disclaimer.h|
+-------------------------+--------------------+-----------------------+
Don't e-mail me at: <mailto:Th*************@gmail.com>
Mar 17 '08 #84
Paul wrote:
) A "hardware stack" is not equivalent to the C stack. If you say "the
) stack" in this newsgroup, you must be referring to the ANSI C implicit
) stack right? If you mean the *x86* stack, then you should say so.

The question was "why does C insist that variables are stored on the stack"
so 'the stack' in that context *cannot* mean 'the place the auto variables
are stored', because otherwise the question would be a tautology.

Reading further into the OP, it becomes obvious that 'the stack' in this
context means the call/return stack, where most C implementations do indeed
store most of the auto variables, but _that is not required_.
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
Mar 17 '08 #85
Keith Thompson <ks***@mib.orgwrites:
Paul Hsieh <we******@gmail.comwrites:
That's a strawman argument. I've lost track of the number of times
that I've said that C *does* implicitly require a "stack" in the
computer science sense of a LIFO data structure.
Well, nothing prevents an implementation to dynamically allocate the
activation records and then garbadge collect them. This to make something
like

int *newInt() {
int i;
return &i;
}

having a reasonnable implementation defined behavior :-) Not really in the
spirit of C, but not impossible if it is a side effect of sharing the back
end of the compiler with a language having proper closures. Obviously, one
of the first optimization done by such a back end would be to use the
hardware stack if available for the activation records which don't need
dynamic allocation because they are not leaked. So the performance cost
of the feature would be quite minimal for properly written C.

A+

--
Jean-Marc
Mar 18 '08 #86
On Mar 17, 1:49 pm, Willem <wil...@stack.nlwrote:
Paul wrote:
) A "hardware stack" is not equivalent to the C stack. If you say "the
) stack" in this newsgroup, you must be referring to the ANSI C implicit
) stack right? If you mean the *x86* stack, then you should say so.

The question was "why does C insist that variables are stored on the stack"
so 'the stack' in that context *cannot* mean 'the place the auto variables
are stored', because otherwise the question would be a tautology.
Its only tautological, if you already know the answer. But a teacher
or other environment will typically refer to "the stack" or something
of that nature in C or other languages while not explaining to the
student that the stack is resultant, not an a priori structure that is
prerequisite.
Reading further into the OP, it becomes obvious that 'the stack' in this
context means the call/return stack, where most C implementations do indeed
store most of the auto variables, but _that is not required_.
Yeah ok, but that means his question makes a semantic confusion that
some people here, for some reason, are buying into.

--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/
Mar 19 '08 #87
Paul Hsieh <we******@gmail.comwrites:
On Mar 18, 9:08 am, Keith Thompson <ks...@mib.orgwrote:
>Paul Hsieh <websn...@gmail.comwrites:
On Mar 16, 1:16 am, Keith Thompson <ks...@mib.orgwrote:
Ian Collins <ian-n...@hotmail.comwrites:
jacob navia wrote:
Keith Thompson wrote:
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"
Come on then, put up or shut up, where did Keith say that?
>I'm fairly sure I've never said that. In fact, I've criticized
CBFalconer for saying that. It's arguably a true statement (for one
particular meaning of the word "stack"), and I think we both
understand what he means by it, but it's also incomplete and
potentially misleading.
That's called equivocation.

No, it's called precision.

You are using the word precision to describe "I think we both
understand what he means by it"? What is this, alt.satire or
something?

In any event, that's besides the point. If you wish, I will grant
that you are being precise -- in fact you are elucidating your
equivocation very precisely by repeating your mistake over and over.
If I understand you correctly, you're saying that, at least in the
context of this newsgroup, the word "stack" can only refer to the
computer science concept of an abstract LIFO data structure, and that
using the word to refer to a particular contiguous hardware
implementation is wrong.

In my opinion, both uses of the term are legitimate. One of those
meanings is applicable to the C language, at least to the C abstract
machine. The other is not, but is applicable only to particular
implementations (most of them, as it happens).

My point in citing the derivation of the word was that "stack", like
any word, can and does have different meanings in different contexts.

I respect your opinion that one meaning is correct and the other is
wrong, but I don't share that opinion. As far as I can tell, that
disagreement (which I think is a minor one) is what's motivated you to
flame me rather than, say, try to help answer the OP's question.

[snip]
The confusion is a matter of perspective. You are implicitly bringing
in a vendor's CPU implementation of the stack, while ignoring the C
language defined stack. *In this newsgroup* that you, among others,
insist must not deviate from discussing C.
No. I *explicitly* discussed a vendor's CPU implementation of the
stack (and it's not just one vendor; I first encountered the concept
on the PDP-11, and most CPUs support something similar). I did so
because the original poster *implicitly* used the term "stack" in that
sense.

As for "ignoring the C language defined", perhaps you're confusing me
with somebody else, because I've discussed it at considerable length.
In this case, I endorse the distinction of the implicit stack, because
the details of a hardware stack are rarely relevant to any compiler.
Huh? They're not relevant to the language, but they're extremely
relevant to any compiler that has to generate code that uses it.
Also, modern compilers heavily make use of the as-if rule, to simplify
and even eliminate the storage of certain auto-variables,
Yes, of course.
making the
mapping to hardware implementation truly meaningless.
It's not completely meaningless, but it's outside the scope of the
language.
>It's very clear that the original poster was using the word "stack"
the way Intel does; otherwise the question wouldn't make sense.

Yeah ok, but that's a mistake.
Which you could have corrected rather than flaming me.

[snip]
>That's a strawman argument. I've lost track of the number of times
that I've said that C *does* implicitly require a "stack" in the
computer science sense of a LIFO data structure.

Oh don't worry about that. I can trace back to when you original
started saying this. I think we both know exactly when that was.
Perhaps you do. Maybe you've kept better track of what I've written
here than I have. I have no idea what point you're trying to make.
>[...] Those responses were both correct (the
C language doesn't insist on any such thing) and very relevant to the
original question.
No, those responses are just technically wrong. Its like saying that
ice cubes are not cubes because they can be made of various kinds of
water.

It's like saying (in fact, it is saying) that the C language, though
it implicitly requires a LIFO mechanism to manage automatic storage
(or at least requires programs to behave *as if* there is such a
mechanism), it does not require a contiguous hardware stack that grows
in a particular direction (what Intel, correctly or incorrectly, calls
"the stack"). If you want to suggest a better way to express that
distinction *without* ignoring the fact that people use the word
"stack" in at least two different ways, please do so.

Yeah there's a simple way. Just be consistent, and in CLC, the stack
is the stack that is implicitly defined by the language. There's no
controversy if you do that, because its technically correct without
introducing any new or restrictive semantics, meaning or terminology.
Also because the correctness rate of anything else said about stacks
in this newsgroup, even in this thread alone is so ridiculous low,
that there's nothing of any substance lost in rejecting that alternate
form of discourse.
I said "*without* ignoring the fact that people use the word 'stack'
in at least two different ways". If you want to ignore that fact, go
ahead; I'd rather acknowledge it and help people understand what's
really going on.

--
Keith Thompson (The_Other_Keith) <ks***@mib.org>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
Mar 20 '08 #88

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

8 posts views Thread by pertheli | last post: by
8 posts views Thread by Andre | last post: by
7 posts views Thread by S. A. Hussain | last post: by
11 posts views Thread by Murali | last post: by
6 posts views Thread by Clausfor | last post: by
20 posts views Thread by tshad | last post: by
reply views Thread by NPC403 | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.