The machine stack and the C language
jacob navia
use a stack" or that "C doesn't imply a stack" because there *could* be
some obscure implementations somewhere in extremely small circuits
where there is no hardware stack.
As has been pointed out several times, the support of recursive
functions in C implies a logical stack. One of the "implementations"
this people presented, didn't implement recursion and can't be counted
as a complete C implementation.
The relevant part of the standard is (6.5.2.2.11):
<quote>
Recursive function calls shall be permitted, both directly and
indirectly through any chain of other functions
<end quote>
Even if several people have pointed out the fact that the language
implies a logical stack (recursion is part of the language), this
people continue to answer in stupid messages like
<quote>
Repeat after me: "There is no stack in the definition of the C
Language"
<end quote>
from Mr "Lew Pitcher"
This is nonsense in the context of the question, since the question
was about stack overflow. Instead of pointing to the several
ways a programmer has to catch stack overflow, they start this
eternal discussion about "There is no stack in C", that they love
to start again and again.
This fits in the general attitude of these people that like to
show their detail knowledge instead of realizing that the overwhelming
part of all C implementations use a hardware stack because the
overwhelming majority of processors has a hardware stack.
This is a fact, but these people are not very interested in those facts.
They use the ignorance of many people here about certain exotic
environments, like, for instance, the IBM Mainframes. Specifically,
Mr "Flash Gordon" said:
<quote>
it won't work on big iron (or even relatively small servers like those
we run our accounts system on in my company)
<end quote>.
There is nothing more "big iron" that the IBM mainframes... at least
within my limited experience since I quit using that environment
in 1984.
The C compiler for the IBM mainframes is "C for VM/ESA", a C89
compiler.
We find in the users guide
http://publibfp.boulder.ibm.com/cgi-bin/bookmgr/BOOKS/cbcvpg00/CCONTENTS
3.1.4.3 Accessing Automatic Memory
Use the EDCDSAD macro to access automatic memory. Automatic memory is
reserved using the USRDSAL, or the DSALEN operand of the EDCPRLG macro.
The length of the allocated area is derived from the ulen and/or dlen
values specified on the EDCPRLG macro. EDCDSAD generates a DSECT, which
reserves space for the *stack frame* needed for the C environment.
<end quote>
I repeat: "... the stack frame needed for the C environment".
Of course this is (maybe, I did not investigate very much) not an
actual hardware stack, but it is a stack OBVIOUSLY!
It would be interesting tha they AT LAST point out the implementations
of C where there is "NO STACK"... Obviously implementations crippled
beyond recgnition that do not implement recursion do NOT count.
This will put them in the same problems that they had the last time
a similar question was asked about "trap representations", and
other mythical implementations whose only users are these people
and exist only in their minds...
--
jacob navia
jacob at jacob point remcomp point fr
logiciels/informatique
http://www.cs.virginia.edu/~lcc-win32
Malcolm McLean
"jacob navia" <ja...@nospam.com> wrote in message
> As has been pointed out several times, the support of recursive
> functions in C implies a logical stack. One of the "implementations"
> this people presented, didn't implement recursion and can't be counted
> as a complete C implementation.
>
a qsort() function, because quicksort is recursive.
It wasn't "crippled beyond recognition" however. It was intended to run a
machine to issue parking tickets. Really all you need is something to count
the money, print the ticket, and I think it didn't give change. No need for
recursion there.
>
> This fits in the general attitude of these people that like to
> show their detail knowledge instead of realizing that the overwhelming
> part of all C implementations use a hardware stack because the
> overwhelming majority of processors has a hardware stack.
>
but the R6000 series, or whatever it weas called, did not. You had to impose
caller-saved and callee-saved registers by convention, jumping to the return
register address, and since it had 32 registers you could actually go quite
deep in trivial functions before needing to resort to putting out data to
memory. The stack itself had no special status at the processor level.
Note that I am very rusty about all this since it is well over ten years
since I coded for either processor.
--
Free games and programming goodies.
http://www.personal.leeds.ac.uk/~bgy1mm
Ben Pfaff
> "jacob navia" <ja...@nospam.com> wrote in message
>> As has been pointed out several times, the support of recursive
>> functions in C implies a logical stack. One of the "implementations"
>> this people presented, didn't implement recursion and can't be counted
>> as a complete C implementation.
>>
> I've used such implementations. Rather stupidly, the vendors didn't
> include a qsort() function, because quicksort is recursive.
qsort() does not have to be implemented as quicksort, and
quicksort does not have to be implemented recursively.
--
char a[]="\n .CJacehknorstu";int putchar(int);int main(void){unsigned long b[]
={0x67dffdff,0x9aa9aa6a,0xa77ffda9,0x7da6aa6a,0xa67f6aaa,0xaa9aa9f6,0x11f6},*p
=b,i=24;for(;p+=!*p;*p/=4)switch(0[p]&3)case 0:{return 0;for(p--;i--;i--)case+
2:{i++;if(i)break;else default:continue;if(0)case 1:putchar(a[i&15]);break;}}}
Eric Sosman
> In this group, there are a group of people that insists that "C doesn't
> use a stack" or that "C doesn't imply a stack" because there *could* be
> some obscure implementations somewhere in extremely small circuits
> where there is no hardware stack.
> Even if several people have pointed out the fact that the language
> implies a logical stack (recursion is part of the language), this
> people continue to answer in stupid messages like
>
> <quote>
> Repeat after me: "There is no stack in the definition of the C
> Language"
> <end quote>
This is one of those occasions (they're not unthinkably rare)
when I find myself in agreement with Jacob. The quoted remark was
pointless and unhelpful, serving only to turn a serious thread
into a pissing contest.
> This is nonsense in the context of the question, since the question
> was about stack overflow. Instead of pointing to the several
> ways a programmer has to catch stack overflow, [...]
Ah, but here's where Jacob and I part ways again. C has *no*
mechanism for detecting stack overflow (sorry, "exhaustion of the
resources that keep track of auto variables and/or whatever's
needed to ensure that a function can return to its caller"). The
various mechanisms that have been mentioned are extra-C, part of
the environment and not part of the language or library. They
are as much a part of C as is the ability to do asynchronous I/O.
--
Eric Sosman
eso...@ieee-dot-org.invalid
jacob navia
Which C?
POSIX has. Why is POSIX not considered as C?
Unix was the birth place of C, and Unix has the best implementations
of the language. There is no charter here, and POSIX is a widely
used standard. Under windows, there are several alternatives as I
said in my message in that thread. Why not discuss here REAL
problems and exchange information about REAL solutions instead of just
"The minimal and worst standard of C, ISO C, doesn't know about
stack overflow so you just go away".
> The
> various mechanisms that have been mentioned are extra-C, part of
> the environment and not part of the language or library. They
> are as much a part of C as is the ability to do asynchronous I/O.
>
Maybe they are not part of ISO C but they part part of POSIX.
Or they are proposed by Microsoft, that even if they aren't a standards
body they have a small market share that justifies that we speak about
solutions in their environment.
I would like to point out how much the FAQ speaks about DOS.
Why?
Because that was 15 years ago, when people using C were younger,
less pedantic, and in general with better BRAINS!
Malcolm McLean
>
questions here about Turbo C will have no access to it, for example.
Willem
) In this group, there are a group of people that insists that "C doesn't
) use a stack" or that "C doesn't imply a stack" because there *could* be
) some obscure implementations somewhere in extremely small circuits
) where there is no hardware stack.
This argument originated as "C doesn't necessarily have a stack such as it
is used on your typical desktop platform".
To be more precise, a stack that is a contiguous area of RAM, with a stack
pointer pointing to the top, and where pushing something onto the stack
means storing it at wherever the pointer points to and then increasing the
pointer by the size of whatever you pushed. The stack where the pointer is
increased by the frame size of the current function when entering, and
decreased again when exiting.
(Or the reversed version, where the stack grows downward from the top).
Usually, the question that gets a "C doesn't have a stack" answer is
a question that assumes *this specific kind* of stack. For example, a
question about how to access the caller's local variables without passing
them as arguments. Or one about what happens when you overflow a local
array.
You know, the kind of people that says "To write a portable program, you
need to add a bit of code that checks if the stack grows upward or downward."
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
Tomás Ó hÉilidhe
> As has been pointed out several times, the support of recursive
> functions in C implies a logical stack. One of the "implementations"
> this people presented, didn't implement recursion and can't be counted
> as a complete C implementation.
You make a brilliant point Jacob. Taking the following program:
(Kindly excuse the typos and stupid erros)
#include <stdio.h>
extern unsigned GetUserInput(void); /* Defined elsewhere */
void Recurse(unsigned const amount_times)
{
if (amount_times <= 1) return;
printf("%u\n",amount_times);
Recurse(i - 1);
}
int main(void)
{
Recurse( GetUserInput() );
return 0;
}
In order for this program to work, I can't fathom any other method than
using a stack. Of course, the C standard leaves the door wide open for
the implementation to achieve the correct behaviour any way it wants,
but the point to be made is that no person has yet to implement a method
other than a stack (and how many decades has it been?).
Just as an aside, there's a similar situation in C++ when it comes to
implementing polymorphism via the use of a V-Table. You'll have people
blue in the face telling you there's no such thing as a V-Table in
C++... yet nobody has ever implemented any other method of achieving
polymorphism.
--
Tomás Ó hÉilidhe
Harald van Dijk
> You make a brilliant point Jacob. Taking the following program:
>
> (Kindly excuse the typos and stupid erros)
>
> #include <stdio.h>
>
> extern unsigned GetUserInput(void); /* Defined elsewhere */
>
> void Recurse(unsigned const amount_times) {
> if (amount_times <= 1) return;
>
> printf("%u\n",amount_times);
>
> Recurse(i - 1);
I'll assume you mean amount_times - 1 here.
> }
>
> int main(void)
> {
> Recurse( GetUserInput() );
>
> return 0;
> }
>
>
> In order for this program to work, I can't fathom any other method than
> using a stack.
Actually, many implementations will generate code for this effectively
equivalent to
#include <stdio.h>
extern unsigned GetUserInput(void); /* Defined elsewhere */
void Recurse(unsigned /*const*/ amount_times) {
start:
if (amount_times <= 1) return;
printf("%u\n",amount_times);
amount_times = amount_times - 1;
goto start;
}
int main(void)
{
Recurse( GetUserInput() );
return 0;
}
It's called "tail call" optimisation, if you want to look it up, and in
this case, it's very easy for the compiler to do.
In the general case, compilers do need something that can function as a
stack, but in your example, there is no need.
Tomás Ó hÉilidhe
> It's called "tail call" optimisation, if you want to look it up, and in
> this case, it's very easy for the compiler to do.
>
> In the general case, compilers do need something that can function as a
> stack, but in your example, there is no need.
I never write recursive functions unless I really really really really
have to. In 95% of cases, you can just use a loop.
For the cases though in which a loop won't do the job, I think you need
a stack.
(As an aside, if I'm trying to do template metaprogramming in C++, I
will write the concept first as a C recursive function in order to get an
understanding of it.)
--
Tomás Ó hÉilidhe
Malcolm McLean
"Tomás Ó hÉilidhe" <t...@lavabit.com> wrote in message
> I never write recursive functions unless I really really really really
> have to. In 95% of cases, you can just use a loop.
>
interpreter, a disguised tree.
J. J. Farrell
> jacob navia:
>
>> As has been pointed out several times, the support of recursive
>> functions in C implies a logical stack. One of the "implementations"
>> this people presented, didn't implement recursion and can't be counted
>> as a complete C implementation.
>
> You make a brilliant point Jacob. Taking the following program:
<recursive program snipped>
> In order for this program to work, I can't fathom any other method than
> using a stack. Of course, the C standard leaves the door wide open for
> the implementation to achieve the correct behaviour any way it wants,
> but the point to be made is that no person has yet to implement a method
> other than a stack (and how many decades has it been?).
SPARC has been around for over two decades. A recursive program needs
something which operates conceptually as a stack. It certainly doesn't
need a single contiguous piece of memory with a stack pointer which
walks up and down it. Whether or not C needs a stack depends solely on
how you choose to define "stack".
> ...
Flash Gordon
<snip>
> They use the ignorance of many people here about certain exotic
> environments, like, for instance, the IBM Mainframes. Specifically,
> Mr "Flash Gordon" said:
>
> <quote>
> it won't work on big iron (or even relatively small servers like those
> we run our accounts system on in my company)
> <end quote>.
The above was posted immediately under your sample code and was in
reference to it. I also pointed out that the reason it would fail on the
server my company uses is that the stack grew in the opposite direction
to that assumed by your code.
--
Flash Gordon
Tim Smith
"Tomás Ó hÉilidhe" <t...@lavabit.com> wrote:
> You make a brilliant point Jacob. Taking the following program:
>
> (Kindly excuse the typos and stupid erros)
>
> #include <stdio.h>
>
> extern unsigned GetUserInput(void); /* Defined elsewhere */
>
> void Recurse(unsigned const amount_times)
> {
> if (amount_times <= 1) return;
>
> printf("%u\n",amount_times);
>
> Recurse(i - 1);
> }
>
> int main(void)
> {
> Recurse( GetUserInput() );
>
> return 0;
> }
>
>
> In order for this program to work, I can't fathom any other method than
> using a stack. Of course, the C standard leaves the door wide open for
You could easily design a runtime that doesn't need a stack. The
function call system would work as follows:
1. When a function is called, it is passed a pointer to a block of
memory. This block of memory contains the return address for the call,
and the arguments to the function, and space for the return value. I'll
call this the argument block.
2. The first thing the function does is allocate a block of memory.
This block of memory is large enough to hold all the local variables of
the function, plus enough extra space to hold the largest argument block
the function needs for any calls it makes. I'll call this the
function's local block.
3. When a function returns, it frees its local block.
4. When a function needs to call another function, it fills in the
argument block as needed for the function it wants to call, and calls it.
5. A specific register is assigned for use in passing the pointer to the
argument block to the called function. The machine's equivalent of goto
is used to actually transfer control to the other function. Similarly,
goto is used to return.
--
--Tim Smith
CBFalconer
> Eric Sosman wrote:
>
... snip ...
>
>> Ah, but here's where Jacob and I part ways again. C has *no*
>> mechanism for detecting stack overflow (sorry, "exhaustion of the
>> resources that keep track of auto variables and/or whatever's
>> needed to ensure that a function can return to its caller").
>
> Which C?
There is only one C - that described in the ISO C standard, or its
antecedants. Once the language is extended, it is no longer
portable C.
>
> POSIX has. Why is POSIX not considered as C?
POSIX is not a language specification. It is an OS specification.
--
[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
CBFalconer
>
... snip ...
>
> #include <stdio.h>
> extern unsigned GetUserInput(void); /* Defined elsewhere */
>
> void Recurse(unsigned const amount_times) {
> if (amount_times <= 1) return;
> printf("%u\n",amount_times);
> Recurse(i - 1);
> }
>
> int main(void) {
> Recurse( GetUserInput() );
> return 0;
> }
>
> In order for this program to work, I can't fathom any other
> method than using a stack. Of course, the C standard leaves the
> door wide open for the implementation to achieve the correct
> behaviour any way it wants, but the point to be made is that no
> person has yet to implement a method other than a stack (and
> how many decades has it been?).
It doesn't need a 'stack'. It needs a means of getting and
releasing memory. As an example, malloc and free will suffice.
Richard Heathfield
> jacob navia wrote:
>> Eric Sosman wrote:
>>
> ... snip ...
>>
>>> Ah, but here's where Jacob and I part ways again. C has *no*
>>> mechanism for detecting stack overflow (sorry, "exhaustion of the
>>> resources that keep track of auto variables and/or whatever's
>>> needed to ensure that a function can return to its caller").
>>
>> Which C?
>
> There is only one C - that described in the ISO C standard, or its
> antecedants.
That's already at least three Cs.
--
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
Pierre Asselin
> [ Tomas' recursive example snipped ]
> It doesn't need a 'stack'. It needs a means of getting and
> releasing memory. As an example, malloc and free will suffice.
There would be a slight chicken-and-egg issue when calling malloc()
to implement the C run-time call mechanism... I'm sure it's doable.
(It helps that malloc isn't recursive.)
--
pa at panix dot com
Keith Thompson
> Eric Sosman wrote:
[...]
>> Ah, but here's where Jacob and I part ways again. C has *no*
>> mechanism for detecting stack overflow (sorry, "exhaustion of the
>> resources that keep track of auto variables and/or whatever's
>> needed to ensure that a function can return to its caller").
>
> Which C?
>
> POSIX has. Why is POSIX not considered as C?
Should comp.unix.programmer be eliminated and merged into comp.lang.*,
since all Unix programming is done in some language?
C is defined by the C standard. That's why it's called the C
standard.
--
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"
Keith Thompson
> =?UTF-8?q?Harald_van_D=C4=B3k?=:
>
>> It's called "tail call" optimisation, if you want to look it up, and in
>> this case, it's very easy for the compiler to do.
>>
>> In the general case, compilers do need something that can function as a
>> stack, but in your example, there is no need.
>
> I never write recursive functions unless I really really really really
> have to. In 95% of cases, you can just use a loop.
>
> For the cases though in which a loop won't do the job, I think you need
> a stack.
In other words, for recursive calls for which a tail-recursion
optimization can't be used (say, Ackermann's function), you need a
stack to implement the recursion. And since a stack is required in
this case, it's usually convenient for the implementation to use a
stack for (almost) all function calls (though optimizations are
possible for leaf functions, i.e., functions that don't call anything
else).
Yes, of course you need a stack, in the sense of a LIFO data
structure. You *don't* need what we've been calling a "hardware
stack", i.e., a contiguous region of memory that grows in a specific
direction and is typically managed via a dedicated hardware register
called a "stack pointer". The stack (LIFO data structure) can be
implemented in a number of ways; a "hardware stack" is merely one such
way. Another way is a linked list of heap-allocated activation
records, where different activation records are not necessarily
ordered in any particular way in memory.
The distinction between a "stack" (a generalized LIFO data structure)
and a "hardware stack" (a contiguous memory space) is exactly what
this whole argument is about. Ignoring that distinction is not
helpful.
Serve Lau
"Tomás Ó hÉilidhe" <t...@lavabit.com> schreef in bericht
news:Xns9A23E42D455...@194.125.133.14...
> I never write recursive functions unless I really really really really
> have to. In 95% of cases, you can just use a loop.
tail recursion can always be rewritten to a loop
Serve Lau
"jacob navia" <ja...@nospam.com> schreef in bericht
news:fmb711$r0b$1...@aioe.org...
> It would be interesting tha they AT LAST point out the implementations
> of C where there is "NO STACK"... Obviously implementations crippled
> beyond recgnition that do not implement recursion do NOT count.
I dont think this has been answered yet. I would love to know about a
"stackless" implementation that does support recursion.
Chris Hills
<cbfal...@yahoo.com> writes
>jacob navia wrote:
>> Eric Sosman wrote:
>>
>... snip ...
>>
>>> Ah, but here's where Jacob and I part ways again. C has *no*
>>> mechanism for detecting stack overflow (sorry, "exhaustion of the
>>> resources that keep track of auto variables and/or whatever's
>>> needed to ensure that a function can return to its caller").
>>
>> Which C?
>
>There is only one C - that described in the ISO C standard, or its
>antecedants. Once the language is extended, it is no longer
>portable C.
The fact it is not portable is not relevant.
You can write perfectly conforming C that is not portable.
--
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
\/\/\/\/\ Chris Hills Staffs England /\/\/\/\/
/\/\/ ch...@phaedsys.org www.phaedsys.org \/\/\
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
James Kuyper
>> There is only one C - that described in the ISO C standard, or its
>> antecedants. Once the language is extended, it is no longer
>> portable C.
>
> The fact it is not portable is not relevant.
>
> You can write perfectly conforming C that is not portable.
True, but should such code be on-topic here? The US declaration of
independence is conforming C code, because a conforming implementation
of C can, as an extension, accept it after issuing at least one
diagnostic message. I believe that a conforming implementation of C
which accepts all code which has no #error directives that survive
conditional compilation, always producing at least one diagnostic
message, has in fact been created. Should that fact be used as an excuse
for discussing the US revolutionary war in this newsgroup? Where do you
draw the line?
jacob navia
Why do we have to draw lines?
The same people that want strictly on topic messages discuss
British poetry for a week, or the wiring standards
for electrical circuits for a week.
We could discuss extensions to C, POSIX and other things that
concern C directly. comp.std.c is for discussing the standard
language.
James Kuyper
I believe it has been. The people who are saying that a stack is not
required are not using the word "stack" in the abstract sense of a
generic LIFO allocation mechanism. They are using it in the more
common, more concrete sense of the word, to refer specifically to
implementation of LIFO semantics by use of a single large block of
memory which grows and shrinks only at one end.
Real implementations have been described in this thread that don't
possess such a stack, using activation records which are allocated and
deallocated from locations in memory that are not in any particular
order. I don't see any reason why such an implementation should have any
trouble supporting recursion.
jacob navia
> Serve Lau wrote:
>>
>> "jacob navia" <ja...@nospam.com> schreef in bericht
>> news:fmb711$r0b$1...@aioe.org...
>>
>>> It would be interesting tha they AT LAST point out the implementations
>>> of C where there is "NO STACK"... Obviously implementations crippled
>>> beyond recgnition that do not implement recursion do NOT count.
>>
>> I dont think this has been answered yet. I would love to know about a
>> "stackless" implementation that does support recursion.
>
> I believe it has been. The people who are saying that a stack is not
> required are not using the word "stack" in the abstract sense of a
> generic LIFO allocation mechanism. They are using it in the more
> common, more concrete sense of the word, to refer specifically to
> implementation of LIFO semantics by use of a single large block of
> memory which grows and shrinks only at one end.
>
that started all this:
Repeat after me: "There is no stack in the definition of the C
Language"
Just that. No qualifiers, no "There is a stack that can be
implemented without a machine stack". JUST THAT.
Besides this is nonsense because even if you have a linear
stack it is based on memory pages this days, that are not
contiguous at all and scattered all around in real memory.
That is why I specified: <<The sentence "there is no stack"
is wrong>>
> Real implementations have been described in this thread that don't
> possess such a stack, using activation records which are allocated and
> deallocated from locations in memory that are not in any particular
> order. I don't see any reason why such an implementation should have any
> trouble supporting recursion.
Because they have a stack OBVIOUSLY!
If there is no hardware stack, the implementation does it with a
software stack BECAUSE C NEEDS A STACK.
I think we agree here with the basics. Lets agree then that the
sentence
"There is no stack in C"
is completely wrong.
The sentence:
C needs a stack and if there is no hardware stack it can
be implemented by other means.
is right.
OK?
Chris Hills
<james...@verizon.net> writes
>Chris Hills wrote:
>> In article <47895B9C...@yahoo.com>, CBFalconer
>><cbfal...@yahoo.com> writes
>...
>>> There is only one C - that described in the ISO C standard, or its
>>> antecedants. Once the language is extended, it is no longer
>>> portable C.
>> The fact it is not portable is not relevant.
>> You can write perfectly conforming C that is not portable.
>
>True, but should such code be on-topic here?
Yes... Now you want Pure ISO C that is completely portable?
James Kuyper
> James Kuyper wrote:
...
>> True, but should such code be on-topic here? The US declaration of
>> independence is conforming C code, because a conforming implementation
>> of C can, as an extension, accept it after issuing at least one
>> diagnostic message. I believe that a conforming implementation of C
>> which accepts all code which has no #error directives that survive
>> conditional compilation, always producing at least one diagnostic
>> message, has in fact been created. Should that fact be used as an
>> excuse for discussing the US revolutionary war in this newsgroup?
>> Where do you draw the line?
>>
>
> Why do we have to draw lines?
>
> The same people that want strictly on topic messages discuss
> British poetry for a week, or the wiring standards
> for electrical circuits for a week.
Wiring standards were originally brought into the discussion simply to
make an on-topic point about standards in general. After that, the
sub-thread drifted. Could you please identify any specific message on
that sub-thread after it drifted, posted by anyone who favors strict
topicality, which didn't include a statement that this was an
inappropriate place for such a discussion?
> We could discuss extensions to C, POSIX and other things that
> concern C directly. comp.std.c is for discussing the standard
> language.
No, comp.std.c is for discussing the language standard - what it means,
whether particular code strictly conforms with the standard, whether a
particular implementation technique is conforming, how it should be
changed, etc.. Discussions of how use the language defined by that
standard are off-topic on comp.std.c. People who want to discuss the
usage of standard C without raising any issues about the standard itself
are routinely re-directed to comp.lang.c.
Ben Bacarisse
You omitted (or glossed over) the fact the these blocks of memory must
be chained together. There are lots of slightly different ways to
this but they all result in a linked list of what are often called
"activation records". To many people, this can be called a stack,
even though the activation records are not contiguous in memory.
One poster said that they can't see how to implement recursion without
a stack, and you may have shown them something that they did not know
(that the activation records can be a non-contiguous linked list) but
whether or not this is a stack is to do with definitions. If everyone
who has posted had appended their definition of a stack, then I don't
think there would have been much of a thread -- except, perhaps, to
argue explicitly about the definitions. I don't think there is any
disagreement about the facts.
Obviously your definition of a call stack is that it must be
contiguous in memory when seen from the program's side of the VM
architecture, but the other point of view is also perfectly
reasonable. Of course, if you feel strongly about the *definition*
and want to have a debate about then, OK, but c.l.c is probably
not the best place. I don't feel strongly enough about the definition
to disagree with you (except to point out the missed chaining in your
otherwise very clear explanation) but I would not object to the other
definition (that there is always a call stack of some sort) either!
--
Ben.
James Kuyper
> In article <rynij.7960$W73.3553@trnddc04>, James Kuyper
> <james...@verizon.net> writes
>> Chris Hills wrote:
>>> In article <47895B9C...@yahoo.com>, CBFalconer
>>> <cbfal...@yahoo.com> writes
>> ...
>>>> There is only one C - that described in the ISO C standard, or its
>>>> antecedants. Once the language is extended, it is no longer
>>>> portable C.
>>> The fact it is not portable is not relevant.
>>> You can write perfectly conforming C that is not portable.
>>
>> True, but should such code be on-topic here?
>
> Yes... Now you want Pure ISO C that is completely portable?
No, I want this group to concentrate on questions about portable aspects
of the C language, leaving the non-portable aspects to be discussed by
other groups which are more competent to discuss them. This group has
way too many messages to be easily reviewed. If we could somehow
magically remove the off-topic messages, the complaints about the
off-topic messages, and the complaints about the complaints about
off-topic messages, it would be a much easier group to monitor. If I
want to learn about, for example, Microsoft-specific issues in C
programming, I'll look for a microsoft-specific newsgroup, I don't want
to see it here.
Serve Lau
"Keith Thompson" <ks...@mib.org> schreef in bericht
news:87wsqes...@kvetch.smov.org...
> Should comp.unix.programmer be eliminated and merged into comp.lang.*,
> since all Unix programming is done in some language?
>
> C is defined by the C standard. That's why it's called the C
> standard.
I always go to alt.bible.bashing when I have questions about bash
Malcolm McLean
"jacob navia" <ja...@nospam.com> wrote
>
> Why do we have to draw lines?
>
> The same people that want strictly on topic messages discuss
> British poetry for a week, or the wiring standards
> for electrical circuits for a week.
>
> We could discuss extensions to C, POSIX and other things that
> concern C directly. comp.std.c is for discussing the standard
> language.
>
For instance a biographical thread about Ada Lovelace would clearly be
off-topic here, but maybe OK on comp.programming.
However discussion about who was first to deprecate gotos, which is topical,
could easily lead to a discussion about Ada Lovelace, which would be
acceptable though not topical, becasue the discussion has naturally led to
that point.
CBFalconer
> <cbfal...@yahoo.com> writes
>> jacob navia wrote:
>>> Eric Sosman wrote:
>>>
>> ... snip ...
>>>
>>>> Ah, but here's where Jacob and I part ways again. C has *no*
>>>> mechanism for detecting stack overflow (sorry, "exhaustion of the
>>>> resources that keep track of auto variables and/or whatever's
>>>> needed to ensure that a function can return to its caller").
>>>
>>> Which C?
>>
>> There is only one C - that described in the ISO C standard, or its
>> antecedants. Once the language is extended, it is no longer
>> portable C.
>
> The fact it is not portable is not relevant. You can write
> perfectly conforming C that is not portable.
In some newsgroups, yes. However, this is c.l.c, and the subject
is the portable standardized C language. I believe you have been
so advised before. Note that you don't receive such topicality
corrections in c.a.e.
Keith Thompson
[...]
> If there is no hardware stack, the implementation does it with a
> software stack BECAUSE C NEEDS A STACK.
I agree, with two minor qualifications.
1. A compiler might generate code for a particular program without
using a stack if it can prove that the particular program doesn't need
recursion. A function for which there is never more than one active
call can have its activation record allocated statically. On most
systems, this is not a particularly useful optimization, but it might
be on some. So a compiler must be able to support a stack (a LIFO
data structure), but it needn't necessarily always use it.
2. There's no need to shout. The conventional way to denote emphasis
is to surround the emphasized text with *asterisks*. Too much
all-caps text makes my eyes bleed.
> I think we agree here with the basics. Lets agree then that the
> sentence
>
> "There is no stack in C"
>
> is completely wrong.
No, it is not completely wrong, it is merely unclear, especially if
you refuse to understand the writer's intent. The word "stack" is
commonly used to refer to a contiguous hardware stack of the kind that
we've discussed to death in this thread. It is perfectly true that
the word "stack" does not appear in the C standard, and that a C
implementation does not need to use a hardware stack.
Someone who says "There is no stack in C" is *clearly* using the word
"stack" in the sense of a hardware stack, not in the sense of a
general LIFO data structure. Such a statement is "completely wrong"
only if you reject the idea that the word "stack" can possibly have
that meaning. And yet posters here very commonly use the unqualified
word "stack" with *exactly* that meaning, particularly when referring
to "*the* stack". I wish they wouldn't, but they do.
Since we're trying to be agreeable, can you agree with the above?
> The sentence:
>
> C needs a stack and if there is no hardware stack it can
> be implemented by other means.
>
> is right.
Agreed.
> OK?
OK.
Keith Thompson
Please stop repeating this falsehood. comp.std.c is for discussing
the language standard.
Malcolm McLean
"Keith Thompson" <ks...@mib.org> wrote in message
> Someone who says "There is no stack in C" is *clearly* using the word
> "stack" in the sense of a hardware stack, not in the sense of a
> general LIFO data structure. Such a statement is "completely wrong"
> only if you reject the idea that the word "stack" can possibly have
> that meaning. And yet posters here very commonly use the unqualified
> word "stack" with *exactly* that meaning, particularly when referring
> to "*the* stack". I wish they wouldn't, but they do.
>
A perfectly reasonable way of explaining it is to say that the automatic
variables are stored on the stack, and the stack pointer is reset when the s
function returns, but the static variables are not.
That's a concrete image a person can get into their head, and it is close
enough to the truth. It's not the full truth of course. The "stack" may or
may not have some sort of hardware support, it might even be optimised to
nothing except in the case of recursive functions.
Where you do need to be more specific is if something thinks it is important
whether the stack grows upwards or downwards in memory, or wants to know how
to avoid stack overflow.
James Kuyper
No. It would be more accurate to say:
"The standard says nothing about stacks as such. What the standard says
about the lifetime of variables with automatic storage duration makes it
natural to implement them using the LIFO semantics of the stack that is
a commonplace feature of many computer architectures. However, the
standard does not mandate the use of such a stack; it doesn't even
mandate the LIFO semantics of an abstract stack, as the term is
understood in computer science."
Before you repeat that the claim, which has been frequently made in this
thread, that LIFO semantics are mandatory, please consider the following
implementation:
It allocates and deallocates space for activation records. It makes sure
that it always allocates a given record before the start of the lifetime
of the variables stored in that record, and it makes sure that it never
deallocates them until after the end of the lifetime of those
variables, but it does not always carry out the allocations and
deallocations in the same order as a LIFO mechanism would.
What requirement of the C standard would such an implementation violate?
Serve Lau
"James Kuyper" <james...@verizon.net> schreef in bericht
news:ILnij.7961$W73.1374@trnddc04...
> I believe it has been. The people who are saying that a stack is not
> required are not using the word "stack" in the abstract sense of a generic
> LIFO allocation mechanism. They are using it in the more common, more
> concrete sense of the word, to refer specifically to implementation of
> LIFO semantics by use of a single large block of memory which grows and
> shrinks only at one end.
>
> Real implementations have been described in this thread that don't possess
> such a stack, using activation records which are allocated and deallocated
> from locations in memory that are not in any particular order. I don't see
> any reason why such an implementation should have any trouble supporting
> recursion.
As has been pointed out, that is merely a software stack implementation. I
was really hoping for something completely different from a stack mechanism.
I dont really care if C calls it a stack or automatics or something else,
I'm just trying to learn something new.
jacob navia
>
> No. It would be more accurate to say:
>
> "The standard says nothing about stacks as such. What the standard says
> about the lifetime of variables with automatic storage duration makes it
> natural to implement them using the LIFO semantics of the stack that is
> a commonplace feature of many computer architectures. However, the
> standard does not mandate the use of such a stack; it doesn't even
> mandate the LIFO semantics of an abstract stack, as the term is
> understood in computer science."
>
Yes it does
int fn(void)
{
int a = 6;
}
int main(void)
{
a = 78;
fn();
}
Before the call to fn() the value of "a" is 78.
During the call to fn it is 6.
After the call to fn, the value of a REVERTS to its previous value
The last value defined is the first that goes away.
Last in, first out (LIFO)
i.e. a stack!
You can call a cat a feline, a domestic animal, and all that
is true but it remains a cat.
> Before you repeat that the claim, which has been frequently made in this
> thread, that LIFO semantics are mandatory, please consider the following
> implementation:
>
> It allocates and deallocates space for activation records. It makes sure
> that it always allocates a given record before the start of the lifetime
> of the variables stored in that record, and it makes sure that it never
> deallocates them until after the end of the lifetime of those
> variables, but it does not always carry out the allocations and
> deallocations in the same order as a LIFO mechanism would.
>
If variable "a" is not deallocated after the call to fn, this
would violate the standard and the C language of course!
The actual storage for that variable is never deallocated right away
in most implementations that use a hardware stack since
memory is allocated in pages, and remains allocated for some
indefinite time until the page is freed. That is why the following
works sometimes:
char *fn(void) { char a; return &a;}
If you experiment in different implementations of gcc, or other
compilers you will see that *sometimes* you can access the value
without crashing. But the fact that you can illegally access
some parts of the stack no longer valid doesn't mean there is
no stack. The same for your example.
> What requirement of the C standard would such an implementation violate?
None since it uses a stack.
Besides you have yet to answer the question about a SINGLE example of
a real implementation that doesn't use a stack!
Flash Gordon
> James Kuyper wrote:
<snip>
>> Real implementations have been described in this thread that don't
>> possess such a stack, using activation records which are allocated and
>> deallocated from locations in memory that are not in any particular
>> order. I don't see any reason why such an implementation should have
>> any trouble supporting recursion.
>
> Because they have a stack OBVIOUSLY!
<snip>
OK, so you consider such implementations to have a stack. So why did you
claim that such implementations where not relevant to the topic of
detecting stack exhaustion? After all, such implementations *can* run
out of memory, so their stack (which you consider them to have) can
become exhausted. Also tell me how your suggested method of taking the
difference in addresses of variables declared in main and in the current
stack frame will give any clue as to stack usage on such an implementation.
--
Flash Gordon
Richard Harter
<ks...@mib.org> wrote:
>jacob navia <ja...@nospam.com> writes:
>[...]
>> comp.std.c is for discussing the standard language.
>
>Please stop repeating this falsehood. comp.std.c is for discussing
>the language standard.
"Falsehood" is far too strong. "Infelicitous phrasing" would be
better, particularly since it is likely that English is not
Jacob's native tongue. He might have well meant that which you
more accurately phrased.
Be that as it may, the tendency of many usenet posters to cast
things in black and white is unfortunate and leads to an
unnecessarily abrasive venue of discourse. Some relish that sort
of brangling. I am quite convinced that you, however, are that.
Harald van Dijk
> James Kuyper wrote:
>> No. It would be more accurate to say:
>>
>> "The standard says nothing about stacks as such. What the standard says
>> about the lifetime of variables with automatic storage duration makes
>> it natural to implement them using the LIFO semantics of the stack that
>> is a commonplace feature of many computer architectures. However, the
>> standard does not mandate the use of such a stack; it doesn't even
>> mandate the LIFO semantics of an abstract stack, as the term is
>> understood in computer science."
>
> Yes it does
int a;
int g()
{
a = 8;
}
> int fn(void)
> {
> int a = 6;
g();
> }
>
> int main(void)
> {
> a = 78;
>
> fn();
> }
>
> Before the call to fn() the value of "a" is 78. During the call to fn it
> is 6.
The global object a is once set to 78, and once to 8 in the function I've
added. During the call to fn, it is not somehow set to 6. Rather, the
global object a cannot be accessed by name, and the local object a can
be. This is why g can access the global a even though the lifetime of the
local a hasn't ended.
> After the call to fn, the value of a REVERTS to its previous value
No, the value of the global object a was never changed by fn, so there's
nothing to revert.
> The
> last value defined is the first that goes away.
>
> Last in, first out (LIFO)
>
> i.e. a stack!
In the simplest cases, sure.
> You can call a cat a feline, a domestic animal, and all that is true but
> it remains a cat.
>
>> Before you repeat that the claim, which has been frequently made in
>> this thread, that LIFO semantics are mandatory, please consider the
>> following implementation:
>>
>> It allocates and deallocates space for activation records. It makes
>> sure that it always allocates a given record before the start of the
>> lifetime of the variables stored in that record, and it makes sure that
>> it never
>> deallocates them until after the end of the lifetime of those
>> variables, but it does not always carry out the allocations and
>> deallocations in the same order as a LIFO mechanism would.
>>
>>
> If variable "a" is not deallocated after the call to fn, this would
> violate the standard and the C language of course!
The local variable a does not have to be deallocated after the call to
fn. It merely ceases to be accessible by name, because it goes out of
scope. Its lifetime may be extended by the implementation for whatever
reason.
>> What requirement of the C standard would such an implementation
>> violate?
>
> None since it uses a stack.
Even if it doesn't consistently release objects in the reverse order of
allocation?
James Kuyper
> On Sun, 13 Jan 2008 08:23:22 -0800, Keith Thompson
> <ks...@mib.org> wrote:
>
>> jacob navia <ja...@nospam.com> writes:
>> [...]
>>> comp.std.c is for discussing the standard language.
>> Please stop repeating this falsehood. comp.std.c is for discussing
>> the language standard.
>
> "Falsehood" is far too strong. "Infelicitous phrasing" would be
> better, particularly since it is likely that English is not
> Jacob's native tongue. He might have well meant that which you
> more accurately phrased.
I think that's unlikely, from context. "language standard" would not fit
as a replacement for "standard language", when you consider then entire
message that the phrase occurred in.
Richard Harter
"You might very well think that ...
James Kuyper
> James Kuyper wrote:
>>
>> No. It would be more accurate to say:
>>
>> "The standard says nothing about stacks as such. What the standard
>> says about the lifetime of variables with automatic storage duration
>> makes it natural to implement them using the LIFO semantics of the
>> stack that is a commonplace feature of many computer architectures.
>> However, the standard does not mandate the use of such a stack; it
>> doesn't even mandate the LIFO semantics of an abstract stack, as the
>> term is understood in computer science."
>>
>
>
> Yes it does
>
> int fn(void)
> {
> int a = 6;
> }
>
> int main(void)
> {
> a = 78;
>
> fn();
> }
>
> Before the call to fn() the value of "a" is 78.
> During the call to fn it is 6.
>
> After the call to fn, the value of a REVERTS to its previous value
> The last value defined is the first that goes away.
>
> Last in, first out (LIFO)
>
> i.e. a stack!
The name 'a' refers to two different variables, depending upon context.
That's a matter of the scope of the variable name, not it's lifetime.
The compiler would probably use a stack to keep track of scopes at
compile time; that doesn't say anything about how memory is managed in
the running program at run time.
If your argument were valid, it would apply equally well even if both
variables were declared 'static'. I don't believe it's your intent to
claim that statically allocated memory also requires a stack mechanism.
The relevant issue is the lifetime of the variables, not their scope.
However, while the lifetime of the variable named 'a' in 'fn' has ended
when the function returns, there's nothing in the standard that requires
that the memory allocated for that variable be deallocated. Not when
it's lifetime ends, and not at any other time, either. The fact that
most implementations deallocate the space at the earliest possible time
is a matter of QoI, not a requirement of the standard.
If, for example, it's inconvenient on a given system to deallocate less
than 512 bytes, I could imagine an implementation which groups together
several functions requiring a total of less than 512 bytes of space for
all automatic variables. It allocates all of their activation records as
soon as any of those functions gets called, and it deallocates all of
their activation records at the same time, only when none of them are
associated with a currently executing function call.
>> Before you repeat that the claim, which has been frequently made in
>> this thread, that LIFO semantics are mandatory, please consider the
>> following implementation:
>>
>> It allocates and deallocates space for activation records. It makes
>> sure that it always allocates a given record before the start of the
>> lifetime of the variables stored in that record, and it makes sure
>> that it never deallocates them until after the end of the lifetime of
>> those variables, but it does not always carry out the allocations and
>> deallocations in the same order as a LIFO mechanism would.
>>
>
> If variable "a" is not deallocated after the call to fn, this
> would violate the standard and the C language of course!
Citation please?
Of course, that's not actually a problem, even if you did have a
supporting citation. The implementation I describe could delay
deallocation of the 'a' in fn() until after the deallocation of the 'a'
in main(). That wouldn't violate the requirement you assert (without
citation), because that deallocation would still be, as specified,
"after the call to fn". It just wouldn't be immediately after.
For dynamically allocated memory, the standard says "The free function
causes the space pointed to by ptr to be deallocated, that is, made
available for further allocation." There is no comparable requirement
for deallocation of automatic memory.
> If you experiment in different implementations of gcc, or other
> compilers you will see that *sometimes* you can access the value
> without crashing. But the fact that you can illegally access
> some parts of the stack no longer valid doesn't mean there is
> no stack. The same for your example.
True. The relevant feature that makes this NOT a stack is the fact that
the memory has not necessarily been been deallocated yet. Whether or not
it can be accessed by illegal constructs is irrelevant. The fact that
the activation records might be allocated in the order (main, fn) and
deallocated in that same order is what makes this not a LIFO, and
therefore not, even in the most abstract sense, a stack.
>> What requirement of the C standard would such an implementation violate?
>
> None since it uses a stack.
>
> Besides you have yet to answer the question about a SINGLE example of
> a real implementation that doesn't use a stack!
Real systems have been described (but not, I think, identified) which
don't use a stack in the commonplace sense of that word. That you insist
on ignoring the fact that this is the commonplace sense of the word is a
problem I can't do anything about.
The fact is, most of the people coming to this newsgroup with a question
about the 'stack' have a question which does not depend upon the
abstract concept of a stack, but rather on the far more concrete and
commonplace idea of a contiguous stack which grows and shrinks only at
one end, and the misconception that the C standard requires such a stack.
Keith Thompson
> James Kuyper wrote:
>> No. It would be more accurate to say:
>>
>> "The standard says nothing about stacks as such. What the standard
>> says about the lifetime of variables with automatic storage duration
>> makes it natural to implement them using the LIFO semantics of the
>> stack that is a commonplace feature of many computer
>> architectures. However, the standard does not mandate the use of
>> such a stack; it doesn't even mandate the LIFO semantics of an
>> abstract stack, as the term is understood in computer science."
>
> Yes it does
>
> int fn(void)
> {
> int a = 6;
> }
>
> int main(void)
> {
> a = 78;
>
> fn();
> }
It would be helpful if you'd use a valid program. You've declared an
object named ``a'' inside fn(). That object is not visible in main().
Presumably the ``a'' referred to in main() either is declared locally
to main(), or is declared outside any function. I'll assume you
intended it to be local to main(), i.e., that ``a = 78;'' should be
``int a = 78;''.
> Before the call to fn() the value of "a" is 78.
> During the call to fn it is 6.
>
> After the call to fn, the value of a REVERTS to its previous value
> The last value defined is the first that goes away.
The ``a'' declared in fn() and the ``a'' declared in main are two
different objects; the fact that they happen to have the same name is
not relevant. Nothing "reverts". The phrase ``the value of "a"''
means different things depending on the context.
[...]
> If variable "a" is not deallocated after the call to fn, this
> would violate the standard and the C language of course!
[...]
It depends on what you mean by "deallocated". It's not visible
outside fn(); that has nothing to do with deallocation.
Perhaps you could try to make your point more clearly.
Keith Thompson
> On Sun, 13 Jan 2008 08:23:22 -0800, Keith Thompson
> <ks...@mib.org> wrote:
>
>>jacob navia <ja...@nospam.com> writes:
>>[...]
>>> comp.std.c is for discussing the standard language.
>>
>>Please stop repeating this falsehood. comp.std.c is for discussing
>>the language standard.
>
> "Falsehood" is far too strong. "Infelicitous phrasing" would be
> better, particularly since it is likely that English is not
> Jacob's native tongue. He might have well meant that which you
> more accurately phrased.
I don't believe so. I believe that jacob meant exactly what he wrote,
that comp.std.c is for discussion of "the standard language". He's
made similar statements in the past. I stand by my use of the word
"falsehood", and I invite jacob to correct me if I've misunderstood
what he wrote.
Richard Harter
<ks...@mib.org> wrote:
>c...@tiac.net (Richard Harter) writes:
>> On Sun, 13 Jan 2008 08:23:22 -0800, Keith Thompson
>> <ks...@mib.org> wrote:
>>
>>>jacob navia <ja...@nospam.com> writes:
>>>[...]
>>>> comp.std.c is for discussing the standard language.
>>>
>>>Please stop repeating this falsehood. comp.std.c is for discussing
>>>the language standard.
>>
>> "Falsehood" is far too strong. "Infelicitous phrasing" would be
>> better, particularly since it is likely that English is not
>> Jacob's native tongue. He might have well meant that which you
>> more accurately phrased.
>[...]
>
>I don't believe so. I believe that jacob meant exactly what he wrote,
>that comp.std.c is for discussion of "the standard language". He's
>made similar statements in the past. I stand by my use of the word
>"falsehood", and I invite jacob to correct me if I've misunderstood
>what he wrote.
I have said what I said. If you choose not to listen, so be it.
Keith Thompson
I listened. I merely disagree.
CBFalconer
>
... snip ...
>
> However discussion about who was first to deprecate gotos, which
> is topical, could easily lead to a discussion about Ada Lovelace,
> which would be acceptable though not topical, becasue the
> discussion has naturally led to that point.
However the 'goto' subject is not topical, because gotos have never
been, and never will be, deprecated. :-) (Speaking topically, of
course.)
CBFalconer
> Keith Thompson <ks...@mib.org> wrote:
>> jacob navia <ja...@nospam.com> writes:
>
>>[...]
>
>>> comp.std.c is for discussing the standard language.
>>
>> Please stop repeating this falsehood. comp.std.c is for discussing
>> the language standard.
>
> "Falsehood" is far too strong. "Infelicitous phrasing" would be
> better, particularly since it is likely that English is not
> Jacob's native tongue. He might have well meant that which you
> more accurately phrased.
I disagree. Jacob has been informed of this many times, and yet he
persists in repeating the erroneous information.
CBFalconer
> James Kuyper wrote:
>
>> No. It would be more accurate to say:
>>
>> "The standard says nothing about stacks as such. What the standard
>> says about the lifetime of variables with automatic storage
>> duration makes it natural to implement them using the LIFO
>> semantics of the stack that is a commonplace feature of many
>> computer architectures. However, the standard does not mandate the
>> use of such a stack; it doesn't even mandate the LIFO semantics of
>> an abstract stack, as the term is understood in computer science."
>
> Yes it does
>
> int fn(void) {
> int a = 6;
> }
>
> int main(void) {
> a = 78;
> fn();
> }
>
> Before the call to fn() the value of "a" is 78.
> During the call to fn it is 6.
>
> After the call to fn, the value of a REVERTS to its previous value
> The last value defined is the first that goes away.
>
> Last in, first out (LIFO)
No. Revise your demo code slightly and make it legal:
int fn(int *p) {int a = 6; return (a == *p);}
int main(void) {int a = 78; fn(&a); return 0;};
and now both 'a's are visible in fn. There is no reverting done.
dS...@arcor.de
> ...
> The local variable a does not have to be deallocated after the call to
> fn. It merely ceases to be accessible by name, because it goes out of
> scope. Its lifetime may be extended by the implementation for whatever
> reason.
The implementation cannot extend the lifetime of an object as it is
defined in section "Storage durations of objects" (e. g. N1256, 6.2.4).
Wolfgang Draxinger
> [nonsense about the standard]
You're making the same error again: You mistake the C standard as
an implementation guide.
The C standard doesn't define the term "stack" bacause it is
irrellevant for the standard itself. The standard just defines
what a C compiler must understand, and what, in the end, the
result of the written code shall _do_.
The standard does NOT, I repeat NOT, define a particular way, how
the details of an implementation shall be implemented. Of course
a stack is the natural way to implement recursive function
calls, as it's the natural way to store the return address, to
where to jump when a function is left.
However if the term "stack" would have been included into the
wording of the C standard, this would imply, also to define all
the dirty details of how to do things on the stack within the
standard. Unfortunately the way, how a stack works can largely
differ between architectured. It would also mean, that
inevitably the language shall provide means to manipulate the
stack. This would however imply, that a language, that defines a
stack would be limited to the common denominator of stack
implementations across architectures, which however doesn't
exist: Have one architecture, which has a stack, that works
orthogonally to other architectures, and the standard would be
no longer architecture independent.
Or in other terms: Just because the C language standard doesn't
define the term stack this doesn't mean, that the authors
neglegted the existence of a stack. It just means, that the
concept of a stack is irrellevant within the well defined terms
of a programming _language_ definition. It doesn't tell anything
about the _runtime implementation_.
If you're fluent in mathematics take it this way: A mathematic
theorem doesn't define algorithms. But theorems give you the
definitions of the "mathematic standard", algorithms are
implementations based on them.
Wolfgang Draxinger
--
E-Mail address works, Jabber: hexa...@jabber.org, ICQ: 134682867
James Kuyper
True, the lifetime is very precisely defined by that clause. However,
the length of time that memory is reserved for an object is only
constrained by that clause, it is not completely specified. That clause
says that the "The _lifetime_ of an object is the portion of program
execution during which storage is guaranteed to be reserved for it."
Storage for an object with automatic storage duration can continue to
reserved even after the guarantee no longer applies - the standard says
nothing to prohibit such an implementation.
As a matter of QoI, any reservations of large amounts of storage space
should be canceled reasonably promptly after the end of an object's
lifetime, or your program is going to unnecessarily run out of memory,
but even QoI doesn't impose strict LIFO ordering as an absolute
requirement, just an optimization that could be omitted if for some
peculiar reason (I've already suggested one possibility), it isn't an
optimization on some particular platform.
The standard does say something to prohibit this for objects with
dynamic storage duration, but only in reverse: deallocation is what
causes the lifetime to end, not vice versa. There's no such wording for
objects with automatic storage duration.
Chris Hills
<james...@verizon.net> writes
>Chris Hills wrote:
>> In article <rynij.7960$W73.3553@trnddc04>, James Kuyper
>><james...@verizon.net> writes
>>> Chris Hills wrote:
>>>> In article <47895B9C...@yahoo.com>, CBFalconer
>>>><cbfal...@yahoo.com> writes
>>> ...
>>>>> There is only one C - that described in the ISO C standard, or its
>>>>> antecedants. Once the language is extended, it is no longer
>>>>> portable C.
>>>> The fact it is not portable is not relevant.
>>>> You can write perfectly conforming C that is not portable.
>>>
>> Yes... Now you want Pure ISO C that is completely portable?
>
>No, I want this group to concentrate on questions about portable
>aspects of the C language,
Well that is an even tighter and artificial restriction on this group
with is computer languages :- C not Standard C or god forbid only
portable standard C
That is up to you. I am sure people will discuss it with you. Others
have different interests in using C
> leaving the non-portable aspects to be discussed by other groups which
Not a chance.
> are more competent to discuss them. This group has way too many
>messages to be easily reviewed. If we could somehow magically remove
>the off-topic messages, the complaints about the off-topic messages,
>and the complaints about the complaints about off-topic messages, it
>would be a much easier group to monitor.
I agree... most of the messages are caused when people start shouting OT
stop the shouts of OT and
> If I want to learn about, for example, Microsoft-specific issues in C
>programming, I'll look for a microsoft-specific newsgroup, I don't want
>to see it here.
So would I . I look on the most appropriate NG but when some one says
"how do I do ABC" it is very helpful to say whell ther eis no STD way
of doing it but the various methods are a , b, c, d and A&B are used
mainly in windows C on macs and D on linux... then the OP and we all
learn something usfull.
Then when the OP says I have a MAC/windows/Linux they can go to the
specific NG for more in depth discussions.
However we all need to know what is outside our own specific box. Not in
detail but we need an awareness.
--
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
\/\/\/\/\ Chris Hills Staffs England /\/\/\/\/
/\/\/ ch...@phaedsys.org www.phaedsys.org \/\/\
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
Keith Thompson
> jacob navia wrote:
>
>> [nonsense about the standard]
>
> You're making the same error again: You mistake the C standard as
> an implementation guide.
>
> The C standard doesn't define the term "stack" bacause it is
> irrellevant for the standard itself. The standard just defines
> what a C compiler must understand, and what, in the end, the
> result of the written code shall _do_.
>
> The standard does NOT, I repeat NOT, define a particular way, how
> the details of an implementation shall be implemented. Of course
> a stack is the natural way to implement recursive function
> calls, as it's the natural way to store the return address, to
> where to jump when a function is left.
And yet another poster throws around the word "stack" without
specifying what it means. One more time, there are two distinct
definitions of the word "stack" in common use: a "hardware stack",
consisting of a contiguous region of memory managed by a "stack
pointer", and a "stack" in the computer science sense of a last-in
first-out data structure, which could be implemented in any of a
number of ways.
The distinction between these two meaning has become the focus of this
thread. Using the word "stack" without qualification merely causes
further confusion.
Kaz Kylheku
> In this group, there are a group of people that insists that "C doesn't
> use a stack" or that "C doesn't imply a stack" because there *could* be
> some obscure implementations somewhere in extremely small circuits
> where there is no hardware stack.
>
> As has been pointed out several times, the support of recursive
> functions in C implies a logical stack.
In proper C terminology, this is called ``automatic storage''.
One of the "implementations"
> this people presented, didn't implement recursion and can't be counted
> as a complete C implementation.
>
> The relevant part of the standard is (6.5.2.2.11):
>
> <quote>
> Recursive function calls shall be permitted, both directly and
> indirectly through any chain of other functions
> <end quote>
>
> Even if several people have pointed out the fact that the language
> implies a logical stack (recursion is part of the language), this
> people continue to answer in stupid messages like
>
> <quote>
> Repeat after me: "There is no stack in the definition of the C
> Language"
> <end quote>
Automatic storage can be implemented using dynamic allocation and
deallocation, rather than a stack.
Automatic storage does form a logical stack, in the sense of the word
when it is generalized to refer to any kind of LIFO structure in
computer science.
This is not what people mean by ``stack'' in the context of the
machine representations of programs; the term ``stack'' refers to a
linear block of memory where allocation and deallocation is performed
by moving a pointer.
> This fits in the general attitude of these people that like to
> show their detail knowledge instead of realizing that the overwhelming
> part of all C implementations use a hardware stack because the
> overwhelming majority of processors has a hardware stack.
That is false. Many modern processors have no special hardware support
for a stack. Some general-purpose register is designated by convention
to serve as a stack pointer, whose value is maintained using ordinary
arithmetic instructions, and which is indirected upon using ordinary
addressing modes. The memory region for the stack is allocated using
ordinary means also.
Maybe by ``overwhelming majority'' you are referring to the installed
base of X86 compatible processors.
jacob navia
Yes. IT could also be implemented by somebody going to the computer
store, buying some RAM, putting it in the machine and then
taking it away when the program exists that function...
But is it REALISTIC?
Do you know of a single C implementation that doesn't use a stack?
I asked this question two days ago and not a single answer came.
THERE IS NONE.
> Automatic storage does form a logical stack, in the sense of the word
> when it is generalized to refer to any kind of LIFO structure in
> computer science.
>
OK. That is what I was saying.
> This is not what people mean by ``stack'' in the context of the
> machine representations of programs; the term ``stack'' refers to a
> linear block of memory where allocation and deallocation is performed
> by moving a pointer.
>
All stacks have a stack pointer! Logical stacks ALSO.
>> This fits in the general attitude of these people that like to
>> show their detail knowledge instead of realizing that the overwhelming
>> part of all C implementations use a hardware stack because the
>> overwhelming majority of processors has a hardware stack.
>
> That is false. Many modern processors have no special hardware support
> for a stack.
Interesting. Can you name a single processor that doesn't have a
stack pointer?
> Some general-purpose register is designated by convention
> to serve as a stack pointer, whose value is maintained using ordinary
> arithmetic instructions, and which is indirected upon using ordinary
> addressing modes. The memory region for the stack is allocated using
> ordinary means also.
Like all hardware stacks that I know of.
Some processors have a stack register assigned by the hardware,
some processors have a stack register assigned by the OS. So what?
The end result is the same.
>
> Maybe by ``overwhelming majority'' you are referring to the installed
> base of X86 compatible processors.
I am referring to the fact that a hardware stack is needed
to save/restore registers and data across function calls in ANY
processor.
Unless the processor doesn't implement calls obviously.
All processors must use some way of saving/restoring the
program counter to be able to implement a function call.
It is amazing how the "regulars" manage to go on speaking nonsense
without ever answering a concrete question:
Where is the C implementation that doesn't use a stack?
Some implementations, lacking some hardware support for
a hardware stack use a software stack but ALL use a stack.
Please name a single one that doesn't use a stack.
Thanks
Lew Pitcher
You, of course, ignored the answers that said that there is such a
beast
> THERE IS NONE.
Wrong. Sorry
[snip]
> Where is the C implementation that doesn't use a stack?
IBM C/390
> Some implementations, lacking some hardware support for
> a hardware stack use a software stack but ALL use a stack.
>
> Please name a single one that doesn't use a stack.
IBM C/390
jacob navia
> You, of course, ignored the answers that said that there is such a
> beast
>
>> THERE IS NONE.
>
> Wrong. Sorry
>
> [snip]
>> Where is the C implementation that doesn't use a stack?
>
> IBM C/390
>
>> Some implementations, lacking some hardware support for
>> a hardware stack use a software stack but ALL use a stack.
>>
>> Please name a single one that doesn't use a stack.
>
> IBM C/390
In the starting message of this thread that apparently you did not read
I wrote:
<quote>
They use the ignorance of many people here about certain exotic
environments, like, for instance, the IBM Mainframes.
There is nothing more "big iron" that the IBM mainframes... at least
within my limited experience since I quit using that environment
in 1984.
The C compiler for the IBM mainframes is "C for VM/ESA", a C89
compiler.
We find in the users guide
http://publibfp.boulder.ibm.com/cgi-bin/bookmgr/BOOKS/cbcvpg00/CCONTENTS
3.1.4.3 Accessing Automatic Memory
Use the EDCDSAD macro to access automatic memory. Automatic memory is
reserved using the USRDSAL, or the DSALEN operand of the EDCPRLG macro.
The length of the allocated area is derived from the ulen and/or dlen
values specified on the EDCPRLG macro. EDCDSAD generates a DSECT, which
reserves space for the *stack frame* needed for the C environment.
<end quote>
I repeat: "... the stack frame needed for the C environment".
The documentation goes on to specify that register 13 (R13) is used to
address this memory.
And you go on telling nonsense as if you could get away with it.
Willem
) Kaz Kylheku wrote:
)> This is not what people mean by ``stack'' in the context of the
)> machine representations of programs; the term ``stack'' refers to a
)> linear block of memory where allocation and deallocation is performed
)> by moving a pointer.
)>
)
) All stacks have a stack pointer! Logical stacks ALSO.
But not all stacks do allocation/deallocation by *moving* the pointer.
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
Lew Pitcher
> Lew Pitcher wrote:
> > You, of course, ignored the answers that said that there is such a
> > beast
>
> >> THERE IS NONE.
>
> > Wrong. Sorry
>
> > [snip]
> >> Where is the C implementation that doesn't use a stack?
>
> > IBM C/390
>
> >> Some implementations, lacking some hardware support for
> >> a hardware stack use a software stack but ALL use a stack.
>
> >> Please name a single one that doesn't use a stack.
>
> > IBM C/390
>
> In the starting message of this thread that apparently you did not read
>
> I wrote:
>
> <quote>
> They use the ignorance of many people here about certain exotic
> environments, like, for instance, the IBM Mainframes.
> There is nothing more "big iron" that the IBM mainframes... at least
> within my limited experience since I quit using that environment
> in 1984.
>
> The C compiler for the IBM mainframes is "C for VM/ESA", a C89
> compiler.
>
>
> 3.1.4.3 Accessing Automatic Memory
> Use the EDCDSAD macro to access automatic memory. Automatic memory is
> reserved using the USRDSAL, or the DSALEN operand of the EDCPRLG macro.
> The length of the allocated area is derived from the ulen and/or dlen
> values specified on the EDCPRLG macro. EDCDSAD generates a DSECT, which
> reserves space for the *stack frame* needed for the C environment.
>
> <end quote>
>
> I repeat: "... the stack frame needed for the C environment".
>
> The documentation goes on to specify that register 13 (R13) is used to
> address this memory.
You've been fooled by IBM's terminology. R13 always points at the
"savearea", which is (as I described) a fixed-size block of memory,
chained between calls. That they call this activation record a "stack
frame" in the C documentation makes little difference to the
implementation, which is as I described it.
jacob navia
> jacob wrote:
> ) Kaz Kylheku wrote:
> )> This is not what people mean by ``stack'' in the context of the
> )> machine representations of programs; the term ``stack'' refers to a
> )> linear block of memory where allocation and deallocation is performed
> )> by moving a pointer.
> )>
> )
> ) All stacks have a stack pointer! Logical stacks ALSO.
>
> But not all stacks do allocation/deallocation by *moving* the pointer.
>
???
PUSH means
place this item at the location pointed by the stack
pointer and increase the stack pointer by the size of the item.
POP means retrieve the item at the location pointed by
the stack pointer and decrease the stack pointer by
the size of the item!
The stack pointer moves, nothing else. If you use a fixed
size stack (that can't grow) when the stack pointer can't
move beyond the specified area you have a stack overflow,
the question at the origin of the other thread.
jacob navia
> You've been fooled by IBM's terminology. R13 always points at the
> "savearea", which is (as I described) a fixed-size block of memory,
> chained between calls. That they call this activation record a "stack
> frame" in the C documentation makes little difference to the
> implementation, which is as I described it.
The documentation specifies also that the function prolog allocates
a stack frame of at least 120 bytes, and that the
function epilogue deallocates that storage.
This is a stack and if you want to name it "IBM SAVEAREA" I do
not care but it remains a stack!
Word games and more word games. Regulars do not know how to do
anything else!
Willem
) Willem wrote:
)> jacob wrote:
)> ) Kaz Kylheku wrote:
)> )> This is not what people mean by ``stack'' in the context of the
)> )> machine representations of programs; the term ``stack'' refers to a
)> )> linear block of memory where allocation and deallocation is performed
)> )> by moving a pointer.
)> )>
)> )
)> ) All stacks have a stack pointer! Logical stacks ALSO.
)> But not all stacks do allocation/deallocation by *moving* the pointer.
)>
)
) ???
)
) PUSH means
) place this item at the location pointed by the stack
) pointer and increase the stack pointer by the size of the item.
)
) POP means retrieve the item at the location pointed by
) the stack pointer and decrease the stack pointer by
) the size of the item!
)
) The stack pointer moves, nothing else. If you use a fixed
) size stack (that can't grow) when the stack pointer can't
) move beyond the specified area you have a stack overflow,
) the question at the origin of the other thread.
You're contradicting yourself.
Above you say "Logical stacks have a stack pointer".
Now you say "In/decrease the stack pointer by the size of the item",
which implies that a linked list is *not* a stack: It does
not have a stack pointer that moves in the way you describe.
Kaz Kylheku
> > deallocation, rather than a stack.
>
> Yes. IT could also be implemented by somebody going to the computer
> store, buying some RAM, putting it in the machine and then
> taking it away when the program exists that function...
No it couldn't. Consumer hardware currently does not support hot
pluggable memory.
> But is it REALISTIC?
>
> Do you know of a single C implementation that doesn't use a stack?
>
> I asked this question two days ago and not a single answer came.
>
> THERE IS NONE.
Induction hypothesis: if no answer came on day N, and no answer came
on day N + 1, then no answer will come on day N + 2.
Base case: no single answer came two days ago.
Therefore, there is no answer.
:)
> > Automatic storage does form a logical stack, in the sense of the word
> > when it is generalized to refer to any kind of LIFO structure in
> > computer science.
>
> OK. That is what I was saying.
Then you're basically arguing about the semantics of the word
``stack''.
When most confused newbies use the term ``stack'', they do not have
this generalized idea in mind.
> > This is not what people mean by ``stack'' in the context of the
> > machine representations of programs; the term ``stack'' refers to a
> > linear block of memory where allocation and deallocation is performed
> > by moving a pointer.
>
> All stacks have a stack pointer! Logical stacks ALSO.
That is false. A stack pointer is a device that is incremented and
decremented in order to push and pop individual words.
The reference to the top frame of a logical stack isn't such a stack
pointer. It's never called a ``stack pointer''.
> >> This fits in the general attitude of these people that like to
> >> show their detail knowledge instead of realizing that the overwhelming
> >> part of all C implementations use a hardware stack because the
> >> overwhelming majority of processors has a hardware stack.
>
> > That is false. Many modern processors have no special hardware support
> > for a stack.
>
> Interesting. Can you name a single processor that doesn't have a
> stack pointer?
MIPS family.
> > Some general-purpose register is designated by convention
> > to serve as a stack pointer, whose value is maintained using ordinary
> > arithmetic instructions, and which is indirected upon using ordinary
> > addressing modes. The memory region for the stack is allocated using
> > ordinary means also.
>
> Like all hardware stacks that I know of.
> Some processors have a stack register assigned by the hardware,
> some processors have a stack register assigned by the OS. So what?
When the stack register is assigned by the OS ABI, that means it's not
a ``hardware'' stack.
> > Maybe by ``overwhelming majority'' you are referring to the installed
> > base of X86 compatible processors.
>
> I am referring to the fact that a hardware stack is needed
> to save/restore registers and data across function calls in ANY
> processor.
Only a software stack is needed for this.
Some RISC processors only save minimal information to be able to
return from a subroutine call. That information is the return address,
and it goes into a register. Returning from the subroutine is done by
branching to the address stored in that register. No stack is
involved.
> Unless the processor doesn't implement calls obviously.
> All processors must use some way of saving/restoring the
> program counter to be able to implement a function call.
This simply requires a modified jump instruction which specifies a
register where the instruction pointer is stored. A regular indirect
jump is then used to perform the return.
> It is amazing how the "regulars" manage to go on speaking nonsense
> without ever answering a concrete question:
>
> Where is the C implementation that doesn't use a stack?
From the CINT documentation:
http://root.cern.ch/root/CintInterpreter.html
``[E]very object created by CINT is a heap object so CINT does not
need the distinction between heap and stack based objects.''
Kaz Kylheku
> Willem wrote:
> > jacob wrote:
> > ) Kaz Kylheku wrote:
> > )> This is not what people mean by ``stack'' in the context of the
> > )> machine representations of programs; the term ``stack'' refers to a
> > )> linear block of memory where allocation and deallocation is performed
> > )> by moving a pointer.
> > )>
> > )
> > ) All stacks have a stack pointer! Logical stacks ALSO.
>
> > But not all stacks do allocation/deallocation by *moving* the pointer.
>
> ???
>
> PUSH means
> place this item at the location pointed by the stack
> pointer and increase the stack pointer by the size of the item.
You mean decrease, if the stack grows downward.
> POP means retrieve the item at the location pointed by
> the stack pointer and decrease the stack pointer by
> the size of the item!
>
> The stack pointer moves, nothing else.
In another posting, you claim that /all/ stacks have a stack pointer,
whether they are linear stacks or just logical stacks.
So here you contradict yourself.
On a logical stack, you push a new frame like this:
1. allocate frame
2. store the current top as the value of the "next"
field of the new frame.
3. overwrite the top reference by a reference to the new frame.
You cannot push individual words onto this type of stack, only whole
frames. It is not meaningful to perform arbitrary pointer arithmetic
on the ``stack pointer'' of a logical stack (except to obtain
displacements in order to address the elements of the record).
Malcolm McLean
"Kaz Kylheku" <kkyl...@gmail.com> wrote in message
>> Interesting. Can you name a single processor that doesn't have a
>> stack pointer?
>
> MIPS family.
>
and I think it might even have had push and pop mnemonics. It's ages since I
coded anything for it.
However all the registers except register zero were in fact identical at the
hardware level, so if you insisted you could use t0 as your stack pointer
and sp as a temporary scratch register, making your code annoyingly
difficult to integrate with C callable functions, but who cares about that
when you've a game to write?
--
Free games and programming goodies.
http://www.personal.leeds.ac.uk/~bgy1mm
Kaz Kylheku
> The C compiler for the IBM mainframes is "C for VM/ESA", a C89
> compiler.
>
>
> 3.1.4.3 Accessing Automatic Memory
> Use the EDCDSAD macro to access automatic memory. Automatic memory is
> reserved using the USRDSAL, or the DSALEN operand of the EDCPRLG macro.
> The length of the allocated area is derived from the ulen and/or dlen
> values specified on the EDCPRLG macro. EDCDSAD generates a DSECT, which
> reserves space for the *stack frame* needed for the C environment.
>
> <end quote>
>
> I repeat: "... the stack frame needed for the C environment".
I can't find any information in that document which would confirm that
this EDCSAD generates a DSECT simply by displacing a stack pointer.
Kaz Kylheku
> Word games and more word games. Regulars do not know how to do
> anything else!
You're not only playing word games, you are losing. To yourself!
Randy Howard
(in article
<d0fbbe31-3c34-4e04...@d21g2000prf.googlegroups.com>):
> On Jan 14, 11:14 am, jacob navia <ja...@nospam.com> wrote:
>> Kaz Kylheku wrote:
>>> Automatic storage can be implemented using dynamic allocation and
>>> deallocation, rather than a stack.
>>
>> Yes. IT could also be implemented by somebody going to the computer
>> store, buying some RAM, putting it in the machine and then
>> taking it away when the program exists that function...
>
> No it couldn't. Consumer hardware currently does not support hot
> pluggable memory.
HP has at least one server platform that has hot add/remove RAID'ed
memory. It's a beast, but "consumers" can, by definition, by one.
--
Randy Howard (2reply remove FOOBAR)
"The power of accurate observation is called cynicism by those
who have not got it." - George Bernard Shaw
jacob navia
>> Jacob wrote: Interesting. Can you name a single processor that doesn't have a
>> stack pointer?
>
> MIPS family.
>
How many lies do I have to argue against?
http://dkrizanc.web.wesleyan.edu/courses/231/07/mips-spim.pdf
MIPS Assembly Language Programming
Page 49:
2. The callee must, as part of the function preamble:
(a) Create a stack frame, by subtracting the frame size from the stack
pointer ($sp).
Note that the minimum stack frame size in the MIPS software architecture
is 32 bytes, so even if you don't need all of this space, you should
still make your stack frames this large.
<end quote>
>>> Some general-purpose register is designated by convention
>>> to serve as a stack pointer, whose value is maintained using ordinary
>>> arithmetic instructions, and which is indirected upon using ordinary
>>> addressing modes. The memory region for the stack is allocated using
>>> ordinary means also.
>> Like all hardware stacks that I know of.
>> Some processors have a stack register assigned by the hardware,
>> some processors have a stack register assigned by the OS. So what?
>
> When the stack register is assigned by the OS ABI, that means it's not
> a ``hardware'' stack.
>
No, a HARDWARE register is a software stack :-)
WORD GAMES AND WORD GAMES. Regular do not know anything else
:-)
At least it is fun!!
>>> Maybe by ``overwhelming majority'' you are referring to the installed
>>> base of X86 compatible processors.
>> I am referring to the fact that a hardware stack is needed
>> to save/restore registers and data across function calls in ANY
>> processor.
>
> Only a software stack is needed for this.
>
> Some RISC processors only save minimal information to be able to
> return from a subroutine call. That information is the return address,
> and it goes into a register. Returning from the subroutine is done by
> branching to the address stored in that register. No stack is
> involved.
>
The power PC (the archetypal RISC) has a dedicated register
for maintaining the stack. (register 2 if I remeber correctly)
WRONG AGAIN!
>> Unless the processor doesn't implement calls obviously.
>> All processors must use some way of saving/restoring the
>> program counter to be able to implement a function call.
>
> This simply requires a modified jump instruction which specifies a
> register where the instruction pointer is stored. A regular indirect
> jump is then used to perform the return.
>
>> It is amazing how the "regulars" manage to go on speaking nonsense
>> without ever answering a concrete question:
>>
>> Where is the C implementation that doesn't use a stack?
>
> From the CINT documentation:
>
> http://root.cern.ch/root/CintInterpreter.html
>
> ``[E]very object created by CINT is a heap object so CINT does not
> need the distinction between heap and stack based objects.''
This produces that CINT is not C...
<quote>
# Scope:
+ Function scope
Variables can be declared in global or function scope.
Unlike ANSI, local variable has function scope. If a local variable is
once declared in a function, it will be alive until execution gets out
from the function even if it is declared within sub-block. In ANSI C,
local
variables have block scope.
void func()
{
int i;
for(i=0;i<10;i++) {
int n; /* block scope */
printf("n=%d\\n",n++);
}
/* n is still alive here in cint, n should be already
dead in ANSI C */
}
<end quote>
That's the problem with not having a stack maybe... ANSI C requires
a stack.
Other problems arise with variable argument functions. For the long
list of non standard features see
http://root.cern.ch/viewcvs/trunk/doc/limitati.txt?root=cint
Conclusion: This implementation is an embedded interpreter that
is not really standard. It shows how necessary a stack is for
a full implementation of C since many of the incompatibilities
arise from this fact.
WRONG AGAIN!
Disclaimer:
This message may contain polemic arguments, and in general
it looks sometimes that I have a great time arguing. This
is of course true (there is nothing more ridiculous than regulars
when they try to hide their incredible assertions: THERE IS NO
STACK IN C), but rest assured that I respect all participants
in this discussion and I mean no offense to anyone.
jacob navia
> I can't find any information in that document which would confirm that
> this EDCSAD generates a DSECT simply by displacing a stack pointer.
The documentation specifies also that the function prolog allocates
a stack frame of at least 120 bytes, and that the
function epilogue deallocates that storage.
Since R13 is dedicated to this... you can take your own conclusions!
robert...@yahoo.com
> Interesting. Can you name a single processor that doesn't have a
> stack pointer?
> Like all hardware stacks that I know of.
> Some processors have a stack register assigned by the hardware,
> some processors have a stack register assigned by the OS. So what?
> The end result is the same.
> I am referring to the fact that a hardware stack is needed
> to save/restore registers and data across function calls in ANY
> processor.
>
> Unless the processor doesn't implement calls obviously.
>
> All processors must use some way of saving/restoring the
> program counter to be able to implement a function call.
Many *processors* do not have stack pointers. S/360, most RISCs,
etc. That the local ABI often assigns a general purpose register for
such a task, is another matter. R13 on S/360, for example. There is
nothing special about R13, but the most common ABIs on the traditional
mainframe OS's use it as a pointer to the most recent save area
(reasonably though of as a partial activation record), which then has
a link to the prior save area (although the specified back link is
omitted on occasion, which typically doesn't break anything other than
debuggers). Clearly a CS LIFO/stack, but certainly not a processor or
hardware stack. For S/360 the R13 usage is only a convention, and you
can easily use R13 for other purposes, with the obvious restriction
that calling other code that expects you to be following the standard
ABI will be problematic. In fact, several C implementations on S/360
use R13 in a non-traditional manner to implement a more typical
"stack", and you have to do something special to call a program using
the traditional ABI (at which point the compiled code will thread its
way back into the traditional chain of save areas). At least one S/
360 C implementation used a separate GP register for the C "stack,"
and left (and wasted) R13 in its traditional role.
Many processors, again, S/360, most of the RISCs, implement calls by
saving the return address in a register, often a general purpose
register. The local ABI usually includes saving that in the current
activation record before issuing another call (and often that's
omitted in leaf functions). Again the ABI typically defines what
register gets used for the subroutine return address. On S/360 for
example, it's R15.
jacob navia
[snip very informative comments about several processors]
I agree with this. As I said in this same thread:
<quote>
Some processors have a stack register assigned by the hardware,
some processors have a stack register assigned by the OS.
The end result is the same.
<end quote>
It is just a matter of conventions. Even under the
x86 you can do arithmetic with the stack pointer,
and if you build an OS that uses another register
for the stack it would be difficult but maybe possible.
The stack is such a fundamental concept in computer architecture
however, that there is always some convention either dictated by
hardware or by the OS that will assign the stack management
to a special register.
My arguments were against people making sweeping blanket statement
like "There is no stack in C"...
That's all.
robert...@yahoo.com
> The stack is such a fundamental concept in computer architecture
> however, that there is always some convention either dictated by
> hardware or by the OS that will assign the stack management
> to a special register.
I still think that's too strong a statement. Probably *today* it's
basically true for general computing devices, but not for embedded
systems. In the past it was also untrue for many "serious" systems.
Consider that old Cobol or Fortran had no need of anything stack like,
and that was the primary workload of many machines. And given the
monolithic nature of many programs from that era, calling conventions
were often fairly well ignored, especially within a program. IIOW,
even on S/360, you'd only see the standard calling linkage/save areas
used when you called a Fortran subprogram from a Cobol one, not when
you called a Cobol subroutine from inside the same Cobol program, and
even then, it was typically completely static in nature - IOW, the
save area that the Cobol program needed to supply to the Fortran
program was statically allocated in the Cobol programs load image.
robert...@yahoo.com
> The power PC (the archetypal RISC)
Certainly PPC is *not* the archetypical RISC. Far from it, in fact.
PPC includes some very non-RISC-traditional elements. The ISA is also
rather a latecomer in the RISC arena.
> has a dedicated register
> for maintaining the stack. (register 2 if I remeber correctly)
No, it's actually a dedicated register in the branch unit (addressed
as SPR8) that hold the result of the last branch-and-link (subroutine
call). The branch unit also holds a dedicate count register used for
implementing "loop" like instructions. In both cases the application
has save/restore those as necessary (per the ABI) around subroutine
calls.
There is no hardware SP, the ABIs of most OS's do assign one of the
GPRs to SP duties, however.
Kaz Kylheku
Baloney. The above issue has nothing to do with stacks. It's simply a
parsing and name lookup issue. A conforming C compiler can let you
access n outside of the block where it is defined, provided that a
diagnostic is issued.
It's perfectly legitimate to treat an entire function scope as one
unit, such that all local variables are given unique locations within
the corresponding activation frame.
The simplest possible algorithm is to simply allocate local variables
in one big frame as the function body is parsed top to bottom.
Whenever a new declaration is parsed, regardless of the block scope in
which it appears, space is set aside and an entry is made under that
name in a symbol table. A name reference goes to the most recent
definition.
For conformance, all you need is to mark definitions out of scope so
that you can diagnose dangling name references.
C doesn't have true lexical scope (i.e. lexical closures) so issues of
instantiation of block scope locals don't matter.
If you could create a lexical closure within that for loop, then it
would matter, because on each iteration, your closure would want to
capture a different instance of n, yet each of these closures would
share the same instance of i.
(Needless to say, a C dialect supporting lexical closures wouldn't be
able to use a conventional flat stack for automatic storage).
> .. ANSI C requires a stack.
Except for the problem that the document doesn't even use the word. Of
course ISO C requires automatic storage: a way to have fresh instances
of local variables, and a way to remember how to get back to the
suspended parent function.
We can't really call this a stack, because not all instances of it
require anything like it.
For instance a trivial leaf function might be compiled into code that
uses registers for representing all local variables (including
incoming parameters), and which returns by branching to an address
which also came in a register, and which passes back a return value in
a register. Such a function effectively has no stack frame (even
though other functions in the same program might have one).
In the abstract language, though, the function has automatic storage.
In comp.lang.c we emphasize the abstract language, because this is the
best way to serve the needs of newbies in their quest for
enlightenment. They are confused by thoughts like ``there is something
called a stack, and a function always has a stack frame''.
> Other problems arise with variable argument functions.
Actually if you read it carefully, the issues are with foreign calls
to compiled variadic functions. For that to work, an architecture-
specific frame has to be generated. If you're calling something that
expects a stack, by golly, you have to set one up.
It doesn't appear to be an internal issue with CINT interpreted
funtions calling variadic CINT functions.
For the long
> list of non standard features seehttp://root.cern.ch/viewcvs/trunk/doc/limitati.txt?root=cint
It's actually quite a short list, which took only a few minutes to
read.
> Conclusion: This implementation is an embedded interpreter that
> is not really standard. It shows how necessary a stack is for
> a full implementation of C since many of the incompatibilities
> arise from this fact.
Outlandish claim.
Except for the foreign calling considerations, none of the other
issues in that list appear to be even remotely connected to how CINT
represents automatic storage.
Kaz Kylheku
> Kaz Kylheku wrote:
> >> Jacob wrote: Interesting. Can you name a single processor that doesn't have a
> >> stack pointer?
>
> > MIPS family.
>
> How many lies do I have to argue against?
>
> http://dkrizanc.web.wesleyan.edu/courses/231/07/mips-spim.pdf
> MIPS Assembly Language Programming
> Page 49:
> 2. The callee must, as part of the function preamble:
> (a) Create a stack frame, by subtracting the frame size from the stack
> pointer ($sp).
Except that not every callee must do any of this. Only callees that
take external function calls in a way that conforms to the ABI.
Within a module, you can do away with these calling conventions. A
private function need do nothing at all with the $SP register.
$SP itself just an assembler mnemonic for a numbered register that
behaves in a certain way if you follow the standard MIPS ABI. The
architecture itself doesn't dictate such use.
> Note that the minimum stack frame size in the MIPS software architecture
Right, the /software/ architecture.
Keith Thompson
> Kaz Kylheku wrote:
[...]
>> From the CINT documentation:
>> http://root.cern.ch/root/CintInterpreter.html
>> ``[E]very object created by CINT is a heap object so CINT does not
>> need the distinction between heap and stack based objects.''
>
> This produces that CINT is not C...
> <quote>
> # Scope:
> + Function scope
> Variables can be declared in global or function scope.
> Unlike ANSI, local variable has function scope. If a local variable is
> once declared in a function, it will be alive until execution gets out
> from the function even if it is declared within sub-block. In ANSI
> C, local
> variables have block scope.
>
> void func()
> {
> int i;
> for(i=0;i<10;i++) {
> int n; /* block scope */
> printf("n=%d\\n",n++);
> }
> /* n is still alive here in cint, n should be already
> dead in ANSI C */
> }
> <end quote>
The sample code invokes undefined behavior by examining the value of n
when it hasn't been initialized, and really doesn't demonstrate
anything about whether the implementation gets scoping right. I
suspect (but I'm only guessing) that the author misunderstood the
distinction between scope and lifetime.
If n is still *visible* after the closing "}" of the for loop, then
that's definitely a point of non-conformance. The *scope* of n ends
at the closing brace of the for loop. But sample code doesn't
actually do that.
Probably CINT allocates all automatic objects for a function in one
chunk when the function is entered, and doesn't do allocation on
entering a block or deallocation on leaving a block (other than the
outermost block of a function definition). But that's a perfectly
valid strategy, and it doesn't conflict in any way with the standard.
Both the lifetime and the scope of n end at the closing "}" of the for
loop, but the actual physical deallocation doesn't have to occur until
the end of the function, or perhaps even later.
> That's the problem with not having a stack maybe... ANSI C requires
> a stack.
The example demonstrates nothing like that.
> Other problems arise with variable argument functions. For the long
> list of non standard features see
> http://root.cern.ch/viewcvs/trunk/doc/limitati.txt?root=cint
According to that web page, variadic functions are supported, but with
some limitations, mostly having to do with interpreted vs. compiled
functions. Some of the problems are caused by the need to interface
to various underlying platforms. I see nothing about problems being
caused by the lack of a contiguous stack.
> Conclusion: This implementation is an embedded interpreter that
> is not really standard.
Agreed, but I see no fundamental reason why it couldn't be made to
conform fully to the standard (except that the authors probably don't
consider it to be worth the effort).
> It shows how necessary a stack is for
> a full implementation of C since many of the incompatibilities
> arise from this fact.
Not really.
[...]
Wolfgang Draxinger
> And yet another poster throws around the word "stack" without
> specifying what it means. One more time, there are two
> distinct definitions of the word "stack" in common use: a
> "hardware stack", consisting of a contiguous region of memory
> managed by a "stack pointer", and a "stack" in the computer
> science sense of a last-in first-out data structure, which
> could be implemented in any of a number of ways.
Still, the C language standard works well without defining any of
these. When I'm using the word "stack" in (most) of my posting,
then it may refer to anything, even to pink bunnies in a closet,
which the computer uses for data management ;-) - the
term "stack" is not defined by the C language standard.
It's like if I'm saying "vector", and everybody thinks of
n-tuples of numbers. But anything can be a vector, as long it's
defined in term of a vector space.
And in this case, anything can be a "stack", as long it fullfills
a certain set of operations.
> The distinction between these two meaning has become the focus
> of this thread. Using the word "stack" without qualification
> merely causes further confusion.
Such a distinction becomes important, when you implement a
runtime environment and a compiler. As long you only talk about
the language standard, "stack" is an abstract, and in case of
the C language redundant term, outside the scope of the language
definition.
Wolfgang Draxinger
--
E-Mail address works, Jabber: hexa...@jabber.org, ICQ: 134682867
Philip Potter
> Kaz Kylheku wrote:
>> Some RISC processors only save minimal information to be able to
>> return from a subroutine call. That information is the return address,
>> and it goes into a register. Returning from the subroutine is done by
>> branching to the address stored in that register. No stack is
>> involved.
>>
>
> The power PC (the archetypal RISC) has a dedicated register
> for maintaining the stack. (register 2 if I remeber correctly)
>
> WRONG AGAIN!
Using all-caps does not make you more correct.
I would agree with both points of view in this particular case. If we
look at the ARM (the only vaguely RISClike I'm familiar with), there is
a hardware stack (by convention) but it is not generally used for the
current function. The current function has access to r0-r3, and the
return address is in r14. If it needs more, it can save r4-10 to the
stack and use those. But the use of the stack is not guaranteed. So for
example:
int f(int n) {
int k = n + 1;
return k;
}
would be implemented as the following nonoptimized pseudoassembly:
ADD r1, r0, 1 ; n passed as r0, k stored in r1
MOV r0, r1 ; move k to r0, where the return value is expected
JMP r14
And it would be called (roughly) like so:
<save r0-r3 and r14 to stack, if necessary>
MOV r14, pc ; save program counter as return address
JMP f
So you are correct that a stack exists, but Kaz is correct that it is
not used at all by f(), and it is not necessary to use it in order to
call f - if registers need to be saved, they could be saved to static or
dynamic memory instead.
Lets assume for a moment that you are correct and that every C
implementation uses a hardware stack. What does that gain you? You still
can't say anything like:
"Local variables are stored on the stack"
"The return address is stored in the current stack frame"
"Calling a function changes the stack"
because f() does not satisfy any of these and yet there exist conforming
C implementations on ARM. On top of that, because there are so many
different ways a hardware stack can be organised, it really doesn't gain
you anything.
I have some sympathy for your point of view - almost every C
implementation probably does use a hardware stack, even though the
Standard doesn't require it - but I don't feel that such knowledge is
useful, so why assert it?
Malcolm McLean
> Kaz Kylheku wrote:
>> I can't find any information in that document which would confirm that
>> this EDCSAD generates a DSECT simply by displacing a stack pointer.
>
> The documentation specifies also that the function prolog allocates
> a stack frame of at least 120 bytes, and that the
> function epilogue deallocates that storage.
>
> Since R13 is dedicated to this... you can take your own conclusions!
>
generate op codes in the form
5 bits 5 bits 5bits bit for luck 16 bits
register A | register B | register C | |operation
(The details might be wrong, I'm working from memory here)
This simplified chip design. It also mean that you didn't have special
instructions like push / pop. Obviously you still had a program counter
register - the idea could be pushed only so far.
However you then have a set of conventions because assembly with register
numbers isn't terribly readable. One of these was that a register was
designated as the "stack pointer". Anohterh was that certain registers were
temporary and could be corrupted by leaf routines, whilst others had to be
preserved.
So you could write a tight little leaf routine that corrupted only the
temporary registers, and didn't need anything else except the jump back,
which was also in aregister designated by convention.
jacob navia
>
> I have some sympathy for your point of view - almost every C
> implementation probably does use a hardware stack, even though the
> Standard doesn't require it - but I don't feel that such knowledge is
> useful, so why assert it?
Because the original question was about stack overflow.
The "regulars" answer is
There is no stack in C. (The first answer from Mr Lew Pitcher.
I just said that this is not true, then a whole series of
wrong posts ensued, some of them trying to prove that
there is a "possible" C implementation that doesn't
use the stack, then they brought the IBM mainframes
argument (wrong) and then the Power PC argument (wrong too).
The only implementation that they could bring was a weird
C interpreter embedded in some CERN software that, as stated
in their own docs, is not standard.
I wat to bring an END to this deliberate leading astray
of people that ask questions with stupid answers like
"C doesn't use a stack".
Philip Potter
> Philip Potter wrote:
>> I have some sympathy for your point of view - almost every C
>> implementation probably does use a hardware stack, even though the
>> Standard doesn't require it - but I don't feel that such knowledge is
>> useful, so why assert it?
>
> Because the original question was about stack overflow.
> The "regulars" answer is
>
> There is no stack in C. (The first answer from Mr Lew Pitcher.
>
> I just said that this is not true, then a whole series of
> wrong posts ensued, some of them trying to prove that
> there is a "possible" C implementation that doesn't
> use the stack, then they brought the IBM mainframes
> argument (wrong) and then the Power PC argument (wrong too).
>
> The only implementation that they could bring was a weird
> C interpreter embedded in some CERN software that, as stated
> in their own docs, is not standard.
There are two issues here:
1) Does C require a stack? Does C require a hardware stack?
[This is the question Lew focused on]
This question is interesting because it relies only on the text of the
Standard, and tells something about all possible C implementations. The
Standard does not define the term "stack", as has been said, but we can
certainly make inferences from the text of the Standard. The Standard's
requirements on the lifetime of variables are very loose, and if the
implementation wishes, it can make every variable exist from the start
to the end of the program. Even the case of multiple instances of local
variables in a recursive function can be catered for when we realise
that C doesn't guarantee infinite recursion depth.
I can also imagine a C implementation which provides closures as an
extension and as a result has a "spaghetti stack" which is certainly not
a true stack. I believe this shows that C does not require a stack.
2) Do all conceivable reasonable C implementations use a stack?
[This is the question jacob has been focusing on]
This question is interesting because answering this question allows us
to make slightly more assumptions than the answer to the above question
does. (One similar question is "Do all conceivable reasonable C
implementations have the English alphabet in increasing numerical
order?" to which many people take the answer to be "yes" even though the
Standard does not require it.)
Unfortunately I feel this question is too general to answer a definite
"yes". Even if all reasonable C implementations today use a stack,
there's no reason one couldn't come along tomorrow which someone
(perhaps me!) may wish to port my code to.
A third issue is:
3) Even if all conceivable reasonable implementations use a stack, does
that gain me anything? (In other words, is it even worth bothering to
answer question 2?)
And for me the answer is definitely "no".
> I wat to bring an END to this deliberate leading astray
> of people that ask questions with stupid answers like
> "C doesn't use a stack".
The word is /require/, not /use/. And the C Standard does not require a
stack, though most implementations use one.
Chris Dollin
> jacob navia wrote:
>> Kaz Kylheku wrote:
>>> Some RISC processors only save minimal information to be able to
>>> return from a subroutine call. That information is the return address,
>>> and it goes into a register. Returning from the subroutine is done by
>>> branching to the address stored in that register. No stack is
>>> involved.
>>>
>>
>> The power PC (the archetypal RISC) has a dedicated register
>> for maintaining the stack. (register 2 if I remeber correctly)
>>
>> WRONG AGAIN!
>
> Using all-caps does not make you more correct.
>
> I would agree with both points of view in this particular case. If we
> look at the ARM (the only vaguely RISClike I'm familiar with), there is
> a hardware stack (by convention) but it is not generally used for the
> current function.
There's no "hardware stack", except in the sense that /any/ of
the registers (except PC) can be used as a stack pointer, and
/by convention/ one of them is used to point to the store used
to hold stackly things.
That register is "the" stack pointer because it's the one
selected by convention and so it makes sense to use it.
When it overflows, at least one ARM C compiler then grabs
a new chunk out of the heap: so automatic store is a bunch
of linked chunks each locally managed "by hardware" but
globally managed "by software", and there isn't just the
one contiguous region of store for "the stack" even within
a single application's user address space.
--
Far-Fetched Hedgehog
"Based on their behaviour so far -- I have no idea" /Sahara/
jacob navia
Interesting. The same holds for windows/linux and actually any OS using
virtual addresses!
Flash Gordon
> jacob navia wrote:
>> Philip Potter wrote:
>>> I have some sympathy for your point of view - almost every C
>>> implementation probably does use a hardware stack, even though the
>>> Standard doesn't require it - but I don't feel that such knowledge is
>>> useful, so why assert it?
>>
>> Because the original question was about stack overflow.
>> The "regulars" answer is
>>
>> There is no stack in C. (The first answer from Mr Lew Pitcher.
>>
>> I just said that this is not true, then a whole series of
>> wrong posts ensued, some of them trying to prove that
>> there is a "possible" C implementation that doesn't
>> use the stack, then they brought the IBM mainframes
>> argument (wrong) and then the Power PC argument (wrong too).
>>
>> The only implementation that they could bring was a weird
>> C interpreter embedded in some CERN software that, as stated
>> in their own docs, is not standard.
So if all implementations use a stack do you therefore accept that all
implementations are relevant to a thread about stack exhaustion? This is
a serious question because people have pointed out implementations which
have something that you would describe as a stack (based on the above)
but where the stack (if it is one) is not stored linearly.
> There are two issues here:
>
> 1) Does C require a stack? Does C require a hardware stack?
>
> [This is the question Lew focused on]
>
> This question is interesting because it relies only on the text of the
<snip>
> 2) Do all conceivable reasonable C implementations use a stack?
>
> [This is the question jacob has been focusing on]
<snip>
> Unfortunately I feel this question is too general to answer a definite
> "yes". Even if all reasonable C implementations today use a stack,
> there's no reason one couldn't come along tomorrow which someone
> (perhaps me!) may wish to port my code to.
>
> A third issue is:
>
> 3) Even if all conceivable reasonable implementations use a stack, does
> that gain me anything? (In other words, is it even worth bothering to
> answer question 2?)
>
> And for me the answer is definitely "no".
I will introduced a few more points...
My favourite, the TMS320C2xx series of processors *does* have a HW stack
although there is *no* stack pointer for it. Return addresses are pushed
on to it by the processor on a call, and popped off on a return. There
are also instructions to push data on to the stack and pop it off.
However, that stack is *not* used by the C implementation to implement
the "C system stack" (Texas Instrument's term) because it is only deep.
So for this implementation referring to "the stack" is *very*
misleading, because "the stack" is the HW stack that never overflows
because the C compiler ensures that return addresses are popped off it
before it has a chance and automatic variables are never stored on it.
Also, what about an implementation that uses two stacks, one for return
addresses and a separate stack for automatic variables? This could fully
conform and would have major advantages, such as preventing buffer
overflows from overwriting the return address. On such an implementation
what would you mean by "the stack"?
>> I wat to bring an END to this deliberate leading astray
>> of people that ask questions with stupid answers like
>> "C doesn't use a stack".
>
> The word is /require/, not /use/. And the C Standard does not require a
> stack, though most implementations use one.
True, although it is not always "the HW stack" when the processor has one.
--
Flash Gordon
Paul Hsieh
> On Jan 12, 12:13 pm, jacob navia <ja...@nospam.com> wrote:
> > This fits in the general attitude of these people that like to
> > show their detail knowledge instead of realizing that the overwhelming
> > part of all C implementations use a hardware stack because the
> > overwhelming majority of processors has a hardware stack.
>
> That is false. Many modern processors have no special hardware support
> for a stack.
What the hell are you guys arguing about? "Hardware support for a
stack" need not be anything more than an auto-incrementing/
decrementing memory register. And if you don't have such a thing, but
can increment/decrement the memory register in parallel in some free
pipeline, what the hell is the real difference? When talking about
general stacks, even the most hardwarish of hardware stacks is not
significantly distinguished form just rolling your own from scratch.
> [...] Some general-purpose register is designated by convention
> to serve as a stack pointer, whose value is maintained using ordinary
> arithmetic instructions, and which is indirected upon using ordinary
> addressing modes. The memory region for the stack is allocated using
> ordinary means also.
In the context of C, the only relevance is how this may or may not be
interleaved with the link register. I.e, does the auto-data mix with
return addresses. In non-failing code there shouldn't be a
difference, and there is a rare application that can take advantage of
this in any relevant way (one where you are rolling your own tasking,
perhaps.)
> Maybe by ``overwhelming majority'' you are referring to the installed
> base of X86 compatible processors.
Better add UltraSparc, Itanium and PDP/11 to the that list.
--
Paul
Paul Hsieh
> On Jan 14, 11:14 am, jacob navia <ja...@nospam.com> wrote:
> > > Automatic storage does form a logical stack, in the sense of the word
> > > when it is generalized to refer to any kind of LIFO structure in
> > > computer science.
>
> > OK. That is what I was saying.
>
> Then you're basically arguing about the semantics of the word
> ``stack''.
>
> When most confused newbies use the term ``stack'', they do not have
> this generalized idea in mind.
They don't? Since when do newbies know about hardware machine
implementations, but not basic data structures?
> > > This is not what people mean by ``stack'' in the context of the
> > > machine representations of programs; the term ``stack'' refers to a
> > > linear block of memory where allocation and deallocation is performed
> > > by moving a pointer.
>
> > All stacks have a stack pointer! Logical stacks ALSO.
>
> That is false. A stack pointer is a device that is incremented and
> decremented in order to push and pop individual words.
>
> The reference to the top frame of a logical stack isn't such a stack
> pointer. It's never called a ``stack pointer''.
Its not? What is it called then? (I would call it a "stack pointer",
or "logical stack pointer", since that's easier to say than "top of
stack reference".)
--
Paul
Kenneth Brody
[...]
> True, but should such code be on-topic here? The US declaration of
> independence is conforming C code, because a conforming implementation
> of C can, as an extension, accept it after issuing at least one
> diagnostic message. I believe that a conforming implementation of C
> which accepts all code which has no #error directives that survive
> conditional compilation, always producing at least one diagnostic
> message, has in fact been created. Should that fact be used as an excuse
> for discussing the US revolutionary war in this newsgroup? Where do you
> draw the line?
But, the Declaration of Independence dereferences the value "Creator"
without first initializing it, thereby invoking UB. It also makes
reference to the incomplete struct "unalienableRights"[1].
[1] Or would that be an enum?
--
+-------------------------+--------------------+-----------------------+
| Kenneth J. Brody | www.hvcomputer.com | #include |
| kenbrody/at\spamcop.net | www.fptech.com | <std_disclaimer.h> |
+-------------------------+--------------------+-----------------------+
Don't e-mail me at: <mailto:ThisIsA...@gmail.com>
Chris Dollin
> Chris Dollin wrote:
>> That register is "the" stack pointer because it's the one
>> selected by convention and so it makes sense to use it.
>> When it overflows, at least one ARM C compiler then grabs
>> a new chunk out of the heap: so automatic store is a bunch
>> of linked chunks each locally managed "by hardware" but
>> globally managed "by software", and there isn't just the
>> one contiguous region of store for "the stack" even within
>> a single application's user address space.
>
> Interesting. The same holds for windows/linux and actually any OS using
> virtual addresses!
That only matters if you think that the /physical/ memory address
has anything to do with the point, and in spite of the fact that
an OS using virtual addresses would be free to allocate /contiguous/
physical memory to a single process -- as, if I recall correctly,
some of them did.
Whether something is a "stack" or not is a point of view, and like
all points of view matters mainly in the light of what difference
it makes to what is done. If one thinks that X is likely to think
a "stack" is a contiguous sequence of memory locations with a
distinguished "top" pointer, then one can correctly -- and perhaps
wisely -- tell them that C doesn't /require/ a stack for its
automatic variables. If you think X has a more abstract, behavioural
view of what a stack "is", then you can say, yes, C's requirements
for automatic variables are exactly those of a stack, although
some C programs don't require the run-time pushing and popping
that would imply.
I think it's Keith that's been insisting we should distinguish
stack (the ADT) with stack (contiguous memory + pointer); to
which I say, +1, brother.
/I/ think that people who come here and ask about C and "the
stack" are, usually, thinking of the contiguous-memory thing
with An Important Stack Pointer, and so deserve -- gentle --
illumination and perhaps asking /why/ they're asking, because
it really makes a difference.
--
Knickers Not Twisted Hedgehog
A rock is not a fact. A rock is a rock.
robert...@yahoo.com
> Also, what about an implementation that uses two stacks, one for return
> addresses and a separate stack for automatic variables? This could fully
> conform and would have major advantages, such as preventing buffer
> overflows from overwriting the return address. On such an implementation
> what would you mean by "the stack"?
FWIW, all C implementations for IPF that I'm aware of do just that
(it's possible to not use the RSE in IPF, I just don't know of anyone
who's done that). Although in that case it's all of the integer
registers which are saved on the separate register stack (and the
return address is saved there since return addresses are stored in
registers by the subroutine calls).
SPARC is the same way, although the details of the register windows
stack are a bit different.
In both cases registers are lazily saved to the (register) stack only
when the hardware runs out of registers.
As a general comment, a lot of this discussion revolves around the
overloading of the term stack. Let's all talk about the definition of
a heap next, OK?
The semantics of subroutine calls in C clearly require automatics to
behave in a LIFO manner, and it's perfectly reasonable to call the
current thread of activation records, no matter the implementation, a
stack. If the compiler can determine that no recursion is going to
occur, it could plausible allocate all of the storage for automatics,
parameters, register save areas, and return address save areas
statically, and leave no code that "manages" any sort of stack
structure, or manages a "stack" only for the parts of a program that
can be used recursively. But even then the logical structure of the
currently active activation records is that of a LIFO or stack.
A number of older languages made recursability (is that a word?) an
optional attribution of a function. PL/1, for example, required that
you tag any recursive functions with "recursive" - and storage for all
other functions was typically allocated in a purely static fashion.
Which brings up the real question, is that knowledge useful in any
way? Probably only for reasons that exist outside of the C standard -
interfacing to other languages, debugging, etc.
james...@verizon.net
> > When most confused newbies use the term ``stack'', they do not have
> > this generalized idea in mind.
>
> They don't? Since when do newbies know about hardware machine
> implementations, but not basic data structures?
Most of the newbies I've known were much better informed about machine
architecture (for one particular kind of machine) than about abstract
data structures. YMMV.
james...@verizon.net
> James Kuyper wrote:
> [...]
> > True, but should such code be on-topic here? The US declaration of
> > independence is conforming C code, because a conforming implementation
> > of C can, as an extension, accept it after issuing at least one
> > diagnostic message. I believe that a conforming implementation of C
> > which accepts all code which has no #error directives that survive
> > conditional compilation, always producing at least one diagnostic
> > message, has in fact been created. Should that fact be used as an excuse
> > for discussing the US revolutionary war in this newsgroup? Where do you
> > draw the line?
>
> But, the Declaration of Independence dereferences the value "Creator"
> without first initializing it, thereby invoking UB. It also makes
> reference to the incomplete struct "unalienableRights"[1].
Code containing undefined behavior cannot qualify as "strictly
conforming", but that's no barrier to qualifying as "conforming".
Syntax errors and constraint violations are no problem either. The
only thing that is problematic is a correctly formatted #error
directive, and the Declaration contains not a single one of those.
This renders the term "conforming code" almost completely pointless,
but that was recognised when the current definition of that term was
first created. It was a political compromise whose only value lies in
the fact that it was a political necessity in order to get the
standard to be approved.
Most C extensions are implemented by having the implementation define
specific behavior for code which the C standard specifies as having no
defined behavior. Invoking, for instance, a spell checker rather than
a compiler in such cases would be a perfectly legitimate extension for
a conforming implementation of C.
Kelsey Bjarnason
On Sun, 13 Jan 2008 20:39:27 +0100, jacob navia wrote:
> Yes it does
>
> int fn(void)
> {
> int a = 6;
> }
>
> int main(void)
> {
> a = 78;
>
> fn();
> }
fixing that somewhat:
void fn(void)
{
int a = 6;
}
int main(void)
{
int a = 78;
fn();
return 0;
}
> Before the call to fn() the value of "a" is 78.
> During the call to fn it is 6.
Not as written. Before the call to fn, _a variable's_ value is 78.
During the call to fn, _another variable's_ value is 6. A hypothetical
compiler could do the job thusly (intermediate code stage):
.fn
fn_a = 6
jump reg_r
.main
main_a = 78
reg_r = @end
jump @fn
.end
...
The compiler creates two entirely different variables - fn_a and main_a -
then stores a "return address" in a register and does an absolute jump to
fn, followed by an absolute jump to the address in reg_r - the return.
Different contexts, different variables, different functions, call and
return - and not a stack needed anywhere.
Not sure what the example was supposed to prove, but if it was anything
relevant to the requirement of a LIFO structure, it failed.
CBFalconer
> James Kuyper <james...@verizon.net> writes
>
... snip ...
>>
>> No, I want this group to concentrate on questions about portable
>> aspects of the C language,
>
> Well that is an even tighter and artificial restriction on this
> group with is computer languages :- C not Standard C or god
> forbid only portable standard C
No, it isn't 'tighter'. The ISO standard is known. Arbitrary
extensions and deviations are unknown. When a program will run on
any system that meets that standard, it can be expected to run on
all such systems. It is simply a necessary characteristic for
portability.
--
[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