What is a stack?

[Tim Harig]

the point is you can write C programs without knowing the deatils of
the stack layout (or even if it has a contiguous in memory stack) for
your particular implementation. You can even write programs not

I would almost agree with you. I agree that in theory programming in C
should theoretically not require any knowledge of memory models or stack
implementation details. Most of the time it is probably a moot point.

However, since stacks *may* have limitations imposed beyond what is
available in physical memory, it is possible to write 100% bug free,
standards complient code that still crashes because it overflows the
stack.

Imagine yourself as a "newbie" who has just had their program crash, not
because they wrote a bug in their code, but because in their implementation
there code overflowed the stack. What is your likely reaction? Would you
know how to find the problem? If you didn't know the program stack
existed, much less that it might be limited, how would you know to check
to see if it might have overflowed? You might even notice that it happens
when using larger data sets with higher levels of recursion; but, you can
see that your system still has plenty of memory left.

your particular implementation. You can even write programs not
knowing what the program is going to run on. Newbie questions are

Assuming you are careful not to use large amounts of local memory and avoid
using recursive algorithms this is probably true; but, that you do so
probably means that you know that these things help to prevent stack
overflows. Somebody who isn't aware of the problem might not have the same
instincts.

This is particularly true of those who come from languages that emphasize
the use of recursive algorithms, which is often true of those languages
that where designed in academic settings and tend to be highly based on
mathematical constructs.

It is also possible to be quite unaware of how much memory one is
actually creating locally. One of the reasons that some people do not
like typedefs is that type definitions of large structures (or objects in
OOP languages) may lure people into allocating them locally not realizing
how large the structures actually are.

knowing what the program is going to run on. Newbie questions are
often an indication of an unhealthy interest in implementation
details. Knowing how it /could/ be implemented can be useful just so

It is my experience that people make better decisions when they have better
information. This is true on the factory floor where having some idea of
what the next person down the line will encounter from your work may cause
you to lay the product in a different position that will be easier for them
to work with and it is true of programming where having some small idea
of what lies beyond the abstraction layers can help you make better
decsions in how you make use of that abstraction in your code.

details. Knowing how it /could/ be implemented can be useful just so
long as no one walks away thinking it /must/ be implemted that way.

I agree 100% and I don't expect people to be experts in their systems
implementation details. Knowing different ways in which stacks might be
implemented, what complications each may cause, and knowing what your
target implemenations may use can be valuable information.

Do you really look at the hardware stack when your program crashes? I
use a debugger. The last time I looked at a stack as a contiguous
series of memory elemts it was was running on a 680x0... ('20? '10?).
We weren't allowed to sell 68030s in some countries then...

1. I run my code through a debugger using test data whether or not
it crashes. It lets me see how my code is actually being used.

2. Its not uncommon for me to keep my eye on the stack dump to make sure
everything is working properly. I can often see problems before
they ever manifest any symptoms.

3. I don't always look at the stack in a dump format. More often I look
at the stack trace which automagically breaks it down into the
variables, types, and translated data of the variables that have
been pushed onto it as well as the address and identity of the
calling functional location. I know how my stack is organized
so if I see something corrupted, I can usually make a guess as
to what has overflowed and track back the cause of the overflow
from there. The stack trace ouput format does not however show
the magic numbers used for testing and protection of stack frame
boundries if they have been requested so it is occasionally
useful to see the stack in its full glory.

 

[Nick Keighley]

this why people say C doesn't have a stack...

With a linked list it is sometimes easier to implement a stack of
variable sized objects. Also, the stack doesn't have to be contiguous
in memory, which means that expensive reallocation and copy operations
aren't needed to expand the buffer when it overflows.

also you could reuse the space when the stack is empty. The "nodes"
could be reused elsewhere. You might have mutiple stacks or queues.

 

[Nick Keighley]

i speak about one array of pointers, that can be reallocated easy

its easy but realloc() (or whatever) can be expensive.

and each cell of that array can point each memory you want; it is always array

tou've complicated the implementation beyond a simple array.Yes the
linked list is a complication as well but its a trade off depending on
the circumstances. The nice thing about using an abstract definition
of "stack" is that you can hide the implementation from the rest of
the program. Then the stack inplementation can be changed if
necessary.

yes the only restriction that the array of pointers has to be "contiguous"

i prefer a fixed size array, and push can fail (in the same way pop can fail
if stack is empy)
but possibly not know very much the argument

it depends on the circumstances. If you /know/ you have a fixed
maximum stack depth (simple parser for example) then a fixed sized
stack may be fine. If you're implementing a programming language that
allows recursion then a fixed stack may not be adequate.

You could implement a stack as a linked list of blocks of entries. A
bit like C++'s deque.

 

[Nick Keighley]

yes. I'm one of them. With new constucts I like to think about how it
might be implemented. In some pseudo assembler of these days low level
C. But once I have that concrete representation squared away I try
think about things more abstractly. To me automatic variables are all
hovering in their own little address space.
to ask (as people do!) if this

int x, y;
int *p = &x;
*(p + 1) += 1;

