Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > What is a stack?

Reply
Thread Tools

What is a stack?

 
 
Tim Harig
Guest
Posts: n/a
 
      06-02-2010
On 2010-06-01, Nick Keighley <(E-Mail Removed)> wrote:
> On 31 May, 08:23, Tim Harig <(E-Mail Removed)> wrote:
>> On 2010-05-31, Seebs <(E-Mail Removed)> wrote:
>> > On 2010-05-31, Tim Harig <(E-Mail Removed)> wrote:
>> >> While this is theoretically true, I think it is still useful for C
>> >> programmers to have some idea about how the stack is implemented on their
>> >> system/compiler; especially for stacks that are effectively continuous
>> >> arrays whether hardware implemented or not.

>>
>> > It can be. *However, it's important to get it right -- if you know how the
>> > stack was implemented on something else, it can be extremely bad, because
>> > it can lead to you *mistakenly* thinking it has provided any of these
>> > benefits... *And it's surprising just how often these things can change.
>> > There are cases where a compiler option can result in different behavior
>> > for the same compiler, same operating system, and same hardware...

>>
>> I thought that being correct went without saying. *Using mistaken
>> information always puts you at risk of doing the wrong thing. (I could make
>> a political statement here; but, I will refrain.)

>
> 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.
 
Reply With Quote
 
 
 
 
Nick Keighley
Guest
Posts: n/a
 
      06-02-2010
On 2 June, 11:54, Malcolm McLean <(E-Mail Removed)>
wrote:
> On Jun 2, 11:09*am, "io_x" <(E-Mail Removed)> wrote:> "spinoza1111" <(E-Mail Removed)> ha scritto nel messaggionews:(E-Mail Removed)...


> > in my naive think, stack should be one array.
> > Where are the reasons for use a linked list?


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.
 
Reply With Quote
 
 
 
 
Nick Keighley
Guest
Posts: n/a
 
      06-02-2010
On 2 June, 12:57, "io_x" <(E-Mail Removed)> wrote:
> "Malcolm McLean" <> ha scritto nel messaggionews:(E-Mail Removed)...
>
> >On Jun 2, 11:09 am, "io_x" <(E-Mail Removed)> wrote:
> >> "spinoza1111" <(E-Mail Removed)> ha scritto nel
> >> messaggionews:84e098eb-8f7e-402e-97af->c224d3d15__BEGIN_MASK_n#9g02mG7!__...__END_MASK_i ?a63jfAD$(E-Mail Removed)...

>
> >> in my naive think, stack should be one array.
> >> Where are the reasons for use a linked list?

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

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

 
Reply With Quote
 
Nick Keighley
Guest
Posts: n/a
 
      06-02-2010
On 1 June, 20:34, Keith Thompson <(E-Mail Removed)> wrote:
> Malcolm McLean <(E-Mail Removed)> writes:
> > On May 30, 10:05*pm, Keith Thompson <(E-Mail Removed)> wrote:
> >> Chad <(E-Mail Removed)> writes:


> >> Unless you're dealing with very
> >> low-level details, you don't need to know about how the hardware
> >> stack works to understand how a C program works.

>
> > Most people need a concrete picture in their mind to understand
> > something.


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.

> > Whilst theoretically using abstract definitions like
> > "automatic storage duration" gives someone the information required to
> > understand how a C program works, in fact it takes most people an
> > unacceptably long time to understand something described in those
> > terms. A description of a stack pushing variables on and popping them
> > off, however, will give most people a good enopugh mental picture.
> > Much later you can introduce the idea that some very small or very
> > high-level implemetations might not have harware stacks, but only
> > after they are already fluent C programmers.

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

 
Reply With Quote
 
Seebs
Guest
Posts: n/a
 
      06-02-2010
On 2010-06-02, Nick Keighley <(E-Mail Removed)> wrote:
> 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
--
Copyright 2010, all wrongs reversed. Peter Seebach / http://www.velocityreviews.com/forums/(E-Mail Removed)
http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
 
Reply With Quote
 
Nick Keighley
Guest
Posts: n/a
 
      06-04-2010
On 3 June, 18:56, "io_x" <(E-Mail Removed)> wrote:
> "Nick Keighley" <> ha scritto nel messaggionews:(E-Mail Removed)...
> > On 2 June, 12:57, "io_x" <(E-Mail Removed)> wrote:
> >> "Malcolm McLean" <> ha scritto nel
> >> messaggionews:(E-Mail Removed)...
> >> >On Jun 2, 11:09 am, "io_x" <(E-Mail Removed)> wrote:
> >> >> "spinoza1111" <(E-Mail Removed)> ha scritto nel
> >> >> messaggionews:84e098eb-8f7e-402e-97af->c224d3d15__BEGIN_MASK_n#9g02mG7!__...__END_MASK_i ?a63jfAD$__BEGIN_MASK_n#9g02mG7!__...__END_MASK_i? a63jfAD$(E-Mail Removed)...



> >> >> in my naive think, stack should be one array.
> >> >> Where are the reasons for use a linked list?

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

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

>
> > it's easy but realloc() (or whatever) can be expensive.

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

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

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


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

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


--
Never worry about theory as long as the machinery does what it's
supposed to do.
(Robert A Heinlein)

 
Reply With Quote
 
robertwessel2@yahoo.com
Guest
Posts: n/a
 
      06-04-2010
On Jun 4, 12:42*pm, "io_x" <(E-Mail Removed)> wrote:
> "Nick Keighley" <(E-Mail Removed)> ha scritto nel messaggionews:(E-Mail Removed)...
> > what's a "stack-queue"?

>
> 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.
 
Reply With Quote
 
Nick Keighley
Guest
Posts: n/a
 
      06-06-2010
On 4 June, 18:42, "io_x" <(E-Mail Removed)> wrote:
> "Nick Keighley" <(E-Mail Removed)> ha scritto nel messaggionews:(E-Mail Removed)...
> > On 3 June, 18:56, "io_x" <(E-Mail Removed)> wrote:


<snip>

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


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.

> > The hardware stack
> > on a typical processor is an implementation of a computer science
> > stack but there are other ways to do it.

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

 
Reply With Quote
 
Wolfgang Draxinger
Guest
Posts: n/a
 
      07-01-2010
On Mon, 31 May 2010 07:31:39 +0000 (UTC)
Tim Harig <(E-Mail Removed)> wrote:

> 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

 
Reply With Quote
 
Tim Harig
Guest
Posts: n/a
 
      07-01-2010
On 2010-07-01, Wolfgang Draxinger <(E-Mail Removed)> wrote:
> On Mon, 31 May 2010 07:31:39 +0000 (UTC)
> Tim Harig <(E-Mail Removed)> wrote:
>
>> 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.


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

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off




Advertisments