The machine stack and the C language

[jacob navia]

In proper C terminology, this is called ``automatic storage''.

One of the "implementations"

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

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.

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]

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.

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]

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.


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]

You, of course, ignored the answers that said that there is such a
beast

Wrong. Sorry

[snip]
Where is the C implementation that doesn't use a stack?

IBM C/390

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 guidehttp://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.

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]

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


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

 

[CBFalconer]

.... snip ...

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.

/* (Ignoring malloc failures) */

typedef struct item {
struct item *last;
void *data;
} item;

item *stktop = NULL;

void push(void *datum) {
item *temp;

temp = malloc(sizeof temp*);
temp->last = stktop; temp->data = datum;
stktop = temp;
} /* untested */

/* ----------------- */

void *pop(void) {
item *temp;
void *val;

temp = stktop;
stktop = temp->last; val = temp->data;
free(temp);
return val;
} /* untested */

I see no 'increase the stack pointer'. I see no 'place item at
stack pointer location'. I see no 'decrease the stack pointer'.
Barring my silly errors, I see no reason for the above code to
fail. Popping an empty stack is an error. Pushing when malloc
fails is an error.

 

[Kaz Kylheku]

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.

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.

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

Interesting. Can you name a single processor that doesn't have a
stack pointer?

MIPS family.

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.

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]

???

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

 

[gregk]

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!

C programmers tend to be an anal-retentive bunch.

Actually, most programmers are that way.

TRUE STORY -- THE GREAT "SPACE" WAR: Some months back a programmer where I
work almost got fired because he refused to indent in multiples of exactly
three spaces. He thought his code was easier on the eyes if he used five
spaces; the lead programmer begged to differ. A war of wills developed,
escalated, spread like cancer, and culminated in about half the coding
staff refusing to do anything the lead told them to do. A mutiny,
essentially. This caught the attention of management very soon, because
projects began slipping. A huge closed-door meeting was held, wherein the
CTO himself basically kicked the whole department's collective ass: The
programming lead, his supervisor, and roughly a quarter of the other
programmers were all fired. Some of the survivors swapped seats with QA
staff (the guy who likes spaces is now the QA lead). Newbie programmers
were hired to replace the castoffs. Fun times.

/glad not to be a professional coder

 

[Malcolm McLean]

MIPS family.

Sort of and kind of. There is a register which is conventionally called "sp"
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?

 

[Kaz Kylheku]

The C compiler for the IBM mainframes is "C for VM/ESA", a C89
compiler.

We find in the users guidehttp://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".

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]

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.

 

[jacob navia]

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.

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

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!

 

[robertwessel2]

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]

(e-mail address removed) wrote:
[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.