increments y (assuming I din't make any damn fool mistakes) shows a
serious violation of the abstraction provided by C.

Certainly different people have different ways of understanding
things.

Speaking for myself, it's enough to understand that storage for
called functions is "pushed" when the function is called and "popped"
when it returns (this implies a stack-like data structure but
says nothing about how the storage is allocated).  Knowing whether
successive allocations occupy monotonically increasing or decreasing
storage locations is not something I find particularly helpful.
My mental model of the call stack is more like a linked list than
an array.

I can see that others might find the whole thing easier to
understand if they assume a contiguous stack.  But IMHO that way
of thinking is dangerously close to treating addresses and integers
as interchangeable.  It's also easy to assume that the stack grows
in a particular direction.  And, on some unusual platforms, it's
just wrong.

they are also in for a fun time when they try a language with first
class continuations in it

I suggest that trying to think of it more abstractly is worth
the effort.  Not only is it closer to what the language actually
specifies, it can help you understand why a contiguous stack is
a good way of implementing it (as well as why it's not the only
possible implementation).

yes

 

[Seebs]

yes. I'm one of them. With new constucts I like to think about how it
might be implemented. In some pseudo assembler of these days low level
C. But once I have that concrete representation squared away I try
think about things more abstractly. To me automatic variables are all
hovering in their own little address space.
to ask (as people do!) if this

int x, y;
int *p = &x;
*(p + 1) += 1;

increments y (assuming I din't make any damn fool mistakes) shows a
serious violation of the abstraction provided by C.

Right. Someone who's stuck on the "stack" model will be pretty sure that:

int x = 0, y = 0;
int *p = &x, *q = &y;
*(p + 1) = 2;
*(q + 1) = 2;

is going to have set either x or y to 2. After all, one of them has to be
after the other.

Someone who's adopted a model like yours will be aware that it is certainly
possible that:
*(p + 1) = 2;
will in fact change the value of a local variable declared in a completely
different function which called a function which called a function which
called a function which called this one.

Or dump core.

I think this is a much better model.

-s

 

[Nick Keighley]

Buon Giorno
ciao


all program here, in C or in C++ with Borland compiler, or in asm, here seems
to have one fixed min stack size;

again you're taling about "the hardware stack". I'm talking about the
computer science data abstraction called "a stack". The hardware stack
on a typical processor is an implementation of a computer science
stack but there are other ways to do it.

it is the OS that allow that, right?

many processors provide a hardware stack and many OSs provide you with
a fixed size stack. With virtual memory its possible to have an
expanding stack that exceeds physical memory (whether that's a good
idea is another question...)

i think even the compiler have max stack size and can go to seg faul
due to not see if stack is full

i like the fixed min stack size, with the add that recursion functions can
fail due to stack full (and so return one error). Don't know if my english is
ok...

your english is fine

i don't know the argument, my experience is only about a stack-queue
in fixed size

what's a "stack-queue"?

(used like qeue for a server program);
if i have some stack problem that can not be in resolution by
that
i could think something different, but in each case push() can fail
because malloc() can fail (or because stack is full [if fixed size stack]) ...

I'm not sure what your question is (or even if you have one!)

 

[robertwessel2]

it is one array with the functions
push pop to the head, push pop to the tail

That's usually known as a "double ended queue" or "deque." A stack (a
LIFO structure) and a queue (a FIFO) each provide a (different) subset
of the functionality of a deque. IOW, if you restrict yourself to
pushing and popping at different ends of the deque, you have a queue,
if you push and pop at the same end, you have a stack.

Whether a deque is implemented as an array, or (more commonly) a
doubly linked list, is irrelevant.

 

[Nick Keighley]

this is the best I coule find from Jones "Systematic Software
Development Using VDM". The trick is to define what the data structure
does without constraining how it is done.

Function signatures:
init: -> Stack
push: N x Stack -> Stack
top: Stack -> (N U ERROR)
remove: Stack -> Stack
isempty: Stack -> B

(where N indicates a element (natural numbers in this sace), B
indicates a boolean and U indicates set union)

The semantics
top(init()) = ERROR
top(push(i,s)) = i
remove(init()) = init()
remove(push(i, s)) = s
isempty(init()) = true
isempty(push(i, s)) = false

for computer science definition, in how i think, you have to start
with a subset of ACN "A is a subset of N" doing one function
f:A->B 1-1
define  a,beB  a<=b  <=> f-1(a)<=f-1(b)
define  ++:B-{last}->B the function increment by one ++a=f-1(f-1(a)+1)
                                                     --a= ?
where f-1==inverse of f; start from ++ and -- for define push or pop
or something like that for define pointers to these elements
now i not have the time or the clear for write all down
all i know: it is possible

I'm not familiar with your notation. Does this definition of a stack
assume the elements are stored in contiguous memory? The use of < and +
+ makes me wonder.

so one "hardware stack" follow the definitions of stacks
one implementation of theory

yes. The typical hardware stack follows the semantics (definition) of
an abstract (computer science) stack

<snip>

 

[Wolfgang Draxinger]

I meant to add:

That said, some systems now have stacks that are execution protected
while the heaps are not. On those systems it might make sense to
prefer the stack. Once again, it is a choice based on knowing the
target system.

Execution prevention doesn't help against return based programming
(overwriting the return addresses on the stack to jump into and exploit
already present code to do what you want it to do). The glibc has been
proven to be turing complete with return based programming.


Wolfgang

 

[Tim Harig]

Execution prevention doesn't help against return based programming
(overwriting the return addresses on the stack to jump into and exploit
already present code to do what you want it to do). The glibc has been
proven to be turing complete with return based programming.

I had to look that up. Interesting stuff. Thanks for pointing my
attention to it.