The machine stack and the C language

[jacob navia]

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

 

[Malcolm McLean]

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

I am not sure about that. Z80 processors do have push and pop instructions,
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.

 

[Ben Pfaff]

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.

 

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

 

[jacob navia]

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

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]

Why is POSIX not considered as C?

It is C. But not part of the core language. The Indians who post homework
questions here about Turbo C will have no access to it, for example.

 

[Willem]

jacob wrote:
) 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]

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:

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

 

[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]

=?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.

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

 

[Malcolm McLean]

I never write recursive functions unless I really really really really
have to. In 95% of cases, you can just use a loop.

I use recursion whenever the data structure is a tree, or, as in my Basic
interpreter, a disguised tree.

 

[Flash Gordon]

jacob navia wrote, On 12/01/08 20:13:

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.

 

[J. J. Farrell]

jacob navia:


You make a brilliant point Jacob. Taking the following program:

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

 

[Tim Smith]

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.

 

[CBFalconer]

Eric Sosman wrote:
.... snip ...


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.

 

[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]

CBFalconer said:

There is only one C - that described in the ISO C standard, or its
antecedants.

That's already at least three Cs.

 

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

 

[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]

=?UTF-8?q?Harald_van_D=C4=B3k?=:


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.